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 priority_queue_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 priority queue's behavior, e.g., its underlying
45 #include <ext/pb_ds/priority_queue.hpp>
46 #include <ext/pb_ds/tag_and_trait.hpp>
49 using namespace __gnu_pbds
;
51 template<class DS_Category
>
53 print_container_category(DS_Category
);
57 print_container_category(binary_heap_tag
)
58 { cout
<< "Binary heap:" << endl
; }
62 print_container_category(binomial_heap_tag
)
63 { cout
<< "Binomial heap:" << endl
; }
67 print_container_category(rc_binomial_heap_tag
)
68 { cout
<< "Redundant-counter binomial heap:" << endl
; }
72 print_container_category(pairing_heap_tag
)
73 { cout
<< "Pairing heap:" << endl
; }
77 print_container_category(thin_heap_tag
)
78 { cout
<< "Thin heap:" << endl
; }
80 template<class Invalidation_Guarantee
>
82 print_invalidation_guarantee(Invalidation_Guarantee
);
86 print_invalidation_guarantee(basic_invalidation_guarantee
)
88 cout
<< "Guarantees only that found references, pointers, and "
89 "iterators are valid as long as the container object is not "
95 print_invalidation_guarantee(point_invalidation_guarantee
)
97 cout
<< "Guarantees that found references, pointers, and "
98 "point_iterators are valid even if the container object "
99 "is modified" << endl
;
104 print_invalidation_guarantee(range_invalidation_guarantee
)
106 cout
<< "Guarantees that iterators remain valid even if the "
107 "container object is modified" << endl
;
111 print_split_join_can_throw(bool can
)
115 cout
<< "Can throw exceptions if split or joined" << endl
;
118 cout
<< "Cannot throw exceptions if split or joined" << endl
;
121 template<class DS_Traits
>
123 print_container_attributes()
125 // First print out the data structure category.
126 print_container_category(typename
DS_Traits::container_category());
128 // Now print the attributes of the container.
129 print_invalidation_guarantee(typename
DS_Traits::invalidation_guarantee());
130 print_split_join_can_throw(DS_Traits::split_join_can_throw
);
131 cout
<< endl
<< endl
;
137 // Print the attributes of a binary heap.
139 __gnu_pbds::priority_queue
<
145 print_container_attributes
<container_traits
<t
> >();
149 // Print the attributes of a binomial heap.
151 __gnu_pbds::priority_queue
<
157 print_container_attributes
<container_traits
<t
> >();
161 // Print the attributes of a redundant-counter binomial heap.
163 __gnu_pbds::priority_queue
<
166 rc_binomial_heap_tag
>
169 print_container_attributes
<container_traits
<t
> >();
173 // Print the attributes of a pairing heap.
175 __gnu_pbds::priority_queue
<
181 print_container_attributes
<container_traits
<t
> >();
186 * Print the attributes of a thin heap.
190 __gnu_pbds::priority_queue
<
196 print_container_attributes
<container_traits
<t
> >();