3 // Copyright (C) 2005-2019 Free Software Foundation, Inc.
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
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.
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/>.
21 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
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
33 * @file assoc_container_traits_example.cpp
34 * A basic example showing how to use container_traits for querying container types
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
46 #include <ext/pb_ds/assoc_container.hpp>
47 #include <ext/pb_ds/tag_and_trait.hpp>
50 using namespace __gnu_pbds
;
52 template<class DS_Category
>
54 print_container_category(DS_Category
);
58 print_container_category(cc_hash_tag
)
60 cout
<< "Collision-chaining hash based associative-container:" << endl
;
65 print_container_category(gp_hash_tag
)
67 cout
<< "Probing hash based associative-container:" << endl
;
72 print_container_category(rb_tree_tag
)
74 cout
<< "Red-black tree associative-container:" << endl
;
79 print_container_category(splay_tree_tag
)
81 cout
<< "Splay tree associative-container:" << endl
;
86 print_container_category(ov_tree_tag
)
88 cout
<< "Ordered-vector tree associative-container:" << endl
;
93 print_container_category(list_update_tag
)
95 cout
<< "List-based associative-container:" << endl
;
99 print_erase_can_throw(bool can
)
103 cout
<< "Erase can throw" << endl
;
106 cout
<< "Erase cannot throw" << endl
;
110 print_order_preserving(bool does
)
114 cout
<< "Preserves order" << endl
;
117 cout
<< "Does not preserve order" << endl
;
120 template<class Invalidation_Guarantee
>
122 print_invalidation_guarantee(Invalidation_Guarantee
);
126 print_invalidation_guarantee(basic_invalidation_guarantee
)
128 cout
<< "Guarantees only that found references, pointers, and "
129 "iterators are valid as long as the container object is not "
135 print_invalidation_guarantee(point_invalidation_guarantee
)
137 cout
<< "Guarantees that found references, pointers, and "
138 "point_iterators are valid even if the container object "
139 "is modified" << endl
;
144 print_invalidation_guarantee(range_invalidation_guarantee
)
146 cout
<< "Guarantees that iterators remain valid even if the "
147 "container object is modified" << endl
;
151 print_reverse_iteration(bool does
)
155 cout
<< "Supports reverse iteration" << endl
;
158 cout
<< "Does not support reverse iteration" << endl
;
161 template<class DS_Traits
>
163 print_container_attributes()
165 // First print out the data structure category.
166 print_container_category(typename
DS_Traits::container_category());
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
);
174 cout
<< endl
<< endl
;
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
> >();
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
> >();
193 // Print the attributes of a red-black tree.
194 typedef tree
< int, char> t
;
195 print_container_attributes
<container_traits
<t
> >();
199 // Print the attributes of a splay tree.
208 print_container_attributes
<container_traits
<t
> >();
212 // Print the attributes of an ordered-vector tree.
220 print_container_attributes
<container_traits
<t
> >();
224 // Print the attributes of an list-based container.
225 typedef list_update
< int, char> t
;
226 print_container_attributes
<container_traits
<t
> >();