1// -*- C++ -*- 2 3// Copyright (C) 2005-2015 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 49using namespace std; 50using namespace __gnu_pbds; 51 52template<class DS_Category> 53void 54print_container_category(DS_Category); 55 56template<> 57void 58print_container_category(cc_hash_tag) 59{ 60 cout << "Collision-chaining hash based associative-container:" << endl; 61} 62 63template<> 64void 65print_container_category(gp_hash_tag) 66{ 67 cout << "Probing hash based associative-container:" << endl; 68} 69 70template<> 71void 72print_container_category(rb_tree_tag) 73{ 74 cout << "Red-black tree associative-container:" << endl; 75} 76 77template<> 78void 79print_container_category(splay_tree_tag) 80{ 81 cout << "Splay tree associative-container:" << endl; 82} 83 84template<> 85void 86print_container_category(ov_tree_tag) 87{ 88 cout << "Ordered-vector tree associative-container:" << endl; 89} 90 91template<> 92void 93print_container_category(list_update_tag) 94{ 95 cout << "List-based associative-container:" << endl; 96} 97 98void 99print_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 109void 110print_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 120template<class Invalidation_Guarantee> 121void 122print_invalidation_guarantee(Invalidation_Guarantee); 123 124template<> 125void 126print_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 133template<> 134void 135print_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 142template<> 143void 144print_invalidation_guarantee(range_invalidation_guarantee) 145{ 146 cout << "Guarantees that iterators remain valid even if the " 147 "container object is modified" << endl; 148} 149 150void 151print_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 161template<class DS_Traits> 162void 163print_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 177int 178main() 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} 231