libstdc++-v3/testsuite/ext/pb_ds/example/assoc_container_traits.cc

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2016 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 3, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING3.  If not see
  18 // <http://www.gnu.org/licenses/>.
  19
  20
  21 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  22
  23 // Permission to use, copy, modify, sell, and distribute this software
  24 // is hereby granted without fee, provided that the above copyright
  25 // notice appears in all copies, and that both that copyright notice
  26 // and this permission notice appear in supporting documentation. None
  27 // of the above authors, nor IBM Haifa Research Laboratories, make any
  28 // representation about the suitability of this software for any
  29 // purpose. It is provided "as is" without express or implied
  30 // warranty.
  31
  32 /**
  33  * @file assoc_container_traits_example.cpp
  34  * A basic example showing how to use container_traits for querying container types
  35  *    for their behavior.
  36  */
  37
  38 /**
  39  * The following example shows how to use container_traits in order to print
  40  * out information on an associative container's behavior, e.g., its underlying
  41  * data structure, or whether its objects guarantee storing entries sorted
  42  * by key order.
  43  */
  44
  45 #include <iostream>
  46 #include <ext/pb_ds/assoc_container.hpp>
  47 #include <ext/pb_ds/tag_and_trait.hpp>
  48
  49 using namespace std;
  50 using namespace __gnu_pbds;
  51
  52 template<class DS_Category>
  53 void
  54 print_container_category(DS_Category);
  55
  56 template<>
  57 void
  58 print_container_category(cc_hash_tag)
  59 {
  60   cout << "Collision-chaining hash based associative-container:" << endl;
  61 }
  62
  63 template<>
  64 void
  65 print_container_category(gp_hash_tag)
  66 {
  67   cout << "Probing hash based associative-container:" << endl;
  68 }
  69
  70 template<>
  71 void
  72 print_container_category(rb_tree_tag)
  73 {
  74   cout << "Red-black tree associative-container:" << endl;
  75 }
  76
  77 template<>
  78 void
  79 print_container_category(splay_tree_tag)
  80 {
  81   cout << "Splay tree associative-container:" << endl;
  82 }
  83
  84 template<>
  85 void
  86 print_container_category(ov_tree_tag)
  87 {
  88   cout << "Ordered-vector tree associative-container:" << endl;
  89 }
  90
  91 template<>
  92 void
  93 print_container_category(list_update_tag)
  94 {
  95   cout << "List-based associative-container:" << endl;
  96 }
  97
  98 void
  99 print_erase_can_throw(bool can)
 100 {
 101   if (can)
 102     {
 103       cout << "Erase can throw" << endl;
 104       return;
 105     }
 106   cout << "Erase cannot throw" << endl;
 107 }
 108
 109 void
 110 print_order_preserving(bool does)
 111 {
 112   if (does)
 113     {
 114       cout << "Preserves order" << endl;
 115       return;
 116     }
 117   cout << "Does not preserve order" << endl;
 118 }
 119
 120 template<class Invalidation_Guarantee>
 121 void
 122 print_invalidation_guarantee(Invalidation_Guarantee);
 123
 124 template<>
 125 void
 126 print_invalidation_guarantee(basic_invalidation_guarantee)
 127 {
 128   cout << "Guarantees only that found references, pointers, and "
 129     "iterators are valid as long as the container object is not "
 130     "modified" << endl;
 131 }
 132
 133 template<>
 134 void
 135 print_invalidation_guarantee(point_invalidation_guarantee)
 136 {
 137   cout << "Guarantees that found references, pointers, and "
 138     "point_iterators are valid even if the container object "
 139     "is modified" << endl;
 140 }
 141
 142 template<>
 143 void
 144 print_invalidation_guarantee(range_invalidation_guarantee)
 145 {
 146   cout << "Guarantees that iterators remain valid even if the "
 147     "container object is modified" << endl;
 148 }
 149
 150 void
 151 print_reverse_iteration(bool does)
 152 {
 153   if (does)
 154     {
 155       cout << "Supports reverse iteration" << endl;
 156       return;
 157     }
 158   cout << "Does not support reverse iteration" << endl;
 159 }
 160
 161 template<class DS_Traits>
 162 void
 163 print_container_attributes()
 164 {
 165   // First print out the data structure category.
 166   print_container_category(typename DS_Traits::container_category());
 167
 168   // Now print the attributes of the container.
 169   print_erase_can_throw(DS_Traits::erase_can_throw);
 170   print_order_preserving(DS_Traits::order_preserving);
 171   print_invalidation_guarantee(typename DS_Traits::invalidation_guarantee());
 172   print_reverse_iteration(DS_Traits::reverse_iteration);
 173
 174   cout << endl << endl;
 175 }
 176
 177 int
 178 main()
 179 {
 180   {
 181     // Print the attributes of a collision-chaining hash table.
 182     typedef cc_hash_table< int, char> t;
 183     print_container_attributes<container_traits<t> >();
 184   }
 185
 186   {
 187     // Print the attributes of a (general) probing hash table.
 188     typedef gp_hash_table< int, char> t;
 189     print_container_attributes<container_traits<t> >();
 190   }
 191
 192   {
 193     // Print the attributes of a red-black tree.
 194     typedef tree< int, char> t;
 195     print_container_attributes<container_traits<t> >();
 196   }
 197
 198   {
 199     // Print the attributes of a splay tree.
 200     typedef
 201       tree<
 202       int,
 203       char,
 204       less<int>,
 205       splay_tree_tag>
 206       t;
 207
 208     print_container_attributes<container_traits<t> >();
 209   }
 210
 211   {
 212     // Print the attributes of an ordered-vector tree.
 213     typedef
 214       tree<
 215       int,
 216       char,
 217       less<int>,
 218       ov_tree_tag>
 219       t;
 220     print_container_attributes<container_traits<t> >();
 221   }
 222
 223   {
 224     // Print the attributes of an list-based container.
 225     typedef list_update< int, char> t;
 226     print_container_attributes<container_traits<t> >();
 227   }
 228
 229   return 0;
 230 }