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