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
00043
00044
00045
00046
00047
00048 #ifndef PB_DS_TAG_AND_TRAIT_HPP
00049 #define PB_DS_TAG_AND_TRAIT_HPP
00050
00051 #include <ext/pb_ds/detail/type_utils.hpp>
00052
00053
00054
00055
00056
00057 namespace __gnu_pbds
00058 {
00059
00060
00061 struct trivial_iterator_tag
00062 { };
00063
00064
00065 typedef void trivial_iterator_difference_type;
00066
00067
00068
00069
00070
00071 struct basic_invalidation_guarantee
00072 { };
00073
00074
00075
00076
00077
00078
00079 struct point_invalidation_guarantee : public basic_invalidation_guarantee
00080 { };
00081
00082
00083
00084
00085
00086
00087
00088 struct range_invalidation_guarantee : public point_invalidation_guarantee
00089 { };
00090
00091
00092
00093
00094 struct null_mapped_type { };
00095
00096
00097
00098 struct container_tag
00099 { };
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 template<typename Tag>
00157 struct container_traits_base;
00158
00159 template<>
00160 struct container_traits_base<cc_hash_tag>
00161 {
00162 typedef cc_hash_tag container_category;
00163 typedef point_invalidation_guarantee invalidation_guarantee;
00164
00165 enum
00166 {
00167 order_preserving = false,
00168 erase_can_throw = false,
00169 split_join_can_throw = false,
00170 reverse_iteration = false
00171 };
00172 };
00173
00174 template<>
00175 struct container_traits_base<gp_hash_tag>
00176 {
00177 typedef gp_hash_tag container_category;
00178 typedef basic_invalidation_guarantee invalidation_guarantee;
00179
00180 enum
00181 {
00182 order_preserving = false,
00183 erase_can_throw = false,
00184 split_join_can_throw = false,
00185 reverse_iteration = false
00186 };
00187 };
00188
00189 template<>
00190 struct container_traits_base<rb_tree_tag>
00191 {
00192 typedef rb_tree_tag container_category;
00193 typedef range_invalidation_guarantee invalidation_guarantee;
00194
00195 enum
00196 {
00197 order_preserving = true,
00198 erase_can_throw = false,
00199 split_join_can_throw = false,
00200 reverse_iteration = true
00201 };
00202 };
00203
00204 template<>
00205 struct container_traits_base<splay_tree_tag>
00206 {
00207 typedef splay_tree_tag container_category;
00208 typedef range_invalidation_guarantee invalidation_guarantee;
00209
00210 enum
00211 {
00212 order_preserving = true,
00213 erase_can_throw = false,
00214 split_join_can_throw = false,
00215 reverse_iteration = true
00216 };
00217 };
00218
00219 template<>
00220 struct container_traits_base<ov_tree_tag>
00221 {
00222 typedef ov_tree_tag container_category;
00223 typedef basic_invalidation_guarantee invalidation_guarantee;
00224
00225 enum
00226 {
00227 order_preserving = true,
00228 erase_can_throw = true,
00229 split_join_can_throw = true,
00230 reverse_iteration = false
00231 };
00232 };
00233
00234 template<>
00235 struct container_traits_base<pat_trie_tag>
00236 {
00237 typedef pat_trie_tag container_category;
00238 typedef range_invalidation_guarantee invalidation_guarantee;
00239
00240 enum
00241 {
00242 order_preserving = true,
00243 erase_can_throw = false,
00244 split_join_can_throw = true,
00245 reverse_iteration = true
00246 };
00247 };
00248
00249 template<>
00250 struct container_traits_base<list_update_tag>
00251 {
00252 typedef list_update_tag container_category;
00253 typedef point_invalidation_guarantee invalidation_guarantee;
00254
00255 enum
00256 {
00257 order_preserving = false,
00258 erase_can_throw = false,
00259 split_join_can_throw = false,
00260 reverse_iteration = false
00261 };
00262 };
00263
00264
00265 template<>
00266 struct container_traits_base<pairing_heap_tag>
00267 {
00268 typedef pairing_heap_tag container_category;
00269 typedef point_invalidation_guarantee invalidation_guarantee;
00270
00271 enum
00272 {
00273 order_preserving = false,
00274 erase_can_throw = false,
00275 split_join_can_throw = false,
00276 reverse_iteration = false
00277 };
00278 };
00279
00280 template<>
00281 struct container_traits_base<thin_heap_tag>
00282 {
00283 typedef thin_heap_tag container_category;
00284 typedef point_invalidation_guarantee invalidation_guarantee;
00285
00286 enum
00287 {
00288 order_preserving = false,
00289 erase_can_throw = false,
00290 split_join_can_throw = false,
00291 reverse_iteration = false
00292 };
00293 };
00294
00295 template<>
00296 struct container_traits_base<binomial_heap_tag>
00297 {
00298 typedef binomial_heap_tag container_category;
00299 typedef point_invalidation_guarantee invalidation_guarantee;
00300
00301 enum
00302 {
00303 order_preserving = false,
00304 erase_can_throw = false,
00305 split_join_can_throw = false,
00306 reverse_iteration = false
00307 };
00308 };
00309
00310 template<>
00311 struct container_traits_base<rc_binomial_heap_tag>
00312 {
00313 typedef rc_binomial_heap_tag container_category;
00314 typedef point_invalidation_guarantee invalidation_guarantee;
00315
00316 enum
00317 {
00318 order_preserving = false,
00319 erase_can_throw = false,
00320 split_join_can_throw = false,
00321 reverse_iteration = false
00322 };
00323 };
00324
00325 template<>
00326 struct container_traits_base<binary_heap_tag>
00327 {
00328 typedef binary_heap_tag container_category;
00329 typedef basic_invalidation_guarantee invalidation_guarantee;
00330
00331 enum
00332 {
00333 order_preserving = false,
00334 erase_can_throw = false,
00335 split_join_can_throw = true,
00336 reverse_iteration = false
00337 };
00338 };
00339
00340
00341
00342 template<typename Cntnr>
00343 struct container_traits
00344 : public container_traits_base<typename Cntnr::container_category>
00345 {
00346 typedef Cntnr container_type;
00347 typedef typename Cntnr::container_category container_category;
00348 typedef container_traits_base<container_category> base_type;
00349 typedef typename base_type::invalidation_guarantee invalidation_guarantee;
00350
00351 enum
00352 {
00353 order_preserving = base_type::order_preserving,
00354 erase_can_throw = base_type::erase_can_throw,
00355 split_join_can_throw = base_type::split_join_can_throw,
00356 reverse_iteration = base_type::reverse_iteration
00357 };
00358 };
00359 }
00360
00361 #endif