tag_and_trait.hpp
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042 #ifndef PB_DS_TAG_AND_TRAIT_HPP
00043 #define PB_DS_TAG_AND_TRAIT_HPP
00044
00045 #include <ext/pb_ds/detail/type_utils.hpp>
00046
00047
00048
00049
00050
00051 namespace __gnu_pbds
00052 {
00053
00054
00055 struct trivial_iterator_tag
00056 { };
00057
00058
00059 typedef void trivial_iterator_difference_type;
00060
00061
00062
00063
00064
00065 struct basic_invalidation_guarantee
00066 { };
00067
00068
00069
00070
00071
00072
00073 struct point_invalidation_guarantee : public basic_invalidation_guarantee
00074 { };
00075
00076
00077
00078
00079
00080
00081
00082 struct range_invalidation_guarantee : public point_invalidation_guarantee
00083 { };
00084
00085
00086
00087
00088 struct null_mapped_type { };
00089
00090
00091
00092 struct container_tag
00093 { };
00094
00095
00096 struct string_tag : public container_tag { };
00097
00098
00099 struct sequence_tag : public container_tag { };
00100
00101
00102 struct associative_container_tag : public container_tag { };
00103
00104
00105 struct basic_hash_tag : public associative_container_tag { };
00106
00107
00108 struct cc_hash_tag : public basic_hash_tag { };
00109
00110
00111 struct gp_hash_tag : public basic_hash_tag { };
00112
00113
00114 struct basic_tree_tag : public associative_container_tag { };
00115
00116
00117 struct tree_tag : public basic_tree_tag { };
00118
00119
00120 struct rb_tree_tag : public tree_tag { };
00121
00122
00123 struct splay_tree_tag : public tree_tag { };
00124
00125
00126 struct ov_tree_tag : public tree_tag { };
00127
00128
00129 struct trie_tag : public basic_tree_tag { };
00130
00131
00132 struct pat_trie_tag : public trie_tag { };
00133
00134
00135 struct list_update_tag : public associative_container_tag { };
00136
00137
00138 struct priority_queue_tag : public container_tag { };
00139
00140
00141 struct pairing_heap_tag : public priority_queue_tag { };
00142
00143
00144 struct binomial_heap_tag : public priority_queue_tag { };
00145
00146
00147 struct rc_binomial_heap_tag : public priority_queue_tag { };
00148
00149
00150 struct binary_heap_tag : public priority_queue_tag { };
00151
00152
00153 struct thin_heap_tag : public priority_queue_tag { };
00154
00155
00156
00157 template<typename Tag>
00158 struct container_traits_base;
00159
00160 template<>
00161 struct container_traits_base<cc_hash_tag>
00162 {
00163 typedef cc_hash_tag container_category;
00164 typedef point_invalidation_guarantee invalidation_guarantee;
00165
00166 enum
00167 {
00168 order_preserving = false,
00169 erase_can_throw = false,
00170 split_join_can_throw = false,
00171 reverse_iteration = false
00172 };
00173 };
00174
00175 template<>
00176 struct container_traits_base<gp_hash_tag>
00177 {
00178 typedef gp_hash_tag container_category;
00179 typedef basic_invalidation_guarantee invalidation_guarantee;
00180
00181 enum
00182 {
00183 order_preserving = false,
00184 erase_can_throw = false,
00185 split_join_can_throw = false,
00186 reverse_iteration = false
00187 };
00188 };
00189
00190 template<>
00191 struct container_traits_base<rb_tree_tag>
00192 {
00193 typedef rb_tree_tag container_category;
00194 typedef range_invalidation_guarantee invalidation_guarantee;
00195
00196 enum
00197 {
00198 order_preserving = true,
00199 erase_can_throw = false,
00200 split_join_can_throw = false,
00201 reverse_iteration = true
00202 };
00203 };
00204
00205 template<>
00206 struct container_traits_base<splay_tree_tag>
00207 {
00208 typedef splay_tree_tag container_category;
00209 typedef range_invalidation_guarantee invalidation_guarantee;
00210
00211 enum
00212 {
00213 order_preserving = true,
00214 erase_can_throw = false,
00215 split_join_can_throw = false,
00216 reverse_iteration = true
00217 };
00218 };
00219
00220 template<>
00221 struct container_traits_base<ov_tree_tag>
00222 {
00223 typedef ov_tree_tag container_category;
00224 typedef basic_invalidation_guarantee invalidation_guarantee;
00225
00226 enum
00227 {
00228 order_preserving = true,
00229 erase_can_throw = true,
00230 split_join_can_throw = true,
00231 reverse_iteration = false
00232 };
00233 };
00234
00235 template<>
00236 struct container_traits_base<pat_trie_tag>
00237 {
00238 typedef pat_trie_tag container_category;
00239 typedef range_invalidation_guarantee invalidation_guarantee;
00240
00241 enum
00242 {
00243 order_preserving = true,
00244 erase_can_throw = false,
00245 split_join_can_throw = true,
00246 reverse_iteration = true
00247 };
00248 };
00249
00250 template<>
00251 struct container_traits_base<list_update_tag>
00252 {
00253 typedef list_update_tag container_category;
00254 typedef point_invalidation_guarantee invalidation_guarantee;
00255
00256 enum
00257 {
00258 order_preserving = false,
00259 erase_can_throw = false,
00260 split_join_can_throw = false,
00261 reverse_iteration = false
00262 };
00263 };
00264
00265
00266 template<>
00267 struct container_traits_base<pairing_heap_tag>
00268 {
00269 typedef pairing_heap_tag container_category;
00270 typedef point_invalidation_guarantee invalidation_guarantee;
00271
00272 enum
00273 {
00274 order_preserving = false,
00275 erase_can_throw = false,
00276 split_join_can_throw = false,
00277 reverse_iteration = false
00278 };
00279 };
00280
00281 template<>
00282 struct container_traits_base<thin_heap_tag>
00283 {
00284 typedef thin_heap_tag container_category;
00285 typedef point_invalidation_guarantee invalidation_guarantee;
00286
00287 enum
00288 {
00289 order_preserving = false,
00290 erase_can_throw = false,
00291 split_join_can_throw = false,
00292 reverse_iteration = false
00293 };
00294 };
00295
00296 template<>
00297 struct container_traits_base<binomial_heap_tag>
00298 {
00299 typedef binomial_heap_tag container_category;
00300 typedef point_invalidation_guarantee invalidation_guarantee;
00301
00302 enum
00303 {
00304 order_preserving = false,
00305 erase_can_throw = false,
00306 split_join_can_throw = false,
00307 reverse_iteration = false
00308 };
00309 };
00310
00311 template<>
00312 struct container_traits_base<rc_binomial_heap_tag>
00313 {
00314 typedef rc_binomial_heap_tag container_category;
00315 typedef point_invalidation_guarantee invalidation_guarantee;
00316
00317 enum
00318 {
00319 order_preserving = false,
00320 erase_can_throw = false,
00321 split_join_can_throw = false,
00322 reverse_iteration = false
00323 };
00324 };
00325
00326 template<>
00327 struct container_traits_base<binary_heap_tag>
00328 {
00329 typedef binary_heap_tag container_category;
00330 typedef basic_invalidation_guarantee invalidation_guarantee;
00331
00332 enum
00333 {
00334 order_preserving = false,
00335 erase_can_throw = false,
00336 split_join_can_throw = true,
00337 reverse_iteration = false
00338 };
00339 };
00340
00341
00342
00343
00344 template<typename Cntnr>
00345 struct container_traits
00346 : public container_traits_base<typename Cntnr::container_category>
00347 {
00348 typedef Cntnr container_type;
00349 typedef typename Cntnr::container_category container_category;
00350 typedef container_traits_base<container_category> base_type;
00351 typedef typename base_type::invalidation_guarantee invalidation_guarantee;
00352
00353 enum
00354 {
00355 order_preserving = base_type::order_preserving,
00356 erase_can_throw = base_type::erase_can_throw,
00357 split_join_can_throw = base_type::split_join_can_throw,
00358 reverse_iteration = base_type::reverse_iteration
00359 };
00360 };
00361 }
00362
00363 #endif