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