stl_map.h revision 1.1.1.1
1// Map implementation -*- C++ -*- 2 3// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 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 1204. 269 // NB: DR 675. 270 this->clear(); 271 this->swap(__x); 272 return *this; 273 } 274 275 /** 276 * @brief %Map list assignment operator. 277 * @param l An initializer_list. 278 * 279 * This function fills a %map with copies of the elements in the 280 * initializer list @a l. 281 * 282 * Note that the assignment completely changes the %map and 283 * that the resulting %map's size is the same as the number 284 * of elements assigned. Old data may be lost. 285 */ 286 map& 287 operator=(initializer_list<value_type> __l) 288 { 289 this->clear(); 290 this->insert(__l.begin(), __l.end()); 291 return *this; 292 } 293#endif 294 295 /// Get a copy of the memory allocation object. 296 allocator_type 297 get_allocator() const 298 { return _M_t.get_allocator(); } 299 300 // iterators 301 /** 302 * Returns a read/write iterator that points to the first pair in the 303 * %map. 304 * Iteration is done in ascending order according to the keys. 305 */ 306 iterator 307 begin() 308 { return _M_t.begin(); } 309 310 /** 311 * Returns a read-only (constant) iterator that points to the first pair 312 * in the %map. Iteration is done in ascending order according to the 313 * keys. 314 */ 315 const_iterator 316 begin() const 317 { return _M_t.begin(); } 318 319 /** 320 * Returns a read/write iterator that points one past the last 321 * pair in the %map. Iteration is done in ascending order 322 * according to the keys. 323 */ 324 iterator 325 end() 326 { return _M_t.end(); } 327 328 /** 329 * Returns a read-only (constant) iterator that points one past the last 330 * pair in the %map. Iteration is done in ascending order according to 331 * the keys. 332 */ 333 const_iterator 334 end() const 335 { return _M_t.end(); } 336 337 /** 338 * Returns a read/write reverse iterator that points to the last pair in 339 * the %map. Iteration is done in descending order according to the 340 * keys. 341 */ 342 reverse_iterator 343 rbegin() 344 { return _M_t.rbegin(); } 345 346 /** 347 * Returns a read-only (constant) reverse iterator that points to the 348 * last pair in the %map. Iteration is done in descending order 349 * according to the keys. 350 */ 351 const_reverse_iterator 352 rbegin() const 353 { return _M_t.rbegin(); } 354 355 /** 356 * Returns a read/write reverse iterator that points to one before the 357 * first pair in the %map. Iteration is done in descending order 358 * according to the keys. 359 */ 360 reverse_iterator 361 rend() 362 { return _M_t.rend(); } 363 364 /** 365 * Returns a read-only (constant) reverse iterator that points to one 366 * before the first pair in the %map. Iteration is done in descending 367 * order according to the keys. 368 */ 369 const_reverse_iterator 370 rend() const 371 { return _M_t.rend(); } 372 373#ifdef __GXX_EXPERIMENTAL_CXX0X__ 374 /** 375 * Returns a read-only (constant) iterator that points to the first pair 376 * in the %map. Iteration is done in ascending order according to the 377 * keys. 378 */ 379 const_iterator 380 cbegin() const 381 { return _M_t.begin(); } 382 383 /** 384 * Returns a read-only (constant) iterator that points one past the last 385 * pair in the %map. Iteration is done in ascending order according to 386 * the keys. 387 */ 388 const_iterator 389 cend() const 390 { return _M_t.end(); } 391 392 /** 393 * Returns a read-only (constant) reverse iterator that points to the 394 * last pair in the %map. Iteration is done in descending order 395 * according to the keys. 396 */ 397 const_reverse_iterator 398 crbegin() const 399 { return _M_t.rbegin(); } 400 401 /** 402 * Returns a read-only (constant) reverse iterator that points to one 403 * before the first pair in the %map. Iteration is done in descending 404 * order according to the keys. 405 */ 406 const_reverse_iterator 407 crend() const 408 { return _M_t.rend(); } 409#endif 410 411 // capacity 412 /** Returns true if the %map is empty. (Thus begin() would equal 413 * end().) 414 */ 415 bool 416 empty() const 417 { return _M_t.empty(); } 418 419 /** Returns the size of the %map. */ 420 size_type 421 size() const 422 { return _M_t.size(); } 423 424 /** Returns the maximum size of the %map. */ 425 size_type 426 max_size() const 427 { return _M_t.max_size(); } 428 429 // [23.3.1.2] element access 430 /** 431 * @brief Subscript ( @c [] ) access to %map data. 432 * @param k The key for which data should be retrieved. 433 * @return A reference to the data of the (key,data) %pair. 434 * 435 * Allows for easy lookup with the subscript ( @c [] ) 436 * operator. Returns data associated with the key specified in 437 * subscript. If the key does not exist, a pair with that key 438 * is created using default values, which is then returned. 439 * 440 * Lookup requires logarithmic time. 441 */ 442 mapped_type& 443 operator[](const key_type& __k) 444 { 445 // concept requirements 446 __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>) 447 448 iterator __i = lower_bound(__k); 449 // __i->first is greater than or equivalent to __k. 450 if (__i == end() || key_comp()(__k, (*__i).first)) 451 __i = insert(__i, value_type(__k, mapped_type())); 452 return (*__i).second; 453 } 454 455 // _GLIBCXX_RESOLVE_LIB_DEFECTS 456 // DR 464. Suggestion for new member functions in standard containers. 457 /** 458 * @brief Access to %map data. 459 * @param k The key for which data should be retrieved. 460 * @return A reference to the data whose key is equivalent to @a k, if 461 * such a data is present in the %map. 462 * @throw std::out_of_range If no such data is present. 463 */ 464 mapped_type& 465 at(const key_type& __k) 466 { 467 iterator __i = lower_bound(__k); 468 if (__i == end() || key_comp()(__k, (*__i).first)) 469 __throw_out_of_range(__N("map::at")); 470 return (*__i).second; 471 } 472 473 const mapped_type& 474 at(const key_type& __k) const 475 { 476 const_iterator __i = lower_bound(__k); 477 if (__i == end() || key_comp()(__k, (*__i).first)) 478 __throw_out_of_range(__N("map::at")); 479 return (*__i).second; 480 } 481 482 // modifiers 483 /** 484 * @brief Attempts to insert a std::pair into the %map. 485 486 * @param x Pair to be inserted (see std::make_pair for easy creation 487 * of pairs). 488 489 * @return A pair, of which the first element is an iterator that 490 * points to the possibly inserted pair, and the second is 491 * a bool that is true if the pair was actually inserted. 492 * 493 * This function attempts to insert a (key, value) %pair into the %map. 494 * A %map relies on unique keys and thus a %pair is only inserted if its 495 * first element (the key) is not already present in the %map. 496 * 497 * Insertion requires logarithmic time. 498 */ 499 std::pair<iterator, bool> 500 insert(const value_type& __x) 501 { return _M_t._M_insert_unique(__x); } 502 503#ifdef __GXX_EXPERIMENTAL_CXX0X__ 504 /** 505 * @brief Attempts to insert a list of std::pairs into the %map. 506 * @param list A std::initializer_list<value_type> of pairs to be 507 * inserted. 508 * 509 * Complexity similar to that of the range constructor. 510 */ 511 void 512 insert(std::initializer_list<value_type> __list) 513 { insert (__list.begin(), __list.end()); } 514#endif 515 516 /** 517 * @brief Attempts to insert a std::pair into the %map. 518 * @param position An iterator that serves as a hint as to where the 519 * pair should be inserted. 520 * @param x Pair to be inserted (see std::make_pair for easy creation 521 * of pairs). 522 * @return An iterator that points to the element with key of @a x (may 523 * or may not be the %pair passed in). 524 * 525 526 * This function is not concerned about whether the insertion 527 * took place, and thus does not return a boolean like the 528 * single-argument insert() does. Note that the first 529 * parameter is only a hint and can potentially improve the 530 * performance of the insertion process. A bad hint would 531 * cause no gains in efficiency. 532 * 533 * See 534 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html 535 * for more on @a hinting. 536 * 537 * Insertion requires logarithmic time (if the hint is not taken). 538 */ 539 iterator 540 insert(iterator __position, const value_type& __x) 541 { return _M_t._M_insert_unique_(__position, __x); } 542 543 /** 544 * @brief Template function that attempts to insert a range of elements. 545 * @param first Iterator pointing to the start of the range to be 546 * inserted. 547 * @param last Iterator pointing to the end of the range. 548 * 549 * Complexity similar to that of the range constructor. 550 */ 551 template<typename _InputIterator> 552 void 553 insert(_InputIterator __first, _InputIterator __last) 554 { _M_t._M_insert_unique(__first, __last); } 555 556#ifdef __GXX_EXPERIMENTAL_CXX0X__ 557 // _GLIBCXX_RESOLVE_LIB_DEFECTS 558 // DR 130. Associative erase should return an iterator. 559 /** 560 * @brief Erases an element from a %map. 561 * @param position An iterator pointing to the element to be erased. 562 * @return An iterator pointing to the element immediately following 563 * @a position prior to the element being erased. If no such 564 * element exists, end() is returned. 565 * 566 * This function erases an element, pointed to by the given 567 * iterator, from a %map. Note that this function only erases 568 * the element, and that if the element is itself a pointer, 569 * the pointed-to memory is not touched in any way. Managing 570 * the pointer is the user's responsibility. 571 */ 572 iterator 573 erase(iterator __position) 574 { return _M_t.erase(__position); } 575#else 576 /** 577 * @brief Erases an element from a %map. 578 * @param position An iterator pointing to the element to be erased. 579 * 580 * This function erases an element, pointed to by the given 581 * iterator, from a %map. Note that this function only erases 582 * the element, and that if the element is itself a pointer, 583 * the pointed-to memory is not touched in any way. Managing 584 * the pointer is the user's responsibility. 585 */ 586 void 587 erase(iterator __position) 588 { _M_t.erase(__position); } 589#endif 590 591 /** 592 * @brief Erases elements according to the provided key. 593 * @param x Key of element to be erased. 594 * @return The number of elements erased. 595 * 596 * This function erases all the elements located by the given key from 597 * a %map. 598 * Note that this function only erases the element, and that if 599 * the element is itself a pointer, the pointed-to memory is not touched 600 * in any way. Managing the pointer is the user's responsibility. 601 */ 602 size_type 603 erase(const key_type& __x) 604 { return _M_t.erase(__x); } 605 606#ifdef __GXX_EXPERIMENTAL_CXX0X__ 607 // _GLIBCXX_RESOLVE_LIB_DEFECTS 608 // DR 130. Associative erase should return an iterator. 609 /** 610 * @brief Erases a [first,last) range of elements from a %map. 611 * @param first Iterator pointing to the start of the range to be 612 * erased. 613 * @param last Iterator pointing to the end of the range to be erased. 614 * @return The iterator @a last. 615 * 616 * This function erases a sequence of elements from a %map. 617 * Note that this function only erases the element, and that if 618 * the element is itself a pointer, the pointed-to memory is not touched 619 * in any way. Managing the pointer is the user's responsibility. 620 */ 621 iterator 622 erase(iterator __first, iterator __last) 623 { return _M_t.erase(__first, __last); } 624#else 625 /** 626 * @brief Erases a [first,last) range of elements from a %map. 627 * @param first Iterator pointing to the start of the range to be 628 * erased. 629 * @param last Iterator pointing to the end of the range to be erased. 630 * 631 * This function erases a sequence of elements from a %map. 632 * Note that this function only erases the element, and that if 633 * the element is itself a pointer, the pointed-to memory is not touched 634 * in any way. Managing the pointer is the user's responsibility. 635 */ 636 void 637 erase(iterator __first, iterator __last) 638 { _M_t.erase(__first, __last); } 639#endif 640 641 /** 642 * @brief Swaps data with another %map. 643 * @param x A %map of the same element and allocator types. 644 * 645 * This exchanges the elements between two maps in constant 646 * time. (It is only swapping a pointer, an integer, and an 647 * instance of the @c Compare type (which itself is often 648 * stateless and empty), so it should be quite fast.) Note 649 * that the global std::swap() function is specialized such 650 * that std::swap(m1,m2) will feed to this function. 651 */ 652 void 653 swap(map& __x) 654 { _M_t.swap(__x._M_t); } 655 656 /** 657 * Erases all elements in a %map. Note that this function only 658 * erases the elements, and that if the elements themselves are 659 * pointers, the pointed-to memory is not touched in any way. 660 * Managing the pointer is the user's responsibility. 661 */ 662 void 663 clear() 664 { _M_t.clear(); } 665 666 // observers 667 /** 668 * Returns the key comparison object out of which the %map was 669 * constructed. 670 */ 671 key_compare 672 key_comp() const 673 { return _M_t.key_comp(); } 674 675 /** 676 * Returns a value comparison object, built from the key comparison 677 * object out of which the %map was constructed. 678 */ 679 value_compare 680 value_comp() const 681 { return value_compare(_M_t.key_comp()); } 682 683 // [23.3.1.3] map operations 684 /** 685 * @brief Tries to locate an element in a %map. 686 * @param x Key of (key, value) %pair to be located. 687 * @return Iterator pointing to sought-after element, or end() if not 688 * found. 689 * 690 * This function takes a key and tries to locate the element with which 691 * the key matches. If successful the function returns an iterator 692 * pointing to the sought after %pair. If unsuccessful it returns the 693 * past-the-end ( @c end() ) iterator. 694 */ 695 iterator 696 find(const key_type& __x) 697 { return _M_t.find(__x); } 698 699 /** 700 * @brief Tries to locate an element in a %map. 701 * @param x Key of (key, value) %pair to be located. 702 * @return Read-only (constant) iterator pointing to sought-after 703 * element, or end() if not found. 704 * 705 * This function takes a key and tries to locate the element with which 706 * the key matches. If successful the function returns a constant 707 * iterator pointing to the sought after %pair. If unsuccessful it 708 * returns the past-the-end ( @c end() ) iterator. 709 */ 710 const_iterator 711 find(const key_type& __x) const 712 { return _M_t.find(__x); } 713 714 /** 715 * @brief Finds the number of elements with given key. 716 * @param x Key of (key, value) pairs to be located. 717 * @return Number of elements with specified key. 718 * 719 * This function only makes sense for multimaps; for map the result will 720 * either be 0 (not present) or 1 (present). 721 */ 722 size_type 723 count(const key_type& __x) const 724 { return _M_t.find(__x) == _M_t.end() ? 0 : 1; } 725 726 /** 727 * @brief Finds the beginning of a subsequence matching given key. 728 * @param x Key of (key, value) pair to be located. 729 * @return Iterator pointing to first element equal to or greater 730 * than key, or end(). 731 * 732 * This function returns the first element of a subsequence of elements 733 * that matches the given key. If unsuccessful it returns an iterator 734 * pointing to the first element that has a greater value than given key 735 * or end() if no such element exists. 736 */ 737 iterator 738 lower_bound(const key_type& __x) 739 { return _M_t.lower_bound(__x); } 740 741 /** 742 * @brief Finds the beginning of a subsequence matching given key. 743 * @param x Key of (key, value) pair to be located. 744 * @return Read-only (constant) iterator pointing to first element 745 * equal to or greater than key, or end(). 746 * 747 * This function returns the first element of a subsequence of elements 748 * that matches the given key. If unsuccessful it returns an iterator 749 * pointing to the first element that has a greater value than given key 750 * or end() if no such element exists. 751 */ 752 const_iterator 753 lower_bound(const key_type& __x) const 754 { return _M_t.lower_bound(__x); } 755 756 /** 757 * @brief Finds the end of a subsequence matching given key. 758 * @param x Key of (key, value) pair to be located. 759 * @return Iterator pointing to the first element 760 * greater than key, or end(). 761 */ 762 iterator 763 upper_bound(const key_type& __x) 764 { return _M_t.upper_bound(__x); } 765 766 /** 767 * @brief Finds the end of a subsequence matching given key. 768 * @param x Key of (key, value) pair to be located. 769 * @return Read-only (constant) iterator pointing to first iterator 770 * greater than key, or end(). 771 */ 772 const_iterator 773 upper_bound(const key_type& __x) const 774 { return _M_t.upper_bound(__x); } 775 776 /** 777 * @brief Finds a subsequence matching given key. 778 * @param x Key of (key, value) pairs to be located. 779 * @return Pair of iterators that possibly points to the subsequence 780 * matching given key. 781 * 782 * This function is equivalent to 783 * @code 784 * std::make_pair(c.lower_bound(val), 785 * c.upper_bound(val)) 786 * @endcode 787 * (but is faster than making the calls separately). 788 * 789 * This function probably only makes sense for multimaps. 790 */ 791 std::pair<iterator, iterator> 792 equal_range(const key_type& __x) 793 { return _M_t.equal_range(__x); } 794 795 /** 796 * @brief Finds a subsequence matching given key. 797 * @param x Key of (key, value) pairs to be located. 798 * @return Pair of read-only (constant) iterators that possibly points 799 * to the subsequence matching given key. 800 * 801 * This function is equivalent to 802 * @code 803 * std::make_pair(c.lower_bound(val), 804 * c.upper_bound(val)) 805 * @endcode 806 * (but is faster than making the calls separately). 807 * 808 * This function probably only makes sense for multimaps. 809 */ 810 std::pair<const_iterator, const_iterator> 811 equal_range(const key_type& __x) const 812 { return _M_t.equal_range(__x); } 813 814 template<typename _K1, typename _T1, typename _C1, typename _A1> 815 friend bool 816 operator==(const map<_K1, _T1, _C1, _A1>&, 817 const map<_K1, _T1, _C1, _A1>&); 818 819 template<typename _K1, typename _T1, typename _C1, typename _A1> 820 friend bool 821 operator<(const map<_K1, _T1, _C1, _A1>&, 822 const map<_K1, _T1, _C1, _A1>&); 823 }; 824 825 /** 826 * @brief Map equality comparison. 827 * @param x A %map. 828 * @param y A %map of the same type as @a x. 829 * @return True iff the size and elements of the maps are equal. 830 * 831 * This is an equivalence relation. It is linear in the size of the 832 * maps. Maps are considered equivalent if their sizes are equal, 833 * and if corresponding elements compare equal. 834 */ 835 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 836 inline bool 837 operator==(const map<_Key, _Tp, _Compare, _Alloc>& __x, 838 const map<_Key, _Tp, _Compare, _Alloc>& __y) 839 { return __x._M_t == __y._M_t; } 840 841 /** 842 * @brief Map ordering relation. 843 * @param x A %map. 844 * @param y A %map of the same type as @a x. 845 * @return True iff @a x is lexicographically less than @a y. 846 * 847 * This is a total ordering relation. It is linear in the size of the 848 * maps. The elements must be comparable with @c <. 849 * 850 * See std::lexicographical_compare() for how the determination is made. 851 */ 852 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 853 inline bool 854 operator<(const map<_Key, _Tp, _Compare, _Alloc>& __x, 855 const map<_Key, _Tp, _Compare, _Alloc>& __y) 856 { return __x._M_t < __y._M_t; } 857 858 /// Based on operator== 859 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 860 inline bool 861 operator!=(const map<_Key, _Tp, _Compare, _Alloc>& __x, 862 const map<_Key, _Tp, _Compare, _Alloc>& __y) 863 { return !(__x == __y); } 864 865 /// Based on operator< 866 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 867 inline bool 868 operator>(const map<_Key, _Tp, _Compare, _Alloc>& __x, 869 const map<_Key, _Tp, _Compare, _Alloc>& __y) 870 { return __y < __x; } 871 872 /// Based on operator< 873 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 874 inline bool 875 operator<=(const map<_Key, _Tp, _Compare, _Alloc>& __x, 876 const map<_Key, _Tp, _Compare, _Alloc>& __y) 877 { return !(__y < __x); } 878 879 /// Based on operator< 880 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 881 inline bool 882 operator>=(const map<_Key, _Tp, _Compare, _Alloc>& __x, 883 const map<_Key, _Tp, _Compare, _Alloc>& __y) 884 { return !(__x < __y); } 885 886 /// See std::map::swap(). 887 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 888 inline void 889 swap(map<_Key, _Tp, _Compare, _Alloc>& __x, 890 map<_Key, _Tp, _Compare, _Alloc>& __y) 891 { __x.swap(__y); } 892 893_GLIBCXX_END_NESTED_NAMESPACE 894 895#endif /* _STL_MAP_H */ 896