libstdc++
stl_map.h
Go to the documentation of this file.
00001 // Map implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2015 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 __gnu_cxx::__alloc_traits<_Alloc>::template
00132         rebind<value_type>::other _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       typedef __gnu_cxx::__alloc_traits<_Pair_alloc_type> _Alloc_traits;
00141 
00142     public:
00143       // many of these are specified differently in ISO, but the following are
00144       // "functionally equivalent"
00145       typedef typename _Alloc_traits::pointer            pointer;
00146       typedef typename _Alloc_traits::const_pointer      const_pointer;
00147       typedef typename _Alloc_traits::reference          reference;
00148       typedef typename _Alloc_traits::const_reference    const_reference;
00149       typedef typename _Rep_type::iterator               iterator;
00150       typedef typename _Rep_type::const_iterator         const_iterator;
00151       typedef typename _Rep_type::size_type              size_type;
00152       typedef typename _Rep_type::difference_type        difference_type;
00153       typedef typename _Rep_type::reverse_iterator       reverse_iterator;
00154       typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
00155 
00156       // [23.3.1.1] construct/copy/destroy
00157       // (get_allocator() is also listed in this section)
00158 
00159       /**
00160        *  @brief  Default constructor creates no elements.
00161        */
00162       map()
00163 #if __cplusplus >= 201103L
00164       noexcept(is_nothrow_default_constructible<allocator_type>::value)
00165 #endif
00166       : _M_t() { }
00167 
00168       /**
00169        *  @brief  Creates a %map with no elements.
00170        *  @param  __comp  A comparison object.
00171        *  @param  __a  An allocator object.
00172        */
00173       explicit
00174       map(const _Compare& __comp,
00175           const allocator_type& __a = allocator_type())
00176       : _M_t(__comp, _Pair_alloc_type(__a)) { }
00177 
00178       /**
00179        *  @brief  %Map copy constructor.
00180        *  @param  __x  A %map of identical element and allocator types.
00181        *
00182        *  The newly-created %map uses a copy of the allocation object
00183        *  used by @a __x.
00184        */
00185       map(const map& __x)
00186       : _M_t(__x._M_t) { }
00187 
00188 #if __cplusplus >= 201103L
00189       /**
00190        *  @brief  %Map move constructor.
00191        *  @param  __x  A %map of identical element and allocator types.
00192        *
00193        *  The newly-created %map contains the exact contents of @a __x.
00194        *  The contents of @a __x are a valid, but unspecified %map.
00195        */
00196       map(map&& __x)
00197       noexcept(is_nothrow_copy_constructible<_Compare>::value)
00198       : _M_t(std::move(__x._M_t)) { }
00199 
00200       /**
00201        *  @brief  Builds a %map from an initializer_list.
00202        *  @param  __l  An initializer_list.
00203        *  @param  __comp  A comparison object.
00204        *  @param  __a  An allocator object.
00205        *
00206        *  Create a %map consisting of copies of the elements in the
00207        *  initializer_list @a __l.
00208        *  This is linear in N if the range is already sorted, and NlogN
00209        *  otherwise (where N is @a __l.size()).
00210        */
00211       map(initializer_list<value_type> __l,
00212           const _Compare& __comp = _Compare(),
00213           const allocator_type& __a = allocator_type())
00214       : _M_t(__comp, _Pair_alloc_type(__a))
00215       { _M_t._M_insert_unique(__l.begin(), __l.end()); }
00216 
00217       /// Allocator-extended default constructor.
00218       explicit
00219       map(const allocator_type& __a)
00220       : _M_t(_Compare(), _Pair_alloc_type(__a)) { }
00221 
00222       /// Allocator-extended copy constructor.
00223       map(const map& __m, const allocator_type& __a)
00224       : _M_t(__m._M_t, _Pair_alloc_type(__a)) { }
00225 
00226       /// Allocator-extended move constructor.
00227       map(map&& __m, const allocator_type& __a)
00228       noexcept(is_nothrow_copy_constructible<_Compare>::value
00229                && _Alloc_traits::_S_always_equal())
00230       : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { }
00231 
00232       /// Allocator-extended initialier-list constructor.
00233       map(initializer_list<value_type> __l, const allocator_type& __a)
00234       : _M_t(_Compare(), _Pair_alloc_type(__a))
00235       { _M_t._M_insert_unique(__l.begin(), __l.end()); }
00236 
00237       /// Allocator-extended range constructor.
00238       template<typename _InputIterator>
00239         map(_InputIterator __first, _InputIterator __last,
00240             const allocator_type& __a)
00241         : _M_t(_Compare(), _Pair_alloc_type(__a))
00242         { _M_t._M_insert_unique(__first, __last); }
00243 #endif
00244 
00245       /**
00246        *  @brief  Builds a %map from a range.
00247        *  @param  __first  An input iterator.
00248        *  @param  __last  An input iterator.
00249        *
00250        *  Create a %map consisting of copies of the elements from
00251        *  [__first,__last).  This is linear in N if the range is
00252        *  already sorted, and NlogN otherwise (where N is
00253        *  distance(__first,__last)).
00254        */
00255       template<typename _InputIterator>
00256         map(_InputIterator __first, _InputIterator __last)
00257         : _M_t()
00258         { _M_t._M_insert_unique(__first, __last); }
00259 
00260       /**
00261        *  @brief  Builds a %map from a range.
00262        *  @param  __first  An input iterator.
00263        *  @param  __last  An input iterator.
00264        *  @param  __comp  A comparison functor.
00265        *  @param  __a  An allocator object.
00266        *
00267        *  Create a %map consisting of copies of the elements from
00268        *  [__first,__last).  This is linear in N if the range is
00269        *  already sorted, and NlogN otherwise (where N is
00270        *  distance(__first,__last)).
00271        */
00272       template<typename _InputIterator>
00273         map(_InputIterator __first, _InputIterator __last,
00274             const _Compare& __comp,
00275             const allocator_type& __a = allocator_type())
00276         : _M_t(__comp, _Pair_alloc_type(__a))
00277         { _M_t._M_insert_unique(__first, __last); }
00278 
00279       // FIXME There is no dtor declared, but we should have something
00280       // generated by Doxygen.  I don't know what tags to add to this
00281       // paragraph to make that happen:
00282       /**
00283        *  The dtor only erases the elements, and note that if the elements
00284        *  themselves are pointers, the pointed-to memory is not touched in any
00285        *  way.  Managing the pointer is the user's responsibility.
00286        */
00287 
00288       /**
00289        *  @brief  %Map assignment operator.
00290        *  @param  __x  A %map of identical element and allocator types.
00291        *
00292        *  All the elements of @a __x are copied, but unlike the copy
00293        *  constructor, the allocator object is not copied.
00294        */
00295       map&
00296       operator=(const map& __x)
00297       {
00298         _M_t = __x._M_t;
00299         return *this;
00300       }
00301 
00302 #if __cplusplus >= 201103L
00303       /// Move assignment operator.
00304       map&
00305       operator=(map&&) = default;
00306 
00307       /**
00308        *  @brief  %Map list assignment operator.
00309        *  @param  __l  An initializer_list.
00310        *
00311        *  This function fills a %map with copies of the elements in the
00312        *  initializer list @a __l.
00313        *
00314        *  Note that the assignment completely changes the %map and
00315        *  that the resulting %map's size is the same as the number
00316        *  of elements assigned.  Old data may be lost.
00317        */
00318       map&
00319       operator=(initializer_list<value_type> __l)
00320       {
00321         _M_t._M_assign_unique(__l.begin(), __l.end());
00322         return *this;
00323       }
00324 #endif
00325 
00326       /// Get a copy of the memory allocation object.
00327       allocator_type
00328       get_allocator() const _GLIBCXX_NOEXCEPT
00329       { return allocator_type(_M_t.get_allocator()); }
00330 
00331       // iterators
00332       /**
00333        *  Returns a read/write iterator that points to the first pair in the
00334        *  %map.
00335        *  Iteration is done in ascending order according to the keys.
00336        */
00337       iterator
00338       begin() _GLIBCXX_NOEXCEPT
00339       { return _M_t.begin(); }
00340 
00341       /**
00342        *  Returns a read-only (constant) iterator that points to the first pair
00343        *  in the %map.  Iteration is done in ascending order according to the
00344        *  keys.
00345        */
00346       const_iterator
00347       begin() const _GLIBCXX_NOEXCEPT
00348       { return _M_t.begin(); }
00349 
00350       /**
00351        *  Returns a read/write iterator that points one past the last
00352        *  pair in the %map.  Iteration is done in ascending order
00353        *  according to the keys.
00354        */
00355       iterator
00356       end() _GLIBCXX_NOEXCEPT
00357       { return _M_t.end(); }
00358 
00359       /**
00360        *  Returns a read-only (constant) iterator that points one past the last
00361        *  pair in the %map.  Iteration is done in ascending order according to
00362        *  the keys.
00363        */
00364       const_iterator
00365       end() const _GLIBCXX_NOEXCEPT
00366       { return _M_t.end(); }
00367 
00368       /**
00369        *  Returns a read/write reverse iterator that points to the last pair in
00370        *  the %map.  Iteration is done in descending order according to the
00371        *  keys.
00372        */
00373       reverse_iterator
00374       rbegin() _GLIBCXX_NOEXCEPT
00375       { return _M_t.rbegin(); }
00376 
00377       /**
00378        *  Returns a read-only (constant) reverse iterator that points to the
00379        *  last pair in the %map.  Iteration is done in descending order
00380        *  according to the keys.
00381        */
00382       const_reverse_iterator
00383       rbegin() const _GLIBCXX_NOEXCEPT
00384       { return _M_t.rbegin(); }
00385 
00386       /**
00387        *  Returns a read/write reverse iterator that points to one before the
00388        *  first pair in the %map.  Iteration is done in descending order
00389        *  according to the keys.
00390        */
00391       reverse_iterator
00392       rend() _GLIBCXX_NOEXCEPT
00393       { return _M_t.rend(); }
00394 
00395       /**
00396        *  Returns a read-only (constant) reverse iterator that points to one
00397        *  before the first pair in the %map.  Iteration is done in descending
00398        *  order according to the keys.
00399        */
00400       const_reverse_iterator
00401       rend() const _GLIBCXX_NOEXCEPT
00402       { return _M_t.rend(); }
00403 
00404 #if __cplusplus >= 201103L
00405       /**
00406        *  Returns a read-only (constant) iterator that points to the first pair
00407        *  in the %map.  Iteration is done in ascending order according to the
00408        *  keys.
00409        */
00410       const_iterator
00411       cbegin() const noexcept
00412       { return _M_t.begin(); }
00413 
00414       /**
00415        *  Returns a read-only (constant) iterator that points one past the last
00416        *  pair in the %map.  Iteration is done in ascending order according to
00417        *  the keys.
00418        */
00419       const_iterator
00420       cend() const noexcept
00421       { return _M_t.end(); }
00422 
00423       /**
00424        *  Returns a read-only (constant) reverse iterator that points to the
00425        *  last pair in the %map.  Iteration is done in descending order
00426        *  according to the keys.
00427        */
00428       const_reverse_iterator
00429       crbegin() const noexcept
00430       { return _M_t.rbegin(); }
00431 
00432       /**
00433        *  Returns a read-only (constant) reverse iterator that points to one
00434        *  before the first pair in the %map.  Iteration is done in descending
00435        *  order according to the keys.
00436        */
00437       const_reverse_iterator
00438       crend() const noexcept
00439       { return _M_t.rend(); }
00440 #endif
00441 
00442       // capacity
00443       /** Returns true if the %map is empty.  (Thus begin() would equal
00444        *  end().)
00445       */
00446       bool
00447       empty() const _GLIBCXX_NOEXCEPT
00448       { return _M_t.empty(); }
00449 
00450       /** Returns the size of the %map.  */
00451       size_type
00452       size() const _GLIBCXX_NOEXCEPT
00453       { return _M_t.size(); }
00454 
00455       /** Returns the maximum size of the %map.  */
00456       size_type
00457       max_size() const _GLIBCXX_NOEXCEPT
00458       { return _M_t.max_size(); }
00459 
00460       // [23.3.1.2] element access
00461       /**
00462        *  @brief  Subscript ( @c [] ) access to %map data.
00463        *  @param  __k  The key for which data should be retrieved.
00464        *  @return  A reference to the data of the (key,data) %pair.
00465        *
00466        *  Allows for easy lookup with the subscript ( @c [] )
00467        *  operator.  Returns data associated with the key specified in
00468        *  subscript.  If the key does not exist, a pair with that key
00469        *  is created using default values, which is then returned.
00470        *
00471        *  Lookup requires logarithmic time.
00472        */
00473       mapped_type&
00474       operator[](const key_type& __k)
00475       {
00476         // concept requirements
00477         __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)
00478 
00479         iterator __i = lower_bound(__k);
00480         // __i->first is greater than or equivalent to __k.
00481         if (__i == end() || key_comp()(__k, (*__i).first))
00482 #if __cplusplus >= 201103L
00483           __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct,
00484                                             std::tuple<const key_type&>(__k),
00485                                             std::tuple<>());
00486 #else
00487           __i = insert(__i, value_type(__k, mapped_type()));
00488 #endif
00489         return (*__i).second;
00490       }
00491 
00492 #if __cplusplus >= 201103L
00493       mapped_type&
00494       operator[](key_type&& __k)
00495       {
00496         // concept requirements
00497         __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)
00498 
00499         iterator __i = lower_bound(__k);
00500         // __i->first is greater than or equivalent to __k.
00501         if (__i == end() || key_comp()(__k, (*__i).first))
00502           __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct,
00503                                         std::forward_as_tuple(std::move(__k)),
00504                                         std::tuple<>());
00505         return (*__i).second;
00506       }
00507 #endif
00508 
00509       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00510       // DR 464. Suggestion for new member functions in standard containers.
00511       /**
00512        *  @brief  Access to %map data.
00513        *  @param  __k  The key for which data should be retrieved.
00514        *  @return  A reference to the data whose key is equivalent to @a __k, if
00515        *           such a data is present in the %map.
00516        *  @throw  std::out_of_range  If no such data is present.
00517        */
00518       mapped_type&
00519       at(const key_type& __k)
00520       {
00521         iterator __i = lower_bound(__k);
00522         if (__i == end() || key_comp()(__k, (*__i).first))
00523           __throw_out_of_range(__N("map::at"));
00524         return (*__i).second;
00525       }
00526 
00527       const mapped_type&
00528       at(const key_type& __k) const
00529       {
00530         const_iterator __i = lower_bound(__k);
00531         if (__i == end() || key_comp()(__k, (*__i).first))
00532           __throw_out_of_range(__N("map::at"));
00533         return (*__i).second;
00534       }
00535 
00536       // modifiers
00537 #if __cplusplus >= 201103L
00538       /**
00539        *  @brief Attempts to build and insert a std::pair into the %map.
00540        *
00541        *  @param __args  Arguments used to generate a new pair instance (see
00542        *                std::piecewise_contruct for passing arguments to each
00543        *                part of the pair constructor).
00544        *
00545        *  @return  A pair, of which the first element is an iterator that points
00546        *           to the possibly inserted pair, and the second is a bool that
00547        *           is true if the pair was actually inserted.
00548        *
00549        *  This function attempts to build and insert a (key, value) %pair into
00550        *  the %map.
00551        *  A %map relies on unique keys and thus a %pair is only inserted if its
00552        *  first element (the key) is not already present in the %map.
00553        *
00554        *  Insertion requires logarithmic time.
00555        */
00556       template<typename... _Args>
00557         std::pair<iterator, bool>
00558         emplace(_Args&&... __args)
00559         { return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); }
00560 
00561       /**
00562        *  @brief Attempts to build and insert a std::pair into the %map.
00563        *
00564        *  @param  __pos  An iterator that serves as a hint as to where the pair
00565        *                should be inserted.
00566        *  @param  __args  Arguments used to generate a new pair instance (see
00567        *                 std::piecewise_contruct for passing arguments to each
00568        *                 part of the pair constructor).
00569        *  @return An iterator that points to the element with key of the
00570        *          std::pair built from @a __args (may or may not be that
00571        *          std::pair).
00572        *
00573        *  This function is not concerned about whether the insertion took place,
00574        *  and thus does not return a boolean like the single-argument emplace()
00575        *  does.
00576        *  Note that the first parameter is only a hint and can potentially
00577        *  improve the performance of the insertion process. A bad hint would
00578        *  cause no gains in efficiency.
00579        *
00580        *  See
00581        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
00582        *  for more on @a hinting.
00583        *
00584        *  Insertion requires logarithmic time (if the hint is not taken).
00585        */
00586       template<typename... _Args>
00587         iterator
00588         emplace_hint(const_iterator __pos, _Args&&... __args)
00589         {
00590           return _M_t._M_emplace_hint_unique(__pos,
00591                                              std::forward<_Args>(__args)...);
00592         }
00593 #endif
00594 
00595       /**
00596        *  @brief Attempts to insert a std::pair into the %map.
00597 
00598        *  @param __x Pair to be inserted (see std::make_pair for easy
00599        *             creation of pairs).
00600        *
00601        *  @return  A pair, of which the first element is an iterator that 
00602        *           points to the possibly inserted pair, and the second is 
00603        *           a bool that is true if the pair was actually inserted.
00604        *
00605        *  This function attempts to insert a (key, value) %pair into the %map.
00606        *  A %map relies on unique keys and thus a %pair is only inserted if its
00607        *  first element (the key) is not already present in the %map.
00608        *
00609        *  Insertion requires logarithmic time.
00610        */
00611       std::pair<iterator, bool>
00612       insert(const value_type& __x)
00613       { return _M_t._M_insert_unique(__x); }
00614 
00615 #if __cplusplus >= 201103L
00616       template<typename _Pair, typename = typename
00617                std::enable_if<std::is_constructible<value_type,
00618                                                     _Pair&&>::value>::type>
00619         std::pair<iterator, bool>
00620         insert(_Pair&& __x)
00621         { return _M_t._M_insert_unique(std::forward<_Pair>(__x)); }
00622 #endif
00623 
00624 #if __cplusplus >= 201103L
00625       /**
00626        *  @brief Attempts to insert a list of std::pairs into the %map.
00627        *  @param  __list  A std::initializer_list<value_type> of pairs to be
00628        *                  inserted.
00629        *
00630        *  Complexity similar to that of the range constructor.
00631        */
00632       void
00633       insert(std::initializer_list<value_type> __list)
00634       { insert(__list.begin(), __list.end()); }
00635 #endif
00636 
00637       /**
00638        *  @brief Attempts to insert a std::pair into the %map.
00639        *  @param  __position  An iterator that serves as a hint as to where the
00640        *                    pair should be inserted.
00641        *  @param  __x  Pair to be inserted (see std::make_pair for easy creation
00642        *               of pairs).
00643        *  @return An iterator that points to the element with key of
00644        *           @a __x (may or may not be the %pair passed in).
00645        *
00646 
00647        *  This function is not concerned about whether the insertion
00648        *  took place, and thus does not return a boolean like the
00649        *  single-argument insert() does.  Note that the first
00650        *  parameter is only a hint and can potentially improve the
00651        *  performance of the insertion process.  A bad hint would
00652        *  cause no gains in efficiency.
00653        *
00654        *  See
00655        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
00656        *  for more on @a hinting.
00657        *
00658        *  Insertion requires logarithmic time (if the hint is not taken).
00659        */
00660       iterator
00661 #if __cplusplus >= 201103L
00662       insert(const_iterator __position, const value_type& __x)
00663 #else
00664       insert(iterator __position, const value_type& __x)
00665 #endif
00666       { return _M_t._M_insert_unique_(__position, __x); }
00667 
00668 #if __cplusplus >= 201103L
00669       template<typename _Pair, typename = typename
00670                std::enable_if<std::is_constructible<value_type,
00671                                                     _Pair&&>::value>::type>
00672         iterator
00673         insert(const_iterator __position, _Pair&& __x)
00674         { return _M_t._M_insert_unique_(__position,
00675                                         std::forward<_Pair>(__x)); }
00676 #endif
00677 
00678       /**
00679        *  @brief Template function that attempts to insert a range of elements.
00680        *  @param  __first  Iterator pointing to the start of the range to be
00681        *                   inserted.
00682        *  @param  __last  Iterator pointing to the end of the range.
00683        *
00684        *  Complexity similar to that of the range constructor.
00685        */
00686       template<typename _InputIterator>
00687         void
00688         insert(_InputIterator __first, _InputIterator __last)
00689         { _M_t._M_insert_unique(__first, __last); }
00690 
00691 #if __cplusplus >= 201103L
00692       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00693       // DR 130. Associative erase should return an iterator.
00694       /**
00695        *  @brief Erases an element from a %map.
00696        *  @param  __position  An iterator pointing to the element to be erased.
00697        *  @return An iterator pointing to the element immediately following
00698        *          @a position prior to the element being erased. If no such 
00699        *          element exists, end() is returned.
00700        *
00701        *  This function erases an element, pointed to by the given
00702        *  iterator, from a %map.  Note that this function only erases
00703        *  the element, and that if the element is itself a pointer,
00704        *  the pointed-to memory is not touched in any way.  Managing
00705        *  the pointer is the user's responsibility.
00706        */
00707       iterator
00708       erase(const_iterator __position)
00709       { return _M_t.erase(__position); }
00710 
00711       // LWG 2059
00712       _GLIBCXX_ABI_TAG_CXX11
00713       iterator
00714       erase(iterator __position)
00715       { return _M_t.erase(__position); }
00716 #else
00717       /**
00718        *  @brief Erases an element from a %map.
00719        *  @param  __position  An iterator pointing to the element to be erased.
00720        *
00721        *  This function erases an element, pointed to by the given
00722        *  iterator, from a %map.  Note that this function only erases
00723        *  the element, and that if the element is itself a pointer,
00724        *  the pointed-to memory is not touched in any way.  Managing
00725        *  the pointer is the user's responsibility.
00726        */
00727       void
00728       erase(iterator __position)
00729       { _M_t.erase(__position); }
00730 #endif
00731 
00732       /**
00733        *  @brief Erases elements according to the provided key.
00734        *  @param  __x  Key of element to be erased.
00735        *  @return  The number of elements erased.
00736        *
00737        *  This function erases all the elements located by the given key from
00738        *  a %map.
00739        *  Note that this function only erases the element, and that if
00740        *  the element is itself a pointer, the pointed-to memory is not touched
00741        *  in any way.  Managing the pointer is the user's responsibility.
00742        */
00743       size_type
00744       erase(const key_type& __x)
00745       { return _M_t.erase(__x); }
00746 
00747 #if __cplusplus >= 201103L
00748       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00749       // DR 130. Associative erase should return an iterator.
00750       /**
00751        *  @brief Erases a [first,last) range of elements from a %map.
00752        *  @param  __first  Iterator pointing to the start of the range to be
00753        *                   erased.
00754        *  @param __last Iterator pointing to the end of the range to
00755        *                be erased.
00756        *  @return The iterator @a __last.
00757        *
00758        *  This function erases a sequence of elements from a %map.
00759        *  Note that this function only erases the element, and that if
00760        *  the element is itself a pointer, the pointed-to memory is not touched
00761        *  in any way.  Managing the pointer is the user's responsibility.
00762        */
00763       iterator
00764       erase(const_iterator __first, const_iterator __last)
00765       { return _M_t.erase(__first, __last); }
00766 #else
00767       /**
00768        *  @brief Erases a [__first,__last) range of elements from a %map.
00769        *  @param  __first  Iterator pointing to the start of the range to be
00770        *                   erased.
00771        *  @param __last Iterator pointing to the end of the range to
00772        *                be erased.
00773        *
00774        *  This function erases a sequence of elements from a %map.
00775        *  Note that this function only erases the element, and that if
00776        *  the element is itself a pointer, the pointed-to memory is not touched
00777        *  in any way.  Managing the pointer is the user's responsibility.
00778        */
00779       void
00780       erase(iterator __first, iterator __last)
00781       { _M_t.erase(__first, __last); }
00782 #endif
00783 
00784       /**
00785        *  @brief  Swaps data with another %map.
00786        *  @param  __x  A %map of the same element and allocator types.
00787        *
00788        *  This exchanges the elements between two maps in constant
00789        *  time.  (It is only swapping a pointer, an integer, and an
00790        *  instance of the @c Compare type (which itself is often
00791        *  stateless and empty), so it should be quite fast.)  Note
00792        *  that the global std::swap() function is specialized such
00793        *  that std::swap(m1,m2) will feed to this function.
00794        */
00795       void
00796       swap(map& __x)
00797 #if __cplusplus >= 201103L
00798       noexcept(_Alloc_traits::_S_nothrow_swap())
00799 #endif
00800       { _M_t.swap(__x._M_t); }
00801 
00802       /**
00803        *  Erases all elements in a %map.  Note that this function only
00804        *  erases the elements, and that if the elements themselves are
00805        *  pointers, the pointed-to memory is not touched in any way.
00806        *  Managing the pointer is the user's responsibility.
00807        */
00808       void
00809       clear() _GLIBCXX_NOEXCEPT
00810       { _M_t.clear(); }
00811 
00812       // observers
00813       /**
00814        *  Returns the key comparison object out of which the %map was
00815        *  constructed.
00816        */
00817       key_compare
00818       key_comp() const
00819       { return _M_t.key_comp(); }
00820 
00821       /**
00822        *  Returns a value comparison object, built from the key comparison
00823        *  object out of which the %map was constructed.
00824        */
00825       value_compare
00826       value_comp() const
00827       { return value_compare(_M_t.key_comp()); }
00828 
00829       // [23.3.1.3] map operations
00830 
00831       //@{
00832       /**
00833        *  @brief Tries to locate an element in a %map.
00834        *  @param  __x  Key of (key, value) %pair to be located.
00835        *  @return  Iterator pointing to sought-after element, or end() if not
00836        *           found.
00837        *
00838        *  This function takes a key and tries to locate the element with which
00839        *  the key matches.  If successful the function returns an iterator
00840        *  pointing to the sought after %pair.  If unsuccessful it returns the
00841        *  past-the-end ( @c end() ) iterator.
00842        */
00843 
00844       iterator
00845       find(const key_type& __x)
00846       { return _M_t.find(__x); }
00847 
00848 #if __cplusplus > 201103L
00849       template<typename _Kt>
00850         auto
00851         find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x))
00852         { return _M_t._M_find_tr(__x); }
00853 #endif
00854       //@}
00855 
00856       //@{
00857       /**
00858        *  @brief Tries to locate an element in a %map.
00859        *  @param  __x  Key of (key, value) %pair to be located.
00860        *  @return  Read-only (constant) iterator pointing to sought-after
00861        *           element, or end() if not found.
00862        *
00863        *  This function takes a key and tries to locate the element with which
00864        *  the key matches.  If successful the function returns a constant
00865        *  iterator pointing to the sought after %pair. If unsuccessful it
00866        *  returns the past-the-end ( @c end() ) iterator.
00867        */
00868 
00869       const_iterator
00870       find(const key_type& __x) const
00871       { return _M_t.find(__x); }
00872 
00873 #if __cplusplus > 201103L
00874       template<typename _Kt>
00875         auto
00876         find(const _Kt& __x) const -> decltype(_M_t._M_find_tr(__x))
00877         { return _M_t._M_find_tr(__x); }
00878 #endif
00879       //@}
00880 
00881       //@{
00882       /**
00883        *  @brief  Finds the number of elements with given key.
00884        *  @param  __x  Key of (key, value) pairs to be located.
00885        *  @return  Number of elements with specified key.
00886        *
00887        *  This function only makes sense for multimaps; for map the result will
00888        *  either be 0 (not present) or 1 (present).
00889        */
00890       size_type
00891       count(const key_type& __x) const
00892       { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
00893 
00894 #if __cplusplus > 201103L
00895       template<typename _Kt>
00896         auto
00897         count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x))
00898         { return _M_t._M_find_tr(__x) == _M_t.end() ? 0 : 1; }
00899 #endif
00900       //@}
00901 
00902       //@{
00903       /**
00904        *  @brief Finds the beginning of a subsequence matching given key.
00905        *  @param  __x  Key of (key, value) pair to be located.
00906        *  @return  Iterator pointing to first element equal to or greater
00907        *           than key, or end().
00908        *
00909        *  This function returns the first element of a subsequence of elements
00910        *  that matches the given key.  If unsuccessful it returns an iterator
00911        *  pointing to the first element that has a greater value than given key
00912        *  or end() if no such element exists.
00913        */
00914       iterator
00915       lower_bound(const key_type& __x)
00916       { return _M_t.lower_bound(__x); }
00917 
00918 #if __cplusplus > 201103L
00919       template<typename _Kt>
00920         auto
00921         lower_bound(const _Kt& __x)
00922         -> decltype(_M_t._M_lower_bound_tr(__x))
00923         { return _M_t._M_lower_bound_tr(__x); }
00924 #endif
00925       //@}
00926 
00927       //@{
00928       /**
00929        *  @brief Finds the beginning of a subsequence matching given key.
00930        *  @param  __x  Key of (key, value) pair to be located.
00931        *  @return  Read-only (constant) iterator pointing to first element
00932        *           equal to or greater than key, or end().
00933        *
00934        *  This function returns the first element of a subsequence of elements
00935        *  that matches the given key.  If unsuccessful it returns an iterator
00936        *  pointing to the first element that has a greater value than given key
00937        *  or end() if no such element exists.
00938        */
00939       const_iterator
00940       lower_bound(const key_type& __x) const
00941       { return _M_t.lower_bound(__x); }
00942 
00943 #if __cplusplus > 201103L
00944       template<typename _Kt>
00945         auto
00946         lower_bound(const _Kt& __x) const
00947         -> decltype(_M_t._M_lower_bound_tr(__x))
00948         { return _M_t._M_lower_bound_tr(__x); }
00949 #endif
00950       //@}
00951 
00952       //@{
00953       /**
00954        *  @brief Finds the end of a subsequence matching given key.
00955        *  @param  __x  Key of (key, value) pair to be located.
00956        *  @return Iterator pointing to the first element
00957        *          greater than key, or end().
00958        */
00959       iterator
00960       upper_bound(const key_type& __x)
00961       { return _M_t.upper_bound(__x); }
00962 
00963 #if __cplusplus > 201103L
00964       template<typename _Kt>
00965         auto
00966         upper_bound(const _Kt& __x)
00967         -> decltype(_M_t._M_upper_bound_tr(__x))
00968         { return _M_t._M_upper_bound_tr(__x); }
00969 #endif
00970       //@}
00971 
00972       //@{
00973       /**
00974        *  @brief Finds the end of a subsequence matching given key.
00975        *  @param  __x  Key of (key, value) pair to be located.
00976        *  @return  Read-only (constant) iterator pointing to first iterator
00977        *           greater than key, or end().
00978        */
00979       const_iterator
00980       upper_bound(const key_type& __x) const
00981       { return _M_t.upper_bound(__x); }
00982 
00983 #if __cplusplus > 201103L
00984       template<typename _Kt>
00985         auto
00986         upper_bound(const _Kt& __x) const
00987         -> decltype(_M_t._M_upper_bound_tr(__x))
00988         { return _M_t._M_upper_bound_tr(__x); }
00989 #endif
00990       //@}
00991 
00992       //@{
00993       /**
00994        *  @brief Finds a subsequence matching given key.
00995        *  @param  __x  Key of (key, value) pairs to be located.
00996        *  @return  Pair of iterators that possibly points to the subsequence
00997        *           matching given key.
00998        *
00999        *  This function is equivalent to
01000        *  @code
01001        *    std::make_pair(c.lower_bound(val),
01002        *                   c.upper_bound(val))
01003        *  @endcode
01004        *  (but is faster than making the calls separately).
01005        *
01006        *  This function probably only makes sense for multimaps.
01007        */
01008       std::pair<iterator, iterator>
01009       equal_range(const key_type& __x)
01010       { return _M_t.equal_range(__x); }
01011 
01012 #if __cplusplus > 201103L
01013       template<typename _Kt>
01014         auto
01015         equal_range(const _Kt& __x)
01016         -> decltype(_M_t._M_equal_range_tr(__x))
01017         { return _M_t._M_equal_range_tr(__x); }
01018 #endif
01019       //@}
01020 
01021       //@{
01022       /**
01023        *  @brief Finds a subsequence matching given key.
01024        *  @param  __x  Key of (key, value) pairs to be located.
01025        *  @return  Pair of read-only (constant) iterators that possibly points
01026        *           to the subsequence matching given key.
01027        *
01028        *  This function is equivalent to
01029        *  @code
01030        *    std::make_pair(c.lower_bound(val),
01031        *                   c.upper_bound(val))
01032        *  @endcode
01033        *  (but is faster than making the calls separately).
01034        *
01035        *  This function probably only makes sense for multimaps.
01036        */
01037       std::pair<const_iterator, const_iterator>
01038       equal_range(const key_type& __x) const
01039       { return _M_t.equal_range(__x); }
01040 
01041 #if __cplusplus > 201103L
01042       template<typename _Kt>
01043         auto
01044         equal_range(const _Kt& __x) const
01045         -> decltype(_M_t._M_equal_range_tr(__x))
01046         { return _M_t._M_equal_range_tr(__x); }
01047 #endif
01048       //@}
01049 
01050       template<typename _K1, typename _T1, typename _C1, typename _A1>
01051         friend bool
01052         operator==(const map<_K1, _T1, _C1, _A1>&,
01053                    const map<_K1, _T1, _C1, _A1>&);
01054 
01055       template<typename _K1, typename _T1, typename _C1, typename _A1>
01056         friend bool
01057         operator<(const map<_K1, _T1, _C1, _A1>&,
01058                   const map<_K1, _T1, _C1, _A1>&);
01059     };
01060 
01061   /**
01062    *  @brief  Map equality comparison.
01063    *  @param  __x  A %map.
01064    *  @param  __y  A %map of the same type as @a x.
01065    *  @return  True iff the size and elements of the maps are equal.
01066    *
01067    *  This is an equivalence relation.  It is linear in the size of the
01068    *  maps.  Maps are considered equivalent if their sizes are equal,
01069    *  and if corresponding elements compare equal.
01070   */
01071   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
01072     inline bool
01073     operator==(const map<_Key, _Tp, _Compare, _Alloc>& __x,
01074                const map<_Key, _Tp, _Compare, _Alloc>& __y)
01075     { return __x._M_t == __y._M_t; }
01076 
01077   /**
01078    *  @brief  Map ordering relation.
01079    *  @param  __x  A %map.
01080    *  @param  __y  A %map of the same type as @a x.
01081    *  @return  True iff @a x is lexicographically less than @a y.
01082    *
01083    *  This is a total ordering relation.  It is linear in the size of the
01084    *  maps.  The elements must be comparable with @c <.
01085    *
01086    *  See std::lexicographical_compare() for how the determination is made.
01087   */
01088   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
01089     inline bool
01090     operator<(const map<_Key, _Tp, _Compare, _Alloc>& __x,
01091               const map<_Key, _Tp, _Compare, _Alloc>& __y)
01092     { return __x._M_t < __y._M_t; }
01093 
01094   /// Based on operator==
01095   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
01096     inline bool
01097     operator!=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
01098                const map<_Key, _Tp, _Compare, _Alloc>& __y)
01099     { return !(__x == __y); }
01100 
01101   /// Based on operator<
01102   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
01103     inline bool
01104     operator>(const map<_Key, _Tp, _Compare, _Alloc>& __x,
01105               const map<_Key, _Tp, _Compare, _Alloc>& __y)
01106     { return __y < __x; }
01107 
01108   /// Based on operator<
01109   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
01110     inline bool
01111     operator<=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
01112                const map<_Key, _Tp, _Compare, _Alloc>& __y)
01113     { return !(__y < __x); }
01114 
01115   /// Based on operator<
01116   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
01117     inline bool
01118     operator>=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
01119                const map<_Key, _Tp, _Compare, _Alloc>& __y)
01120     { return !(__x < __y); }
01121 
01122   /// See std::map::swap().
01123   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
01124     inline void
01125     swap(map<_Key, _Tp, _Compare, _Alloc>& __x,
01126          map<_Key, _Tp, _Compare, _Alloc>& __y)
01127     { __x.swap(__y); }
01128 
01129 _GLIBCXX_END_NAMESPACE_CONTAINER
01130 } // namespace std
01131 
01132 #endif /* _STL_MAP_H */