1 // Map implementation -*- C++ -*- 2 3 // Copyright (C) 2001-2015 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 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU 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 /* 26 * 27 * Copyright (c) 1994 28 * Hewlett-Packard Company 29 * 30 * Permission to use, copy, modify, distribute and sell this software 31 * and its documentation for any purpose is hereby granted without fee, 32 * provided that the above copyright notice appear in all copies and 33 * that both that copyright notice and this permission notice appear 34 * in supporting documentation. Hewlett-Packard Company makes no 35 * representations about the suitability of this software for any 36 * purpose. It is provided "as is" without express or implied warranty. 37 * 38 * 39 * Copyright (c) 1996,1997 40 * Silicon Graphics Computer Systems, Inc. 41 * 42 * Permission to use, copy, modify, distribute and sell this software 43 * and its documentation for any purpose is hereby granted without fee, 44 * provided that the above copyright notice appear in all copies and 45 * that both that copyright notice and this permission notice appear 46 * in supporting documentation. Silicon Graphics makes no 47 * representations about the suitability of this software for any 48 * purpose. It is provided "as is" without express or implied warranty. 49 */ 50 51 /** @file bits/stl_map.h 52 * This is an internal header file, included by other library headers. 53 * Do not attempt to use it directly. @headername{map} 54 */ 55 56 #ifndef _STL_MAP_H 57 #define _STL_MAP_H 1 58 59 #include <bits/functexcept.h> 60 #include <bits/concept_check.h> 61 #if __cplusplus >= 201103L 62 #include <initializer_list> 63 #include <tuple> 64 #endif 65 66 namespace std _GLIBCXX_VISIBILITY(default) 67 { 68 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 69 70 /** 71 * @brief A standard container made up of (key,value) pairs, which can be 72 * retrieved based on a key, in logarithmic time. 73 * 74 * @ingroup associative_containers 75 * 76 * @tparam _Key Type of key objects. 77 * @tparam _Tp Type of mapped objects. 78 * @tparam _Compare Comparison function object type, defaults to less<_Key>. 79 * @tparam _Alloc Allocator type, defaults to 80 * allocator<pair<const _Key, _Tp>. 81 * 82 * Meets the requirements of a <a href="tables.html#65">container</a>, a 83 * <a href="tables.html#66">reversible container</a>, and an 84 * <a href="tables.html#69">associative container</a> (using unique keys). 85 * For a @c map<Key,T> the key_type is Key, the mapped_type is T, and the 86 * value_type is std::pair<const Key,T>. 87 * 88 * Maps support bidirectional iterators. 89 * 90 * The private tree data is declared exactly the same way for map and 91 * multimap; the distinction is made entirely in how the tree functions are 92 * called (*_unique versus *_equal, same as the standard). 93 */ 94 template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>, 95 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 96 class map 97 { 98 public: 99 typedef _Key key_type; 100 typedef _Tp mapped_type; 101 typedef std::pair<const _Key, _Tp> value_type; 102 typedef _Compare key_compare; 103 typedef _Alloc allocator_type; 104 105 private: 106 // concept requirements 107 typedef typename _Alloc::value_type _Alloc_value_type; 108 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 109 __glibcxx_class_requires4(_Compare, bool, _Key, _Key, 110 _BinaryFunctionConcept) 111 __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept) 112 113 public: 114 class value_compare 115 : public std::binary_function<value_type, value_type, bool> 116 { 117 friend class map<_Key, _Tp, _Compare, _Alloc>; 118 protected: 119 _Compare comp; 120 121 value_compare(_Compare __c) 122 : comp(__c) { } 123 124 public: 125 bool operator()(const value_type& __x, const value_type& __y) const 126 { return comp(__x.first, __y.first); } 127 }; 128 129 private: 130 /// This turns a red-black tree into a [multi]map. 131 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template 132 rebind<value_type>::other _Pair_alloc_type; 133 134 typedef _Rb_tree<key_type, value_type, _Select1st<value_type>, 135 key_compare, _Pair_alloc_type> _Rep_type; 136 137 /// The actual tree structure. 138 _Rep_type _M_t; 139 140 typedef __gnu_cxx::__alloc_traits<_Pair_alloc_type> _Alloc_traits; 141 142 public: 143 // many of these are specified differently in ISO, but the following are 144 // "functionally equivalent" 145 typedef typename _Alloc_traits::pointer pointer; 146 typedef typename _Alloc_traits::const_pointer const_pointer; 147 typedef typename _Alloc_traits::reference reference; 148 typedef typename _Alloc_traits::const_reference const_reference; 149 typedef typename _Rep_type::iterator iterator; 150 typedef typename _Rep_type::const_iterator const_iterator; 151 typedef typename _Rep_type::size_type size_type; 152 typedef typename _Rep_type::difference_type difference_type; 153 typedef typename _Rep_type::reverse_iterator reverse_iterator; 154 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 155 156 // [23.3.1.1] construct/copy/destroy 157 // (get_allocator() is also listed in this section) 158 159 /** 160 * @brief Default constructor creates no elements. 161 */ 162 map() 163 #if __cplusplus >= 201103L 164 noexcept(is_nothrow_default_constructible<allocator_type>::value 165 && is_nothrow_default_constructible<key_compare>::value) 166 #endif 167 : _M_t() { } 168 169 /** 170 * @brief Creates a %map with no elements. 171 * @param __comp A comparison object. 172 * @param __a An allocator object. 173 */ 174 explicit 175 map(const _Compare& __comp, 176 const allocator_type& __a = allocator_type()) 177 : _M_t(__comp, _Pair_alloc_type(__a)) { } 178 179 /** 180 * @brief %Map copy constructor. 181 * @param __x A %map of identical element and allocator types. 182 * 183 * The newly-created %map uses a copy of the allocation object 184 * used by @a __x. 185 */ 186 map(const map& __x) 187 : _M_t(__x._M_t) { } 188 189 #if __cplusplus >= 201103L 190 /** 191 * @brief %Map move constructor. 192 * @param __x A %map of identical element and allocator types. 193 * 194 * The newly-created %map contains the exact contents of @a __x. 195 * The contents of @a __x are a valid, but unspecified %map. 196 */ 197 map(map&& __x) 198 noexcept(is_nothrow_copy_constructible<_Compare>::value) 199 : _M_t(std::move(__x._M_t)) { } 200 201 /** 202 * @brief Builds a %map from an initializer_list. 203 * @param __l An initializer_list. 204 * @param __comp A comparison object. 205 * @param __a An allocator object. 206 * 207 * Create a %map consisting of copies of the elements in the 208 * initializer_list @a __l. 209 * This is linear in N if the range is already sorted, and NlogN 210 * otherwise (where N is @a __l.size()). 211 */ 212 map(initializer_list<value_type> __l, 213 const _Compare& __comp = _Compare(), 214 const allocator_type& __a = allocator_type()) 215 : _M_t(__comp, _Pair_alloc_type(__a)) 216 { _M_t._M_insert_unique(__l.begin(), __l.end()); } 217 218 /// Allocator-extended default constructor. 219 explicit 220 map(const allocator_type& __a) 221 : _M_t(_Compare(), _Pair_alloc_type(__a)) { } 222 223 /// Allocator-extended copy constructor. 224 map(const map& __m, const allocator_type& __a) 225 : _M_t(__m._M_t, _Pair_alloc_type(__a)) { } 226 227 /// Allocator-extended move constructor. 228 map(map&& __m, const allocator_type& __a) 229 noexcept(is_nothrow_copy_constructible<_Compare>::value 230 && _Alloc_traits::_S_always_equal()) 231 : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { } 232 233 /// Allocator-extended initialier-list constructor. 234 map(initializer_list<value_type> __l, const allocator_type& __a) 235 : _M_t(_Compare(), _Pair_alloc_type(__a)) 236 { _M_t._M_insert_unique(__l.begin(), __l.end()); } 237 238 /// Allocator-extended range constructor. 239 template<typename _InputIterator> 240 map(_InputIterator __first, _InputIterator __last, 241 const allocator_type& __a) 242 : _M_t(_Compare(), _Pair_alloc_type(__a)) 243 { _M_t._M_insert_unique(__first, __last); } 244 #endif 245 246 /** 247 * @brief Builds a %map from a range. 248 * @param __first An input iterator. 249 * @param __last An input iterator. 250 * 251 * Create a %map consisting of copies of the elements from 252 * [__first,__last). This is linear in N if the range is 253 * already sorted, and NlogN otherwise (where N is 254 * distance(__first,__last)). 255 */ 256 template<typename _InputIterator> 257 map(_InputIterator __first, _InputIterator __last) 258 : _M_t() 259 { _M_t._M_insert_unique(__first, __last); } 260 261 /** 262 * @brief Builds a %map from a range. 263 * @param __first An input iterator. 264 * @param __last An input iterator. 265 * @param __comp A comparison functor. 266 * @param __a An allocator object. 267 * 268 * Create a %map consisting of copies of the elements from 269 * [__first,__last). This is linear in N if the range is 270 * already sorted, and NlogN otherwise (where N is 271 * distance(__first,__last)). 272 */ 273 template<typename _InputIterator> 274 map(_InputIterator __first, _InputIterator __last, 275 const _Compare& __comp, 276 const allocator_type& __a = allocator_type()) 277 : _M_t(__comp, _Pair_alloc_type(__a)) 278 { _M_t._M_insert_unique(__first, __last); } 279 280 // FIXME There is no dtor declared, but we should have something 281 // generated by Doxygen. I don't know what tags to add to this 282 // paragraph to make that happen: 283 /** 284 * The dtor only erases the elements, and note that if the elements 285 * themselves are pointers, the pointed-to memory is not touched in any 286 * way. Managing the pointer is the user's responsibility. 287 */ 288 289 /** 290 * @brief %Map assignment operator. 291 * @param __x A %map of identical element and allocator types. 292 * 293 * All the elements of @a __x are copied, but unlike the copy 294 * constructor, the allocator object is not copied. 295 */ 296 map& 297 operator=(const map& __x) 298 { 299 _M_t = __x._M_t; 300 return *this; 301 } 302 303 #if __cplusplus >= 201103L 304 /// Move assignment operator. 305 map& 306 operator=(map&&) = default; 307 308 /** 309 * @brief %Map list assignment operator. 310 * @param __l An initializer_list. 311 * 312 * This function fills a %map with copies of the elements in the 313 * initializer list @a __l. 314 * 315 * Note that the assignment completely changes the %map and 316 * that the resulting %map's size is the same as the number 317 * of elements assigned. Old data may be lost. 318 */ 319 map& 320 operator=(initializer_list<value_type> __l) 321 { 322 _M_t._M_assign_unique(__l.begin(), __l.end()); 323 return *this; 324 } 325 #endif 326 327 /// Get a copy of the memory allocation object. 328 allocator_type 329 get_allocator() const _GLIBCXX_NOEXCEPT 330 { return allocator_type(_M_t.get_allocator()); } 331 332 // iterators 333 /** 334 * Returns a read/write iterator that points to the first pair in the 335 * %map. 336 * Iteration is done in ascending order according to the keys. 337 */ 338 iterator 339 begin() _GLIBCXX_NOEXCEPT 340 { return _M_t.begin(); } 341 342 /** 343 * Returns a read-only (constant) iterator that points to the first pair 344 * in the %map. Iteration is done in ascending order according to the 345 * keys. 346 */ 347 const_iterator 348 begin() const _GLIBCXX_NOEXCEPT 349 { return _M_t.begin(); } 350 351 /** 352 * Returns a read/write iterator that points one past the last 353 * pair in the %map. Iteration is done in ascending order 354 * according to the keys. 355 */ 356 iterator 357 end() _GLIBCXX_NOEXCEPT 358 { return _M_t.end(); } 359 360 /** 361 * Returns a read-only (constant) iterator that points one past the last 362 * pair in the %map. Iteration is done in ascending order according to 363 * the keys. 364 */ 365 const_iterator 366 end() const _GLIBCXX_NOEXCEPT 367 { return _M_t.end(); } 368 369 /** 370 * Returns a read/write reverse iterator that points to the last pair in 371 * the %map. Iteration is done in descending order according to the 372 * keys. 373 */ 374 reverse_iterator 375 rbegin() _GLIBCXX_NOEXCEPT 376 { return _M_t.rbegin(); } 377 378 /** 379 * Returns a read-only (constant) reverse iterator that points to the 380 * last pair in the %map. Iteration is done in descending order 381 * according to the keys. 382 */ 383 const_reverse_iterator 384 rbegin() const _GLIBCXX_NOEXCEPT 385 { return _M_t.rbegin(); } 386 387 /** 388 * Returns a read/write reverse iterator that points to one before the 389 * first pair in the %map. Iteration is done in descending order 390 * according to the keys. 391 */ 392 reverse_iterator 393 rend() _GLIBCXX_NOEXCEPT 394 { return _M_t.rend(); } 395 396 /** 397 * Returns a read-only (constant) reverse iterator that points to one 398 * before the first pair in the %map. Iteration is done in descending 399 * order according to the keys. 400 */ 401 const_reverse_iterator 402 rend() const _GLIBCXX_NOEXCEPT 403 { return _M_t.rend(); } 404 405 #if __cplusplus >= 201103L 406 /** 407 * Returns a read-only (constant) iterator that points to the first pair 408 * in the %map. Iteration is done in ascending order according to the 409 * keys. 410 */ 411 const_iterator 412 cbegin() const noexcept 413 { return _M_t.begin(); } 414 415 /** 416 * Returns a read-only (constant) iterator that points one past the last 417 * pair in the %map. Iteration is done in ascending order according to 418 * the keys. 419 */ 420 const_iterator 421 cend() const noexcept 422 { return _M_t.end(); } 423 424 /** 425 * Returns a read-only (constant) reverse iterator that points to the 426 * last pair in the %map. Iteration is done in descending order 427 * according to the keys. 428 */ 429 const_reverse_iterator 430 crbegin() const noexcept 431 { return _M_t.rbegin(); } 432 433 /** 434 * Returns a read-only (constant) reverse iterator that points to one 435 * before the first pair in the %map. Iteration is done in descending 436 * order according to the keys. 437 */ 438 const_reverse_iterator 439 crend() const noexcept 440 { return _M_t.rend(); } 441 #endif 442 443 // capacity 444 /** Returns true if the %map is empty. (Thus begin() would equal 445 * end().) 446 */ 447 bool 448 empty() const _GLIBCXX_NOEXCEPT 449 { return _M_t.empty(); } 450 451 /** Returns the size of the %map. */ 452 size_type 453 size() const _GLIBCXX_NOEXCEPT 454 { return _M_t.size(); } 455 456 /** Returns the maximum size of the %map. */ 457 size_type 458 max_size() const _GLIBCXX_NOEXCEPT 459 { return _M_t.max_size(); } 460 461 // [23.3.1.2] element access 462 /** 463 * @brief Subscript ( @c [] ) access to %map data. 464 * @param __k The key for which data should be retrieved. 465 * @return A reference to the data of the (key,data) %pair. 466 * 467 * Allows for easy lookup with the subscript ( @c [] ) 468 * operator. Returns data associated with the key specified in 469 * subscript. If the key does not exist, a pair with that key 470 * is created using default values, which is then returned. 471 * 472 * Lookup requires logarithmic time. 473 */ 474 mapped_type& 475 operator[](const key_type& __k) 476 { 477 // concept requirements 478 __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>) 479 480 iterator __i = lower_bound(__k); 481 // __i->first is greater than or equivalent to __k. 482 if (__i == end() || key_comp()(__k, (*__i).first)) 483 #if __cplusplus >= 201103L 484 __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct, 485 std::tuple<const key_type&>(__k), 486 std::tuple<>()); 487 #else 488 __i = insert(__i, value_type(__k, mapped_type())); 489 #endif 490 return (*__i).second; 491 } 492 493 #if __cplusplus >= 201103L 494 mapped_type& 495 operator[](key_type&& __k) 496 { 497 // concept requirements 498 __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>) 499 500 iterator __i = lower_bound(__k); 501 // __i->first is greater than or equivalent to __k. 502 if (__i == end() || key_comp()(__k, (*__i).first)) 503 __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct, 504 std::forward_as_tuple(std::move(__k)), 505 std::tuple<>()); 506 return (*__i).second; 507 } 508 #endif 509 510 // _GLIBCXX_RESOLVE_LIB_DEFECTS 511 // DR 464. Suggestion for new member functions in standard containers. 512 /** 513 * @brief Access to %map data. 514 * @param __k The key for which data should be retrieved. 515 * @return A reference to the data whose key is equivalent to @a __k, if 516 * such a data is present in the %map. 517 * @throw std::out_of_range If no such data is present. 518 */ 519 mapped_type& 520 at(const key_type& __k) 521 { 522 iterator __i = lower_bound(__k); 523 if (__i == end() || key_comp()(__k, (*__i).first)) 524 __throw_out_of_range(__N("map::at")); 525 return (*__i).second; 526 } 527 528 const mapped_type& 529 at(const key_type& __k) const 530 { 531 const_iterator __i = lower_bound(__k); 532 if (__i == end() || key_comp()(__k, (*__i).first)) 533 __throw_out_of_range(__N("map::at")); 534 return (*__i).second; 535 } 536 537 // modifiers 538 #if __cplusplus >= 201103L 539 /** 540 * @brief Attempts to build and insert a std::pair into the %map. 541 * 542 * @param __args Arguments used to generate a new pair instance (see 543 * std::piecewise_contruct for passing arguments to each 544 * part of the pair constructor). 545 * 546 * @return A pair, of which the first element is an iterator that points 547 * to the possibly inserted pair, and the second is a bool that 548 * is true if the pair was actually inserted. 549 * 550 * This function attempts to build and insert a (key, value) %pair into 551 * the %map. 552 * A %map relies on unique keys and thus a %pair is only inserted if its 553 * first element (the key) is not already present in the %map. 554 * 555 * Insertion requires logarithmic time. 556 */ 557 template<typename... _Args> 558 std::pair<iterator, bool> 559 emplace(_Args&&... __args) 560 { return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); } 561 562 /** 563 * @brief Attempts to build and insert a std::pair into the %map. 564 * 565 * @param __pos An iterator that serves as a hint as to where the pair 566 * should be inserted. 567 * @param __args Arguments used to generate a new pair instance (see 568 * std::piecewise_contruct for passing arguments to each 569 * part of the pair constructor). 570 * @return An iterator that points to the element with key of the 571 * std::pair built from @a __args (may or may not be that 572 * std::pair). 573 * 574 * This function is not concerned about whether the insertion took place, 575 * and thus does not return a boolean like the single-argument emplace() 576 * does. 577 * Note that the first parameter is only a hint and can potentially 578 * improve the performance of the insertion process. A bad hint would 579 * cause no gains in efficiency. 580 * 581 * See 582 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 583 * for more on @a hinting. 584 * 585 * Insertion requires logarithmic time (if the hint is not taken). 586 */ 587 template<typename... _Args> 588 iterator 589 emplace_hint(const_iterator __pos, _Args&&... __args) 590 { 591 return _M_t._M_emplace_hint_unique(__pos, 592 std::forward<_Args>(__args)...); 593 } 594 #endif 595 596 /** 597 * @brief Attempts to insert a std::pair into the %map. 598 599 * @param __x Pair to be inserted (see std::make_pair for easy 600 * creation of pairs). 601 * 602 * @return A pair, of which the first element is an iterator that 603 * points to the possibly inserted pair, and the second is 604 * a bool that is true if the pair was actually inserted. 605 * 606 * This function attempts to insert a (key, value) %pair into the %map. 607 * A %map relies on unique keys and thus a %pair is only inserted if its 608 * first element (the key) is not already present in the %map. 609 * 610 * Insertion requires logarithmic time. 611 */ 612 std::pair<iterator, bool> 613 insert(const value_type& __x) 614 { return _M_t._M_insert_unique(__x); } 615 616 #if __cplusplus >= 201103L 617 template<typename _Pair, typename = typename 618 std::enable_if<std::is_constructible<value_type, 619 _Pair&&>::value>::type> 620 std::pair<iterator, bool> 621 insert(_Pair&& __x) 622 { return _M_t._M_insert_unique(std::forward<_Pair>(__x)); } 623 #endif 624 625 #if __cplusplus >= 201103L 626 /** 627 * @brief Attempts to insert a list of std::pairs into the %map. 628 * @param __list A std::initializer_list<value_type> of pairs to be 629 * inserted. 630 * 631 * Complexity similar to that of the range constructor. 632 */ 633 void 634 insert(std::initializer_list<value_type> __list) 635 { insert(__list.begin(), __list.end()); } 636 #endif 637 638 /** 639 * @brief Attempts to insert a std::pair into the %map. 640 * @param __position An iterator that serves as a hint as to where the 641 * pair should be inserted. 642 * @param __x Pair to be inserted (see std::make_pair for easy creation 643 * of pairs). 644 * @return An iterator that points to the element with key of 645 * @a __x (may or may not be the %pair passed in). 646 * 647 648 * This function is not concerned about whether the insertion 649 * took place, and thus does not return a boolean like the 650 * single-argument insert() does. Note that the first 651 * parameter is only a hint and can potentially improve the 652 * performance of the insertion process. A bad hint would 653 * cause no gains in efficiency. 654 * 655 * See 656 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 657 * for more on @a hinting. 658 * 659 * Insertion requires logarithmic time (if the hint is not taken). 660 */ 661 iterator 662 #if __cplusplus >= 201103L 663 insert(const_iterator __position, const value_type& __x) 664 #else 665 insert(iterator __position, const value_type& __x) 666 #endif 667 { return _M_t._M_insert_unique_(__position, __x); } 668 669 #if __cplusplus >= 201103L 670 template<typename _Pair, typename = typename 671 std::enable_if<std::is_constructible<value_type, 672 _Pair&&>::value>::type> 673 iterator 674 insert(const_iterator __position, _Pair&& __x) 675 { return _M_t._M_insert_unique_(__position, 676 std::forward<_Pair>(__x)); } 677 #endif 678 679 /** 680 * @brief Template function that attempts to insert a range of elements. 681 * @param __first Iterator pointing to the start of the range to be 682 * inserted. 683 * @param __last Iterator pointing to the end of the range. 684 * 685 * Complexity similar to that of the range constructor. 686 */ 687 template<typename _InputIterator> 688 void 689 insert(_InputIterator __first, _InputIterator __last) 690 { _M_t._M_insert_unique(__first, __last); } 691 692 #if __cplusplus >= 201103L 693 // _GLIBCXX_RESOLVE_LIB_DEFECTS 694 // DR 130. Associative erase should return an iterator. 695 /** 696 * @brief Erases an element from a %map. 697 * @param __position An iterator pointing to the element to be erased. 698 * @return An iterator pointing to the element immediately following 699 * @a position prior to the element being erased. If no such 700 * element exists, end() is returned. 701 * 702 * This function erases an element, pointed to by the given 703 * iterator, from a %map. Note that this function only erases 704 * the element, and that if the element is itself a pointer, 705 * the pointed-to memory is not touched in any way. Managing 706 * the pointer is the user's responsibility. 707 */ 708 iterator 709 erase(const_iterator __position) 710 { return _M_t.erase(__position); } 711 712 // LWG 2059 713 _GLIBCXX_ABI_TAG_CXX11 714 iterator 715 erase(iterator __position) 716 { return _M_t.erase(__position); } 717 #else 718 /** 719 * @brief Erases an element from a %map. 720 * @param __position An iterator pointing to the element to be erased. 721 * 722 * This function erases an element, pointed to by the given 723 * iterator, from a %map. Note that this function only erases 724 * the element, and that if the element is itself a pointer, 725 * the pointed-to memory is not touched in any way. Managing 726 * the pointer is the user's responsibility. 727 */ 728 void 729 erase(iterator __position) 730 { _M_t.erase(__position); } 731 #endif 732 733 /** 734 * @brief Erases elements according to the provided key. 735 * @param __x Key of element to be erased. 736 * @return The number of elements erased. 737 * 738 * This function erases all the elements located by the given key from 739 * a %map. 740 * Note that this function only erases the element, and that if 741 * the element is itself a pointer, the pointed-to memory is not touched 742 * in any way. Managing the pointer is the user's responsibility. 743 */ 744 size_type 745 erase(const key_type& __x) 746 { return _M_t.erase(__x); } 747 748 #if __cplusplus >= 201103L 749 // _GLIBCXX_RESOLVE_LIB_DEFECTS 750 // DR 130. Associative erase should return an iterator. 751 /** 752 * @brief Erases a [first,last) range of elements from a %map. 753 * @param __first Iterator pointing to the start of the range to be 754 * erased. 755 * @param __last Iterator pointing to the end of the range to 756 * be erased. 757 * @return The iterator @a __last. 758 * 759 * This function erases a sequence of elements from a %map. 760 * Note that this function only erases the element, and that if 761 * the element is itself a pointer, the pointed-to memory is not touched 762 * in any way. Managing the pointer is the user's responsibility. 763 */ 764 iterator 765 erase(const_iterator __first, const_iterator __last) 766 { return _M_t.erase(__first, __last); } 767 #else 768 /** 769 * @brief Erases a [__first,__last) range of elements from a %map. 770 * @param __first Iterator pointing to the start of the range to be 771 * erased. 772 * @param __last Iterator pointing to the end of the range to 773 * be erased. 774 * 775 * This function erases a sequence of elements from a %map. 776 * Note that this function only erases the element, and that if 777 * the element is itself a pointer, the pointed-to memory is not touched 778 * in any way. Managing the pointer is the user's responsibility. 779 */ 780 void 781 erase(iterator __first, iterator __last) 782 { _M_t.erase(__first, __last); } 783 #endif 784 785 /** 786 * @brief Swaps data with another %map. 787 * @param __x A %map of the same element and allocator types. 788 * 789 * This exchanges the elements between two maps in constant 790 * time. (It is only swapping a pointer, an integer, and an 791 * instance of the @c Compare type (which itself is often 792 * stateless and empty), so it should be quite fast.) Note 793 * that the global std::swap() function is specialized such 794 * that std::swap(m1,m2) will feed to this function. 795 */ 796 void 797 swap(map& __x) 798 #if __cplusplus >= 201103L 799 noexcept(_Alloc_traits::_S_nothrow_swap()) 800 #endif 801 { _M_t.swap(__x._M_t); } 802 803 /** 804 * Erases all elements in a %map. Note that this function only 805 * erases the elements, and that if the elements themselves are 806 * pointers, the pointed-to memory is not touched in any way. 807 * Managing the pointer is the user's responsibility. 808 */ 809 void 810 clear() _GLIBCXX_NOEXCEPT 811 { _M_t.clear(); } 812 813 // observers 814 /** 815 * Returns the key comparison object out of which the %map was 816 * constructed. 817 */ 818 key_compare 819 key_comp() const 820 { return _M_t.key_comp(); } 821 822 /** 823 * Returns a value comparison object, built from the key comparison 824 * object out of which the %map was constructed. 825 */ 826 value_compare 827 value_comp() const 828 { return value_compare(_M_t.key_comp()); } 829 830 // [23.3.1.3] map operations 831 832 //@{ 833 /** 834 * @brief Tries to locate an element in a %map. 835 * @param __x Key of (key, value) %pair to be located. 836 * @return Iterator pointing to sought-after element, or end() if not 837 * found. 838 * 839 * This function takes a key and tries to locate the element with which 840 * the key matches. If successful the function returns an iterator 841 * pointing to the sought after %pair. If unsuccessful it returns the 842 * past-the-end ( @c end() ) iterator. 843 */ 844 845 iterator 846 find(const key_type& __x) 847 { return _M_t.find(__x); } 848 849 #if __cplusplus > 201103L 850 template<typename _Kt> 851 auto 852 find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x)) 853 { return _M_t._M_find_tr(__x); } 854 #endif 855 //@} 856 857 //@{ 858 /** 859 * @brief Tries to locate an element in a %map. 860 * @param __x Key of (key, value) %pair to be located. 861 * @return Read-only (constant) iterator pointing to sought-after 862 * element, or end() if not found. 863 * 864 * This function takes a key and tries to locate the element with which 865 * the key matches. If successful the function returns a constant 866 * iterator pointing to the sought after %pair. If unsuccessful it 867 * returns the past-the-end ( @c end() ) iterator. 868 */ 869 870 const_iterator 871 find(const key_type& __x) const 872 { return _M_t.find(__x); } 873 874 #if __cplusplus > 201103L 875 template<typename _Kt> 876 auto 877 find(const _Kt& __x) const -> decltype(_M_t._M_find_tr(__x)) 878 { return _M_t._M_find_tr(__x); } 879 #endif 880 //@} 881 882 //@{ 883 /** 884 * @brief Finds the number of elements with given key. 885 * @param __x Key of (key, value) pairs to be located. 886 * @return Number of elements with specified key. 887 * 888 * This function only makes sense for multimaps; for map the result will 889 * either be 0 (not present) or 1 (present). 890 */ 891 size_type 892 count(const key_type& __x) const 893 { return _M_t.find(__x) == _M_t.end() ? 0 : 1; } 894 895 #if __cplusplus > 201103L 896 template<typename _Kt> 897 auto 898 count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x)) 899 { return _M_t._M_count_tr(__x); } 900 #endif 901 //@} 902 903 //@{ 904 /** 905 * @brief Finds the beginning of a subsequence matching given key. 906 * @param __x Key of (key, value) pair to be located. 907 * @return Iterator pointing to first element equal to or greater 908 * than key, or end(). 909 * 910 * This function returns the first element of a subsequence of elements 911 * that matches the given key. If unsuccessful it returns an iterator 912 * pointing to the first element that has a greater value than given key 913 * or end() if no such element exists. 914 */ 915 iterator 916 lower_bound(const key_type& __x) 917 { return _M_t.lower_bound(__x); } 918 919 #if __cplusplus > 201103L 920 template<typename _Kt> 921 auto 922 lower_bound(const _Kt& __x) 923 -> decltype(iterator(_M_t._M_lower_bound_tr(__x))) 924 { return iterator(_M_t._M_lower_bound_tr(__x)); } 925 #endif 926 //@} 927 928 //@{ 929 /** 930 * @brief Finds the beginning of a subsequence matching given key. 931 * @param __x Key of (key, value) pair to be located. 932 * @return Read-only (constant) iterator pointing to first element 933 * equal to or greater than key, or end(). 934 * 935 * This function returns the first element of a subsequence of elements 936 * that matches the given key. If unsuccessful it returns an iterator 937 * pointing to the first element that has a greater value than given key 938 * or end() if no such element exists. 939 */ 940 const_iterator 941 lower_bound(const key_type& __x) const 942 { return _M_t.lower_bound(__x); } 943 944 #if __cplusplus > 201103L 945 template<typename _Kt> 946 auto 947 lower_bound(const _Kt& __x) const 948 -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x))) 949 { return const_iterator(_M_t._M_lower_bound_tr(__x)); } 950 #endif 951 //@} 952 953 //@{ 954 /** 955 * @brief Finds the end of a subsequence matching given key. 956 * @param __x Key of (key, value) pair to be located. 957 * @return Iterator pointing to the first element 958 * greater than key, or end(). 959 */ 960 iterator 961 upper_bound(const key_type& __x) 962 { return _M_t.upper_bound(__x); } 963 964 #if __cplusplus > 201103L 965 template<typename _Kt> 966 auto 967 upper_bound(const _Kt& __x) 968 -> decltype(iterator(_M_t._M_upper_bound_tr(__x))) 969 { return iterator(_M_t._M_upper_bound_tr(__x)); } 970 #endif 971 //@} 972 973 //@{ 974 /** 975 * @brief Finds the end of a subsequence matching given key. 976 * @param __x Key of (key, value) pair to be located. 977 * @return Read-only (constant) iterator pointing to first iterator 978 * greater than key, or end(). 979 */ 980 const_iterator 981 upper_bound(const key_type& __x) const 982 { return _M_t.upper_bound(__x); } 983 984 #if __cplusplus > 201103L 985 template<typename _Kt> 986 auto 987 upper_bound(const _Kt& __x) const 988 -> decltype(const_iterator(_M_t._M_upper_bound_tr(__x))) 989 { return const_iterator(_M_t._M_upper_bound_tr(__x)); } 990 #endif 991 //@} 992 993 //@{ 994 /** 995 * @brief Finds a subsequence matching given key. 996 * @param __x Key of (key, value) pairs to be located. 997 * @return Pair of iterators that possibly points to the subsequence 998 * matching given key. 999 * 1000 * This function is equivalent to 1001 * @code 1002 * std::make_pair(c.lower_bound(val), 1003 * c.upper_bound(val)) 1004 * @endcode 1005 * (but is faster than making the calls separately). 1006 * 1007 * This function probably only makes sense for multimaps. 1008 */ 1009 std::pair<iterator, iterator> 1010 equal_range(const key_type& __x) 1011 { return _M_t.equal_range(__x); } 1012 1013 #if __cplusplus > 201103L 1014 template<typename _Kt> 1015 auto 1016 equal_range(const _Kt& __x) 1017 -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x))) 1018 { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); } 1019 #endif 1020 //@} 1021 1022 //@{ 1023 /** 1024 * @brief Finds a subsequence matching given key. 1025 * @param __x Key of (key, value) pairs to be located. 1026 * @return Pair of read-only (constant) iterators that possibly points 1027 * to the subsequence matching given key. 1028 * 1029 * This function is equivalent to 1030 * @code 1031 * std::make_pair(c.lower_bound(val), 1032 * c.upper_bound(val)) 1033 * @endcode 1034 * (but is faster than making the calls separately). 1035 * 1036 * This function probably only makes sense for multimaps. 1037 */ 1038 std::pair<const_iterator, const_iterator> 1039 equal_range(const key_type& __x) const 1040 { return _M_t.equal_range(__x); } 1041 1042 #if __cplusplus > 201103L 1043 template<typename _Kt> 1044 auto 1045 equal_range(const _Kt& __x) const 1046 -> decltype(pair<const_iterator, const_iterator>( 1047 _M_t._M_equal_range_tr(__x))) 1048 { 1049 return pair<const_iterator, const_iterator>( 1050 _M_t._M_equal_range_tr(__x)); 1051 } 1052 #endif 1053 //@} 1054 1055 template<typename _K1, typename _T1, typename _C1, typename _A1> 1056 friend bool 1057 operator==(const map<_K1, _T1, _C1, _A1>&, 1058 const map<_K1, _T1, _C1, _A1>&); 1059 1060 template<typename _K1, typename _T1, typename _C1, typename _A1> 1061 friend bool 1062 operator<(const map<_K1, _T1, _C1, _A1>&, 1063 const map<_K1, _T1, _C1, _A1>&); 1064 }; 1065 1066 /** 1067 * @brief Map equality comparison. 1068 * @param __x A %map. 1069 * @param __y A %map of the same type as @a x. 1070 * @return True iff the size and elements of the maps are equal. 1071 * 1072 * This is an equivalence relation. It is linear in the size of the 1073 * maps. Maps are considered equivalent if their sizes are equal, 1074 * and if corresponding elements compare equal. 1075 */ 1076 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 1077 inline bool 1078 operator==(const map<_Key, _Tp, _Compare, _Alloc>& __x, 1079 const map<_Key, _Tp, _Compare, _Alloc>& __y) 1080 { return __x._M_t == __y._M_t; } 1081 1082 /** 1083 * @brief Map ordering relation. 1084 * @param __x A %map. 1085 * @param __y A %map of the same type as @a x. 1086 * @return True iff @a x is lexicographically less than @a y. 1087 * 1088 * This is a total ordering relation. It is linear in the size of the 1089 * maps. The elements must be comparable with @c <. 1090 * 1091 * See std::lexicographical_compare() for how the determination is made. 1092 */ 1093 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 1094 inline bool 1095 operator<(const map<_Key, _Tp, _Compare, _Alloc>& __x, 1096 const map<_Key, _Tp, _Compare, _Alloc>& __y) 1097 { return __x._M_t < __y._M_t; } 1098 1099 /// Based on operator== 1100 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 1101 inline bool 1102 operator!=(const map<_Key, _Tp, _Compare, _Alloc>& __x, 1103 const map<_Key, _Tp, _Compare, _Alloc>& __y) 1104 { return !(__x == __y); } 1105 1106 /// Based on operator< 1107 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 1108 inline bool 1109 operator>(const map<_Key, _Tp, _Compare, _Alloc>& __x, 1110 const map<_Key, _Tp, _Compare, _Alloc>& __y) 1111 { return __y < __x; } 1112 1113 /// Based on operator< 1114 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 1115 inline bool 1116 operator<=(const map<_Key, _Tp, _Compare, _Alloc>& __x, 1117 const map<_Key, _Tp, _Compare, _Alloc>& __y) 1118 { return !(__y < __x); } 1119 1120 /// Based on operator< 1121 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 1122 inline bool 1123 operator>=(const map<_Key, _Tp, _Compare, _Alloc>& __x, 1124 const map<_Key, _Tp, _Compare, _Alloc>& __y) 1125 { return !(__x < __y); } 1126 1127 /// See std::map::swap(). 1128 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 1129 inline void 1130 swap(map<_Key, _Tp, _Compare, _Alloc>& __x, 1131 map<_Key, _Tp, _Compare, _Alloc>& __y) 1132 { __x.swap(__y); } 1133 1134 _GLIBCXX_END_NAMESPACE_CONTAINER 1135 } // namespace std 1136 1137 #endif /* _STL_MAP_H */ 1138