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