btree_map.h (33201B)
1 // Copyright 2018 The Abseil Authors. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 // 15 // ----------------------------------------------------------------------------- 16 // File: btree_map.h 17 // ----------------------------------------------------------------------------- 18 // 19 // This header file defines B-tree maps: sorted associative containers mapping 20 // keys to values. 21 // 22 // * `absl::btree_map<>` 23 // * `absl::btree_multimap<>` 24 // 25 // These B-tree types are similar to the corresponding types in the STL 26 // (`std::map` and `std::multimap`) and generally conform to the STL interfaces 27 // of those types. However, because they are implemented using B-trees, they 28 // are more efficient in most situations. 29 // 30 // Unlike `std::map` and `std::multimap`, which are commonly implemented using 31 // red-black tree nodes, B-tree maps use more generic B-tree nodes able to hold 32 // multiple values per node. Holding multiple values per node often makes 33 // B-tree maps perform better than their `std::map` counterparts, because 34 // multiple entries can be checked within the same cache hit. 35 // 36 // However, these types should not be considered drop-in replacements for 37 // `std::map` and `std::multimap` as there are some API differences, which are 38 // noted in this header file. The most consequential differences with respect to 39 // migrating to b-tree from the STL types are listed in the next paragraph. 40 // Other API differences are minor. 41 // 42 // Importantly, insertions and deletions may invalidate outstanding iterators, 43 // pointers, and references to elements. Such invalidations are typically only 44 // an issue if insertion and deletion operations are interleaved with the use of 45 // more than one iterator, pointer, or reference simultaneously. For this 46 // reason, `insert()`, `erase()`, and `extract_and_get_next()` return a valid 47 // iterator at the current position. Another important difference is that 48 // key-types must be copy-constructible. 49 // 50 // There are other API differences: first, btree iterators can be subtracted, 51 // and this is faster than using `std::distance`. Additionally, btree 52 // iterators can be advanced via `operator+=` and `operator-=`, which is faster 53 // than using `std::advance`. 54 // 55 // B-tree maps are not exception-safe. 56 57 #ifndef ABSL_CONTAINER_BTREE_MAP_H_ 58 #define ABSL_CONTAINER_BTREE_MAP_H_ 59 60 #include "absl/base/attributes.h" 61 #include "absl/container/internal/btree.h" // IWYU pragma: export 62 #include "absl/container/internal/btree_container.h" // IWYU pragma: export 63 64 namespace absl { 65 ABSL_NAMESPACE_BEGIN 66 67 namespace container_internal { 68 69 template <typename Key, typename Data, typename Compare, typename Alloc, 70 int TargetNodeSize, bool IsMulti> 71 struct map_params; 72 73 } // namespace container_internal 74 75 // absl::btree_map<> 76 // 77 // An `absl::btree_map<K, V>` is an ordered associative container of 78 // unique keys and associated values designed to be a more efficient replacement 79 // for `std::map` (in most cases). 80 // 81 // Keys are sorted using an (optional) comparison function, which defaults to 82 // `std::less<K>`. 83 // 84 // An `absl::btree_map<K, V>` uses a default allocator of 85 // `std::allocator<std::pair<const K, V>>` to allocate (and deallocate) 86 // nodes, and construct and destruct values within those nodes. You may 87 // instead specify a custom allocator `A` (which in turn requires specifying a 88 // custom comparator `C`) as in `absl::btree_map<K, V, C, A>`. 89 // 90 template <typename Key, typename Value, typename Compare = std::less<Key>, 91 typename Alloc = std::allocator<std::pair<const Key, Value>>> 92 class ABSL_ATTRIBUTE_OWNER btree_map 93 : public container_internal::btree_map_container< 94 container_internal::btree<container_internal::map_params< 95 Key, Value, Compare, Alloc, /*TargetNodeSize=*/256, 96 /*IsMulti=*/false>>> { 97 using Base = typename btree_map::btree_map_container; 98 99 public: 100 // Constructors and Assignment Operators 101 // 102 // A `btree_map` supports the same overload set as `std::map` 103 // for construction and assignment: 104 // 105 // * Default constructor 106 // 107 // absl::btree_map<int, std::string> map1; 108 // 109 // * Initializer List constructor 110 // 111 // absl::btree_map<int, std::string> map2 = 112 // {{1, "huey"}, {2, "dewey"}, {3, "louie"},}; 113 // 114 // * Copy constructor 115 // 116 // absl::btree_map<int, std::string> map3(map2); 117 // 118 // * Copy assignment operator 119 // 120 // absl::btree_map<int, std::string> map4; 121 // map4 = map3; 122 // 123 // * Move constructor 124 // 125 // // Move is guaranteed efficient 126 // absl::btree_map<int, std::string> map5(std::move(map4)); 127 // 128 // * Move assignment operator 129 // 130 // // May be efficient if allocators are compatible 131 // absl::btree_map<int, std::string> map6; 132 // map6 = std::move(map5); 133 // 134 // * Range constructor 135 // 136 // std::vector<std::pair<int, std::string>> v = {{1, "a"}, {2, "b"}}; 137 // absl::btree_map<int, std::string> map7(v.begin(), v.end()); 138 btree_map() {} 139 using Base::Base; 140 141 // btree_map::begin() 142 // 143 // Returns an iterator to the beginning of the `btree_map`. 144 using Base::begin; 145 146 // btree_map::cbegin() 147 // 148 // Returns a const iterator to the beginning of the `btree_map`. 149 using Base::cbegin; 150 151 // btree_map::end() 152 // 153 // Returns an iterator to the end of the `btree_map`. 154 using Base::end; 155 156 // btree_map::cend() 157 // 158 // Returns a const iterator to the end of the `btree_map`. 159 using Base::cend; 160 161 // btree_map::empty() 162 // 163 // Returns whether or not the `btree_map` is empty. 164 using Base::empty; 165 166 // btree_map::max_size() 167 // 168 // Returns the largest theoretical possible number of elements within a 169 // `btree_map` under current memory constraints. This value can be thought 170 // of as the largest value of `std::distance(begin(), end())` for a 171 // `btree_map<Key, T>`. 172 using Base::max_size; 173 174 // btree_map::size() 175 // 176 // Returns the number of elements currently within the `btree_map`. 177 using Base::size; 178 179 // btree_map::clear() 180 // 181 // Removes all elements from the `btree_map`. Invalidates any references, 182 // pointers, or iterators referring to contained elements. 183 using Base::clear; 184 185 // btree_map::erase() 186 // 187 // Erases elements within the `btree_map`. If an erase occurs, any references, 188 // pointers, or iterators are invalidated. 189 // Overloads are listed below. 190 // 191 // iterator erase(iterator position): 192 // iterator erase(const_iterator position): 193 // 194 // Erases the element at `position` of the `btree_map`, returning 195 // the iterator pointing to the element after the one that was erased 196 // (or end() if none exists). 197 // 198 // iterator erase(const_iterator first, const_iterator last): 199 // 200 // Erases the elements in the open interval [`first`, `last`), returning 201 // the iterator pointing to the element after the interval that was erased 202 // (or end() if none exists). 203 // 204 // template <typename K> size_type erase(const K& key): 205 // 206 // Erases the element with the matching key, if it exists, returning the 207 // number of elements erased (0 or 1). 208 using Base::erase; 209 210 // btree_map::insert() 211 // 212 // Inserts an element of the specified value into the `btree_map`, 213 // returning an iterator pointing to the newly inserted element, provided that 214 // an element with the given key does not already exist. If an insertion 215 // occurs, any references, pointers, or iterators are invalidated. 216 // Overloads are listed below. 217 // 218 // std::pair<iterator,bool> insert(const value_type& value): 219 // 220 // Inserts a value into the `btree_map`. Returns a pair consisting of an 221 // iterator to the inserted element (or to the element that prevented the 222 // insertion) and a bool denoting whether the insertion took place. 223 // 224 // std::pair<iterator,bool> insert(value_type&& value): 225 // 226 // Inserts a moveable value into the `btree_map`. Returns a pair 227 // consisting of an iterator to the inserted element (or to the element that 228 // prevented the insertion) and a bool denoting whether the insertion took 229 // place. 230 // 231 // iterator insert(const_iterator hint, const value_type& value): 232 // iterator insert(const_iterator hint, value_type&& value): 233 // 234 // Inserts a value, using the position of `hint` as a non-binding suggestion 235 // for where to begin the insertion search. Returns an iterator to the 236 // inserted element, or to the existing element that prevented the 237 // insertion. 238 // 239 // void insert(InputIterator first, InputIterator last): 240 // 241 // Inserts a range of values [`first`, `last`). 242 // 243 // void insert(std::initializer_list<init_type> ilist): 244 // 245 // Inserts the elements within the initializer list `ilist`. 246 using Base::insert; 247 248 // btree_map::insert_or_assign() 249 // 250 // Inserts an element of the specified value into the `btree_map` provided 251 // that a value with the given key does not already exist, or replaces the 252 // corresponding mapped type with the forwarded `obj` argument if a key for 253 // that value already exists, returning an iterator pointing to the newly 254 // inserted element. Overloads are listed below. 255 // 256 // pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj): 257 // pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj): 258 // 259 // Inserts/Assigns (or moves) the element of the specified key into the 260 // `btree_map`. If the returned bool is true, insertion took place, and if 261 // it's false, assignment took place. 262 // 263 // iterator insert_or_assign(const_iterator hint, 264 // const key_type& k, M&& obj): 265 // iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj): 266 // 267 // Inserts/Assigns (or moves) the element of the specified key into the 268 // `btree_map` using the position of `hint` as a non-binding suggestion 269 // for where to begin the insertion search. 270 using Base::insert_or_assign; 271 272 // btree_map::emplace() 273 // 274 // Inserts an element of the specified value by constructing it in-place 275 // within the `btree_map`, provided that no element with the given key 276 // already exists. 277 // 278 // The element may be constructed even if there already is an element with the 279 // key in the container, in which case the newly constructed element will be 280 // destroyed immediately. Prefer `try_emplace()` unless your key is not 281 // copyable or moveable. 282 // 283 // If an insertion occurs, any references, pointers, or iterators are 284 // invalidated. 285 using Base::emplace; 286 287 // btree_map::emplace_hint() 288 // 289 // Inserts an element of the specified value by constructing it in-place 290 // within the `btree_map`, using the position of `hint` as a non-binding 291 // suggestion for where to begin the insertion search, and only inserts 292 // provided that no element with the given key already exists. 293 // 294 // The element may be constructed even if there already is an element with the 295 // key in the container, in which case the newly constructed element will be 296 // destroyed immediately. Prefer `try_emplace()` unless your key is not 297 // copyable or moveable. 298 // 299 // If an insertion occurs, any references, pointers, or iterators are 300 // invalidated. 301 using Base::emplace_hint; 302 303 // btree_map::try_emplace() 304 // 305 // Inserts an element of the specified value by constructing it in-place 306 // within the `btree_map`, provided that no element with the given key 307 // already exists. Unlike `emplace()`, if an element with the given key 308 // already exists, we guarantee that no element is constructed. 309 // 310 // If an insertion occurs, any references, pointers, or iterators are 311 // invalidated. 312 // 313 // Overloads are listed below. 314 // 315 // std::pair<iterator, bool> try_emplace(const key_type& k, Args&&... args): 316 // std::pair<iterator, bool> try_emplace(key_type&& k, Args&&... args): 317 // 318 // Inserts (via copy or move) the element of the specified key into the 319 // `btree_map`. 320 // 321 // iterator try_emplace(const_iterator hint, 322 // const key_type& k, Args&&... args): 323 // iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args): 324 // 325 // Inserts (via copy or move) the element of the specified key into the 326 // `btree_map` using the position of `hint` as a non-binding suggestion 327 // for where to begin the insertion search. 328 using Base::try_emplace; 329 330 // btree_map::extract() 331 // 332 // Extracts the indicated element, erasing it in the process, and returns it 333 // as a C++17-compatible node handle. Any references, pointers, or iterators 334 // are invalidated. Overloads are listed below. 335 // 336 // node_type extract(const_iterator position): 337 // 338 // Extracts the element at the indicated position and returns a node handle 339 // owning that extracted data. 340 // 341 // template <typename K> node_type extract(const K& k): 342 // 343 // Extracts the element with the key matching the passed key value and 344 // returns a node handle owning that extracted data. If the `btree_map` 345 // does not contain an element with a matching key, this function returns an 346 // empty node handle. 347 // 348 // NOTE: when compiled in an earlier version of C++ than C++17, 349 // `node_type::key()` returns a const reference to the key instead of a 350 // mutable reference. We cannot safely return a mutable reference without 351 // std::launder (which is not available before C++17). 352 // 353 // NOTE: In this context, `node_type` refers to the C++17 concept of a 354 // move-only type that owns and provides access to the elements in associative 355 // containers (https://en.cppreference.com/w/cpp/container/node_handle). 356 // It does NOT refer to the data layout of the underlying btree. 357 using Base::extract; 358 359 // btree_map::extract_and_get_next() 360 // 361 // Extracts the indicated element, erasing it in the process, and returns it 362 // as a C++17-compatible node handle along with an iterator to the next 363 // element. 364 // 365 // extract_and_get_next_return_type extract_and_get_next( 366 // const_iterator position): 367 // 368 // Extracts the element at the indicated position, returns a struct 369 // containing a member named `node`: a node handle owning that extracted 370 // data and a member named `next`: an iterator pointing to the next element 371 // in the btree. 372 using Base::extract_and_get_next; 373 374 // btree_map::merge() 375 // 376 // Extracts elements from a given `source` btree_map into this 377 // `btree_map`. If the destination `btree_map` already contains an 378 // element with an equivalent key, that element is not extracted. 379 using Base::merge; 380 381 // btree_map::swap(btree_map& other) 382 // 383 // Exchanges the contents of this `btree_map` with those of the `other` 384 // btree_map, avoiding invocation of any move, copy, or swap operations on 385 // individual elements. 386 // 387 // All iterators and references on the `btree_map` remain valid, excepting 388 // for the past-the-end iterator, which is invalidated. 389 using Base::swap; 390 391 // btree_map::at() 392 // 393 // Returns a reference to the mapped value of the element with key equivalent 394 // to the passed key. 395 using Base::at; 396 397 // btree_map::contains() 398 // 399 // template <typename K> bool contains(const K& key) const: 400 // 401 // Determines whether an element comparing equal to the given `key` exists 402 // within the `btree_map`, returning `true` if so or `false` otherwise. 403 // 404 // Supports heterogeneous lookup, provided that the map has a compatible 405 // heterogeneous comparator. 406 using Base::contains; 407 408 // btree_map::count() 409 // 410 // template <typename K> size_type count(const K& key) const: 411 // 412 // Returns the number of elements comparing equal to the given `key` within 413 // the `btree_map`. Note that this function will return either `1` or `0` 414 // since duplicate elements are not allowed within a `btree_map`. 415 // 416 // Supports heterogeneous lookup, provided that the map has a compatible 417 // heterogeneous comparator. 418 using Base::count; 419 420 // btree_map::equal_range() 421 // 422 // Returns a half-open range [first, last), defined by a `std::pair` of two 423 // iterators, containing all elements with the passed key in the `btree_map`. 424 using Base::equal_range; 425 426 // btree_map::find() 427 // 428 // template <typename K> iterator find(const K& key): 429 // template <typename K> const_iterator find(const K& key) const: 430 // 431 // Finds an element with the passed `key` within the `btree_map`. 432 // 433 // Supports heterogeneous lookup, provided that the map has a compatible 434 // heterogeneous comparator. 435 using Base::find; 436 437 // btree_map::lower_bound() 438 // 439 // template <typename K> iterator lower_bound(const K& key): 440 // template <typename K> const_iterator lower_bound(const K& key) const: 441 // 442 // Finds the first element with a key that is not less than `key` within the 443 // `btree_map`. 444 // 445 // Supports heterogeneous lookup, provided that the map has a compatible 446 // heterogeneous comparator. 447 using Base::lower_bound; 448 449 // btree_map::upper_bound() 450 // 451 // template <typename K> iterator upper_bound(const K& key): 452 // template <typename K> const_iterator upper_bound(const K& key) const: 453 // 454 // Finds the first element with a key that is greater than `key` within the 455 // `btree_map`. 456 // 457 // Supports heterogeneous lookup, provided that the map has a compatible 458 // heterogeneous comparator. 459 using Base::upper_bound; 460 461 // btree_map::operator[]() 462 // 463 // Returns a reference to the value mapped to the passed key within the 464 // `btree_map`, performing an `insert()` if the key does not already 465 // exist. 466 // 467 // If an insertion occurs, any references, pointers, or iterators are 468 // invalidated. Otherwise iterators are not affected and references are not 469 // invalidated. Overloads are listed below. 470 // 471 // T& operator[](key_type&& key): 472 // T& operator[](const key_type& key): 473 // 474 // Inserts a value_type object constructed in-place if the element with the 475 // given key does not exist. 476 using Base::operator[]; 477 478 // btree_map::get_allocator() 479 // 480 // Returns the allocator function associated with this `btree_map`. 481 using Base::get_allocator; 482 483 // btree_map::key_comp(); 484 // 485 // Returns the key comparator associated with this `btree_map`. 486 using Base::key_comp; 487 488 // btree_map::value_comp(); 489 // 490 // Returns the value comparator associated with this `btree_map`. 491 using Base::value_comp; 492 }; 493 494 // absl::swap(absl::btree_map<>, absl::btree_map<>) 495 // 496 // Swaps the contents of two `absl::btree_map` containers. 497 template <typename K, typename V, typename C, typename A> 498 void swap(btree_map<K, V, C, A> &x, btree_map<K, V, C, A> &y) { 499 return x.swap(y); 500 } 501 502 // absl::erase_if(absl::btree_map<>, Pred) 503 // 504 // Erases all elements that satisfy the predicate pred from the container. 505 // Returns the number of erased elements. 506 template <typename K, typename V, typename C, typename A, typename Pred> 507 typename btree_map<K, V, C, A>::size_type erase_if( 508 btree_map<K, V, C, A> &map, Pred pred) { 509 return container_internal::btree_access::erase_if(map, std::move(pred)); 510 } 511 512 // absl::btree_multimap 513 // 514 // An `absl::btree_multimap<K, V>` is an ordered associative container of 515 // keys and associated values designed to be a more efficient replacement for 516 // `std::multimap` (in most cases). Unlike `absl::btree_map`, a B-tree multimap 517 // allows multiple elements with equivalent keys. 518 // 519 // Keys are sorted using an (optional) comparison function, which defaults to 520 // `std::less<K>`. 521 // 522 // An `absl::btree_multimap<K, V>` uses a default allocator of 523 // `std::allocator<std::pair<const K, V>>` to allocate (and deallocate) 524 // nodes, and construct and destruct values within those nodes. You may 525 // instead specify a custom allocator `A` (which in turn requires specifying a 526 // custom comparator `C`) as in `absl::btree_multimap<K, V, C, A>`. 527 // 528 template <typename Key, typename Value, typename Compare = std::less<Key>, 529 typename Alloc = std::allocator<std::pair<const Key, Value>>> 530 class ABSL_ATTRIBUTE_OWNER btree_multimap 531 : public container_internal::btree_multimap_container< 532 container_internal::btree<container_internal::map_params< 533 Key, Value, Compare, Alloc, /*TargetNodeSize=*/256, 534 /*IsMulti=*/true>>> { 535 using Base = typename btree_multimap::btree_multimap_container; 536 537 public: 538 // Constructors and Assignment Operators 539 // 540 // A `btree_multimap` supports the same overload set as `std::multimap` 541 // for construction and assignment: 542 // 543 // * Default constructor 544 // 545 // absl::btree_multimap<int, std::string> map1; 546 // 547 // * Initializer List constructor 548 // 549 // absl::btree_multimap<int, std::string> map2 = 550 // {{1, "huey"}, {2, "dewey"}, {3, "louie"},}; 551 // 552 // * Copy constructor 553 // 554 // absl::btree_multimap<int, std::string> map3(map2); 555 // 556 // * Copy assignment operator 557 // 558 // absl::btree_multimap<int, std::string> map4; 559 // map4 = map3; 560 // 561 // * Move constructor 562 // 563 // // Move is guaranteed efficient 564 // absl::btree_multimap<int, std::string> map5(std::move(map4)); 565 // 566 // * Move assignment operator 567 // 568 // // May be efficient if allocators are compatible 569 // absl::btree_multimap<int, std::string> map6; 570 // map6 = std::move(map5); 571 // 572 // * Range constructor 573 // 574 // std::vector<std::pair<int, std::string>> v = {{1, "a"}, {2, "b"}}; 575 // absl::btree_multimap<int, std::string> map7(v.begin(), v.end()); 576 btree_multimap() {} 577 using Base::Base; 578 579 // btree_multimap::begin() 580 // 581 // Returns an iterator to the beginning of the `btree_multimap`. 582 using Base::begin; 583 584 // btree_multimap::cbegin() 585 // 586 // Returns a const iterator to the beginning of the `btree_multimap`. 587 using Base::cbegin; 588 589 // btree_multimap::end() 590 // 591 // Returns an iterator to the end of the `btree_multimap`. 592 using Base::end; 593 594 // btree_multimap::cend() 595 // 596 // Returns a const iterator to the end of the `btree_multimap`. 597 using Base::cend; 598 599 // btree_multimap::empty() 600 // 601 // Returns whether or not the `btree_multimap` is empty. 602 using Base::empty; 603 604 // btree_multimap::max_size() 605 // 606 // Returns the largest theoretical possible number of elements within a 607 // `btree_multimap` under current memory constraints. This value can be 608 // thought of as the largest value of `std::distance(begin(), end())` for a 609 // `btree_multimap<Key, T>`. 610 using Base::max_size; 611 612 // btree_multimap::size() 613 // 614 // Returns the number of elements currently within the `btree_multimap`. 615 using Base::size; 616 617 // btree_multimap::clear() 618 // 619 // Removes all elements from the `btree_multimap`. Invalidates any references, 620 // pointers, or iterators referring to contained elements. 621 using Base::clear; 622 623 // btree_multimap::erase() 624 // 625 // Erases elements within the `btree_multimap`. If an erase occurs, any 626 // references, pointers, or iterators are invalidated. 627 // Overloads are listed below. 628 // 629 // iterator erase(iterator position): 630 // iterator erase(const_iterator position): 631 // 632 // Erases the element at `position` of the `btree_multimap`, returning 633 // the iterator pointing to the element after the one that was erased 634 // (or end() if none exists). 635 // 636 // iterator erase(const_iterator first, const_iterator last): 637 // 638 // Erases the elements in the open interval [`first`, `last`), returning 639 // the iterator pointing to the element after the interval that was erased 640 // (or end() if none exists). 641 // 642 // template <typename K> size_type erase(const K& key): 643 // 644 // Erases the elements matching the key, if any exist, returning the 645 // number of elements erased. 646 using Base::erase; 647 648 // btree_multimap::insert() 649 // 650 // Inserts an element of the specified value into the `btree_multimap`, 651 // returning an iterator pointing to the newly inserted element. 652 // Any references, pointers, or iterators are invalidated. Overloads are 653 // listed below. 654 // 655 // iterator insert(const value_type& value): 656 // 657 // Inserts a value into the `btree_multimap`, returning an iterator to the 658 // inserted element. 659 // 660 // iterator insert(value_type&& value): 661 // 662 // Inserts a moveable value into the `btree_multimap`, returning an iterator 663 // to the inserted element. 664 // 665 // iterator insert(const_iterator hint, const value_type& value): 666 // iterator insert(const_iterator hint, value_type&& value): 667 // 668 // Inserts a value, using the position of `hint` as a non-binding suggestion 669 // for where to begin the insertion search. Returns an iterator to the 670 // inserted element. 671 // 672 // void insert(InputIterator first, InputIterator last): 673 // 674 // Inserts a range of values [`first`, `last`). 675 // 676 // void insert(std::initializer_list<init_type> ilist): 677 // 678 // Inserts the elements within the initializer list `ilist`. 679 using Base::insert; 680 681 // btree_multimap::emplace() 682 // 683 // Inserts an element of the specified value by constructing it in-place 684 // within the `btree_multimap`. Any references, pointers, or iterators are 685 // invalidated. 686 using Base::emplace; 687 688 // btree_multimap::emplace_hint() 689 // 690 // Inserts an element of the specified value by constructing it in-place 691 // within the `btree_multimap`, using the position of `hint` as a non-binding 692 // suggestion for where to begin the insertion search. 693 // 694 // Any references, pointers, or iterators are invalidated. 695 using Base::emplace_hint; 696 697 // btree_multimap::extract() 698 // 699 // Extracts the indicated element, erasing it in the process, and returns it 700 // as a C++17-compatible node handle. Overloads are listed below. 701 // 702 // node_type extract(const_iterator position): 703 // 704 // Extracts the element at the indicated position and returns a node handle 705 // owning that extracted data. 706 // 707 // template <typename K> node_type extract(const K& k): 708 // 709 // Extracts the element with the key matching the passed key value and 710 // returns a node handle owning that extracted data. If the `btree_multimap` 711 // does not contain an element with a matching key, this function returns an 712 // empty node handle. 713 // 714 // NOTE: when compiled in an earlier version of C++ than C++17, 715 // `node_type::key()` returns a const reference to the key instead of a 716 // mutable reference. We cannot safely return a mutable reference without 717 // std::launder (which is not available before C++17). 718 // 719 // NOTE: In this context, `node_type` refers to the C++17 concept of a 720 // move-only type that owns and provides access to the elements in associative 721 // containers (https://en.cppreference.com/w/cpp/container/node_handle). 722 // It does NOT refer to the data layout of the underlying btree. 723 using Base::extract; 724 725 // btree_multimap::extract_and_get_next() 726 // 727 // Extracts the indicated element, erasing it in the process, and returns it 728 // as a C++17-compatible node handle along with an iterator to the next 729 // element. 730 // 731 // extract_and_get_next_return_type extract_and_get_next( 732 // const_iterator position): 733 // 734 // Extracts the element at the indicated position, returns a struct 735 // containing a member named `node`: a node handle owning that extracted 736 // data and a member named `next`: an iterator pointing to the next element 737 // in the btree. 738 using Base::extract_and_get_next; 739 740 // btree_multimap::merge() 741 // 742 // Extracts all elements from a given `source` btree_multimap into this 743 // `btree_multimap`. 744 using Base::merge; 745 746 // btree_multimap::swap(btree_multimap& other) 747 // 748 // Exchanges the contents of this `btree_multimap` with those of the `other` 749 // btree_multimap, avoiding invocation of any move, copy, or swap operations 750 // on individual elements. 751 // 752 // All iterators and references on the `btree_multimap` remain valid, 753 // excepting for the past-the-end iterator, which is invalidated. 754 using Base::swap; 755 756 // btree_multimap::contains() 757 // 758 // template <typename K> bool contains(const K& key) const: 759 // 760 // Determines whether an element comparing equal to the given `key` exists 761 // within the `btree_multimap`, returning `true` if so or `false` otherwise. 762 // 763 // Supports heterogeneous lookup, provided that the map has a compatible 764 // heterogeneous comparator. 765 using Base::contains; 766 767 // btree_multimap::count() 768 // 769 // template <typename K> size_type count(const K& key) const: 770 // 771 // Returns the number of elements comparing equal to the given `key` within 772 // the `btree_multimap`. 773 // 774 // Supports heterogeneous lookup, provided that the map has a compatible 775 // heterogeneous comparator. 776 using Base::count; 777 778 // btree_multimap::equal_range() 779 // 780 // Returns a half-open range [first, last), defined by a `std::pair` of two 781 // iterators, containing all elements with the passed key in the 782 // `btree_multimap`. 783 using Base::equal_range; 784 785 // btree_multimap::find() 786 // 787 // template <typename K> iterator find(const K& key): 788 // template <typename K> const_iterator find(const K& key) const: 789 // 790 // Finds an element with the passed `key` within the `btree_multimap`. 791 // 792 // Supports heterogeneous lookup, provided that the map has a compatible 793 // heterogeneous comparator. 794 using Base::find; 795 796 // btree_multimap::lower_bound() 797 // 798 // template <typename K> iterator lower_bound(const K& key): 799 // template <typename K> const_iterator lower_bound(const K& key) const: 800 // 801 // Finds the first element with a key that is not less than `key` within the 802 // `btree_multimap`. 803 // 804 // Supports heterogeneous lookup, provided that the map has a compatible 805 // heterogeneous comparator. 806 using Base::lower_bound; 807 808 // btree_multimap::upper_bound() 809 // 810 // template <typename K> iterator upper_bound(const K& key): 811 // template <typename K> const_iterator upper_bound(const K& key) const: 812 // 813 // Finds the first element with a key that is greater than `key` within the 814 // `btree_multimap`. 815 // 816 // Supports heterogeneous lookup, provided that the map has a compatible 817 // heterogeneous comparator. 818 using Base::upper_bound; 819 820 // btree_multimap::get_allocator() 821 // 822 // Returns the allocator function associated with this `btree_multimap`. 823 using Base::get_allocator; 824 825 // btree_multimap::key_comp(); 826 // 827 // Returns the key comparator associated with this `btree_multimap`. 828 using Base::key_comp; 829 830 // btree_multimap::value_comp(); 831 // 832 // Returns the value comparator associated with this `btree_multimap`. 833 using Base::value_comp; 834 }; 835 836 // absl::swap(absl::btree_multimap<>, absl::btree_multimap<>) 837 // 838 // Swaps the contents of two `absl::btree_multimap` containers. 839 template <typename K, typename V, typename C, typename A> 840 void swap(btree_multimap<K, V, C, A> &x, btree_multimap<K, V, C, A> &y) { 841 return x.swap(y); 842 } 843 844 // absl::erase_if(absl::btree_multimap<>, Pred) 845 // 846 // Erases all elements that satisfy the predicate pred from the container. 847 // Returns the number of erased elements. 848 template <typename K, typename V, typename C, typename A, typename Pred> 849 typename btree_multimap<K, V, C, A>::size_type erase_if( 850 btree_multimap<K, V, C, A> &map, Pred pred) { 851 return container_internal::btree_access::erase_if(map, std::move(pred)); 852 } 853 854 namespace container_internal { 855 856 // A parameters structure for holding the type parameters for a btree_map. 857 // Compare and Alloc should be nothrow copy-constructible. 858 template <typename Key, typename Data, typename Compare, typename Alloc, 859 int TargetNodeSize, bool IsMulti> 860 struct map_params : common_params<Key, Compare, Alloc, TargetNodeSize, IsMulti, 861 /*IsMap=*/true, map_slot_policy<Key, Data>> { 862 using super_type = typename map_params::common_params; 863 using mapped_type = Data; 864 // This type allows us to move keys when it is safe to do so. It is safe 865 // for maps in which value_type and mutable_value_type are layout compatible. 866 using slot_policy = typename super_type::slot_policy; 867 using slot_type = typename super_type::slot_type; 868 using value_type = typename super_type::value_type; 869 using init_type = typename super_type::init_type; 870 871 template <typename V> 872 static auto key(const V &value ABSL_ATTRIBUTE_LIFETIME_BOUND) 873 -> decltype((value.first)) { 874 return value.first; 875 } 876 static const Key &key(const slot_type *s) { return slot_policy::key(s); } 877 static const Key &key(slot_type *s) { return slot_policy::key(s); } 878 // For use in node handle. 879 static auto mutable_key(slot_type *s) 880 -> decltype(slot_policy::mutable_key(s)) { 881 return slot_policy::mutable_key(s); 882 } 883 static mapped_type &value(value_type *value) { return value->second; } 884 }; 885 886 } // namespace container_internal 887 888 ABSL_NAMESPACE_END 889 } // namespace absl 890 891 #endif // ABSL_CONTAINER_BTREE_MAP_H_