stl_map.h revision 117397
197403Sobrien// Map implementation -*- C++ -*- 297403Sobrien 397403Sobrien// Copyright (C) 2001, 2002 Free Software Foundation, Inc. 497403Sobrien// 597403Sobrien// This file is part of the GNU ISO C++ Library. This library is free 697403Sobrien// software; you can redistribute it and/or modify it under the 797403Sobrien// terms of the GNU General Public License as published by the 897403Sobrien// Free Software Foundation; either version 2, or (at your option) 997403Sobrien// any later version. 1097403Sobrien 1197403Sobrien// This library is distributed in the hope that it will be useful, 1297403Sobrien// but WITHOUT ANY WARRANTY; without even the implied warranty of 1397403Sobrien// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1497403Sobrien// GNU General Public License for more details. 1597403Sobrien 1697403Sobrien// You should have received a copy of the GNU General Public License along 1797403Sobrien// with this library; see the file COPYING. If not, write to the Free 1897403Sobrien// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 1997403Sobrien// USA. 2097403Sobrien 2197403Sobrien// As a special exception, you may use this file as part of a free software 2297403Sobrien// library without restriction. Specifically, if other files instantiate 2397403Sobrien// templates or use macros or inline functions from this file, or you compile 2497403Sobrien// this file and link it with other files to produce an executable, this 2597403Sobrien// file does not by itself cause the resulting executable to be covered by 2697403Sobrien// the GNU General Public License. This exception does not however 2797403Sobrien// invalidate any other reasons why the executable file might be covered by 2897403Sobrien// the GNU General Public License. 2997403Sobrien 3097403Sobrien/* 3197403Sobrien * 3297403Sobrien * Copyright (c) 1994 3397403Sobrien * Hewlett-Packard Company 3497403Sobrien * 3597403Sobrien * Permission to use, copy, modify, distribute and sell this software 3697403Sobrien * and its documentation for any purpose is hereby granted without fee, 3797403Sobrien * provided that the above copyright notice appear in all copies and 3897403Sobrien * that both that copyright notice and this permission notice appear 3997403Sobrien * in supporting documentation. Hewlett-Packard Company makes no 4097403Sobrien * representations about the suitability of this software for any 4197403Sobrien * purpose. It is provided "as is" without express or implied warranty. 4297403Sobrien * 4397403Sobrien * 4497403Sobrien * Copyright (c) 1996,1997 4597403Sobrien * Silicon Graphics Computer Systems, Inc. 4697403Sobrien * 4797403Sobrien * Permission to use, copy, modify, distribute and sell this software 4897403Sobrien * and its documentation for any purpose is hereby granted without fee, 4997403Sobrien * provided that the above copyright notice appear in all copies and 5097403Sobrien * that both that copyright notice and this permission notice appear 5197403Sobrien * in supporting documentation. Silicon Graphics makes no 5297403Sobrien * representations about the suitability of this software for any 5397403Sobrien * purpose. It is provided "as is" without express or implied warranty. 5497403Sobrien */ 5597403Sobrien 5697403Sobrien/** @file stl_map.h 5797403Sobrien * This is an internal header file, included by other library headers. 5897403Sobrien * You should not attempt to use it directly. 5997403Sobrien */ 6097403Sobrien 61117397Skan#ifndef __GLIBCPP_INTERNAL_MAP_H 62117397Skan#define __GLIBCPP_INTERNAL_MAP_H 6397403Sobrien 6497403Sobrien#include <bits/concept_check.h> 6597403Sobrien 6697403Sobriennamespace std 6797403Sobrien{ 6897403Sobrien /** 69117397Skan * @brief A standard container made up of (key,value) pairs, which can be 70117397Skan * retrieved based on a key, in logarithmic time. 7197403Sobrien * 72117397Skan * @ingroup Containers 73117397Skan * @ingroup Assoc_containers 7497403Sobrien * 75117397Skan * Meets the requirements of a <a href="tables.html#65">container</a>, a 76117397Skan * <a href="tables.html#66">reversible container</a>, and an 77117397Skan * <a href="tables.html#69">associative container</a> (using unique keys). 78117397Skan * For a @c map<Key,T> the key_type is Key, the mapped_type is T, and the 79117397Skan * value_type is std::pair<const Key,T>. 8097403Sobrien * 81117397Skan * Maps support bidirectional iterators. 8297403Sobrien * 83117397Skan * @if maint 84117397Skan * The private tree data is declared exactly the same way for map and 85117397Skan * multimap; the distinction is made entirely in how the tree functions are 86117397Skan * called (*_unique versus *_equal, same as the standard). 87117397Skan * @endif 8897403Sobrien */ 89117397Skan template <typename _Key, typename _Tp, typename _Compare = less<_Key>, 90117397Skan typename _Alloc = allocator<pair<const _Key, _Tp> > > 91117397Skan class map 92117397Skan { 93117397Skan // concept requirements 94117397Skan __glibcpp_class_requires(_Tp, _SGIAssignableConcept) 95117397Skan __glibcpp_class_requires4(_Compare, bool, _Key, _Key, _BinaryFunctionConcept) 96117397Skan 97117397Skan public: 98117397Skan typedef _Key key_type; 99117397Skan typedef _Tp mapped_type; 100117397Skan typedef pair<const _Key, _Tp> value_type; 101117397Skan typedef _Compare key_compare; 102117397Skan 103117397Skan class value_compare 104117397Skan : public binary_function<value_type, value_type, bool> 105117397Skan { 106117397Skan friend class map<_Key,_Tp,_Compare,_Alloc>; 107117397Skan protected: 108117397Skan _Compare comp; 109117397Skan value_compare(_Compare __c) : comp(__c) {} 110117397Skan public: 111117397Skan bool operator()(const value_type& __x, const value_type& __y) const 112117397Skan { return comp(__x.first, __y.first); } 113117397Skan }; 114117397Skan 115117397Skan private: 116117397Skan /// @if maint This turns a red-black tree into a [multi]map. @endif 117117397Skan typedef _Rb_tree<key_type, value_type, 118117397Skan _Select1st<value_type>, key_compare, _Alloc> _Rep_type; 119117397Skan /// @if maint The actual tree structure. @endif 120117397Skan _Rep_type _M_t; 121117397Skan 122117397Skan public: 123117397Skan // many of these are specified differently in ISO, but the following are 124117397Skan // "functionally equivalent" 125117397Skan typedef typename _Rep_type::allocator_type allocator_type; 126117397Skan typedef typename _Rep_type::reference reference; 127117397Skan typedef typename _Rep_type::const_reference const_reference; 128117397Skan typedef typename _Rep_type::iterator iterator; 129117397Skan typedef typename _Rep_type::const_iterator const_iterator; 130117397Skan typedef typename _Rep_type::size_type size_type; 131117397Skan typedef typename _Rep_type::difference_type difference_type; 132117397Skan typedef typename _Rep_type::pointer pointer; 133117397Skan typedef typename _Rep_type::const_pointer const_pointer; 134117397Skan typedef typename _Rep_type::reverse_iterator reverse_iterator; 135117397Skan typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 136117397Skan 137117397Skan 138117397Skan // [23.3.1.1] construct/copy/destroy 139117397Skan // (get_allocator() is normally listed in this section, but seems to have 140117397Skan // been accidentally omitted in the printed standard) 141117397Skan /** 142117397Skan * @brief Default constructor creates no elements. 143117397Skan */ 144117397Skan map() : _M_t(_Compare(), allocator_type()) { } 145117397Skan 146117397Skan // for some reason this was made a separate function 147117397Skan /** 148117397Skan * @brief Default constructor creates no elements. 149117397Skan */ 150117397Skan explicit 151117397Skan map(const _Compare& __comp, const allocator_type& __a = allocator_type()) 152117397Skan : _M_t(__comp, __a) { } 153117397Skan 154117397Skan /** 155117397Skan * @brief Map copy constructor. 156117397Skan * @param x A %map of identical element and allocator types. 157117397Skan * 158117397Skan * The newly-created %map uses a copy of the allocation object used 159117397Skan * by @a x. 160117397Skan */ 161117397Skan map(const map& __x) 162117397Skan : _M_t(__x._M_t) { } 163117397Skan 164117397Skan /** 165117397Skan * @brief Builds a %map from a range. 166117397Skan * @param first An input iterator. 167117397Skan * @param last An input iterator. 168117397Skan * 169117397Skan * Create a %map consisting of copies of the elements from [first,last). 170117397Skan * This is linear in N if the range is already sorted, and NlogN 171117397Skan * otherwise (where N is distance(first,last)). 172117397Skan */ 173117397Skan template <typename _InputIterator> 174117397Skan map(_InputIterator __first, _InputIterator __last) 175117397Skan : _M_t(_Compare(), allocator_type()) 176117397Skan { _M_t.insert_unique(__first, __last); } 177117397Skan 178117397Skan /** 179117397Skan * @brief Builds a %map from a range. 180117397Skan * @param first An input iterator. 181117397Skan * @param last An input iterator. 182117397Skan * @param comp A comparison functor. 183117397Skan * @param a An allocator object. 184117397Skan * 185117397Skan * Create a %map consisting of copies of the elements from [first,last). 186117397Skan * This is linear in N if the range is already sorted, and NlogN 187117397Skan * otherwise (where N is distance(first,last)). 188117397Skan */ 189117397Skan template <typename _InputIterator> 190117397Skan map(_InputIterator __first, _InputIterator __last, 191117397Skan const _Compare& __comp, const allocator_type& __a = allocator_type()) 192117397Skan : _M_t(__comp, __a) 193117397Skan { _M_t.insert_unique(__first, __last); } 194117397Skan 195117397Skan // FIXME There is no dtor declared, but we should have something generated 196117397Skan // by Doxygen. I don't know what tags to add to this paragraph to make 197117397Skan // that happen: 198117397Skan /** 199117397Skan * The dtor only erases the elements, and note that if the elements 200117397Skan * themselves are pointers, the pointed-to memory is not touched in any 201117397Skan * way. Managing the pointer is the user's responsibilty. 202117397Skan */ 203117397Skan 204117397Skan /** 205117397Skan * @brief Map assignment operator. 206117397Skan * @param x A %map of identical element and allocator types. 207117397Skan * 208117397Skan * All the elements of @a x are copied, but unlike the copy constructor, 209117397Skan * the allocator object is not copied. 210117397Skan */ 211117397Skan map& 212117397Skan operator=(const map& __x) 213117397Skan { 214117397Skan _M_t = __x._M_t; 215117397Skan return *this; 216117397Skan } 217117397Skan 218117397Skan /// Get a copy of the memory allocation object. 219117397Skan allocator_type 220117397Skan get_allocator() const { return _M_t.get_allocator(); } 221117397Skan 222117397Skan // iterators 223117397Skan /** 224117397Skan * Returns a read/write iterator that points to the first pair in the %map. 225117397Skan * Iteration is done in ascending order according to the keys. 226117397Skan */ 227117397Skan iterator 228117397Skan begin() { return _M_t.begin(); } 229117397Skan 230117397Skan /** 231117397Skan * Returns a read-only (constant) iterator that points to the first pair 232117397Skan * in the %map. Iteration is done in ascending order according to the 233117397Skan * keys. 234117397Skan */ 235117397Skan const_iterator 236117397Skan begin() const { return _M_t.begin(); } 237117397Skan 238117397Skan /** 239117397Skan * Returns a read/write iterator that points one past the last pair in the 240117397Skan * %map. Iteration is done in ascending order according to the keys. 241117397Skan */ 242117397Skan iterator 243117397Skan end() { return _M_t.end(); } 244117397Skan 245117397Skan /** 246117397Skan * Returns a read-only (constant) iterator that points one past the last 247117397Skan * pair in the %map. Iteration is done in ascending order according to the 248117397Skan * keys. 249117397Skan */ 250117397Skan const_iterator 251117397Skan end() const { return _M_t.end(); } 252117397Skan 253117397Skan /** 254117397Skan * Returns a read/write reverse iterator that points to the last pair in 255117397Skan * the %map. Iteration is done in descending order according to the keys. 256117397Skan */ 257117397Skan reverse_iterator 258117397Skan rbegin() { return _M_t.rbegin(); } 259117397Skan 260117397Skan /** 261117397Skan * Returns a read-only (constant) reverse iterator that points to the last 262117397Skan * pair in the %map. Iteration is done in descending order according to 263117397Skan * the keys. 264117397Skan */ 265117397Skan const_reverse_iterator 266117397Skan rbegin() const { return _M_t.rbegin(); } 267117397Skan 268117397Skan /** 269117397Skan * Returns a read/write reverse iterator that points to one before the 270117397Skan * first pair in the %map. Iteration is done in descending order according 271117397Skan * to the keys. 272117397Skan */ 273117397Skan reverse_iterator 274117397Skan rend() { return _M_t.rend(); } 275117397Skan 276117397Skan /** 277117397Skan * Returns a read-only (constant) reverse iterator that points to one 278117397Skan * before the first pair in the %map. Iteration is done in descending 279117397Skan * order according to the keys. 280117397Skan */ 281117397Skan const_reverse_iterator 282117397Skan rend() const { return _M_t.rend(); } 283117397Skan 284117397Skan // capacity 285117397Skan /** Returns true if the %map is empty. (Thus begin() would equal end().) */ 286117397Skan bool 287117397Skan empty() const { return _M_t.empty(); } 288117397Skan 289117397Skan /** Returns the size of the %map. */ 290117397Skan size_type 291117397Skan size() const { return _M_t.size(); } 292117397Skan 293117397Skan /** Returns the maximum size of the %map. */ 294117397Skan size_type 295117397Skan max_size() const { return _M_t.max_size(); } 296117397Skan 297117397Skan // [23.3.1.2] element access 298117397Skan /** 299117397Skan * @brief Subscript ( @c [] ) access to %map data. 300117397Skan * @param k The key for which data should be retrieved. 301117397Skan * @return A reference to the data of the (key,data) %pair. 302117397Skan * 303117397Skan * Allows for easy lookup with the subscript ( @c [] ) operator. Returns 304117397Skan * data associated with the key specified in subscript. If the key does 305117397Skan * not exist, a pair with that key is created using default values, which 306117397Skan * is then returned. 307117397Skan * 308117397Skan * Lookup requires logarithmic time. 309117397Skan */ 310117397Skan mapped_type& 311117397Skan operator[](const key_type& __k) 312117397Skan { 313117397Skan // concept requirements 314117397Skan __glibcpp_function_requires(_DefaultConstructibleConcept<mapped_type>) 315117397Skan 316117397Skan iterator __i = lower_bound(__k); 317117397Skan // __i->first is greater than or equivalent to __k. 318117397Skan if (__i == end() || key_comp()(__k, (*__i).first)) 319117397Skan __i = insert(__i, value_type(__k, mapped_type())); 320117397Skan return (*__i).second; 321117397Skan } 322117397Skan 323117397Skan // modifiers 324117397Skan /** 325117397Skan * @brief Attempts to insert a std::pair into the %map. 326117397Skan * @param x Pair to be inserted (see std::make_pair for easy creation of 327117397Skan * pairs). 328117397Skan * @return A pair, of which the first element is an iterator that points 329117397Skan * to the possibly inserted pair, and the second is a bool that 330117397Skan * is true if the pair was actually inserted. 331117397Skan * 332117397Skan * This function attempts to insert a (key, value) %pair into the %map. 333117397Skan * A %map relies on unique keys and thus a %pair is only inserted if its 334117397Skan * first element (the key) is not already present in the %map. 335117397Skan * 336117397Skan * Insertion requires logarithmic time. 337117397Skan */ 338117397Skan pair<iterator,bool> 339117397Skan insert(const value_type& __x) 340117397Skan { return _M_t.insert_unique(__x); } 341117397Skan 342117397Skan /** 343117397Skan * @brief Attempts to insert a std::pair into the %map. 344117397Skan * @param position An iterator that serves as a hint as to where the 345117397Skan * pair should be inserted. 346117397Skan * @param x Pair to be inserted (see std::make_pair for easy creation of 347117397Skan * pairs). 348117397Skan * @return An iterator that points to the element with key of @a x (may 349117397Skan * or may not be the %pair passed in). 350117397Skan * 351117397Skan * This function is not concerned about whether the insertion took place, 352117397Skan * and thus does not return a boolean like the single-argument 353117397Skan * insert() does. Note that the first parameter is only a hint and can 354117397Skan * potentially improve the performance of the insertion process. A bad 355117397Skan * hint would cause no gains in efficiency. 356117397Skan * 357117397Skan * See http://gcc.gnu.org/onlinedocs/libstdc++/23_containers/howto.html#4 358117397Skan * for more on "hinting". 359117397Skan * 360117397Skan * Insertion requires logarithmic time (if the hint is not taken). 361117397Skan */ 362117397Skan iterator 363117397Skan insert(iterator position, const value_type& __x) 364117397Skan { return _M_t.insert_unique(position, __x); } 365117397Skan 366117397Skan /** 367117397Skan * @brief A template function that attemps to insert a range of elements. 368117397Skan * @param first Iterator pointing to the start of the range to be 369117397Skan * inserted. 370117397Skan * @param last Iterator pointing to the end of the range. 371117397Skan * 372117397Skan * Complexity similar to that of the range constructor. 373117397Skan */ 374117397Skan template <typename _InputIterator> 375117397Skan void 376117397Skan insert(_InputIterator __first, _InputIterator __last) 377117397Skan { _M_t.insert_unique(__first, __last); } 378117397Skan 379117397Skan /** 380117397Skan * @brief Erases an element from a %map. 381117397Skan * @param position An iterator pointing to the element to be erased. 382117397Skan * 383117397Skan * This function erases an element, pointed to by the given iterator, from 384117397Skan * a %map. Note that this function only erases the element, and that if 385117397Skan * the element is itself a pointer, the pointed-to memory is not touched 386117397Skan * in any way. Managing the pointer is the user's responsibilty. 387117397Skan */ 388117397Skan void 389117397Skan erase(iterator __position) { _M_t.erase(__position); } 390117397Skan 391117397Skan /** 392117397Skan * @brief Erases elements according to the provided key. 393117397Skan * @param x Key of element to be erased. 394117397Skan * @return The number of elements erased. 395117397Skan * 396117397Skan * This function erases all the elements located by the given key from 397117397Skan * a %map. 398117397Skan * Note that this function only erases the element, and that if 399117397Skan * the element is itself a pointer, the pointed-to memory is not touched 400117397Skan * in any way. Managing the pointer is the user's responsibilty. 401117397Skan */ 402117397Skan size_type 403117397Skan erase(const key_type& __x) { return _M_t.erase(__x); } 404117397Skan 405117397Skan /** 406117397Skan * @brief Erases a [first,last) range of elements from a %map. 407117397Skan * @param first Iterator pointing to the start of the range to be erased. 408117397Skan * @param last Iterator pointing to the end of the range to be erased. 409117397Skan * 410117397Skan * This function erases a sequence of elements from a %map. 411117397Skan * Note that this function only erases the element, and that if 412117397Skan * the element is itself a pointer, the pointed-to memory is not touched 413117397Skan * in any way. Managing the pointer is the user's responsibilty. 414117397Skan */ 415117397Skan void 416117397Skan erase(iterator __first, iterator __last) { _M_t.erase(__first, __last); } 417117397Skan 418117397Skan /** 419117397Skan * @brief Swaps data with another %map. 420117397Skan * @param x A %map of the same element and allocator types. 421117397Skan * 422117397Skan * This exchanges the elements between two maps in constant time. 423117397Skan * (It is only swapping a pointer, an integer, and an instance of 424117397Skan * the @c Compare type (which itself is often stateless and empty), so it 425117397Skan * should be quite fast.) 426117397Skan * Note that the global std::swap() function is specialized such that 427117397Skan * std::swap(m1,m2) will feed to this function. 428117397Skan */ 429117397Skan void 430117397Skan swap(map& __x) { _M_t.swap(__x._M_t); } 431117397Skan 432117397Skan /** 433117397Skan * Erases all elements in a %map. Note that this function only erases 434117397Skan * the elements, and that if the elements themselves are pointers, the 435117397Skan * pointed-to memory is not touched in any way. Managing the pointer is 436117397Skan * the user's responsibilty. 437117397Skan */ 438117397Skan void 439117397Skan clear() { _M_t.clear(); } 440117397Skan 441117397Skan // observers 442117397Skan /** 443117397Skan * Returns the key comparison object out of which the %map was constructed. 444117397Skan */ 445117397Skan key_compare 446117397Skan key_comp() const { return _M_t.key_comp(); } 447117397Skan 448117397Skan /** 449117397Skan * Returns a value comparison object, built from the key comparison 450117397Skan * object out of which the %map was constructed. 451117397Skan */ 452117397Skan value_compare 453117397Skan value_comp() const { return value_compare(_M_t.key_comp()); } 454117397Skan 455117397Skan // [23.3.1.3] map operations 456117397Skan /** 457117397Skan * @brief Tries to locate an element in a %map. 458117397Skan * @param x Key of (key, value) %pair to be located. 459117397Skan * @return Iterator pointing to sought-after element, or end() if not 460117397Skan * found. 461117397Skan * 462117397Skan * This function takes a key and tries to locate the element with which 463117397Skan * the key matches. If successful the function returns an iterator 464117397Skan * pointing to the sought after %pair. If unsuccessful it returns the 465117397Skan * past-the-end ( @c end() ) iterator. 466117397Skan */ 467117397Skan iterator 468117397Skan find(const key_type& __x) { return _M_t.find(__x); } 469117397Skan 470117397Skan /** 471117397Skan * @brief Tries to locate an element in a %map. 472117397Skan * @param x Key of (key, value) %pair to be located. 473117397Skan * @return Read-only (constant) iterator pointing to sought-after 474117397Skan * element, or end() if not found. 475117397Skan * 476117397Skan * This function takes a key and tries to locate the element with which 477117397Skan * the key matches. If successful the function returns a constant iterator 478117397Skan * pointing to the sought after %pair. If unsuccessful it returns the 479117397Skan * past-the-end ( @c end() ) iterator. 480117397Skan */ 481117397Skan const_iterator 482117397Skan find(const key_type& __x) const { return _M_t.find(__x); } 483117397Skan 484117397Skan /** 485117397Skan * @brief Finds the number of elements with given key. 486117397Skan * @param x Key of (key, value) pairs to be located. 487117397Skan * @return Number of elements with specified key. 488117397Skan * 489117397Skan * This function only makes sense for multimaps; for map the result will 490117397Skan * either be 0 (not present) or 1 (present). 491117397Skan */ 492117397Skan size_type 493117397Skan count(const key_type& __x) const 494117397Skan { return _M_t.find(__x) == _M_t.end() ? 0 : 1; } 495117397Skan 496117397Skan /** 497117397Skan * @brief Finds the beginning of a subsequence matching given key. 498117397Skan * @param x Key of (key, value) pair to be located. 499117397Skan * @return Iterator pointing to first element matching given key, or 500117397Skan * end() if not found. 501117397Skan * 502117397Skan * This function is useful only with multimaps. It returns the first 503117397Skan * element of a subsequence of elements that matches the given key. If 504117397Skan * unsuccessful it returns an iterator pointing to the first element that 505117397Skan * has a greater value than given key or end() if no such element exists. 506117397Skan */ 507117397Skan iterator 508117397Skan lower_bound(const key_type& __x) { return _M_t.lower_bound(__x); } 509117397Skan 510117397Skan /** 511117397Skan * @brief Finds the beginning of a subsequence matching given key. 512117397Skan * @param x Key of (key, value) pair to be located. 513117397Skan * @return Read-only (constant) iterator pointing to first element 514117397Skan * matching given key, or end() if not found. 515117397Skan * 516117397Skan * This function is useful only with multimaps. It returns the first 517117397Skan * element of a subsequence of elements that matches the given key. If 518117397Skan * unsuccessful the iterator will point to the next greatest element or, 519117397Skan * if no such greater element exists, to end(). 520117397Skan */ 521117397Skan const_iterator 522117397Skan lower_bound(const key_type& __x) const { return _M_t.lower_bound(__x); } 523117397Skan 524117397Skan /** 525117397Skan * @brief Finds the end of a subsequence matching given key. 526117397Skan * @param x Key of (key, value) pair to be located. 527117397Skan * @return Iterator pointing to last element matching given key. 528117397Skan * 529117397Skan * This function only makes sense with multimaps. 530117397Skan */ 531117397Skan iterator 532117397Skan upper_bound(const key_type& __x) { return _M_t.upper_bound(__x); } 533117397Skan 534117397Skan /** 535117397Skan * @brief Finds the end of a subsequence matching given key. 536117397Skan * @param x Key of (key, value) pair to be located. 537117397Skan * @return Read-only (constant) iterator pointing to last element matching 538117397Skan * given key. 539117397Skan * 540117397Skan * This function only makes sense with multimaps. 541117397Skan */ 542117397Skan const_iterator 543117397Skan upper_bound(const key_type& __x) const 544117397Skan { return _M_t.upper_bound(__x); } 545117397Skan 546117397Skan /** 547117397Skan * @brief Finds a subsequence matching given key. 548117397Skan * @param x Key of (key, value) pairs to be located. 549117397Skan * @return Pair of iterators that possibly points to the subsequence 550117397Skan * matching given key. 551117397Skan * 552117397Skan * This function returns a pair of which the first 553117397Skan * element possibly points to the first element matching the given key 554117397Skan * and the second element possibly points to the last element matching the 555117397Skan * given key. If unsuccessful the first element of the returned pair will 556117397Skan * contain an iterator pointing to the next greatest element or, if no such 557117397Skan * greater element exists, to end(). 558117397Skan * 559117397Skan * This function only makes sense for multimaps. 560117397Skan */ 561117397Skan pair<iterator,iterator> 562117397Skan equal_range(const key_type& __x) 563117397Skan { return _M_t.equal_range(__x); } 564117397Skan 565117397Skan /** 566117397Skan * @brief Finds a subsequence matching given key. 567117397Skan * @param x Key of (key, value) pairs to be located. 568117397Skan * @return Pair of read-only (constant) iterators that possibly points to 569117397Skan * the subsequence matching given key. 570117397Skan * 571117397Skan * This function returns a pair of which the first 572117397Skan * element possibly points to the first element matching the given key 573117397Skan * and the second element possibly points to the last element matching the 574117397Skan * given key. If unsuccessful the first element of the returned pair will 575117397Skan * contain an iterator pointing to the next greatest element or, if no such 576117397Skan * a greater element exists, to end(). 577117397Skan * 578117397Skan * This function only makes sense for multimaps. 579117397Skan */ 580117397Skan pair<const_iterator,const_iterator> 581117397Skan equal_range(const key_type& __x) const 582117397Skan { return _M_t.equal_range(__x); } 583117397Skan 584117397Skan template <typename _K1, typename _T1, typename _C1, typename _A1> 585117397Skan friend bool operator== (const map<_K1,_T1,_C1,_A1>&, 586117397Skan const map<_K1,_T1,_C1,_A1>&); 587117397Skan template <typename _K1, typename _T1, typename _C1, typename _A1> 588117397Skan friend bool operator< (const map<_K1,_T1,_C1,_A1>&, 589117397Skan const map<_K1,_T1,_C1,_A1>&); 590117397Skan }; 591117397Skan 592117397Skan 59397403Sobrien /** 594117397Skan * @brief Map equality comparison. 595117397Skan * @param x A %map. 596117397Skan * @param y A %map of the same type as @a x. 597117397Skan * @return True iff the size and elements of the maps are equal. 59897403Sobrien * 599117397Skan * This is an equivalence relation. It is linear in the size of the 600117397Skan * maps. Maps are considered equivalent if their sizes are equal, 601117397Skan * and if corresponding elements compare equal. 60297403Sobrien */ 603117397Skan template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 604117397Skan inline bool 605117397Skan operator==(const map<_Key,_Tp,_Compare,_Alloc>& __x, 606117397Skan const map<_Key,_Tp,_Compare,_Alloc>& __y) 607117397Skan { return __x._M_t == __y._M_t; } 608117397Skan 60997403Sobrien /** 610117397Skan * @brief Map ordering relation. 611117397Skan * @param x A %map. 612117397Skan * @param y A %map of the same type as @a x. 613117397Skan * @return True iff @a x is lexographically less than @a y. 61497403Sobrien * 615117397Skan * This is a total ordering relation. It is linear in the size of the 616117397Skan * maps. The elements must be comparable with @c <. 61797403Sobrien * 618117397Skan * See std::lexographical_compare() for how the determination is made. 61997403Sobrien */ 620117397Skan template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 621117397Skan inline bool 622117397Skan operator<(const map<_Key,_Tp,_Compare,_Alloc>& __x, 623117397Skan const map<_Key,_Tp,_Compare,_Alloc>& __y) 624117397Skan { return __x._M_t < __y._M_t; } 625117397Skan 626117397Skan /// Based on operator== 627117397Skan template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 628117397Skan inline bool 629117397Skan operator!=(const map<_Key,_Tp,_Compare,_Alloc>& __x, 630117397Skan const map<_Key,_Tp,_Compare,_Alloc>& __y) 631117397Skan { return !(__x == __y); } 632117397Skan 633117397Skan /// Based on operator< 634117397Skan template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 635117397Skan inline bool 636117397Skan operator>(const map<_Key,_Tp,_Compare,_Alloc>& __x, 637117397Skan const map<_Key,_Tp,_Compare,_Alloc>& __y) 638117397Skan { return __y < __x; } 639117397Skan 640117397Skan /// Based on operator< 641117397Skan template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 642117397Skan inline bool 643117397Skan operator<=(const map<_Key,_Tp,_Compare,_Alloc>& __x, 644117397Skan const map<_Key,_Tp,_Compare,_Alloc>& __y) 645117397Skan { return !(__y < __x); } 646117397Skan 647117397Skan /// Based on operator< 648117397Skan template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 649117397Skan inline bool 650117397Skan operator>=(const map<_Key,_Tp,_Compare,_Alloc>& __x, 651117397Skan const map<_Key,_Tp,_Compare,_Alloc>& __y) 652117397Skan { return !(__x < __y); } 653117397Skan 654117397Skan /// See std::map::swap(). 655117397Skan template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 656117397Skan inline void 657117397Skan swap(map<_Key,_Tp,_Compare,_Alloc>& __x, map<_Key,_Tp,_Compare,_Alloc>& __y) 658117397Skan { __x.swap(__y); } 65997403Sobrien} // namespace std 66097403Sobrien 661117397Skan#endif /* __GLIBCPP_INTERNAL_MAP_H */ 662