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