00001 // Map implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 2, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // You should have received a copy of the GNU General Public License along 00018 // with this library; see the file COPYING. If not, write to the Free 00019 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 00020 // USA. 00021 00022 // As a special exception, you may use this file as part of a free software 00023 // library without restriction. Specifically, if other files instantiate 00024 // templates or use macros or inline functions from this file, or you compile 00025 // this file and link it with other files to produce an executable, this 00026 // file does not by itself cause the resulting executable to be covered by 00027 // the GNU General Public License. This exception does not however 00028 // invalidate any other reasons why the executable file might be covered by 00029 // the GNU General Public License. 00030 00031 /* 00032 * 00033 * Copyright (c) 1994 00034 * Hewlett-Packard Company 00035 * 00036 * Permission to use, copy, modify, distribute and sell this software 00037 * and its documentation for any purpose is hereby granted without fee, 00038 * provided that the above copyright notice appear in all copies and 00039 * that both that copyright notice and this permission notice appear 00040 * in supporting documentation. Hewlett-Packard Company makes no 00041 * representations about the suitability of this software for any 00042 * purpose. It is provided "as is" without express or implied warranty. 00043 * 00044 * 00045 * Copyright (c) 1996,1997 00046 * Silicon Graphics Computer Systems, Inc. 00047 * 00048 * Permission to use, copy, modify, distribute and sell this software 00049 * and its documentation for any purpose is hereby granted without fee, 00050 * provided that the above copyright notice appear in all copies and 00051 * that both that copyright notice and this permission notice appear 00052 * in supporting documentation. Silicon Graphics makes no 00053 * representations about the suitability of this software for any 00054 * purpose. It is provided "as is" without express or implied warranty. 00055 */ 00056 00057 /** @file stl_map.h 00058 * This is an internal header file, included by other library headers. 00059 * You should not attempt to use it directly. 00060 */ 00061 00062 #ifndef _STL_MAP_H 00063 #define _STL_MAP_H 1 00064 00065 #include <bits/functexcept.h> 00066 #include <bits/concept_check.h> 00067 00068 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) 00069 00070 /** 00071 * @brief A standard container made up of (key,value) pairs, which can be 00072 * retrieved based on a key, in logarithmic time. 00073 * 00074 * @ingroup Containers 00075 * @ingroup Assoc_containers 00076 * 00077 * Meets the requirements of a <a href="tables.html#65">container</a>, a 00078 * <a href="tables.html#66">reversible container</a>, and an 00079 * <a href="tables.html#69">associative container</a> (using unique keys). 00080 * For a @c map<Key,T> the key_type is Key, the mapped_type is T, and the 00081 * value_type is std::pair<const Key,T>. 00082 * 00083 * Maps support bidirectional iterators. 00084 * 00085 * The private tree data is declared exactly the same way for map and 00086 * multimap; the distinction is made entirely in how the tree functions are 00087 * called (*_unique versus *_equal, same as the standard). 00088 */ 00089 template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>, 00090 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 00091 class map 00092 { 00093 public: 00094 typedef _Key key_type; 00095 typedef _Tp mapped_type; 00096 typedef std::pair<const _Key, _Tp> value_type; 00097 typedef _Compare key_compare; 00098 typedef _Alloc allocator_type; 00099 00100 private: 00101 // concept requirements 00102 typedef typename _Alloc::value_type _Alloc_value_type; 00103 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 00104 __glibcxx_class_requires4(_Compare, bool, _Key, _Key, 00105 _BinaryFunctionConcept) 00106 __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept) 00107 00108 public: 00109 class value_compare 00110 : public std::binary_function<value_type, value_type, bool> 00111 { 00112 friend class map<_Key, _Tp, _Compare, _Alloc>; 00113 protected: 00114 _Compare comp; 00115 00116 value_compare(_Compare __c) 00117 : comp(__c) { } 00118 00119 public: 00120 bool operator()(const value_type& __x, const value_type& __y) const 00121 { return comp(__x.first, __y.first); } 00122 }; 00123 00124 private: 00125 /// This turns a red-black tree into a [multi]map. 00126 typedef typename _Alloc::template rebind<value_type>::other 00127 _Pair_alloc_type; 00128 00129 typedef _Rb_tree<key_type, value_type, _Select1st<value_type>, 00130 key_compare, _Pair_alloc_type> _Rep_type; 00131 00132 /// The actual tree structure. 00133 _Rep_type _M_t; 00134 00135 public: 00136 // many of these are specified differently in ISO, but the following are 00137 // "functionally equivalent" 00138 typedef typename _Pair_alloc_type::pointer pointer; 00139 typedef typename _Pair_alloc_type::const_pointer const_pointer; 00140 typedef typename _Pair_alloc_type::reference reference; 00141 typedef typename _Pair_alloc_type::const_reference const_reference; 00142 typedef typename _Rep_type::iterator iterator; 00143 typedef typename _Rep_type::const_iterator const_iterator; 00144 typedef typename _Rep_type::size_type size_type; 00145 typedef typename _Rep_type::difference_type difference_type; 00146 typedef typename _Rep_type::reverse_iterator reverse_iterator; 00147 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 00148 00149 // [23.3.1.1] construct/copy/destroy 00150 // (get_allocator() is normally listed in this section, but seems to have 00151 // been accidentally omitted in the printed standard) 00152 /** 00153 * @brief Default constructor creates no elements. 00154 */ 00155 map() 00156 : _M_t() { } 00157 00158 /** 00159 * @brief Creates a %map with no elements. 00160 * @param comp A comparison object. 00161 * @param a An allocator object. 00162 */ 00163 explicit 00164 map(const _Compare& __comp, 00165 const allocator_type& __a = allocator_type()) 00166 : _M_t(__comp, __a) { } 00167 00168 /** 00169 * @brief %Map copy constructor. 00170 * @param x A %map of identical element and allocator types. 00171 * 00172 * The newly-created %map uses a copy of the allocation object 00173 * used by @a x. 00174 */ 00175 map(const map& __x) 00176 : _M_t(__x._M_t) { } 00177 00178 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00179 /** 00180 * @brief %Map move constructor. 00181 * @param x A %map of identical element and allocator types. 00182 * 00183 * The newly-created %map contains the exact contents of @a x. 00184 * The contents of @a x are a valid, but unspecified %map. 00185 */ 00186 map(map&& __x) 00187 : _M_t(std::forward<_Rep_type>(__x._M_t)) { } 00188 #endif 00189 00190 /** 00191 * @brief Builds a %map from a range. 00192 * @param first An input iterator. 00193 * @param last An input iterator. 00194 * 00195 * Create a %map consisting of copies of the elements from [first,last). 00196 * This is linear in N if the range is already sorted, and NlogN 00197 * otherwise (where N is distance(first,last)). 00198 */ 00199 template<typename _InputIterator> 00200 map(_InputIterator __first, _InputIterator __last) 00201 : _M_t() 00202 { _M_t._M_insert_unique(__first, __last); } 00203 00204 /** 00205 * @brief Builds a %map from a range. 00206 * @param first An input iterator. 00207 * @param last An input iterator. 00208 * @param comp A comparison functor. 00209 * @param a An allocator object. 00210 * 00211 * Create a %map consisting of copies of the elements from [first,last). 00212 * This is linear in N if the range is already sorted, and NlogN 00213 * otherwise (where N is distance(first,last)). 00214 */ 00215 template<typename _InputIterator> 00216 map(_InputIterator __first, _InputIterator __last, 00217 const _Compare& __comp, 00218 const allocator_type& __a = allocator_type()) 00219 : _M_t(__comp, __a) 00220 { _M_t._M_insert_unique(__first, __last); } 00221 00222 // FIXME There is no dtor declared, but we should have something 00223 // generated by Doxygen. I don't know what tags to add to this 00224 // paragraph to make that happen: 00225 /** 00226 * The dtor only erases the elements, and note that if the elements 00227 * themselves are pointers, the pointed-to memory is not touched in any 00228 * way. Managing the pointer is the user's responsibility. 00229 */ 00230 00231 /** 00232 * @brief %Map assignment operator. 00233 * @param x A %map of identical element and allocator types. 00234 * 00235 * All the elements of @a x are copied, but unlike the copy constructor, 00236 * the allocator object is not copied. 00237 */ 00238 map& 00239 operator=(const map& __x) 00240 { 00241 _M_t = __x._M_t; 00242 return *this; 00243 } 00244 00245 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00246 /** 00247 * @brief %Map move assignment operator. 00248 * @param x A %map of identical element and allocator types. 00249 * 00250 * The contents of @a x are moved into this map (without copying). 00251 * @a x is a valid, but unspecified %map. 00252 */ 00253 map& 00254 operator=(map&& __x) 00255 { 00256 // NB: DR 675. 00257 this->clear(); 00258 this->swap(__x); 00259 return *this; 00260 } 00261 #endif 00262 00263 /// Get a copy of the memory allocation object. 00264 allocator_type 00265 get_allocator() const 00266 { return _M_t.get_allocator(); } 00267 00268 // iterators 00269 /** 00270 * Returns a read/write iterator that points to the first pair in the 00271 * %map. 00272 * Iteration is done in ascending order according to the keys. 00273 */ 00274 iterator 00275 begin() 00276 { return _M_t.begin(); } 00277 00278 /** 00279 * Returns a read-only (constant) iterator that points to the first pair 00280 * in the %map. Iteration is done in ascending order according to the 00281 * keys. 00282 */ 00283 const_iterator 00284 begin() const 00285 { return _M_t.begin(); } 00286 00287 /** 00288 * Returns a read/write iterator that points one past the last 00289 * pair in the %map. Iteration is done in ascending order 00290 * according to the keys. 00291 */ 00292 iterator 00293 end() 00294 { return _M_t.end(); } 00295 00296 /** 00297 * Returns a read-only (constant) iterator that points one past the last 00298 * pair in the %map. Iteration is done in ascending order according to 00299 * the keys. 00300 */ 00301 const_iterator 00302 end() const 00303 { return _M_t.end(); } 00304 00305 /** 00306 * Returns a read/write reverse iterator that points to the last pair in 00307 * the %map. Iteration is done in descending order according to the 00308 * keys. 00309 */ 00310 reverse_iterator 00311 rbegin() 00312 { return _M_t.rbegin(); } 00313 00314 /** 00315 * Returns a read-only (constant) reverse iterator that points to the 00316 * last pair in the %map. Iteration is done in descending order 00317 * according to the keys. 00318 */ 00319 const_reverse_iterator 00320 rbegin() const 00321 { return _M_t.rbegin(); } 00322 00323 /** 00324 * Returns a read/write reverse iterator that points to one before the 00325 * first pair in the %map. Iteration is done in descending order 00326 * according to the keys. 00327 */ 00328 reverse_iterator 00329 rend() 00330 { return _M_t.rend(); } 00331 00332 /** 00333 * Returns a read-only (constant) reverse iterator that points to one 00334 * before the first pair in the %map. Iteration is done in descending 00335 * order according to the keys. 00336 */ 00337 const_reverse_iterator 00338 rend() const 00339 { return _M_t.rend(); } 00340 00341 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00342 /** 00343 * Returns a read-only (constant) iterator that points to the first pair 00344 * in the %map. Iteration is done in ascending order according to the 00345 * keys. 00346 */ 00347 const_iterator 00348 cbegin() const 00349 { return _M_t.begin(); } 00350 00351 /** 00352 * Returns a read-only (constant) iterator that points one past the last 00353 * pair in the %map. Iteration is done in ascending order according to 00354 * the keys. 00355 */ 00356 const_iterator 00357 cend() const 00358 { return _M_t.end(); } 00359 00360 /** 00361 * Returns a read-only (constant) reverse iterator that points to the 00362 * last pair in the %map. Iteration is done in descending order 00363 * according to the keys. 00364 */ 00365 const_reverse_iterator 00366 crbegin() const 00367 { return _M_t.rbegin(); } 00368 00369 /** 00370 * Returns a read-only (constant) reverse iterator that points to one 00371 * before the first pair in the %map. Iteration is done in descending 00372 * order according to the keys. 00373 */ 00374 const_reverse_iterator 00375 crend() const 00376 { return _M_t.rend(); } 00377 #endif 00378 00379 // capacity 00380 /** Returns true if the %map is empty. (Thus begin() would equal 00381 * end().) 00382 */ 00383 bool 00384 empty() const 00385 { return _M_t.empty(); } 00386 00387 /** Returns the size of the %map. */ 00388 size_type 00389 size() const 00390 { return _M_t.size(); } 00391 00392 /** Returns the maximum size of the %map. */ 00393 size_type 00394 max_size() const 00395 { return _M_t.max_size(); } 00396 00397 // [23.3.1.2] element access 00398 /** 00399 * @brief Subscript ( @c [] ) access to %map data. 00400 * @param k The key for which data should be retrieved. 00401 * @return A reference to the data of the (key,data) %pair. 00402 * 00403 * Allows for easy lookup with the subscript ( @c [] ) 00404 * operator. Returns data associated with the key specified in 00405 * subscript. If the key does not exist, a pair with that key 00406 * is created using default values, which is then returned. 00407 * 00408 * Lookup requires logarithmic time. 00409 */ 00410 mapped_type& 00411 operator[](const key_type& __k) 00412 { 00413 // concept requirements 00414 __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>) 00415 00416 iterator __i = lower_bound(__k); 00417 // __i->first is greater than or equivalent to __k. 00418 if (__i == end() || key_comp()(__k, (*__i).first)) 00419 __i = insert(__i, value_type(__k, mapped_type())); 00420 return (*__i).second; 00421 } 00422 00423 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00424 // DR 464. Suggestion for new member functions in standard containers. 00425 /** 00426 * @brief Access to %map data. 00427 * @param k The key for which data should be retrieved. 00428 * @return A reference to the data whose key is equivalent to @a k, if 00429 * such a data is present in the %map. 00430 * @throw std::out_of_range If no such data is present. 00431 */ 00432 mapped_type& 00433 at(const key_type& __k) 00434 { 00435 iterator __i = lower_bound(__k); 00436 if (__i == end() || key_comp()(__k, (*__i).first)) 00437 __throw_out_of_range(__N("map::at")); 00438 return (*__i).second; 00439 } 00440 00441 const mapped_type& 00442 at(const key_type& __k) const 00443 { 00444 const_iterator __i = lower_bound(__k); 00445 if (__i == end() || key_comp()(__k, (*__i).first)) 00446 __throw_out_of_range(__N("map::at")); 00447 return (*__i).second; 00448 } 00449 00450 // modifiers 00451 /** 00452 * @brief Attempts to insert a std::pair into the %map. 00453 00454 * @param x Pair to be inserted (see std::make_pair for easy creation 00455 * of pairs). 00456 00457 * @return A pair, of which the first element is an iterator that 00458 * points to the possibly inserted pair, and the second is 00459 * a bool that is true if the pair was actually inserted. 00460 * 00461 * This function attempts to insert a (key, value) %pair into the %map. 00462 * A %map relies on unique keys and thus a %pair is only inserted if its 00463 * first element (the key) is not already present in the %map. 00464 * 00465 * Insertion requires logarithmic time. 00466 */ 00467 std::pair<iterator, bool> 00468 insert(const value_type& __x) 00469 { return _M_t._M_insert_unique(__x); } 00470 00471 /** 00472 * @brief Attempts to insert a std::pair into the %map. 00473 * @param position An iterator that serves as a hint as to where the 00474 * pair should be inserted. 00475 * @param x Pair to be inserted (see std::make_pair for easy creation 00476 * of pairs). 00477 * @return An iterator that points to the element with key of @a x (may 00478 * or may not be the %pair passed in). 00479 * 00480 00481 * This function is not concerned about whether the insertion 00482 * took place, and thus does not return a boolean like the 00483 * single-argument insert() does. Note that the first 00484 * parameter is only a hint and can potentially improve the 00485 * performance of the insertion process. A bad hint would 00486 * cause no gains in efficiency. 00487 * 00488 * See 00489 * http://gcc.gnu.org/onlinedocs/libstdc++/23_containers/howto.html#4 00490 * for more on "hinting". 00491 * 00492 * Insertion requires logarithmic time (if the hint is not taken). 00493 */ 00494 iterator 00495 insert(iterator __position, const value_type& __x) 00496 { return _M_t._M_insert_unique_(__position, __x); } 00497 00498 /** 00499 * @brief Template function that attempts to insert a range of elements. 00500 * @param first Iterator pointing to the start of the range to be 00501 * inserted. 00502 * @param last Iterator pointing to the end of the range. 00503 * 00504 * Complexity similar to that of the range constructor. 00505 */ 00506 template<typename _InputIterator> 00507 void 00508 insert(_InputIterator __first, _InputIterator __last) 00509 { _M_t._M_insert_unique(__first, __last); } 00510 00511 /** 00512 * @brief Erases an element from a %map. 00513 * @param position An iterator pointing to the element to be erased. 00514 * 00515 * This function erases an element, pointed to by the given 00516 * iterator, from a %map. Note that this function only erases 00517 * the element, and that if the element is itself a pointer, 00518 * the pointed-to memory is not touched in any way. Managing 00519 * the pointer is the user's responsibility. 00520 */ 00521 void 00522 erase(iterator __position) 00523 { _M_t.erase(__position); } 00524 00525 /** 00526 * @brief Erases elements according to the provided key. 00527 * @param x Key of element to be erased. 00528 * @return The number of elements erased. 00529 * 00530 * This function erases all the elements located by the given key from 00531 * a %map. 00532 * Note that this function only erases the element, and that if 00533 * the element is itself a pointer, the pointed-to memory is not touched 00534 * in any way. Managing the pointer is the user's responsibility. 00535 */ 00536 size_type 00537 erase(const key_type& __x) 00538 { return _M_t.erase(__x); } 00539 00540 /** 00541 * @brief Erases a [first,last) range of elements from a %map. 00542 * @param first Iterator pointing to the start of the range to be 00543 * erased. 00544 * @param last Iterator pointing to the end of the range to be erased. 00545 * 00546 * This function erases a sequence of elements from a %map. 00547 * Note that this function only erases the element, and that if 00548 * the element is itself a pointer, the pointed-to memory is not touched 00549 * in any way. Managing the pointer is the user's responsibility. 00550 */ 00551 void 00552 erase(iterator __first, iterator __last) 00553 { _M_t.erase(__first, __last); } 00554 00555 /** 00556 * @brief Swaps data with another %map. 00557 * @param x A %map of the same element and allocator types. 00558 * 00559 * This exchanges the elements between two maps in constant 00560 * time. (It is only swapping a pointer, an integer, and an 00561 * instance of the @c Compare type (which itself is often 00562 * stateless and empty), so it should be quite fast.) Note 00563 * that the global std::swap() function is specialized such 00564 * that std::swap(m1,m2) will feed to this function. 00565 */ 00566 void 00567 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00568 swap(map&& __x) 00569 #else 00570 swap(map& __x) 00571 #endif 00572 { _M_t.swap(__x._M_t); } 00573 00574 /** 00575 * Erases all elements in a %map. Note that this function only 00576 * erases the elements, and that if the elements themselves are 00577 * pointers, the pointed-to memory is not touched in any way. 00578 * Managing the pointer is the user's responsibility. 00579 */ 00580 void 00581 clear() 00582 { _M_t.clear(); } 00583 00584 // observers 00585 /** 00586 * Returns the key comparison object out of which the %map was 00587 * constructed. 00588 */ 00589 key_compare 00590 key_comp() const 00591 { return _M_t.key_comp(); } 00592 00593 /** 00594 * Returns a value comparison object, built from the key comparison 00595 * object out of which the %map was constructed. 00596 */ 00597 value_compare 00598 value_comp() const 00599 { return value_compare(_M_t.key_comp()); } 00600 00601 // [23.3.1.3] map operations 00602 /** 00603 * @brief Tries to locate an element in a %map. 00604 * @param x Key of (key, value) %pair to be located. 00605 * @return Iterator pointing to sought-after element, or end() if not 00606 * found. 00607 * 00608 * This function takes a key and tries to locate the element with which 00609 * the key matches. If successful the function returns an iterator 00610 * pointing to the sought after %pair. If unsuccessful it returns the 00611 * past-the-end ( @c end() ) iterator. 00612 */ 00613 iterator 00614 find(const key_type& __x) 00615 { return _M_t.find(__x); } 00616 00617 /** 00618 * @brief Tries to locate an element in a %map. 00619 * @param x Key of (key, value) %pair to be located. 00620 * @return Read-only (constant) iterator pointing to sought-after 00621 * element, or end() if not found. 00622 * 00623 * This function takes a key and tries to locate the element with which 00624 * the key matches. If successful the function returns a constant 00625 * iterator pointing to the sought after %pair. If unsuccessful it 00626 * returns the past-the-end ( @c end() ) iterator. 00627 */ 00628 const_iterator 00629 find(const key_type& __x) const 00630 { return _M_t.find(__x); } 00631 00632 /** 00633 * @brief Finds the number of elements with given key. 00634 * @param x Key of (key, value) pairs to be located. 00635 * @return Number of elements with specified key. 00636 * 00637 * This function only makes sense for multimaps; for map the result will 00638 * either be 0 (not present) or 1 (present). 00639 */ 00640 size_type 00641 count(const key_type& __x) const 00642 { return _M_t.find(__x) == _M_t.end() ? 0 : 1; } 00643 00644 /** 00645 * @brief Finds the beginning of a subsequence matching given key. 00646 * @param x Key of (key, value) pair to be located. 00647 * @return Iterator pointing to first element equal to or greater 00648 * than key, or end(). 00649 * 00650 * This function returns the first element of a subsequence of elements 00651 * that matches the given key. If unsuccessful it returns an iterator 00652 * pointing to the first element that has a greater value than given key 00653 * or end() if no such element exists. 00654 */ 00655 iterator 00656 lower_bound(const key_type& __x) 00657 { return _M_t.lower_bound(__x); } 00658 00659 /** 00660 * @brief Finds the beginning of a subsequence matching given key. 00661 * @param x Key of (key, value) pair to be located. 00662 * @return Read-only (constant) iterator pointing to first element 00663 * equal to or greater than key, or end(). 00664 * 00665 * This function returns the first element of a subsequence of elements 00666 * that matches the given key. If unsuccessful it returns an iterator 00667 * pointing to the first element that has a greater value than given key 00668 * or end() if no such element exists. 00669 */ 00670 const_iterator 00671 lower_bound(const key_type& __x) const 00672 { return _M_t.lower_bound(__x); } 00673 00674 /** 00675 * @brief Finds the end of a subsequence matching given key. 00676 * @param x Key of (key, value) pair to be located. 00677 * @return Iterator pointing to the first element 00678 * greater than key, or end(). 00679 */ 00680 iterator 00681 upper_bound(const key_type& __x) 00682 { return _M_t.upper_bound(__x); } 00683 00684 /** 00685 * @brief Finds the end of a subsequence matching given key. 00686 * @param x Key of (key, value) pair to be located. 00687 * @return Read-only (constant) iterator pointing to first iterator 00688 * greater than key, or end(). 00689 */ 00690 const_iterator 00691 upper_bound(const key_type& __x) const 00692 { return _M_t.upper_bound(__x); } 00693 00694 /** 00695 * @brief Finds a subsequence matching given key. 00696 * @param x Key of (key, value) pairs to be located. 00697 * @return Pair of iterators that possibly points to the subsequence 00698 * matching given key. 00699 * 00700 * This function is equivalent to 00701 * @code 00702 * std::make_pair(c.lower_bound(val), 00703 * c.upper_bound(val)) 00704 * @endcode 00705 * (but is faster than making the calls separately). 00706 * 00707 * This function probably only makes sense for multimaps. 00708 */ 00709 std::pair<iterator, iterator> 00710 equal_range(const key_type& __x) 00711 { return _M_t.equal_range(__x); } 00712 00713 /** 00714 * @brief Finds a subsequence matching given key. 00715 * @param x Key of (key, value) pairs to be located. 00716 * @return Pair of read-only (constant) iterators that possibly points 00717 * to the subsequence matching given key. 00718 * 00719 * This function is equivalent to 00720 * @code 00721 * std::make_pair(c.lower_bound(val), 00722 * c.upper_bound(val)) 00723 * @endcode 00724 * (but is faster than making the calls separately). 00725 * 00726 * This function probably only makes sense for multimaps. 00727 */ 00728 std::pair<const_iterator, const_iterator> 00729 equal_range(const key_type& __x) const 00730 { return _M_t.equal_range(__x); } 00731 00732 template<typename _K1, typename _T1, typename _C1, typename _A1> 00733 friend bool 00734 operator==(const map<_K1, _T1, _C1, _A1>&, 00735 const map<_K1, _T1, _C1, _A1>&); 00736 00737 template<typename _K1, typename _T1, typename _C1, typename _A1> 00738 friend bool 00739 operator<(const map<_K1, _T1, _C1, _A1>&, 00740 const map<_K1, _T1, _C1, _A1>&); 00741 }; 00742 00743 /** 00744 * @brief Map equality comparison. 00745 * @param x A %map. 00746 * @param y A %map of the same type as @a x. 00747 * @return True iff the size and elements of the maps are equal. 00748 * 00749 * This is an equivalence relation. It is linear in the size of the 00750 * maps. Maps are considered equivalent if their sizes are equal, 00751 * and if corresponding elements compare equal. 00752 */ 00753 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 00754 inline bool 00755 operator==(const map<_Key, _Tp, _Compare, _Alloc>& __x, 00756 const map<_Key, _Tp, _Compare, _Alloc>& __y) 00757 { return __x._M_t == __y._M_t; } 00758 00759 /** 00760 * @brief Map ordering relation. 00761 * @param x A %map. 00762 * @param y A %map of the same type as @a x. 00763 * @return True iff @a x is lexicographically less than @a y. 00764 * 00765 * This is a total ordering relation. It is linear in the size of the 00766 * maps. The elements must be comparable with @c <. 00767 * 00768 * See std::lexicographical_compare() for how the determination is made. 00769 */ 00770 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 00771 inline bool 00772 operator<(const map<_Key, _Tp, _Compare, _Alloc>& __x, 00773 const map<_Key, _Tp, _Compare, _Alloc>& __y) 00774 { return __x._M_t < __y._M_t; } 00775 00776 /// Based on operator== 00777 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 00778 inline bool 00779 operator!=(const map<_Key, _Tp, _Compare, _Alloc>& __x, 00780 const map<_Key, _Tp, _Compare, _Alloc>& __y) 00781 { return !(__x == __y); } 00782 00783 /// Based on operator< 00784 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 00785 inline bool 00786 operator>(const map<_Key, _Tp, _Compare, _Alloc>& __x, 00787 const map<_Key, _Tp, _Compare, _Alloc>& __y) 00788 { return __y < __x; } 00789 00790 /// Based on operator< 00791 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 00792 inline bool 00793 operator<=(const map<_Key, _Tp, _Compare, _Alloc>& __x, 00794 const map<_Key, _Tp, _Compare, _Alloc>& __y) 00795 { return !(__y < __x); } 00796 00797 /// Based on operator< 00798 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 00799 inline bool 00800 operator>=(const map<_Key, _Tp, _Compare, _Alloc>& __x, 00801 const map<_Key, _Tp, _Compare, _Alloc>& __y) 00802 { return !(__x < __y); } 00803 00804 /// See std::map::swap(). 00805 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 00806 inline void 00807 swap(map<_Key, _Tp, _Compare, _Alloc>& __x, 00808 map<_Key, _Tp, _Compare, _Alloc>& __y) 00809 { __x.swap(__y); } 00810 00811 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00812 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 00813 inline void 00814 swap(map<_Key, _Tp, _Compare, _Alloc>&& __x, 00815 map<_Key, _Tp, _Compare, _Alloc>& __y) 00816 { __x.swap(__y); } 00817 00818 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 00819 inline void 00820 swap(map<_Key, _Tp, _Compare, _Alloc>& __x, 00821 map<_Key, _Tp, _Compare, _Alloc>&& __y) 00822 { __x.swap(__y); } 00823 #endif 00824 00825 _GLIBCXX_END_NESTED_NAMESPACE 00826 00827 #endif /* _STL_MAP_H */