1 // -*- C++ -*- 2 3 // Copyright (C) 2005, 2006, 2008, 2009, 2010, 2011 4 // Free Software Foundation, Inc. 5 // 6 // This file is part of the GNU ISO C++ Library. This library is free 7 // software; you can redistribute it and/or modify it under the terms 8 // of the GNU General Public License as published by the Free Software 9 // Foundation; either version 3, or (at your option) any later 10 // version. 11 12 // This library is distributed in the hope that it will be useful, but 13 // WITHOUT ANY WARRANTY; without even the implied warranty of 14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15 // General Public License for more details. 16 17 // Under Section 7 of GPL version 3, you are granted additional 18 // permissions described in the GCC Runtime Library Exception, version 19 // 3.1, as published by the Free Software Foundation. 20 21 // You should have received a copy of the GNU General Public License and 22 // a copy of the GCC Runtime Library Exception along with this program; 23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24 // <http://www.gnu.org/licenses/>. 25 26 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 27 28 // Permission to use, copy, modify, sell, and distribute this software 29 // is hereby granted without fee, provided that the above copyright 30 // notice appears in all copies, and that both that copyright notice 31 // and this permission notice appear in supporting documentation. None 32 // of the above authors, nor IBM Haifa Research Laboratories, make any 33 // representation about the suitability of this software for any 34 // purpose. It is provided "as is" without express or implied 35 // warranty. 36 37 /** 38 * @file tag_and_trait.hpp 39 * Contains tags and traits, e.g., ones describing underlying 40 * data structures. 41 */ 42 43 #ifndef PB_DS_TAG_AND_TRAIT_HPP 44 #define PB_DS_TAG_AND_TRAIT_HPP 45 46 #include <bits/c++config.h> 47 #include <ext/pb_ds/detail/type_utils.hpp> 48 49 /** 50 * @namespace __gnu_pbds 51 * @brief GNU extensions for policy-based data structures for public use. 52 */ 53 namespace __gnu_pbds 54 { 55 /** @defgroup pbds Policy-Based Data Structures 56 * @ingroup extensions 57 * 58 * This is a library of policy-based elementary data structures: 59 * associative containers and priority queues. It is designed for 60 * high-performance, flexibility, semantic safety, and conformance 61 * to the corresponding containers in std (except for some points 62 * where it differs by design). 63 * 64 * For details, see: 65 * http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/index.html 66 * 67 * @{ 68 */ 69 70 /** 71 * @defgroup tags Tags 72 * @{ 73 */ 74 /// A trivial iterator tag. Signifies that the iterators has none of 75 /// std::iterators's movement abilities. 76 struct trivial_iterator_tag 77 { }; 78 79 /// Prohibit moving trivial iterators. 80 typedef void trivial_iterator_difference_type; 81 82 83 /** 84 * @defgroup invalidation_tags Invalidation Guarantees 85 * @ingroup tags 86 * @{ 87 */ 88 89 /** 90 * Signifies a basic invalidation guarantee that any iterator, 91 * pointer, or reference to a container object's mapped value type 92 * is valid as long as the container is not modified. 93 */ 94 struct basic_invalidation_guarantee 95 { }; 96 97 /** 98 * Signifies an invalidation guarantee that includes all those of 99 * its base, and additionally, that any point-type iterator, 100 * pointer, or reference to a container object's mapped value type 101 * is valid as long as its corresponding entry has not be erased, 102 * regardless of modifications to the container object. 103 */ 104 struct point_invalidation_guarantee : public basic_invalidation_guarantee 105 { }; 106 107 /** 108 * Signifies an invalidation guarantee that includes all those of 109 * its base, and additionally, that any range-type iterator 110 * (including the returns of begin() and end()) is in the correct 111 * relative positions to other range-type iterators as long as its 112 * corresponding entry has not be erased, regardless of 113 * modifications to the container object. 114 */ 115 struct range_invalidation_guarantee : public point_invalidation_guarantee 116 { }; 117 //@} 118 119 120 /** 121 * @defgroup ds_tags Data Structure Type 122 * @ingroup tags 123 * @{ 124 */ 125 /// Base data structure tag. 126 struct container_tag 127 { }; 128 129 /// Basic sequence. 130 struct sequence_tag : public container_tag { }; 131 132 /// Basic string container, inclusive of strings, ropes, etc. 133 struct string_tag : public sequence_tag { }; 134 135 /// Basic associative-container. 136 struct associative_tag : public container_tag { }; 137 138 /// Basic hash structure. 139 struct basic_hash_tag : public associative_tag { }; 140 141 /// Collision-chaining hash. 142 struct cc_hash_tag : public basic_hash_tag { }; 143 144 /// General-probing hash. 145 struct gp_hash_tag : public basic_hash_tag { }; 146 147 /// Basic branch structure. 148 struct basic_branch_tag : public associative_tag { }; 149 150 /// Basic tree structure. 151 struct tree_tag : public basic_branch_tag { }; 152 153 /// Red-black tree. 154 struct rb_tree_tag : public tree_tag { }; 155 156 /// Splay tree. 157 struct splay_tree_tag : public tree_tag { }; 158 159 /// Ordered-vector tree. 160 struct ov_tree_tag : public tree_tag { }; 161 162 /// Basic trie structure. 163 struct trie_tag : public basic_branch_tag { }; 164 165 /// PATRICIA trie. 166 struct pat_trie_tag : public trie_tag { }; 167 168 /// List-update. 169 struct list_update_tag : public associative_tag { }; 170 171 /// Basic priority-queue. 172 struct priority_queue_tag : public container_tag { }; 173 174 /// Pairing-heap. 175 struct pairing_heap_tag : public priority_queue_tag { }; 176 177 /// Binomial-heap. 178 struct binomial_heap_tag : public priority_queue_tag { }; 179 180 /// Redundant-counter binomial-heap. 181 struct rc_binomial_heap_tag : public priority_queue_tag { }; 182 183 /// Binary-heap (array-based). 184 struct binary_heap_tag : public priority_queue_tag { }; 185 186 /// Thin heap. 187 struct thin_heap_tag : public priority_queue_tag { }; 188 //@} 189 //@} 190 191 192 /** 193 * @defgroup traits Traits 194 * @{ 195 */ 196 197 /** 198 * @brief Represents no type, or absence of type, for template tricks. 199 * 200 * In a mapped-policy, indicates that an associative container is a set. 201 * 202 * In a list-update policy, indicates that each link does not need 203 * metadata. 204 * 205 * In a hash policy, indicates that the combining hash function 206 * is actually a ranged hash function. 207 * 208 * In a probe policy, indicates that the combining probe function 209 * is actually a ranged probe function. 210 */ 211 struct null_type { }; 212 213 /// A null node updator, indicating that no node updates are required. 214 template<typename _Tp1, typename _Tp2, typename _Tp3, typename _Tp4> 215 struct null_node_update : public null_type 216 { }; 217 218 219 /// Primary template, container traits base. 220 template<typename _Tag> 221 struct container_traits_base; 222 223 /// Specialization, cc hash. 224 template<> 225 struct container_traits_base<cc_hash_tag> 226 { 227 typedef cc_hash_tag container_category; 228 typedef point_invalidation_guarantee invalidation_guarantee; 229 230 enum 231 { 232 order_preserving = false, 233 erase_can_throw = false, 234 split_join_can_throw = false, 235 reverse_iteration = false 236 }; 237 }; 238 239 /// Specialization, gp hash. 240 template<> 241 struct container_traits_base<gp_hash_tag> 242 { 243 typedef gp_hash_tag container_category; 244 typedef basic_invalidation_guarantee invalidation_guarantee; 245 246 enum 247 { 248 order_preserving = false, 249 erase_can_throw = false, 250 split_join_can_throw = false, 251 reverse_iteration = false 252 }; 253 }; 254 255 /// Specialization, rb tree. 256 template<> 257 struct container_traits_base<rb_tree_tag> 258 { 259 typedef rb_tree_tag container_category; 260 typedef range_invalidation_guarantee invalidation_guarantee; 261 262 enum 263 { 264 order_preserving = true, 265 erase_can_throw = false, 266 split_join_can_throw = false, 267 reverse_iteration = true 268 }; 269 }; 270 271 /// Specialization, splay tree. 272 template<> 273 struct container_traits_base<splay_tree_tag> 274 { 275 typedef splay_tree_tag container_category; 276 typedef range_invalidation_guarantee invalidation_guarantee; 277 278 enum 279 { 280 order_preserving = true, 281 erase_can_throw = false, 282 split_join_can_throw = false, 283 reverse_iteration = true 284 }; 285 }; 286 287 /// Specialization, ov tree. 288 template<> 289 struct container_traits_base<ov_tree_tag> 290 { 291 typedef ov_tree_tag container_category; 292 typedef basic_invalidation_guarantee invalidation_guarantee; 293 294 enum 295 { 296 order_preserving = true, 297 erase_can_throw = true, 298 split_join_can_throw = true, 299 reverse_iteration = false 300 }; 301 }; 302 303 /// Specialization, pat trie. 304 template<> 305 struct container_traits_base<pat_trie_tag> 306 { 307 typedef pat_trie_tag container_category; 308 typedef range_invalidation_guarantee invalidation_guarantee; 309 310 enum 311 { 312 order_preserving = true, 313 erase_can_throw = false, 314 split_join_can_throw = true, 315 reverse_iteration = true 316 }; 317 }; 318 319 /// Specialization, list update. 320 template<> 321 struct container_traits_base<list_update_tag> 322 { 323 typedef list_update_tag container_category; 324 typedef point_invalidation_guarantee invalidation_guarantee; 325 326 enum 327 { 328 order_preserving = false, 329 erase_can_throw = false, 330 split_join_can_throw = false, 331 reverse_iteration = false 332 }; 333 }; 334 335 /// Specialization, pairing heap. 336 template<> 337 struct container_traits_base<pairing_heap_tag> 338 { 339 typedef pairing_heap_tag container_category; 340 typedef point_invalidation_guarantee invalidation_guarantee; 341 342 enum 343 { 344 order_preserving = false, 345 erase_can_throw = false, 346 split_join_can_throw = false, 347 reverse_iteration = false 348 }; 349 }; 350 351 /// Specialization, thin heap. 352 template<> 353 struct container_traits_base<thin_heap_tag> 354 { 355 typedef thin_heap_tag container_category; 356 typedef point_invalidation_guarantee invalidation_guarantee; 357 358 enum 359 { 360 order_preserving = false, 361 erase_can_throw = false, 362 split_join_can_throw = false, 363 reverse_iteration = false 364 }; 365 }; 366 367 /// Specialization, binomial heap. 368 template<> 369 struct container_traits_base<binomial_heap_tag> 370 { 371 typedef binomial_heap_tag container_category; 372 typedef point_invalidation_guarantee invalidation_guarantee; 373 374 enum 375 { 376 order_preserving = false, 377 erase_can_throw = false, 378 split_join_can_throw = false, 379 reverse_iteration = false 380 }; 381 }; 382 383 /// Specialization, rc binomial heap. 384 template<> 385 struct container_traits_base<rc_binomial_heap_tag> 386 { 387 typedef rc_binomial_heap_tag container_category; 388 typedef point_invalidation_guarantee invalidation_guarantee; 389 390 enum 391 { 392 order_preserving = false, 393 erase_can_throw = false, 394 split_join_can_throw = false, 395 reverse_iteration = false 396 }; 397 }; 398 399 /// Specialization, binary heap. 400 template<> 401 struct container_traits_base<binary_heap_tag> 402 { 403 typedef binary_heap_tag container_category; 404 typedef basic_invalidation_guarantee invalidation_guarantee; 405 406 enum 407 { 408 order_preserving = false, 409 erase_can_throw = false, 410 split_join_can_throw = true, 411 reverse_iteration = false 412 }; 413 }; 414 415 416 /// Container traits. 417 // See Matt Austern for the name, S. Meyers MEFC++ #2, others. 418 template<typename Cntnr> 419 struct container_traits 420 : public container_traits_base<typename Cntnr::container_category> 421 { 422 typedef Cntnr container_type; 423 typedef typename Cntnr::container_category container_category; 424 typedef container_traits_base<container_category> base_type; 425 typedef typename base_type::invalidation_guarantee invalidation_guarantee; 426 427 enum 428 { 429 /// True only if Cntnr objects guarantee storing keys by order. 430 order_preserving = base_type::order_preserving, 431 432 /// True only if erasing a key can throw. 433 erase_can_throw = base_type::erase_can_throw, 434 435 /// True only if split or join operations can throw. 436 split_join_can_throw = base_type::split_join_can_throw, 437 438 /// True only reverse iterators are supported. 439 reverse_iteration = base_type::reverse_iteration 440 }; 441 }; 442 //@} 443 444 445 namespace detail 446 { 447 /// Dispatch mechanism, primary template for associative types. 448 template<typename Key, typename Mapped, typename _Alloc, typename Tag, 449 typename Policy_Tl = null_type> 450 struct container_base_dispatch; 451 } // namespace __detail 452 //@} 453 } // namespace __gnu_pbds 454 455 #endif 456