1 // Map implementation -*- C++ -*- 2 3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 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 8 // terms of the GNU General Public License as published by the 9 // Free Software Foundation; either version 3, or (at your option) 10 // any later version. 11 12 // This library is distributed in the hope that it will be useful, 13 // but WITHOUT ANY WARRANTY; without even the implied warranty of 14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 // GNU 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 /* 27 * 28 * Copyright (c) 1994 29 * Hewlett-Packard Company 30 * 31 * Permission to use, copy, modify, distribute and sell this software 32 * and its documentation for any purpose is hereby granted without fee, 33 * provided that the above copyright notice appear in all copies and 34 * that both that copyright notice and this permission notice appear 35 * in supporting documentation. Hewlett-Packard Company makes no 36 * representations about the suitability of this software for any 37 * purpose. It is provided "as is" without express or implied warranty. 38 * 39 * 40 * Copyright (c) 1996,1997 41 * Silicon Graphics Computer Systems, Inc. 42 * 43 * Permission to use, copy, modify, distribute and sell this software 44 * and its documentation for any purpose is hereby granted without fee, 45 * provided that the above copyright notice appear in all copies and 46 * that both that copyright notice and this permission notice appear 47 * in supporting documentation. Silicon Graphics makes no 48 * representations about the suitability of this software for any 49 * purpose. It is provided "as is" without express or implied warranty. 50 */ 51 52 /** @file stl_map.h 53 * This is an internal header file, included by other library headers. 54 * You should not attempt to use it directly. 55 */ 56 57 #ifndef _STL_MAP_H 58 #define _STL_MAP_H 1 59 60 #include <bits/functexcept.h> 61 #include <bits/concept_check.h> 62 #include <initializer_list> 63 64 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) 65 66 /** 67 * @brief A standard container made up of (key,value) pairs, which can be 68 * retrieved based on a key, in logarithmic time. 69 * 70 * @ingroup associative_containers 71 * 72 * Meets the requirements of a <a href="tables.html#65">container</a>, a 73 * <a href="tables.html#66">reversible container</a>, and an 74 * <a href="tables.html#69">associative container</a> (using unique keys). 75 * For a @c map<Key,T> the key_type is Key, the mapped_type is T, and the 76 * value_type is std::pair<const Key,T>. 77 * 78 * Maps support bidirectional iterators. 79 * 80 * The private tree data is declared exactly the same way for map and 81 * multimap; the distinction is made entirely in how the tree functions are 82 * called (*_unique versus *_equal, same as the standard). 83 */ 84 template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>, 85 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 86 class map 87 { 88 public: 89 typedef _Key key_type; 90 typedef _Tp mapped_type; 91 typedef std::pair<const _Key, _Tp> value_type; 92 typedef _Compare key_compare; 93 typedef _Alloc allocator_type; 94 95 private: 96 // concept requirements 97 typedef typename _Alloc::value_type _Alloc_value_type; 98 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 99 __glibcxx_class_requires4(_Compare, bool, _Key, _Key, 100 _BinaryFunctionConcept) 101 __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept) 102 103 public: 104 class value_compare 105 : public std::binary_function<value_type, value_type, bool> 106 { 107 friend class map<_Key, _Tp, _Compare, _Alloc>; 108 protected: 109 _Compare comp; 110 111 value_compare(_Compare __c) 112 : comp(__c) { } 113 114 public: 115 bool operator()(const value_type& __x, const value_type& __y) const 116 { return comp(__x.first, __y.first); } 117 }; 118 119 private: 120 /// This turns a red-black tree into a [multi]map. 121 typedef typename _Alloc::template rebind<value_type>::other 122 _Pair_alloc_type; 123 124 typedef _Rb_tree<key_type, value_type, _Select1st<value_type>, 125 key_compare, _Pair_alloc_type> _Rep_type; 126 127 /// The actual tree structure. 128 _Rep_type _M_t; 129 130 public: 131 // many of these are specified differently in ISO, but the following are 132 // "functionally equivalent" 133 typedef typename _Pair_alloc_type::pointer pointer; 134 typedef typename _Pair_alloc_type::const_pointer const_pointer; 135 typedef typename _Pair_alloc_type::reference reference; 136 typedef typename _Pair_alloc_type::const_reference const_reference; 137 typedef typename _Rep_type::iterator iterator; 138 typedef typename _Rep_type::const_iterator const_iterator; 139 typedef typename _Rep_type::size_type size_type; 140 typedef typename _Rep_type::difference_type difference_type; 141 typedef typename _Rep_type::reverse_iterator reverse_iterator; 142 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 143 144 // [23.3.1.1] construct/copy/destroy 145 // (get_allocator() is normally listed in this section, but seems to have 146 // been accidentally omitted in the printed standard) 147 /** 148 * @brief Default constructor creates no elements. 149 */ 150 map() 151 : _M_t() { } 152 153 /** 154 * @brief Creates a %map with no elements. 155 * @param comp A comparison object. 156 * @param a An allocator object. 157 */ 158 explicit 159 map(const _Compare& __comp, 160 const allocator_type& __a = allocator_type()) 161 : _M_t(__comp, __a) { } 162 163 /** 164 * @brief %Map copy constructor. 165 * @param x A %map of identical element and allocator types. 166 * 167 * The newly-created %map uses a copy of the allocation object 168 * used by @a x. 169 */ 170 map(const map& __x) 171 : _M_t(__x._M_t) { } 172 173 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 174 /** 175 * @brief %Map move constructor. 176 * @param x A %map of identical element and allocator types. 177 * 178 * The newly-created %map contains the exact contents of @a x. 179 * The contents of @a x are a valid, but unspecified %map. 180 */ 181 map(map&& __x) 182 : _M_t(std::forward<_Rep_type>(__x._M_t)) { } 183 184 /** 185 * @brief Builds a %map from an initializer_list. 186 * @param l An initializer_list. 187 * @param comp A comparison object. 188 * @param a An allocator object. 189 * 190 * Create a %map consisting of copies of the elements in the 191 * initializer_list @a l. 192 * This is linear in N if the range is already sorted, and NlogN 193 * otherwise (where N is @a l.size()). 194 */ 195 map(initializer_list<value_type> __l, 196 const _Compare& __c = _Compare(), 197 const allocator_type& __a = allocator_type()) 198 : _M_t(__c, __a) 199 { _M_t._M_insert_unique(__l.begin(), __l.end()); } 200 #endif 201 202 /** 203 * @brief Builds a %map from a range. 204 * @param first An input iterator. 205 * @param last An input iterator. 206 * 207 * Create a %map consisting of copies of the elements from [first,last). 208 * This is linear in N if the range is already sorted, and NlogN 209 * otherwise (where N is distance(first,last)). 210 */ 211 template<typename _InputIterator> 212 map(_InputIterator __first, _InputIterator __last) 213 : _M_t() 214 { _M_t._M_insert_unique(__first, __last); } 215 216 /** 217 * @brief Builds a %map from a range. 218 * @param first An input iterator. 219 * @param last An input iterator. 220 * @param comp A comparison functor. 221 * @param a An allocator object. 222 * 223 * Create a %map consisting of copies of the elements from [first,last). 224 * This is linear in N if the range is already sorted, and NlogN 225 * otherwise (where N is distance(first,last)). 226 */ 227 template<typename _InputIterator> 228 map(_InputIterator __first, _InputIterator __last, 229 const _Compare& __comp, 230 const allocator_type& __a = allocator_type()) 231 : _M_t(__comp, __a) 232 { _M_t._M_insert_unique(__first, __last); } 233 234 // FIXME There is no dtor declared, but we should have something 235 // generated by Doxygen. I don't know what tags to add to this 236 // paragraph to make that happen: 237 /** 238 * The dtor only erases the elements, and note that if the elements 239 * themselves are pointers, the pointed-to memory is not touched in any 240 * way. Managing the pointer is the user's responsibility. 241 */ 242 243 /** 244 * @brief %Map assignment operator. 245 * @param x A %map of identical element and allocator types. 246 * 247 * All the elements of @a x are copied, but unlike the copy constructor, 248 * the allocator object is not copied. 249 */ 250 map& 251 operator=(const map& __x) 252 { 253 _M_t = __x._M_t; 254 return *this; 255 } 256 257 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 258 /** 259 * @brief %Map move assignment operator. 260 * @param x A %map of identical element and allocator types. 261 * 262 * The contents of @a x are moved into this map (without copying). 263 * @a x is a valid, but unspecified %map. 264 */ 265 map& 266 operator=(map&& __x) 267 { 268 // NB: DR 675. 269 this->clear(); 270 this->swap(__x); 271 return *this; 272 } 273 274 /** 275 * @brief %Map list assignment operator. 276 * @param l An initializer_list. 277 * 278 * This function fills a %map with copies of the elements in the 279 * initializer list @a l. 280 * 281 * Note that the assignment completely changes the %map and 282 * that the resulting %map's size is the same as the number 283 * of elements assigned. Old data may be lost. 284 */ 285 map& 286 operator=(initializer_list<value_type> __l) 287 { 288 this->clear(); 289 this->insert(__l.begin(), __l.end()); 290 return *this; 291 } 292 #endif 293 294 /// Get a copy of the memory allocation object. 295 allocator_type 296 get_allocator() const 297 { return _M_t.get_allocator(); } 298 299 // iterators 300 /** 301 * Returns a read/write iterator that points to the first pair in the 302 * %map. 303 * Iteration is done in ascending order according to the keys. 304 */ 305 iterator 306 begin() 307 { return _M_t.begin(); } 308 309 /** 310 * Returns a read-only (constant) iterator that points to the first pair 311 * in the %map. Iteration is done in ascending order according to the 312 * keys. 313 */ 314 const_iterator 315 begin() const 316 { return _M_t.begin(); } 317 318 /** 319 * Returns a read/write iterator that points one past the last 320 * pair in the %map. Iteration is done in ascending order 321 * according to the keys. 322 */ 323 iterator 324 end() 325 { return _M_t.end(); } 326 327 /** 328 * Returns a read-only (constant) iterator that points one past the last 329 * pair in the %map. Iteration is done in ascending order according to 330 * the keys. 331 */ 332 const_iterator 333 end() const 334 { return _M_t.end(); } 335 336 /** 337 * Returns a read/write reverse iterator that points to the last pair in 338 * the %map. Iteration is done in descending order according to the 339 * keys. 340 */ 341 reverse_iterator 342 rbegin() 343 { return _M_t.rbegin(); } 344 345 /** 346 * Returns a read-only (constant) reverse iterator that points to the 347 * last pair in the %map. Iteration is done in descending order 348 * according to the keys. 349 */ 350 const_reverse_iterator 351 rbegin() const 352 { return _M_t.rbegin(); } 353 354 /** 355 * Returns a read/write reverse iterator that points to one before the 356 * first pair in the %map. Iteration is done in descending order 357 * according to the keys. 358 */ 359 reverse_iterator 360 rend() 361 { return _M_t.rend(); } 362 363 /** 364 * Returns a read-only (constant) reverse iterator that points to one 365 * before the first pair in the %map. Iteration is done in descending 366 * order according to the keys. 367 */ 368 const_reverse_iterator 369 rend() const 370 { return _M_t.rend(); } 371 372 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 373 /** 374 * Returns a read-only (constant) iterator that points to the first pair 375 * in the %map. Iteration is done in ascending order according to the 376 * keys. 377 */ 378 const_iterator 379 cbegin() const 380 { return _M_t.begin(); } 381 382 /** 383 * Returns a read-only (constant) iterator that points one past the last 384 * pair in the %map. Iteration is done in ascending order according to 385 * the keys. 386 */ 387 const_iterator 388 cend() const 389 { return _M_t.end(); } 390 391 /** 392 * Returns a read-only (constant) reverse iterator that points to the 393 * last pair in the %map. Iteration is done in descending order 394 * according to the keys. 395 */ 396 const_reverse_iterator 397 crbegin() const 398 { return _M_t.rbegin(); } 399 400 /** 401 * Returns a read-only (constant) reverse iterator that points to one 402 * before the first pair in the %map. Iteration is done in descending 403 * order according to the keys. 404 */ 405 const_reverse_iterator 406 crend() const 407 { return _M_t.rend(); } 408 #endif 409 410 // capacity 411 /** Returns true if the %map is empty. (Thus begin() would equal 412 * end().) 413 */ 414 bool 415 empty() const 416 { return _M_t.empty(); } 417 418 /** Returns the size of the %map. */ 419 size_type 420 size() const 421 { return _M_t.size(); } 422 423 /** Returns the maximum size of the %map. */ 424 size_type 425 max_size() const 426 { return _M_t.max_size(); } 427 428 // [23.3.1.2] element access 429 /** 430 * @brief Subscript ( @c [] ) access to %map data. 431 * @param k The key for which data should be retrieved. 432 * @return A reference to the data of the (key,data) %pair. 433 * 434 * Allows for easy lookup with the subscript ( @c [] ) 435 * operator. Returns data associated with the key specified in 436 * subscript. If the key does not exist, a pair with that key 437 * is created using default values, which is then returned. 438 * 439 * Lookup requires logarithmic time. 440 */ 441 mapped_type& 442 operator[](const key_type& __k) 443 { 444 // concept requirements 445 __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>) 446 447 iterator __i = lower_bound(__k); 448 // __i->first is greater than or equivalent to __k. 449 if (__i == end() || key_comp()(__k, (*__i).first)) 450 __i = insert(__i, value_type(__k, mapped_type())); 451 return (*__i).second; 452 } 453 454 // _GLIBCXX_RESOLVE_LIB_DEFECTS 455 // DR 464. Suggestion for new member functions in standard containers. 456 /** 457 * @brief Access to %map data. 458 * @param k The key for which data should be retrieved. 459 * @return A reference to the data whose key is equivalent to @a k, if 460 * such a data is present in the %map. 461 * @throw std::out_of_range If no such data is present. 462 */ 463 mapped_type& 464 at(const key_type& __k) 465 { 466 iterator __i = lower_bound(__k); 467 if (__i == end() || key_comp()(__k, (*__i).first)) 468 __throw_out_of_range(__N("map::at")); 469 return (*__i).second; 470 } 471 472 const mapped_type& 473 at(const key_type& __k) const 474 { 475 const_iterator __i = lower_bound(__k); 476 if (__i == end() || key_comp()(__k, (*__i).first)) 477 __throw_out_of_range(__N("map::at")); 478 return (*__i).second; 479 } 480 481 // modifiers 482 /** 483 * @brief Attempts to insert a std::pair into the %map. 484 485 * @param x Pair to be inserted (see std::make_pair for easy creation 486 * of pairs). 487 488 * @return A pair, of which the first element is an iterator that 489 * points to the possibly inserted pair, and the second is 490 * a bool that is true if the pair was actually inserted. 491 * 492 * This function attempts to insert a (key, value) %pair into the %map. 493 * A %map relies on unique keys and thus a %pair is only inserted if its 494 * first element (the key) is not already present in the %map. 495 * 496 * Insertion requires logarithmic time. 497 */ 498 std::pair<iterator, bool> 499 insert(const value_type& __x) 500 { return _M_t._M_insert_unique(__x); } 501 502 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 503 /** 504 * @brief Attempts to insert a list of std::pairs into the %map. 505 * @param list A std::initializer_list<value_type> of pairs to be 506 * inserted. 507 * 508 * Complexity similar to that of the range constructor. 509 */ 510 void 511 insert(std::initializer_list<value_type> __list) 512 { insert (__list.begin(), __list.end()); } 513 #endif 514 515 /** 516 * @brief Attempts to insert a std::pair into the %map. 517 * @param position An iterator that serves as a hint as to where the 518 * pair should be inserted. 519 * @param x Pair to be inserted (see std::make_pair for easy creation 520 * of pairs). 521 * @return An iterator that points to the element with key of @a x (may 522 * or may not be the %pair passed in). 523 * 524 525 * This function is not concerned about whether the insertion 526 * took place, and thus does not return a boolean like the 527 * single-argument insert() does. Note that the first 528 * parameter is only a hint and can potentially improve the 529 * performance of the insertion process. A bad hint would 530 * cause no gains in efficiency. 531 * 532 * See 533 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html 534 * for more on "hinting". 535 * 536 * Insertion requires logarithmic time (if the hint is not taken). 537 */ 538 iterator 539 insert(iterator __position, const value_type& __x) 540 { return _M_t._M_insert_unique_(__position, __x); } 541 542 /** 543 * @brief Template function that attempts to insert a range of elements. 544 * @param first Iterator pointing to the start of the range to be 545 * inserted. 546 * @param last Iterator pointing to the end of the range. 547 * 548 * Complexity similar to that of the range constructor. 549 */ 550 template<typename _InputIterator> 551 void 552 insert(_InputIterator __first, _InputIterator __last) 553 { _M_t._M_insert_unique(__first, __last); } 554 555 /** 556 * @brief Erases an element from a %map. 557 * @param position An iterator pointing to the element to be erased. 558 * 559 * This function erases an element, pointed to by the given 560 * iterator, from a %map. Note that this function only erases 561 * the element, and that if the element is itself a pointer, 562 * the pointed-to memory is not touched in any way. Managing 563 * the pointer is the user's responsibility. 564 */ 565 void 566 erase(iterator __position) 567 { _M_t.erase(__position); } 568 569 /** 570 * @brief Erases elements according to the provided key. 571 * @param x Key of element to be erased. 572 * @return The number of elements erased. 573 * 574 * This function erases all the elements located by the given key from 575 * a %map. 576 * Note that this function only erases the element, and that if 577 * the element is itself a pointer, the pointed-to memory is not touched 578 * in any way. Managing the pointer is the user's responsibility. 579 */ 580 size_type 581 erase(const key_type& __x) 582 { return _M_t.erase(__x); } 583 584 /** 585 * @brief Erases a [first,last) range of elements from a %map. 586 * @param first Iterator pointing to the start of the range to be 587 * erased. 588 * @param last Iterator pointing to the end of the range to be erased. 589 * 590 * This function erases a sequence of elements from a %map. 591 * Note that this function only erases the element, and that if 592 * the element is itself a pointer, the pointed-to memory is not touched 593 * in any way. Managing the pointer is the user's responsibility. 594 */ 595 void 596 erase(iterator __first, iterator __last) 597 { _M_t.erase(__first, __last); } 598 599 /** 600 * @brief Swaps data with another %map. 601 * @param x A %map of the same element and allocator types. 602 * 603 * This exchanges the elements between two maps in constant 604 * time. (It is only swapping a pointer, an integer, and an 605 * instance of the @c Compare type (which itself is often 606 * stateless and empty), so it should be quite fast.) Note 607 * that the global std::swap() function is specialized such 608 * that std::swap(m1,m2) will feed to this function. 609 */ 610 void 611 swap(map& __x) 612 { _M_t.swap(__x._M_t); } 613 614 /** 615 * Erases all elements in a %map. Note that this function only 616 * erases the elements, and that if the elements themselves are 617 * pointers, the pointed-to memory is not touched in any way. 618 * Managing the pointer is the user's responsibility. 619 */ 620 void 621 clear() 622 { _M_t.clear(); } 623 624 // observers 625 /** 626 * Returns the key comparison object out of which the %map was 627 * constructed. 628 */ 629 key_compare 630 key_comp() const 631 { return _M_t.key_comp(); } 632 633 /** 634 * Returns a value comparison object, built from the key comparison 635 * object out of which the %map was constructed. 636 */ 637 value_compare 638 value_comp() const 639 { return value_compare(_M_t.key_comp()); } 640 641 // [23.3.1.3] map operations 642 /** 643 * @brief Tries to locate an element in a %map. 644 * @param x Key of (key, value) %pair to be located. 645 * @return Iterator pointing to sought-after element, or end() if not 646 * found. 647 * 648 * This function takes a key and tries to locate the element with which 649 * the key matches. If successful the function returns an iterator 650 * pointing to the sought after %pair. If unsuccessful it returns the 651 * past-the-end ( @c end() ) iterator. 652 */ 653 iterator 654 find(const key_type& __x) 655 { return _M_t.find(__x); } 656 657 /** 658 * @brief Tries to locate an element in a %map. 659 * @param x Key of (key, value) %pair to be located. 660 * @return Read-only (constant) iterator pointing to sought-after 661 * element, or end() if not found. 662 * 663 * This function takes a key and tries to locate the element with which 664 * the key matches. If successful the function returns a constant 665 * iterator pointing to the sought after %pair. If unsuccessful it 666 * returns the past-the-end ( @c end() ) iterator. 667 */ 668 const_iterator 669 find(const key_type& __x) const 670 { return _M_t.find(__x); } 671 672 /** 673 * @brief Finds the number of elements with given key. 674 * @param x Key of (key, value) pairs to be located. 675 * @return Number of elements with specified key. 676 * 677 * This function only makes sense for multimaps; for map the result will 678 * either be 0 (not present) or 1 (present). 679 */ 680 size_type 681 count(const key_type& __x) const 682 { return _M_t.find(__x) == _M_t.end() ? 0 : 1; } 683 684 /** 685 * @brief Finds the beginning of a subsequence matching given key. 686 * @param x Key of (key, value) pair to be located. 687 * @return Iterator pointing to first element equal to or greater 688 * than key, or end(). 689 * 690 * This function returns the first element of a subsequence of elements 691 * that matches the given key. If unsuccessful it returns an iterator 692 * pointing to the first element that has a greater value than given key 693 * or end() if no such element exists. 694 */ 695 iterator 696 lower_bound(const key_type& __x) 697 { return _M_t.lower_bound(__x); } 698 699 /** 700 * @brief Finds the beginning of a subsequence matching given key. 701 * @param x Key of (key, value) pair to be located. 702 * @return Read-only (constant) iterator pointing to first element 703 * equal to or greater than key, or end(). 704 * 705 * This function returns the first element of a subsequence of elements 706 * that matches the given key. If unsuccessful it returns an iterator 707 * pointing to the first element that has a greater value than given key 708 * or end() if no such element exists. 709 */ 710 const_iterator 711 lower_bound(const key_type& __x) const 712 { return _M_t.lower_bound(__x); } 713 714 /** 715 * @brief Finds the end of a subsequence matching given key. 716 * @param x Key of (key, value) pair to be located. 717 * @return Iterator pointing to the first element 718 * greater than key, or end(). 719 */ 720 iterator 721 upper_bound(const key_type& __x) 722 { return _M_t.upper_bound(__x); } 723 724 /** 725 * @brief Finds the end of a subsequence matching given key. 726 * @param x Key of (key, value) pair to be located. 727 * @return Read-only (constant) iterator pointing to first iterator 728 * greater than key, or end(). 729 */ 730 const_iterator 731 upper_bound(const key_type& __x) const 732 { return _M_t.upper_bound(__x); } 733 734 /** 735 * @brief Finds a subsequence matching given key. 736 * @param x Key of (key, value) pairs to be located. 737 * @return Pair of iterators that possibly points to the subsequence 738 * matching given key. 739 * 740 * This function is equivalent to 741 * @code 742 * std::make_pair(c.lower_bound(val), 743 * c.upper_bound(val)) 744 * @endcode 745 * (but is faster than making the calls separately). 746 * 747 * This function probably only makes sense for multimaps. 748 */ 749 std::pair<iterator, iterator> 750 equal_range(const key_type& __x) 751 { return _M_t.equal_range(__x); } 752 753 /** 754 * @brief Finds a subsequence matching given key. 755 * @param x Key of (key, value) pairs to be located. 756 * @return Pair of read-only (constant) iterators that possibly points 757 * to the subsequence matching given key. 758 * 759 * This function is equivalent to 760 * @code 761 * std::make_pair(c.lower_bound(val), 762 * c.upper_bound(val)) 763 * @endcode 764 * (but is faster than making the calls separately). 765 * 766 * This function probably only makes sense for multimaps. 767 */ 768 std::pair<const_iterator, const_iterator> 769 equal_range(const key_type& __x) const 770 { return _M_t.equal_range(__x); } 771 772 template<typename _K1, typename _T1, typename _C1, typename _A1> 773 friend bool 774 operator==(const map<_K1, _T1, _C1, _A1>&, 775 const map<_K1, _T1, _C1, _A1>&); 776 777 template<typename _K1, typename _T1, typename _C1, typename _A1> 778 friend bool 779 operator<(const map<_K1, _T1, _C1, _A1>&, 780 const map<_K1, _T1, _C1, _A1>&); 781 }; 782 783 /** 784 * @brief Map equality comparison. 785 * @param x A %map. 786 * @param y A %map of the same type as @a x. 787 * @return True iff the size and elements of the maps are equal. 788 * 789 * This is an equivalence relation. It is linear in the size of the 790 * maps. Maps are considered equivalent if their sizes are equal, 791 * and if corresponding elements compare equal. 792 */ 793 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 794 inline bool 795 operator==(const map<_Key, _Tp, _Compare, _Alloc>& __x, 796 const map<_Key, _Tp, _Compare, _Alloc>& __y) 797 { return __x._M_t == __y._M_t; } 798 799 /** 800 * @brief Map ordering relation. 801 * @param x A %map. 802 * @param y A %map of the same type as @a x. 803 * @return True iff @a x is lexicographically less than @a y. 804 * 805 * This is a total ordering relation. It is linear in the size of the 806 * maps. The elements must be comparable with @c <. 807 * 808 * See std::lexicographical_compare() for how the determination is made. 809 */ 810 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 811 inline bool 812 operator<(const map<_Key, _Tp, _Compare, _Alloc>& __x, 813 const map<_Key, _Tp, _Compare, _Alloc>& __y) 814 { return __x._M_t < __y._M_t; } 815 816 /// Based on operator== 817 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 818 inline bool 819 operator!=(const map<_Key, _Tp, _Compare, _Alloc>& __x, 820 const map<_Key, _Tp, _Compare, _Alloc>& __y) 821 { return !(__x == __y); } 822 823 /// Based on operator< 824 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 825 inline bool 826 operator>(const map<_Key, _Tp, _Compare, _Alloc>& __x, 827 const map<_Key, _Tp, _Compare, _Alloc>& __y) 828 { return __y < __x; } 829 830 /// Based on operator< 831 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 832 inline bool 833 operator<=(const map<_Key, _Tp, _Compare, _Alloc>& __x, 834 const map<_Key, _Tp, _Compare, _Alloc>& __y) 835 { return !(__y < __x); } 836 837 /// Based on operator< 838 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 839 inline bool 840 operator>=(const map<_Key, _Tp, _Compare, _Alloc>& __x, 841 const map<_Key, _Tp, _Compare, _Alloc>& __y) 842 { return !(__x < __y); } 843 844 /// See std::map::swap(). 845 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 846 inline void 847 swap(map<_Key, _Tp, _Compare, _Alloc>& __x, 848 map<_Key, _Tp, _Compare, _Alloc>& __y) 849 { __x.swap(__y); } 850 851 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 852 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 853 inline void 854 swap(map<_Key, _Tp, _Compare, _Alloc>&& __x, 855 map<_Key, _Tp, _Compare, _Alloc>& __y) 856 { __x.swap(__y); } 857 858 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 859 inline void 860 swap(map<_Key, _Tp, _Compare, _Alloc>& __x, 861 map<_Key, _Tp, _Compare, _Alloc>&& __y) 862 { __x.swap(__y); } 863 #endif 864 865 _GLIBCXX_END_NESTED_NAMESPACE 866 867 #endif /* _STL_MAP_H */ 868