libstdc++
stl_map.h
Go to the documentation of this file.
00001 // Map implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2016 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       _GLIBCXX_NOEXCEPT_IF(
00164           is_nothrow_default_constructible<allocator_type>::value
00165           && is_nothrow_default_constructible<key_compare>::value)
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 #if __cplusplus > 201402L
00596 #define __cpp_lib_map_try_emplace 201411
00597       /**
00598        *  @brief Attempts to build and insert a std::pair into the %map.
00599        *
00600        *  @param __k    Key to use for finding a possibly existing pair in
00601        *                the map.
00602        *  @param __args  Arguments used to generate the .second for a new pair 
00603        *                instance.
00604        *
00605        *  @return  A pair, of which the first element is an iterator that points
00606        *           to the possibly inserted pair, and the second is a bool that
00607        *           is true if the pair was actually inserted.
00608        *
00609        *  This function attempts to build and insert a (key, value) %pair into
00610        *  the %map.
00611        *  A %map relies on unique keys and thus a %pair is only inserted if its
00612        *  first element (the key) is not already present in the %map.
00613        *  If a %pair is not inserted, this function has no effect.
00614        *
00615        *  Insertion requires logarithmic time.
00616        */
00617       template <typename... _Args>
00618         pair<iterator, bool>
00619         try_emplace(const key_type& __k, _Args&&... __args)
00620         {
00621           iterator __i = lower_bound(__k);
00622           if (__i == end() || key_comp()(__k, (*__i).first))
00623             {
00624               __i = emplace_hint(__i, std::piecewise_construct,
00625                                  std::forward_as_tuple(__k),
00626                                  std::forward_as_tuple(
00627                                    std::forward<_Args>(__args)...));
00628               return {__i, true};
00629             }
00630           return {__i, false};
00631         }
00632 
00633       // move-capable overload
00634       template <typename... _Args>
00635         pair<iterator, bool>
00636         try_emplace(key_type&& __k, _Args&&... __args)
00637         {
00638           iterator __i = lower_bound(__k);
00639           if (__i == end() || key_comp()(__k, (*__i).first))
00640             {
00641               __i = emplace_hint(__i, std::piecewise_construct,
00642                                  std::forward_as_tuple(std::move(__k)),
00643                                  std::forward_as_tuple(
00644                                    std::forward<_Args>(__args)...));
00645               return {__i, true};
00646             }
00647           return {__i, false};
00648         }
00649 
00650       /**
00651        *  @brief Attempts to build and insert a std::pair into the %map.
00652        *
00653        *  @param  __hint  An iterator that serves as a hint as to where the
00654        *                  pair should be inserted.
00655        *  @param __k    Key to use for finding a possibly existing pair in
00656        *                the map.
00657        *  @param __args  Arguments used to generate the .second for a new pair 
00658        *                instance.
00659        *  @return An iterator that points to the element with key of the
00660        *          std::pair built from @a __args (may or may not be that
00661        *          std::pair).
00662        *
00663        *  This function is not concerned about whether the insertion took place,
00664        *  and thus does not return a boolean like the single-argument 
00665        *  try_emplace() does. However, if insertion did not take place,
00666        *  this function has no effect.
00667        *  Note that the first parameter is only a hint and can potentially
00668        *  improve the performance of the insertion process. A bad hint would
00669        *  cause no gains in efficiency.
00670        *
00671        *  See
00672        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
00673        *  for more on @a hinting.
00674        *
00675        *  Insertion requires logarithmic time (if the hint is not taken).
00676        */
00677       template <typename... _Args>
00678         iterator
00679         try_emplace(const_iterator __hint, const key_type& __k,
00680                     _Args&&... __args)
00681         {
00682           iterator __i;
00683           auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);
00684           if (__true_hint.second)
00685             __i = emplace_hint(iterator(__true_hint.second),
00686                                std::piecewise_construct,
00687                                std::forward_as_tuple(__k),
00688                                std::forward_as_tuple(
00689                                  std::forward<_Args>(__args)...));
00690           else
00691             __i = iterator(__true_hint.first);
00692           return __i;
00693         }
00694 
00695       // move-capable overload
00696       template <typename... _Args>
00697         iterator
00698         try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
00699         {
00700           iterator __i;
00701           auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);
00702           if (__true_hint.second)
00703             __i = emplace_hint(iterator(__true_hint.second),
00704                                std::piecewise_construct,
00705                                std::forward_as_tuple(std::move(__k)),
00706                                std::forward_as_tuple(
00707                                  std::forward<_Args>(__args)...));
00708           else
00709             __i = iterator(__true_hint.first);
00710           return __i;
00711         }
00712 #endif
00713 
00714       /**
00715        *  @brief Attempts to insert a std::pair into the %map.
00716 
00717        *  @param __x Pair to be inserted (see std::make_pair for easy
00718        *             creation of pairs).
00719        *
00720        *  @return  A pair, of which the first element is an iterator that 
00721        *           points to the possibly inserted pair, and the second is 
00722        *           a bool that is true if the pair was actually inserted.
00723        *
00724        *  This function attempts to insert a (key, value) %pair into the %map.
00725        *  A %map relies on unique keys and thus a %pair is only inserted if its
00726        *  first element (the key) is not already present in the %map.
00727        *
00728        *  Insertion requires logarithmic time.
00729        */
00730       std::pair<iterator, bool>
00731       insert(const value_type& __x)
00732       { return _M_t._M_insert_unique(__x); }
00733 
00734 #if __cplusplus >= 201103L
00735       template<typename _Pair, typename = typename
00736                std::enable_if<std::is_constructible<value_type,
00737                                                     _Pair&&>::value>::type>
00738         std::pair<iterator, bool>
00739         insert(_Pair&& __x)
00740         { return _M_t._M_insert_unique(std::forward<_Pair>(__x)); }
00741 #endif
00742 
00743 #if __cplusplus >= 201103L
00744       /**
00745        *  @brief Attempts to insert a list of std::pairs into the %map.
00746        *  @param  __list  A std::initializer_list<value_type> of pairs to be
00747        *                  inserted.
00748        *
00749        *  Complexity similar to that of the range constructor.
00750        */
00751       void
00752       insert(std::initializer_list<value_type> __list)
00753       { insert(__list.begin(), __list.end()); }
00754 #endif
00755 
00756       /**
00757        *  @brief Attempts to insert a std::pair into the %map.
00758        *  @param  __position  An iterator that serves as a hint as to where the
00759        *                    pair should be inserted.
00760        *  @param  __x  Pair to be inserted (see std::make_pair for easy creation
00761        *               of pairs).
00762        *  @return An iterator that points to the element with key of
00763        *           @a __x (may or may not be the %pair passed in).
00764        *
00765 
00766        *  This function is not concerned about whether the insertion
00767        *  took place, and thus does not return a boolean like the
00768        *  single-argument insert() does.  Note that the first
00769        *  parameter is only a hint and can potentially improve the
00770        *  performance of the insertion process.  A bad hint would
00771        *  cause no gains in efficiency.
00772        *
00773        *  See
00774        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
00775        *  for more on @a hinting.
00776        *
00777        *  Insertion requires logarithmic time (if the hint is not taken).
00778        */
00779       iterator
00780 #if __cplusplus >= 201103L
00781       insert(const_iterator __position, const value_type& __x)
00782 #else
00783       insert(iterator __position, const value_type& __x)
00784 #endif
00785       { return _M_t._M_insert_unique_(__position, __x); }
00786 
00787 #if __cplusplus >= 201103L
00788       template<typename _Pair, typename = typename
00789                std::enable_if<std::is_constructible<value_type,
00790                                                     _Pair&&>::value>::type>
00791         iterator
00792         insert(const_iterator __position, _Pair&& __x)
00793         { return _M_t._M_insert_unique_(__position,
00794                                         std::forward<_Pair>(__x)); }
00795 #endif
00796 
00797       /**
00798        *  @brief Template function that attempts to insert a range of elements.
00799        *  @param  __first  Iterator pointing to the start of the range to be
00800        *                   inserted.
00801        *  @param  __last  Iterator pointing to the end of the range.
00802        *
00803        *  Complexity similar to that of the range constructor.
00804        */
00805       template<typename _InputIterator>
00806         void
00807         insert(_InputIterator __first, _InputIterator __last)
00808         { _M_t._M_insert_unique(__first, __last); }
00809 
00810 #if __cplusplus > 201402L
00811 #define __cpp_lib_map_insertion 201411
00812       /**
00813        *  @brief Attempts to insert or assign a std::pair into the %map.
00814        *  @param __k    Key to use for finding a possibly existing pair in
00815        *                the map.
00816        *  @param __obj  Argument used to generate the .second for a pair 
00817        *                instance.
00818        *
00819        *  @return  A pair, of which the first element is an iterator that 
00820        *           points to the possibly inserted pair, and the second is 
00821        *           a bool that is true if the pair was actually inserted.
00822        *
00823        *  This function attempts to insert a (key, value) %pair into the %map.
00824        *  A %map relies on unique keys and thus a %pair is only inserted if its
00825        *  first element (the key) is not already present in the %map.
00826        *  If the %pair was already in the %map, the .second of the %pair
00827        *  is assigned from __obj.
00828        *
00829        *  Insertion requires logarithmic time.
00830        */
00831       template <typename _Obj>
00832         pair<iterator, bool>
00833         insert_or_assign(const key_type& __k, _Obj&& __obj)
00834         {
00835           iterator __i = lower_bound(__k);
00836           if (__i == end() || key_comp()(__k, (*__i).first))
00837             {
00838               __i = emplace_hint(__i, std::piecewise_construct,
00839                                  std::forward_as_tuple(__k),
00840                                  std::forward_as_tuple(
00841                                    std::forward<_Obj>(__obj)));
00842               return {__i, true};
00843             }
00844           (*__i).second = std::forward<_Obj>(__obj);
00845           return {__i, false};
00846         }
00847 
00848       // move-capable overload
00849       template <typename _Obj>
00850         pair<iterator, bool>
00851         insert_or_assign(key_type&& __k, _Obj&& __obj)
00852         {
00853           iterator __i = lower_bound(__k);
00854           if (__i == end() || key_comp()(__k, (*__i).first))
00855             {
00856               __i = emplace_hint(__i, std::piecewise_construct,
00857                                  std::forward_as_tuple(std::move(__k)),
00858                                  std::forward_as_tuple(
00859                                    std::forward<_Obj>(__obj)));
00860               return {__i, true};
00861             }
00862           (*__i).second = std::forward<_Obj>(__obj);
00863           return {__i, false};
00864         }
00865 
00866       /**
00867        *  @brief Attempts to insert or assign a std::pair into the %map.
00868        *  @param  __hint  An iterator that serves as a hint as to where the
00869        *                  pair should be inserted.
00870        *  @param __k    Key to use for finding a possibly existing pair in
00871        *                the map.
00872        *  @param __obj  Argument used to generate the .second for a pair 
00873        *                instance.
00874        *
00875        *  @return An iterator that points to the element with key of
00876        *           @a __x (may or may not be the %pair passed in).
00877        *
00878        *  This function attempts to insert a (key, value) %pair into the %map.
00879        *  A %map relies on unique keys and thus a %pair is only inserted if its
00880        *  first element (the key) is not already present in the %map.
00881        *  If the %pair was already in the %map, the .second of the %pair
00882        *  is assigned from __obj.
00883        *
00884        *  Insertion requires logarithmic time.
00885        */
00886       template <typename _Obj>
00887         iterator
00888         insert_or_assign(const_iterator __hint,
00889                          const key_type& __k, _Obj&& __obj)
00890         {
00891           iterator __i;
00892           auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);
00893           if (__true_hint.second)
00894             {
00895               return emplace_hint(iterator(__true_hint.second),
00896                                   std::piecewise_construct,
00897                                   std::forward_as_tuple(__k),
00898                                   std::forward_as_tuple(
00899                                     std::forward<_Obj>(__obj)));
00900             }
00901           __i = iterator(__true_hint.first);
00902           (*__i).second = std::forward<_Obj>(__obj);
00903           return __i;
00904         }
00905 
00906       // move-capable overload
00907       template <typename _Obj>
00908         iterator
00909         insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
00910         {
00911           iterator __i;
00912           auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);
00913           if (__true_hint.second)
00914             {
00915               return emplace_hint(iterator(__true_hint.second),
00916                                   std::piecewise_construct,
00917                                   std::forward_as_tuple(std::move(__k)),
00918                                   std::forward_as_tuple(
00919                                     std::forward<_Obj>(__obj)));
00920             }
00921           __i = iterator(__true_hint.first);
00922           (*__i).second = std::forward<_Obj>(__obj);
00923           return __i;
00924         }
00925 #endif
00926 
00927 #if __cplusplus >= 201103L
00928       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00929       // DR 130. Associative erase should return an iterator.
00930       /**
00931        *  @brief Erases an element from a %map.
00932        *  @param  __position  An iterator pointing to the element to be erased.
00933        *  @return An iterator pointing to the element immediately following
00934        *          @a position prior to the element being erased. If no such 
00935        *          element exists, end() is returned.
00936        *
00937        *  This function erases an element, pointed to by the given
00938        *  iterator, from a %map.  Note that this function only erases
00939        *  the element, and that if the element is itself a pointer,
00940        *  the pointed-to memory is not touched in any way.  Managing
00941        *  the pointer is the user's responsibility.
00942        */
00943       iterator
00944       erase(const_iterator __position)
00945       { return _M_t.erase(__position); }
00946 
00947       // LWG 2059
00948       _GLIBCXX_ABI_TAG_CXX11
00949       iterator
00950       erase(iterator __position)
00951       { return _M_t.erase(__position); }
00952 #else
00953       /**
00954        *  @brief Erases an element from a %map.
00955        *  @param  __position  An iterator pointing to the element to be erased.
00956        *
00957        *  This function erases an element, pointed to by the given
00958        *  iterator, from a %map.  Note that this function only erases
00959        *  the element, and that if the element is itself a pointer,
00960        *  the pointed-to memory is not touched in any way.  Managing
00961        *  the pointer is the user's responsibility.
00962        */
00963       void
00964       erase(iterator __position)
00965       { _M_t.erase(__position); }
00966 #endif
00967 
00968       /**
00969        *  @brief Erases elements according to the provided key.
00970        *  @param  __x  Key of element to be erased.
00971        *  @return  The number of elements erased.
00972        *
00973        *  This function erases all the elements located by the given key from
00974        *  a %map.
00975        *  Note that this function only erases the element, and that if
00976        *  the element is itself a pointer, the pointed-to memory is not touched
00977        *  in any way.  Managing the pointer is the user's responsibility.
00978        */
00979       size_type
00980       erase(const key_type& __x)
00981       { return _M_t.erase(__x); }
00982 
00983 #if __cplusplus >= 201103L
00984       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00985       // DR 130. Associative erase should return an iterator.
00986       /**
00987        *  @brief Erases a [first,last) range of elements from a %map.
00988        *  @param  __first  Iterator pointing to the start of the range to be
00989        *                   erased.
00990        *  @param __last Iterator pointing to the end of the range to
00991        *                be erased.
00992        *  @return The iterator @a __last.
00993        *
00994        *  This function erases a sequence of elements from a %map.
00995        *  Note that this function only erases the element, and that if
00996        *  the element is itself a pointer, the pointed-to memory is not touched
00997        *  in any way.  Managing the pointer is the user's responsibility.
00998        */
00999       iterator
01000       erase(const_iterator __first, const_iterator __last)
01001       { return _M_t.erase(__first, __last); }
01002 #else
01003       /**
01004        *  @brief Erases a [__first,__last) range of elements from a %map.
01005        *  @param  __first  Iterator pointing to the start of the range to be
01006        *                   erased.
01007        *  @param __last Iterator pointing to the end of the range to
01008        *                be erased.
01009        *
01010        *  This function erases a sequence of elements from a %map.
01011        *  Note that this function only erases the element, and that if
01012        *  the element is itself a pointer, the pointed-to memory is not touched
01013        *  in any way.  Managing the pointer is the user's responsibility.
01014        */
01015       void
01016       erase(iterator __first, iterator __last)
01017       { _M_t.erase(__first, __last); }
01018 #endif
01019 
01020       /**
01021        *  @brief  Swaps data with another %map.
01022        *  @param  __x  A %map of the same element and allocator types.
01023        *
01024        *  This exchanges the elements between two maps in constant
01025        *  time.  (It is only swapping a pointer, an integer, and an
01026        *  instance of the @c Compare type (which itself is often
01027        *  stateless and empty), so it should be quite fast.)  Note
01028        *  that the global std::swap() function is specialized such
01029        *  that std::swap(m1,m2) will feed to this function.
01030        */
01031       void
01032       swap(map& __x)
01033       _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
01034       { _M_t.swap(__x._M_t); }
01035 
01036       /**
01037        *  Erases all elements in a %map.  Note that this function only
01038        *  erases the elements, and that if the elements themselves are
01039        *  pointers, the pointed-to memory is not touched in any way.
01040        *  Managing the pointer is the user's responsibility.
01041        */
01042       void
01043       clear() _GLIBCXX_NOEXCEPT
01044       { _M_t.clear(); }
01045 
01046       // observers
01047       /**
01048        *  Returns the key comparison object out of which the %map was
01049        *  constructed.
01050        */
01051       key_compare
01052       key_comp() const
01053       { return _M_t.key_comp(); }
01054 
01055       /**
01056        *  Returns a value comparison object, built from the key comparison
01057        *  object out of which the %map was constructed.
01058        */
01059       value_compare
01060       value_comp() const
01061       { return value_compare(_M_t.key_comp()); }
01062 
01063       // [23.3.1.3] map operations
01064 
01065       //@{
01066       /**
01067        *  @brief Tries to locate an element in a %map.
01068        *  @param  __x  Key of (key, value) %pair to be located.
01069        *  @return  Iterator pointing to sought-after element, or end() if not
01070        *           found.
01071        *
01072        *  This function takes a key and tries to locate the element with which
01073        *  the key matches.  If successful the function returns an iterator
01074        *  pointing to the sought after %pair.  If unsuccessful it returns the
01075        *  past-the-end ( @c end() ) iterator.
01076        */
01077 
01078       iterator
01079       find(const key_type& __x)
01080       { return _M_t.find(__x); }
01081 
01082 #if __cplusplus > 201103L
01083       template<typename _Kt>
01084         auto
01085         find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x))
01086         { return _M_t._M_find_tr(__x); }
01087 #endif
01088       //@}
01089 
01090       //@{
01091       /**
01092        *  @brief Tries to locate an element in a %map.
01093        *  @param  __x  Key of (key, value) %pair to be located.
01094        *  @return  Read-only (constant) iterator pointing to sought-after
01095        *           element, or end() if not found.
01096        *
01097        *  This function takes a key and tries to locate the element with which
01098        *  the key matches.  If successful the function returns a constant
01099        *  iterator pointing to the sought after %pair. If unsuccessful it
01100        *  returns the past-the-end ( @c end() ) iterator.
01101        */
01102 
01103       const_iterator
01104       find(const key_type& __x) const
01105       { return _M_t.find(__x); }
01106 
01107 #if __cplusplus > 201103L
01108       template<typename _Kt>
01109         auto
01110         find(const _Kt& __x) const -> decltype(_M_t._M_find_tr(__x))
01111         { return _M_t._M_find_tr(__x); }
01112 #endif
01113       //@}
01114 
01115       //@{
01116       /**
01117        *  @brief  Finds the number of elements with given key.
01118        *  @param  __x  Key of (key, value) pairs to be located.
01119        *  @return  Number of elements with specified key.
01120        *
01121        *  This function only makes sense for multimaps; for map the result will
01122        *  either be 0 (not present) or 1 (present).
01123        */
01124       size_type
01125       count(const key_type& __x) const
01126       { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
01127 
01128 #if __cplusplus > 201103L
01129       template<typename _Kt>
01130         auto
01131         count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x))
01132         { return _M_t._M_count_tr(__x); }
01133 #endif
01134       //@}
01135 
01136       //@{
01137       /**
01138        *  @brief Finds the beginning of a subsequence matching given key.
01139        *  @param  __x  Key of (key, value) pair to be located.
01140        *  @return  Iterator pointing to first element equal to or greater
01141        *           than key, or end().
01142        *
01143        *  This function returns the first element of a subsequence of elements
01144        *  that matches the given key.  If unsuccessful it returns an iterator
01145        *  pointing to the first element that has a greater value than given key
01146        *  or end() if no such element exists.
01147        */
01148       iterator
01149       lower_bound(const key_type& __x)
01150       { return _M_t.lower_bound(__x); }
01151 
01152 #if __cplusplus > 201103L
01153       template<typename _Kt>
01154         auto
01155         lower_bound(const _Kt& __x)
01156         -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
01157         { return iterator(_M_t._M_lower_bound_tr(__x)); }
01158 #endif
01159       //@}
01160 
01161       //@{
01162       /**
01163        *  @brief Finds the beginning of a subsequence matching given key.
01164        *  @param  __x  Key of (key, value) pair to be located.
01165        *  @return  Read-only (constant) iterator pointing to first element
01166        *           equal to or greater than key, or end().
01167        *
01168        *  This function returns the first element of a subsequence of elements
01169        *  that matches the given key.  If unsuccessful it returns an iterator
01170        *  pointing to the first element that has a greater value than given key
01171        *  or end() if no such element exists.
01172        */
01173       const_iterator
01174       lower_bound(const key_type& __x) const
01175       { return _M_t.lower_bound(__x); }
01176 
01177 #if __cplusplus > 201103L
01178       template<typename _Kt>
01179         auto
01180         lower_bound(const _Kt& __x) const
01181         -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x)))
01182         { return const_iterator(_M_t._M_lower_bound_tr(__x)); }
01183 #endif
01184       //@}
01185 
01186       //@{
01187       /**
01188        *  @brief Finds the end of a subsequence matching given key.
01189        *  @param  __x  Key of (key, value) pair to be located.
01190        *  @return Iterator pointing to the first element
01191        *          greater than key, or end().
01192        */
01193       iterator
01194       upper_bound(const key_type& __x)
01195       { return _M_t.upper_bound(__x); }
01196 
01197 #if __cplusplus > 201103L
01198       template<typename _Kt>
01199         auto
01200         upper_bound(const _Kt& __x)
01201         -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
01202         { return iterator(_M_t._M_upper_bound_tr(__x)); }
01203 #endif
01204       //@}
01205 
01206       //@{
01207       /**
01208        *  @brief Finds the end of a subsequence matching given key.
01209        *  @param  __x  Key of (key, value) pair to be located.
01210        *  @return  Read-only (constant) iterator pointing to first iterator
01211        *           greater than key, or end().
01212        */
01213       const_iterator
01214       upper_bound(const key_type& __x) const
01215       { return _M_t.upper_bound(__x); }
01216 
01217 #if __cplusplus > 201103L
01218       template<typename _Kt>
01219         auto
01220         upper_bound(const _Kt& __x) const
01221         -> decltype(const_iterator(_M_t._M_upper_bound_tr(__x)))
01222         { return const_iterator(_M_t._M_upper_bound_tr(__x)); }
01223 #endif
01224       //@}
01225 
01226       //@{
01227       /**
01228        *  @brief Finds a subsequence matching given key.
01229        *  @param  __x  Key of (key, value) pairs to be located.
01230        *  @return  Pair of iterators that possibly points to the subsequence
01231        *           matching given key.
01232        *
01233        *  This function is equivalent to
01234        *  @code
01235        *    std::make_pair(c.lower_bound(val),
01236        *                   c.upper_bound(val))
01237        *  @endcode
01238        *  (but is faster than making the calls separately).
01239        *
01240        *  This function probably only makes sense for multimaps.
01241        */
01242       std::pair<iterator, iterator>
01243       equal_range(const key_type& __x)
01244       { return _M_t.equal_range(__x); }
01245 
01246 #if __cplusplus > 201103L
01247       template<typename _Kt>
01248         auto
01249         equal_range(const _Kt& __x)
01250         -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)))
01251         { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); }
01252 #endif
01253       //@}
01254 
01255       //@{
01256       /**
01257        *  @brief Finds a subsequence matching given key.
01258        *  @param  __x  Key of (key, value) pairs to be located.
01259        *  @return  Pair of read-only (constant) iterators that possibly points
01260        *           to the subsequence matching given key.
01261        *
01262        *  This function is equivalent to
01263        *  @code
01264        *    std::make_pair(c.lower_bound(val),
01265        *                   c.upper_bound(val))
01266        *  @endcode
01267        *  (but is faster than making the calls separately).
01268        *
01269        *  This function probably only makes sense for multimaps.
01270        */
01271       std::pair<const_iterator, const_iterator>
01272       equal_range(const key_type& __x) const
01273       { return _M_t.equal_range(__x); }
01274 
01275 #if __cplusplus > 201103L
01276       template<typename _Kt>
01277         auto
01278         equal_range(const _Kt& __x) const
01279         -> decltype(pair<const_iterator, const_iterator>(
01280               _M_t._M_equal_range_tr(__x)))
01281         {
01282           return pair<const_iterator, const_iterator>(
01283               _M_t._M_equal_range_tr(__x));
01284         }
01285 #endif
01286       //@}
01287 
01288       template<typename _K1, typename _T1, typename _C1, typename _A1>
01289         friend bool
01290         operator==(const map<_K1, _T1, _C1, _A1>&,
01291                    const map<_K1, _T1, _C1, _A1>&);
01292 
01293       template<typename _K1, typename _T1, typename _C1, typename _A1>
01294         friend bool
01295         operator<(const map<_K1, _T1, _C1, _A1>&,
01296                   const map<_K1, _T1, _C1, _A1>&);
01297     };
01298 
01299   /**
01300    *  @brief  Map equality comparison.
01301    *  @param  __x  A %map.
01302    *  @param  __y  A %map of the same type as @a x.
01303    *  @return  True iff the size and elements of the maps are equal.
01304    *
01305    *  This is an equivalence relation.  It is linear in the size of the
01306    *  maps.  Maps are considered equivalent if their sizes are equal,
01307    *  and if corresponding elements compare equal.
01308   */
01309   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
01310     inline bool
01311     operator==(const map<_Key, _Tp, _Compare, _Alloc>& __x,
01312                const map<_Key, _Tp, _Compare, _Alloc>& __y)
01313     { return __x._M_t == __y._M_t; }
01314 
01315   /**
01316    *  @brief  Map ordering relation.
01317    *  @param  __x  A %map.
01318    *  @param  __y  A %map of the same type as @a x.
01319    *  @return  True iff @a x is lexicographically less than @a y.
01320    *
01321    *  This is a total ordering relation.  It is linear in the size of the
01322    *  maps.  The elements must be comparable with @c <.
01323    *
01324    *  See std::lexicographical_compare() for how the determination is made.
01325   */
01326   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
01327     inline bool
01328     operator<(const map<_Key, _Tp, _Compare, _Alloc>& __x,
01329               const map<_Key, _Tp, _Compare, _Alloc>& __y)
01330     { return __x._M_t < __y._M_t; }
01331 
01332   /// Based on operator==
01333   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
01334     inline bool
01335     operator!=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
01336                const map<_Key, _Tp, _Compare, _Alloc>& __y)
01337     { return !(__x == __y); }
01338 
01339   /// Based on operator<
01340   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
01341     inline bool
01342     operator>(const map<_Key, _Tp, _Compare, _Alloc>& __x,
01343               const map<_Key, _Tp, _Compare, _Alloc>& __y)
01344     { return __y < __x; }
01345 
01346   /// Based on operator<
01347   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
01348     inline bool
01349     operator<=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
01350                const map<_Key, _Tp, _Compare, _Alloc>& __y)
01351     { return !(__y < __x); }
01352 
01353   /// Based on operator<
01354   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
01355     inline bool
01356     operator>=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
01357                const map<_Key, _Tp, _Compare, _Alloc>& __y)
01358     { return !(__x < __y); }
01359 
01360   /// See std::map::swap().
01361   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
01362     inline void
01363     swap(map<_Key, _Tp, _Compare, _Alloc>& __x,
01364          map<_Key, _Tp, _Compare, _Alloc>& __y)
01365     _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
01366     { __x.swap(__y); }
01367 
01368 _GLIBCXX_END_NAMESPACE_CONTAINER
01369 } // namespace std
01370 
01371 #endif /* _STL_MAP_H */