libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005-2015 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00026 00027 // Permission to use, copy, modify, sell, and distribute this software 00028 // is hereby granted without fee, provided that the above copyright 00029 // notice appears in all copies, and that both that copyright notice 00030 // and this permission notice appear in supporting documentation. None 00031 // of the above authors, nor IBM Haifa Research Laboratories, make any 00032 // representation about the suitability of this software for any 00033 // purpose. It is provided "as is" without express or implied 00034 // warranty. 00035 00036 /** 00037 * @file tag_and_trait.hpp 00038 * Contains tags and traits, e.g., ones describing underlying 00039 * data structures. 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 * @namespace __gnu_pbds 00050 * @brief GNU extensions for policy-based data structures for public use. 00051 */ 00052 namespace __gnu_pbds 00053 { 00054 /** @defgroup pbds Policy-Based Data Structures 00055 * @ingroup extensions 00056 * 00057 * This is a library of policy-based elementary data structures: 00058 * associative containers and priority queues. It is designed for 00059 * high-performance, flexibility, semantic safety, and conformance 00060 * to the corresponding containers in std (except for some points 00061 * where it differs by design). 00062 * 00063 * For details, see: 00064 * http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/index.html 00065 * 00066 * @{ 00067 */ 00068 00069 /** 00070 * @defgroup tags Tags 00071 * @{ 00072 */ 00073 /// A trivial iterator tag. Signifies that the iterators has none of 00074 /// std::iterators's movement abilities. 00075 struct trivial_iterator_tag 00076 { }; 00077 00078 /// Prohibit moving trivial iterators. 00079 typedef void trivial_iterator_difference_type; 00080 00081 00082 /** 00083 * @defgroup invalidation_tags Invalidation Guarantees 00084 * @ingroup tags 00085 * @{ 00086 */ 00087 00088 /** 00089 * Signifies a basic invalidation guarantee that any iterator, 00090 * pointer, or reference to a container object's mapped value type 00091 * is valid as long as the container is not modified. 00092 */ 00093 struct basic_invalidation_guarantee 00094 { }; 00095 00096 /** 00097 * Signifies an invalidation guarantee that includes all those of 00098 * its base, and additionally, that any point-type iterator, 00099 * pointer, or reference to a container object's mapped value type 00100 * is valid as long as its corresponding entry has not be erased, 00101 * regardless of modifications to the container object. 00102 */ 00103 struct point_invalidation_guarantee : public basic_invalidation_guarantee 00104 { }; 00105 00106 /** 00107 * Signifies an invalidation guarantee that includes all those of 00108 * its base, and additionally, that any range-type iterator 00109 * (including the returns of begin() and end()) is in the correct 00110 * relative positions to other range-type iterators as long as its 00111 * corresponding entry has not be erased, regardless of 00112 * modifications to the container object. 00113 */ 00114 struct range_invalidation_guarantee : public point_invalidation_guarantee 00115 { }; 00116 //@} 00117 00118 00119 /** 00120 * @defgroup ds_tags Data Structure Type 00121 * @ingroup tags 00122 * @{ 00123 */ 00124 /// Base data structure tag. 00125 struct container_tag 00126 { }; 00127 00128 /// Basic sequence. 00129 struct sequence_tag : public container_tag { }; 00130 00131 /// Basic string container, inclusive of strings, ropes, etc. 00132 struct string_tag : public sequence_tag { }; 00133 00134 /// Basic associative-container. 00135 struct associative_tag : public container_tag { }; 00136 00137 /// Basic hash structure. 00138 struct basic_hash_tag : public associative_tag { }; 00139 00140 /// Collision-chaining hash. 00141 struct cc_hash_tag : public basic_hash_tag { }; 00142 00143 /// General-probing hash. 00144 struct gp_hash_tag : public basic_hash_tag { }; 00145 00146 /// Basic branch structure. 00147 struct basic_branch_tag : public associative_tag { }; 00148 00149 /// Basic tree structure. 00150 struct tree_tag : public basic_branch_tag { }; 00151 00152 /// Red-black tree. 00153 struct rb_tree_tag : public tree_tag { }; 00154 00155 /// Splay tree. 00156 struct splay_tree_tag : public tree_tag { }; 00157 00158 /// Ordered-vector tree. 00159 struct ov_tree_tag : public tree_tag { }; 00160 00161 /// Basic trie structure. 00162 struct trie_tag : public basic_branch_tag { }; 00163 00164 /// PATRICIA trie. 00165 struct pat_trie_tag : public trie_tag { }; 00166 00167 /// List-update. 00168 struct list_update_tag : public associative_tag { }; 00169 00170 /// Basic priority-queue. 00171 struct priority_queue_tag : public container_tag { }; 00172 00173 /// Pairing-heap. 00174 struct pairing_heap_tag : public priority_queue_tag { }; 00175 00176 /// Binomial-heap. 00177 struct binomial_heap_tag : public priority_queue_tag { }; 00178 00179 /// Redundant-counter binomial-heap. 00180 struct rc_binomial_heap_tag : public priority_queue_tag { }; 00181 00182 /// Binary-heap (array-based). 00183 struct binary_heap_tag : public priority_queue_tag { }; 00184 00185 /// Thin heap. 00186 struct thin_heap_tag : public priority_queue_tag { }; 00187 //@} 00188 //@} 00189 00190 00191 /** 00192 * @defgroup traits Traits 00193 * @{ 00194 */ 00195 00196 /** 00197 * @brief Represents no type, or absence of type, for template tricks. 00198 * 00199 * In a mapped-policy, indicates that an associative container is a set. 00200 * 00201 * In a list-update policy, indicates that each link does not need 00202 * metadata. 00203 * 00204 * In a hash policy, indicates that the combining hash function 00205 * is actually a ranged hash function. 00206 * 00207 * In a probe policy, indicates that the combining probe function 00208 * is actually a ranged probe function. 00209 */ 00210 struct null_type { }; 00211 00212 /// A null node updator, indicating that no node updates are required. 00213 template<typename _Tp1, typename _Tp2, typename _Tp3, typename _Tp4> 00214 struct null_node_update : public null_type 00215 { }; 00216 00217 00218 /// Primary template, container traits base. 00219 template<typename _Tag> 00220 struct container_traits_base; 00221 00222 /// Specialization, cc hash. 00223 template<> 00224 struct container_traits_base<cc_hash_tag> 00225 { 00226 typedef cc_hash_tag container_category; 00227 typedef point_invalidation_guarantee invalidation_guarantee; 00228 00229 enum 00230 { 00231 order_preserving = false, 00232 erase_can_throw = false, 00233 split_join_can_throw = false, 00234 reverse_iteration = false 00235 }; 00236 }; 00237 00238 /// Specialization, gp hash. 00239 template<> 00240 struct container_traits_base<gp_hash_tag> 00241 { 00242 typedef gp_hash_tag container_category; 00243 typedef basic_invalidation_guarantee invalidation_guarantee; 00244 00245 enum 00246 { 00247 order_preserving = false, 00248 erase_can_throw = false, 00249 split_join_can_throw = false, 00250 reverse_iteration = false 00251 }; 00252 }; 00253 00254 /// Specialization, rb tree. 00255 template<> 00256 struct container_traits_base<rb_tree_tag> 00257 { 00258 typedef rb_tree_tag container_category; 00259 typedef range_invalidation_guarantee invalidation_guarantee; 00260 00261 enum 00262 { 00263 order_preserving = true, 00264 erase_can_throw = false, 00265 split_join_can_throw = false, 00266 reverse_iteration = true 00267 }; 00268 }; 00269 00270 /// Specialization, splay tree. 00271 template<> 00272 struct container_traits_base<splay_tree_tag> 00273 { 00274 typedef splay_tree_tag container_category; 00275 typedef range_invalidation_guarantee invalidation_guarantee; 00276 00277 enum 00278 { 00279 order_preserving = true, 00280 erase_can_throw = false, 00281 split_join_can_throw = false, 00282 reverse_iteration = true 00283 }; 00284 }; 00285 00286 /// Specialization, ov tree. 00287 template<> 00288 struct container_traits_base<ov_tree_tag> 00289 { 00290 typedef ov_tree_tag container_category; 00291 typedef basic_invalidation_guarantee invalidation_guarantee; 00292 00293 enum 00294 { 00295 order_preserving = true, 00296 erase_can_throw = true, 00297 split_join_can_throw = true, 00298 reverse_iteration = false 00299 }; 00300 }; 00301 00302 /// Specialization, pat trie. 00303 template<> 00304 struct container_traits_base<pat_trie_tag> 00305 { 00306 typedef pat_trie_tag container_category; 00307 typedef range_invalidation_guarantee invalidation_guarantee; 00308 00309 enum 00310 { 00311 order_preserving = true, 00312 erase_can_throw = false, 00313 split_join_can_throw = true, 00314 reverse_iteration = true 00315 }; 00316 }; 00317 00318 /// Specialization, list update. 00319 template<> 00320 struct container_traits_base<list_update_tag> 00321 { 00322 typedef list_update_tag container_category; 00323 typedef point_invalidation_guarantee invalidation_guarantee; 00324 00325 enum 00326 { 00327 order_preserving = false, 00328 erase_can_throw = false, 00329 split_join_can_throw = false, 00330 reverse_iteration = false 00331 }; 00332 }; 00333 00334 /// Specialization, pairing heap. 00335 template<> 00336 struct container_traits_base<pairing_heap_tag> 00337 { 00338 typedef pairing_heap_tag container_category; 00339 typedef point_invalidation_guarantee invalidation_guarantee; 00340 00341 enum 00342 { 00343 order_preserving = false, 00344 erase_can_throw = false, 00345 split_join_can_throw = false, 00346 reverse_iteration = false 00347 }; 00348 }; 00349 00350 /// Specialization, thin heap. 00351 template<> 00352 struct container_traits_base<thin_heap_tag> 00353 { 00354 typedef thin_heap_tag container_category; 00355 typedef point_invalidation_guarantee invalidation_guarantee; 00356 00357 enum 00358 { 00359 order_preserving = false, 00360 erase_can_throw = false, 00361 split_join_can_throw = false, 00362 reverse_iteration = false 00363 }; 00364 }; 00365 00366 /// Specialization, binomial heap. 00367 template<> 00368 struct container_traits_base<binomial_heap_tag> 00369 { 00370 typedef binomial_heap_tag container_category; 00371 typedef point_invalidation_guarantee invalidation_guarantee; 00372 00373 enum 00374 { 00375 order_preserving = false, 00376 erase_can_throw = false, 00377 split_join_can_throw = false, 00378 reverse_iteration = false 00379 }; 00380 }; 00381 00382 /// Specialization, rc binomial heap. 00383 template<> 00384 struct container_traits_base<rc_binomial_heap_tag> 00385 { 00386 typedef rc_binomial_heap_tag container_category; 00387 typedef point_invalidation_guarantee invalidation_guarantee; 00388 00389 enum 00390 { 00391 order_preserving = false, 00392 erase_can_throw = false, 00393 split_join_can_throw = false, 00394 reverse_iteration = false 00395 }; 00396 }; 00397 00398 /// Specialization, binary heap. 00399 template<> 00400 struct container_traits_base<binary_heap_tag> 00401 { 00402 typedef binary_heap_tag container_category; 00403 typedef basic_invalidation_guarantee invalidation_guarantee; 00404 00405 enum 00406 { 00407 order_preserving = false, 00408 erase_can_throw = false, 00409 split_join_can_throw = true, 00410 reverse_iteration = false 00411 }; 00412 }; 00413 00414 00415 /// Container traits. 00416 // See Matt Austern for the name, S. Meyers MEFC++ #2, others. 00417 template<typename Cntnr> 00418 struct container_traits 00419 : public container_traits_base<typename Cntnr::container_category> 00420 { 00421 typedef Cntnr container_type; 00422 typedef typename Cntnr::container_category container_category; 00423 typedef container_traits_base<container_category> base_type; 00424 typedef typename base_type::invalidation_guarantee invalidation_guarantee; 00425 00426 enum 00427 { 00428 /// True only if Cntnr objects guarantee storing keys by order. 00429 order_preserving = base_type::order_preserving, 00430 00431 /// True only if erasing a key can throw. 00432 erase_can_throw = base_type::erase_can_throw, 00433 00434 /// True only if split or join operations can throw. 00435 split_join_can_throw = base_type::split_join_can_throw, 00436 00437 /// True only reverse iterators are supported. 00438 reverse_iteration = base_type::reverse_iteration 00439 }; 00440 }; 00441 //@} 00442 00443 00444 namespace detail 00445 { 00446 /// Dispatch mechanism, primary template for associative types. 00447 template<typename Key, typename Mapped, typename _Alloc, typename Tag, 00448 typename Policy_Tl = null_type> 00449 struct container_base_dispatch; 00450 } // namespace detail 00451 //@} 00452 } // namespace __gnu_pbds 00453 00454 #endif