LCOV - code coverage report
Current view: top level - usr/include/c++/6/bits - stl_map.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 0 19 0.0 %
Date: 2018-11-14 16:53:58 Functions: 0 8 0.0 %

          Line data    Source code
       1             : // Map implementation -*- C++ -*-
       2             : 
       3             : // Copyright (C) 2001-2016 Free Software Foundation, Inc.
       4             : //
       5             : // This file is part of the GNU ISO C++ Library.  This library is free
       6             : // software; you can redistribute it and/or modify it under the
       7             : // terms of the GNU General Public License as published by the
       8             : // Free Software Foundation; either version 3, or (at your option)
       9             : // any later version.
      10             : 
      11             : // This library is distributed in the hope that it will be useful,
      12             : // but WITHOUT ANY WARRANTY; without even the implied warranty of
      13             : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      14             : // GNU General Public License for more details.
      15             : 
      16             : // Under Section 7 of GPL version 3, you are granted additional
      17             : // permissions described in the GCC Runtime Library Exception, version
      18             : // 3.1, as published by the Free Software Foundation.
      19             : 
      20             : // You should have received a copy of the GNU General Public License and
      21             : // a copy of the GCC Runtime Library Exception along with this program;
      22             : // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
      23             : // <http://www.gnu.org/licenses/>.
      24             : 
      25             : /*
      26             :  *
      27             :  * Copyright (c) 1994
      28             :  * Hewlett-Packard Company
      29             :  *
      30             :  * Permission to use, copy, modify, distribute and sell this software
      31             :  * and its documentation for any purpose is hereby granted without fee,
      32             :  * provided that the above copyright notice appear in all copies and
      33             :  * that both that copyright notice and this permission notice appear
      34             :  * in supporting documentation.  Hewlett-Packard Company makes no
      35             :  * representations about the suitability of this software for any
      36             :  * purpose.  It is provided "as is" without express or implied warranty.
      37             :  *
      38             :  *
      39             :  * Copyright (c) 1996,1997
      40             :  * Silicon Graphics Computer Systems, Inc.
      41             :  *
      42             :  * Permission to use, copy, modify, distribute and sell this software
      43             :  * and its documentation for any purpose is hereby granted without fee,
      44             :  * provided that the above copyright notice appear in all copies and
      45             :  * that both that copyright notice and this permission notice appear
      46             :  * in supporting documentation.  Silicon Graphics makes no
      47             :  * representations about the suitability of this software for any
      48             :  * purpose.  It is provided "as is" without express or implied warranty.
      49             :  */
      50             : 
      51             : /** @file bits/stl_map.h
      52             :  *  This is an internal header file, included by other library headers.
      53             :  *  Do not attempt to use it directly. @headername{map}
      54             :  */
      55             : 
      56             : #ifndef _STL_MAP_H
      57             : #define _STL_MAP_H 1
      58             : 
      59             : #include <bits/functexcept.h>
      60             : #include <bits/concept_check.h>
      61             : #if __cplusplus >= 201103L
      62             : #include <initializer_list>
      63             : #include <tuple>
      64             : #endif
      65             : 
      66             : namespace std _GLIBCXX_VISIBILITY(default)
      67             : {
      68             : _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
      69             : 
      70             :   /**
      71             :    *  @brief A standard container made up of (key,value) pairs, which can be
      72             :    *  retrieved based on a key, in logarithmic time.
      73             :    *
      74             :    *  @ingroup associative_containers
      75             :    *
      76             :    *  @tparam _Key  Type of key objects.
      77             :    *  @tparam  _Tp  Type of mapped objects.
      78             :    *  @tparam _Compare  Comparison function object type, defaults to less<_Key>.
      79             :    *  @tparam _Alloc  Allocator type, defaults to 
      80             :    *                  allocator<pair<const _Key, _Tp>.
      81             :    *
      82             :    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
      83             :    *  <a href="tables.html#66">reversible container</a>, and an
      84             :    *  <a href="tables.html#69">associative container</a> (using unique keys).
      85             :    *  For a @c map<Key,T> the key_type is Key, the mapped_type is T, and the
      86             :    *  value_type is std::pair<const Key,T>.
      87             :    *
      88             :    *  Maps support bidirectional iterators.
      89             :    *
      90             :    *  The private tree data is declared exactly the same way for map and
      91             :    *  multimap; the distinction is made entirely in how the tree functions are
      92             :    *  called (*_unique versus *_equal, same as the standard).
      93             :   */
      94             :   template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
      95             :             typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
      96           0 :     class map
      97             :     {
      98             :     public:
      99             :       typedef _Key                                          key_type;
     100             :       typedef _Tp                                           mapped_type;
     101             :       typedef std::pair<const _Key, _Tp>                    value_type;
     102             :       typedef _Compare                                      key_compare;
     103             :       typedef _Alloc                                        allocator_type;
     104             : 
     105             :     private:
     106             :       // concept requirements
     107             :       typedef typename _Alloc::value_type                   _Alloc_value_type;
     108             :       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
     109             :       __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
     110             :                                 _BinaryFunctionConcept)
     111             :       __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept)
     112             : 
     113             :     public:
     114             :       class value_compare
     115             :       : public std::binary_function<value_type, value_type, bool>
     116             :       {
     117             :         friend class map<_Key, _Tp, _Compare, _Alloc>;
     118             :       protected:
     119             :         _Compare comp;
     120             : 
     121             :         value_compare(_Compare __c)
     122             :         : comp(__c) { }
     123             : 
     124             :       public:
     125             :         bool operator()(const value_type& __x, const value_type& __y) const
     126             :         { return comp(__x.first, __y.first); }
     127             :       };
     128             : 
     129             :     private:
     130             :       /// This turns a red-black tree into a [multi]map. 
     131             :       typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
     132             :         rebind<value_type>::other _Pair_alloc_type;
     133             : 
     134             :       typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
     135             :                        key_compare, _Pair_alloc_type> _Rep_type;
     136             : 
     137             :       /// The actual tree structure.
     138             :       _Rep_type _M_t;
     139             : 
     140             :       typedef __gnu_cxx::__alloc_traits<_Pair_alloc_type> _Alloc_traits;
     141             : 
     142             :     public:
     143             :       // many of these are specified differently in ISO, but the following are
     144             :       // "functionally equivalent"
     145             :       typedef typename _Alloc_traits::pointer            pointer;
     146             :       typedef typename _Alloc_traits::const_pointer      const_pointer;
     147             :       typedef typename _Alloc_traits::reference          reference;
     148             :       typedef typename _Alloc_traits::const_reference    const_reference;
     149             :       typedef typename _Rep_type::iterator               iterator;
     150             :       typedef typename _Rep_type::const_iterator         const_iterator;
     151             :       typedef typename _Rep_type::size_type              size_type;
     152             :       typedef typename _Rep_type::difference_type        difference_type;
     153             :       typedef typename _Rep_type::reverse_iterator       reverse_iterator;
     154             :       typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
     155             : 
     156             :       // [23.3.1.1] construct/copy/destroy
     157             :       // (get_allocator() is also listed in this section)
     158             : 
     159             :       /**
     160             :        *  @brief  Default constructor creates no elements.
     161             :        */
     162           0 :       map()
     163             :       _GLIBCXX_NOEXCEPT_IF(
     164             :           is_nothrow_default_constructible<allocator_type>::value
     165             :           && is_nothrow_default_constructible<key_compare>::value)
     166           0 :       : _M_t() { }
     167             : 
     168             :       /**
     169             :        *  @brief  Creates a %map with no elements.
     170             :        *  @param  __comp  A comparison object.
     171             :        *  @param  __a  An allocator object.
     172             :        */
     173             :       explicit
     174             :       map(const _Compare& __comp,
     175             :           const allocator_type& __a = allocator_type())
     176             :       : _M_t(__comp, _Pair_alloc_type(__a)) { }
     177             : 
     178             :       /**
     179             :        *  @brief  %Map copy constructor.
     180             :        *  @param  __x  A %map of identical element and allocator types.
     181             :        *
     182             :        *  The newly-created %map uses a copy of the allocation object
     183             :        *  used by @a __x.
     184             :        */
     185             :       map(const map& __x)
     186             :       : _M_t(__x._M_t) { }
     187             : 
     188             : #if __cplusplus >= 201103L
     189             :       /**
     190             :        *  @brief  %Map move constructor.
     191             :        *  @param  __x  A %map of identical element and allocator types.
     192             :        *
     193             :        *  The newly-created %map contains the exact contents of @a __x.
     194             :        *  The contents of @a __x are a valid, but unspecified %map.
     195             :        */
     196             :       map(map&& __x)
     197             :       noexcept(is_nothrow_copy_constructible<_Compare>::value)
     198             :       : _M_t(std::move(__x._M_t)) { }
     199             : 
     200             :       /**
     201             :        *  @brief  Builds a %map from an initializer_list.
     202             :        *  @param  __l  An initializer_list.
     203             :        *  @param  __comp  A comparison object.
     204             :        *  @param  __a  An allocator object.
     205             :        *
     206             :        *  Create a %map consisting of copies of the elements in the
     207             :        *  initializer_list @a __l.
     208             :        *  This is linear in N if the range is already sorted, and NlogN
     209             :        *  otherwise (where N is @a __l.size()).
     210             :        */
     211             :       map(initializer_list<value_type> __l,
     212             :           const _Compare& __comp = _Compare(),
     213             :           const allocator_type& __a = allocator_type())
     214             :       : _M_t(__comp, _Pair_alloc_type(__a))
     215             :       { _M_t._M_insert_unique(__l.begin(), __l.end()); }
     216             : 
     217             :       /// Allocator-extended default constructor.
     218             :       explicit
     219             :       map(const allocator_type& __a)
     220             :       : _M_t(_Compare(), _Pair_alloc_type(__a)) { }
     221             : 
     222             :       /// Allocator-extended copy constructor.
     223             :       map(const map& __m, const allocator_type& __a)
     224             :       : _M_t(__m._M_t, _Pair_alloc_type(__a)) { }
     225             : 
     226             :       /// Allocator-extended move constructor.
     227             :       map(map&& __m, const allocator_type& __a)
     228             :       noexcept(is_nothrow_copy_constructible<_Compare>::value
     229             :                && _Alloc_traits::_S_always_equal())
     230             :       : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { }
     231             : 
     232             :       /// Allocator-extended initialier-list constructor.
     233             :       map(initializer_list<value_type> __l, const allocator_type& __a)
     234             :       : _M_t(_Compare(), _Pair_alloc_type(__a))
     235             :       { _M_t._M_insert_unique(__l.begin(), __l.end()); }
     236             : 
     237             :       /// Allocator-extended range constructor.
     238             :       template<typename _InputIterator>
     239             :         map(_InputIterator __first, _InputIterator __last,
     240             :             const allocator_type& __a)
     241             :         : _M_t(_Compare(), _Pair_alloc_type(__a))
     242             :         { _M_t._M_insert_unique(__first, __last); }
     243             : #endif
     244             : 
     245             :       /**
     246             :        *  @brief  Builds a %map from a range.
     247             :        *  @param  __first  An input iterator.
     248             :        *  @param  __last  An input iterator.
     249             :        *
     250             :        *  Create a %map consisting of copies of the elements from
     251             :        *  [__first,__last).  This is linear in N if the range is
     252             :        *  already sorted, and NlogN otherwise (where N is
     253             :        *  distance(__first,__last)).
     254             :        */
     255             :       template<typename _InputIterator>
     256             :         map(_InputIterator __first, _InputIterator __last)
     257             :         : _M_t()
     258             :         { _M_t._M_insert_unique(__first, __last); }
     259             : 
     260             :       /**
     261             :        *  @brief  Builds a %map from a range.
     262             :        *  @param  __first  An input iterator.
     263             :        *  @param  __last  An input iterator.
     264             :        *  @param  __comp  A comparison functor.
     265             :        *  @param  __a  An allocator object.
     266             :        *
     267             :        *  Create a %map consisting of copies of the elements from
     268             :        *  [__first,__last).  This is linear in N if the range is
     269             :        *  already sorted, and NlogN otherwise (where N is
     270             :        *  distance(__first,__last)).
     271             :        */
     272             :       template<typename _InputIterator>
     273             :         map(_InputIterator __first, _InputIterator __last,
     274             :             const _Compare& __comp,
     275             :             const allocator_type& __a = allocator_type())
     276             :         : _M_t(__comp, _Pair_alloc_type(__a))
     277             :         { _M_t._M_insert_unique(__first, __last); }
     278             : 
     279             :       // FIXME There is no dtor declared, but we should have something
     280             :       // generated by Doxygen.  I don't know what tags to add to this
     281             :       // paragraph to make that happen:
     282             :       /**
     283             :        *  The dtor only erases the elements, and note that if the elements
     284             :        *  themselves are pointers, the pointed-to memory is not touched in any
     285             :        *  way.  Managing the pointer is the user's responsibility.
     286             :        */
     287             : 
     288             :       /**
     289             :        *  @brief  %Map assignment operator.
     290             :        *  @param  __x  A %map of identical element and allocator types.
     291             :        *
     292             :        *  All the elements of @a __x are copied, but unlike the copy
     293             :        *  constructor, the allocator object is not copied.
     294             :        */
     295             :       map&
     296             :       operator=(const map& __x)
     297             :       {
     298             :         _M_t = __x._M_t;
     299             :         return *this;
     300             :       }
     301             : 
     302             : #if __cplusplus >= 201103L
     303             :       /// Move assignment operator.
     304             :       map&
     305             :       operator=(map&&) = default;
     306             : 
     307             :       /**
     308             :        *  @brief  %Map list assignment operator.
     309             :        *  @param  __l  An initializer_list.
     310             :        *
     311             :        *  This function fills a %map with copies of the elements in the
     312             :        *  initializer list @a __l.
     313             :        *
     314             :        *  Note that the assignment completely changes the %map and
     315             :        *  that the resulting %map's size is the same as the number
     316             :        *  of elements assigned.  Old data may be lost.
     317             :        */
     318             :       map&
     319             :       operator=(initializer_list<value_type> __l)
     320             :       {
     321             :         _M_t._M_assign_unique(__l.begin(), __l.end());
     322             :         return *this;
     323             :       }
     324             : #endif
     325             : 
     326             :       /// Get a copy of the memory allocation object.
     327             :       allocator_type
     328             :       get_allocator() const _GLIBCXX_NOEXCEPT
     329             :       { return allocator_type(_M_t.get_allocator()); }
     330             : 
     331             :       // iterators
     332             :       /**
     333             :        *  Returns a read/write iterator that points to the first pair in the
     334             :        *  %map.
     335             :        *  Iteration is done in ascending order according to the keys.
     336             :        */
     337             :       iterator
     338             :       begin() _GLIBCXX_NOEXCEPT
     339             :       { return _M_t.begin(); }
     340             : 
     341             :       /**
     342             :        *  Returns a read-only (constant) iterator that points to the first pair
     343             :        *  in the %map.  Iteration is done in ascending order according to the
     344             :        *  keys.
     345             :        */
     346             :       const_iterator
     347             :       begin() const _GLIBCXX_NOEXCEPT
     348             :       { return _M_t.begin(); }
     349             : 
     350             :       /**
     351             :        *  Returns a read/write iterator that points one past the last
     352             :        *  pair in the %map.  Iteration is done in ascending order
     353             :        *  according to the keys.
     354             :        */
     355             :       iterator
     356           0 :       end() _GLIBCXX_NOEXCEPT
     357           0 :       { return _M_t.end(); }
     358             : 
     359             :       /**
     360             :        *  Returns a read-only (constant) iterator that points one past the last
     361             :        *  pair in the %map.  Iteration is done in ascending order according to
     362             :        *  the keys.
     363             :        */
     364             :       const_iterator
     365           0 :       end() const _GLIBCXX_NOEXCEPT
     366           0 :       { return _M_t.end(); }
     367             : 
     368             :       /**
     369             :        *  Returns a read/write reverse iterator that points to the last pair in
     370             :        *  the %map.  Iteration is done in descending order according to the
     371             :        *  keys.
     372             :        */
     373             :       reverse_iterator
     374             :       rbegin() _GLIBCXX_NOEXCEPT
     375             :       { return _M_t.rbegin(); }
     376             : 
     377             :       /**
     378             :        *  Returns a read-only (constant) reverse iterator that points to the
     379             :        *  last pair in the %map.  Iteration is done in descending order
     380             :        *  according to the keys.
     381             :        */
     382             :       const_reverse_iterator
     383             :       rbegin() const _GLIBCXX_NOEXCEPT
     384             :       { return _M_t.rbegin(); }
     385             : 
     386             :       /**
     387             :        *  Returns a read/write reverse iterator that points to one before the
     388             :        *  first pair in the %map.  Iteration is done in descending order
     389             :        *  according to the keys.
     390             :        */
     391             :       reverse_iterator
     392             :       rend() _GLIBCXX_NOEXCEPT
     393             :       { return _M_t.rend(); }
     394             : 
     395             :       /**
     396             :        *  Returns a read-only (constant) reverse iterator that points to one
     397             :        *  before the first pair in the %map.  Iteration is done in descending
     398             :        *  order according to the keys.
     399             :        */
     400             :       const_reverse_iterator
     401             :       rend() const _GLIBCXX_NOEXCEPT
     402             :       { return _M_t.rend(); }
     403             : 
     404             : #if __cplusplus >= 201103L
     405             :       /**
     406             :        *  Returns a read-only (constant) iterator that points to the first pair
     407             :        *  in the %map.  Iteration is done in ascending order according to the
     408             :        *  keys.
     409             :        */
     410             :       const_iterator
     411             :       cbegin() const noexcept
     412             :       { return _M_t.begin(); }
     413             : 
     414             :       /**
     415             :        *  Returns a read-only (constant) iterator that points one past the last
     416             :        *  pair in the %map.  Iteration is done in ascending order according to
     417             :        *  the keys.
     418             :        */
     419             :       const_iterator
     420             :       cend() const noexcept
     421             :       { return _M_t.end(); }
     422             : 
     423             :       /**
     424             :        *  Returns a read-only (constant) reverse iterator that points to the
     425             :        *  last pair in the %map.  Iteration is done in descending order
     426             :        *  according to the keys.
     427             :        */
     428             :       const_reverse_iterator
     429             :       crbegin() const noexcept
     430             :       { return _M_t.rbegin(); }
     431             : 
     432             :       /**
     433             :        *  Returns a read-only (constant) reverse iterator that points to one
     434             :        *  before the first pair in the %map.  Iteration is done in descending
     435             :        *  order according to the keys.
     436             :        */
     437             :       const_reverse_iterator
     438             :       crend() const noexcept
     439             :       { return _M_t.rend(); }
     440             : #endif
     441             : 
     442             :       // capacity
     443             :       /** Returns true if the %map is empty.  (Thus begin() would equal
     444             :        *  end().)
     445             :       */
     446             :       bool
     447             :       empty() const _GLIBCXX_NOEXCEPT
     448             :       { return _M_t.empty(); }
     449             : 
     450             :       /** Returns the size of the %map.  */
     451             :       size_type
     452             :       size() const _GLIBCXX_NOEXCEPT
     453             :       { return _M_t.size(); }
     454             : 
     455             :       /** Returns the maximum size of the %map.  */
     456             :       size_type
     457             :       max_size() const _GLIBCXX_NOEXCEPT
     458             :       { return _M_t.max_size(); }
     459             : 
     460             :       // [23.3.1.2] element access
     461             :       /**
     462             :        *  @brief  Subscript ( @c [] ) access to %map data.
     463             :        *  @param  __k  The key for which data should be retrieved.
     464             :        *  @return  A reference to the data of the (key,data) %pair.
     465             :        *
     466             :        *  Allows for easy lookup with the subscript ( @c [] )
     467             :        *  operator.  Returns data associated with the key specified in
     468             :        *  subscript.  If the key does not exist, a pair with that key
     469             :        *  is created using default values, which is then returned.
     470             :        *
     471             :        *  Lookup requires logarithmic time.
     472             :        */
     473             :       mapped_type&
     474             :       operator[](const key_type& __k)
     475             :       {
     476             :         // concept requirements
     477             :         __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)
     478             : 
     479             :         iterator __i = lower_bound(__k);
     480             :         // __i->first is greater than or equivalent to __k.
     481             :         if (__i == end() || key_comp()(__k, (*__i).first))
     482             : #if __cplusplus >= 201103L
     483             :           __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct,
     484             :                                             std::tuple<const key_type&>(__k),
     485             :                                             std::tuple<>());
     486             : #else
     487             :           __i = insert(__i, value_type(__k, mapped_type()));
     488             : #endif
     489             :         return (*__i).second;
     490             :       }
     491             : 
     492             : #if __cplusplus >= 201103L
     493             :       mapped_type&
     494           0 :       operator[](key_type&& __k)
     495             :       {
     496             :         // concept requirements
     497             :         __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)
     498             : 
     499           0 :         iterator __i = lower_bound(__k);
     500             :         // __i->first is greater than or equivalent to __k.
     501           0 :         if (__i == end() || key_comp()(__k, (*__i).first))
     502           0 :           __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct,
     503           0 :                                         std::forward_as_tuple(std::move(__k)),
     504             :                                         std::tuple<>());
     505           0 :         return (*__i).second;
     506             :       }
     507             : #endif
     508             : 
     509             :       // _GLIBCXX_RESOLVE_LIB_DEFECTS
     510             :       // DR 464. Suggestion for new member functions in standard containers.
     511             :       /**
     512             :        *  @brief  Access to %map data.
     513             :        *  @param  __k  The key for which data should be retrieved.
     514             :        *  @return  A reference to the data whose key is equivalent to @a __k, if
     515             :        *           such a data is present in the %map.
     516             :        *  @throw  std::out_of_range  If no such data is present.
     517             :        */
     518             :       mapped_type&
     519             :       at(const key_type& __k)
     520             :       {
     521             :         iterator __i = lower_bound(__k);
     522             :         if (__i == end() || key_comp()(__k, (*__i).first))
     523             :           __throw_out_of_range(__N("map::at"));
     524             :         return (*__i).second;
     525             :       }
     526             : 
     527             :       const mapped_type&
     528             :       at(const key_type& __k) const
     529             :       {
     530             :         const_iterator __i = lower_bound(__k);
     531             :         if (__i == end() || key_comp()(__k, (*__i).first))
     532             :           __throw_out_of_range(__N("map::at"));
     533             :         return (*__i).second;
     534             :       }
     535             : 
     536             :       // modifiers
     537             : #if __cplusplus >= 201103L
     538             :       /**
     539             :        *  @brief Attempts to build and insert a std::pair into the %map.
     540             :        *
     541             :        *  @param __args  Arguments used to generate a new pair instance (see
     542             :        *                std::piecewise_contruct for passing arguments to each
     543             :        *                part of the pair constructor).
     544             :        *
     545             :        *  @return  A pair, of which the first element is an iterator that points
     546             :        *           to the possibly inserted pair, and the second is a bool that
     547             :        *           is true if the pair was actually inserted.
     548             :        *
     549             :        *  This function attempts to build and insert a (key, value) %pair into
     550             :        *  the %map.
     551             :        *  A %map relies on unique keys and thus a %pair is only inserted if its
     552             :        *  first element (the key) is not already present in the %map.
     553             :        *
     554             :        *  Insertion requires logarithmic time.
     555             :        */
     556             :       template<typename... _Args>
     557             :         std::pair<iterator, bool>
     558             :         emplace(_Args&&... __args)
     559             :         { return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); }
     560             : 
     561             :       /**
     562             :        *  @brief Attempts to build and insert a std::pair into the %map.
     563             :        *
     564             :        *  @param  __pos  An iterator that serves as a hint as to where the pair
     565             :        *                should be inserted.
     566             :        *  @param  __args  Arguments used to generate a new pair instance (see
     567             :        *                 std::piecewise_contruct for passing arguments to each
     568             :        *                 part of the pair constructor).
     569             :        *  @return An iterator that points to the element with key of the
     570             :        *          std::pair built from @a __args (may or may not be that
     571             :        *          std::pair).
     572             :        *
     573             :        *  This function is not concerned about whether the insertion took place,
     574             :        *  and thus does not return a boolean like the single-argument emplace()
     575             :        *  does.
     576             :        *  Note that the first parameter is only a hint and can potentially
     577             :        *  improve the performance of the insertion process. A bad hint would
     578             :        *  cause no gains in efficiency.
     579             :        *
     580             :        *  See
     581             :        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
     582             :        *  for more on @a hinting.
     583             :        *
     584             :        *  Insertion requires logarithmic time (if the hint is not taken).
     585             :        */
     586             :       template<typename... _Args>
     587             :         iterator
     588             :         emplace_hint(const_iterator __pos, _Args&&... __args)
     589             :         {
     590             :           return _M_t._M_emplace_hint_unique(__pos,
     591             :                                              std::forward<_Args>(__args)...);
     592             :         }
     593             : #endif
     594             : 
     595             : #if __cplusplus > 201402L
     596             : #define __cpp_lib_map_try_emplace 201411
     597             :       /**
     598             :        *  @brief Attempts to build and insert a std::pair into the %map.
     599             :        *
     600             :        *  @param __k    Key to use for finding a possibly existing pair in
     601             :        *                the map.
     602             :        *  @param __args  Arguments used to generate the .second for a new pair 
     603             :        *                instance.
     604             :        *
     605             :        *  @return  A pair, of which the first element is an iterator that points
     606             :        *           to the possibly inserted pair, and the second is a bool that
     607             :        *           is true if the pair was actually inserted.
     608             :        *
     609             :        *  This function attempts to build and insert a (key, value) %pair into
     610             :        *  the %map.
     611             :        *  A %map relies on unique keys and thus a %pair is only inserted if its
     612             :        *  first element (the key) is not already present in the %map.
     613             :        *  If a %pair is not inserted, this function has no effect.
     614             :        *
     615             :        *  Insertion requires logarithmic time.
     616             :        */
     617             :       template <typename... _Args>
     618             :         pair<iterator, bool>
     619             :         try_emplace(const key_type& __k, _Args&&... __args)
     620             :         {
     621             :           iterator __i = lower_bound(__k);
     622             :           if (__i == end() || key_comp()(__k, (*__i).first))
     623             :             {
     624             :               __i = emplace_hint(__i, std::piecewise_construct,
     625             :                                  std::forward_as_tuple(__k),
     626             :                                  std::forward_as_tuple(
     627             :                                    std::forward<_Args>(__args)...));
     628             :               return {__i, true};
     629             :             }
     630             :           return {__i, false};
     631             :         }
     632             : 
     633             :       // move-capable overload
     634             :       template <typename... _Args>
     635             :         pair<iterator, bool>
     636             :         try_emplace(key_type&& __k, _Args&&... __args)
     637             :         {
     638             :           iterator __i = lower_bound(__k);
     639             :           if (__i == end() || key_comp()(__k, (*__i).first))
     640             :             {
     641             :               __i = emplace_hint(__i, std::piecewise_construct,
     642             :                                  std::forward_as_tuple(std::move(__k)),
     643             :                                  std::forward_as_tuple(
     644             :                                    std::forward<_Args>(__args)...));
     645             :               return {__i, true};
     646             :             }
     647             :           return {__i, false};
     648             :         }
     649             : 
     650             :       /**
     651             :        *  @brief Attempts to build and insert a std::pair into the %map.
     652             :        *
     653             :        *  @param  __hint  An iterator that serves as a hint as to where the
     654             :        *                  pair should be inserted.
     655             :        *  @param __k    Key to use for finding a possibly existing pair in
     656             :        *                the map.
     657             :        *  @param __args  Arguments used to generate the .second for a new pair 
     658             :        *                instance.
     659             :        *  @return An iterator that points to the element with key of the
     660             :        *          std::pair built from @a __args (may or may not be that
     661             :        *          std::pair).
     662             :        *
     663             :        *  This function is not concerned about whether the insertion took place,
     664             :        *  and thus does not return a boolean like the single-argument 
     665             :        *  try_emplace() does. However, if insertion did not take place,
     666             :        *  this function has no effect.
     667             :        *  Note that the first parameter is only a hint and can potentially
     668             :        *  improve the performance of the insertion process. A bad hint would
     669             :        *  cause no gains in efficiency.
     670             :        *
     671             :        *  See
     672             :        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
     673             :        *  for more on @a hinting.
     674             :        *
     675             :        *  Insertion requires logarithmic time (if the hint is not taken).
     676             :        */
     677             :       template <typename... _Args>
     678             :         iterator
     679             :         try_emplace(const_iterator __hint, const key_type& __k,
     680             :                     _Args&&... __args)
     681             :         {
     682             :           iterator __i;
     683             :           auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);
     684             :           if (__true_hint.second)
     685             :             __i = emplace_hint(iterator(__true_hint.second),
     686             :                                std::piecewise_construct,
     687             :                                std::forward_as_tuple(__k),
     688             :                                std::forward_as_tuple(
     689             :                                  std::forward<_Args>(__args)...));
     690             :           else
     691             :             __i = iterator(__true_hint.first);
     692             :           return __i;
     693             :         }
     694             : 
     695             :       // move-capable overload
     696             :       template <typename... _Args>
     697             :         iterator
     698             :         try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
     699             :         {
     700             :           iterator __i;
     701             :           auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);
     702             :           if (__true_hint.second)
     703             :             __i = emplace_hint(iterator(__true_hint.second),
     704             :                                std::piecewise_construct,
     705             :                                std::forward_as_tuple(std::move(__k)),
     706             :                                std::forward_as_tuple(
     707             :                                  std::forward<_Args>(__args)...));
     708             :           else
     709             :             __i = iterator(__true_hint.first);
     710             :           return __i;
     711             :         }
     712             : #endif
     713             : 
     714             :       /**
     715             :        *  @brief Attempts to insert a std::pair into the %map.
     716             : 
     717             :        *  @param __x Pair to be inserted (see std::make_pair for easy
     718             :        *             creation of pairs).
     719             :        *
     720             :        *  @return  A pair, of which the first element is an iterator that 
     721             :        *           points to the possibly inserted pair, and the second is 
     722             :        *           a bool that is true if the pair was actually inserted.
     723             :        *
     724             :        *  This function attempts to insert a (key, value) %pair into the %map.
     725             :        *  A %map relies on unique keys and thus a %pair is only inserted if its
     726             :        *  first element (the key) is not already present in the %map.
     727             :        *
     728             :        *  Insertion requires logarithmic time.
     729             :        */
     730             :       std::pair<iterator, bool>
     731             :       insert(const value_type& __x)
     732             :       { return _M_t._M_insert_unique(__x); }
     733             : 
     734             : #if __cplusplus >= 201103L
     735             :       template<typename _Pair, typename = typename
     736             :                std::enable_if<std::is_constructible<value_type,
     737             :                                                     _Pair&&>::value>::type>
     738             :         std::pair<iterator, bool>
     739             :         insert(_Pair&& __x)
     740             :         { return _M_t._M_insert_unique(std::forward<_Pair>(__x)); }
     741             : #endif
     742             : 
     743             : #if __cplusplus >= 201103L
     744             :       /**
     745             :        *  @brief Attempts to insert a list of std::pairs into the %map.
     746             :        *  @param  __list  A std::initializer_list<value_type> of pairs to be
     747             :        *                  inserted.
     748             :        *
     749             :        *  Complexity similar to that of the range constructor.
     750             :        */
     751             :       void
     752             :       insert(std::initializer_list<value_type> __list)
     753             :       { insert(__list.begin(), __list.end()); }
     754             : #endif
     755             : 
     756             :       /**
     757             :        *  @brief Attempts to insert a std::pair into the %map.
     758             :        *  @param  __position  An iterator that serves as a hint as to where the
     759             :        *                    pair should be inserted.
     760             :        *  @param  __x  Pair to be inserted (see std::make_pair for easy creation
     761             :        *               of pairs).
     762             :        *  @return An iterator that points to the element with key of
     763             :        *           @a __x (may or may not be the %pair passed in).
     764             :        *
     765             : 
     766             :        *  This function is not concerned about whether the insertion
     767             :        *  took place, and thus does not return a boolean like the
     768             :        *  single-argument insert() does.  Note that the first
     769             :        *  parameter is only a hint and can potentially improve the
     770             :        *  performance of the insertion process.  A bad hint would
     771             :        *  cause no gains in efficiency.
     772             :        *
     773             :        *  See
     774             :        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
     775             :        *  for more on @a hinting.
     776             :        *
     777             :        *  Insertion requires logarithmic time (if the hint is not taken).
     778             :        */
     779             :       iterator
     780             : #if __cplusplus >= 201103L
     781             :       insert(const_iterator __position, const value_type& __x)
     782             : #else
     783             :       insert(iterator __position, const value_type& __x)
     784             : #endif
     785             :       { return _M_t._M_insert_unique_(__position, __x); }
     786             : 
     787             : #if __cplusplus >= 201103L
     788             :       template<typename _Pair, typename = typename
     789             :                std::enable_if<std::is_constructible<value_type,
     790             :                                                     _Pair&&>::value>::type>
     791             :         iterator
     792             :         insert(const_iterator __position, _Pair&& __x)
     793             :         { return _M_t._M_insert_unique_(__position,
     794             :                                         std::forward<_Pair>(__x)); }
     795             : #endif
     796             : 
     797             :       /**
     798             :        *  @brief Template function that attempts to insert a range of elements.
     799             :        *  @param  __first  Iterator pointing to the start of the range to be
     800             :        *                   inserted.
     801             :        *  @param  __last  Iterator pointing to the end of the range.
     802             :        *
     803             :        *  Complexity similar to that of the range constructor.
     804             :        */
     805             :       template<typename _InputIterator>
     806             :         void
     807             :         insert(_InputIterator __first, _InputIterator __last)
     808             :         { _M_t._M_insert_unique(__first, __last); }
     809             : 
     810             : #if __cplusplus > 201402L
     811             : #define __cpp_lib_map_insertion 201411
     812             :       /**
     813             :        *  @brief Attempts to insert or assign a std::pair into the %map.
     814             :        *  @param __k    Key to use for finding a possibly existing pair in
     815             :        *                the map.
     816             :        *  @param __obj  Argument used to generate the .second for a pair 
     817             :        *                instance.
     818             :        *
     819             :        *  @return  A pair, of which the first element is an iterator that 
     820             :        *           points to the possibly inserted pair, and the second is 
     821             :        *           a bool that is true if the pair was actually inserted.
     822             :        *
     823             :        *  This function attempts to insert a (key, value) %pair into the %map.
     824             :        *  A %map relies on unique keys and thus a %pair is only inserted if its
     825             :        *  first element (the key) is not already present in the %map.
     826             :        *  If the %pair was already in the %map, the .second of the %pair
     827             :        *  is assigned from __obj.
     828             :        *
     829             :        *  Insertion requires logarithmic time.
     830             :        */
     831             :       template <typename _Obj>
     832             :         pair<iterator, bool>
     833             :         insert_or_assign(const key_type& __k, _Obj&& __obj)
     834             :         {
     835             :           iterator __i = lower_bound(__k);
     836             :           if (__i == end() || key_comp()(__k, (*__i).first))
     837             :             {
     838             :               __i = emplace_hint(__i, std::piecewise_construct,
     839             :                                  std::forward_as_tuple(__k),
     840             :                                  std::forward_as_tuple(
     841             :                                    std::forward<_Obj>(__obj)));
     842             :               return {__i, true};
     843             :             }
     844             :           (*__i).second = std::forward<_Obj>(__obj);
     845             :           return {__i, false};
     846             :         }
     847             : 
     848             :       // move-capable overload
     849             :       template <typename _Obj>
     850             :         pair<iterator, bool>
     851             :         insert_or_assign(key_type&& __k, _Obj&& __obj)
     852             :         {
     853             :           iterator __i = lower_bound(__k);
     854             :           if (__i == end() || key_comp()(__k, (*__i).first))
     855             :             {
     856             :               __i = emplace_hint(__i, std::piecewise_construct,
     857             :                                  std::forward_as_tuple(std::move(__k)),
     858             :                                  std::forward_as_tuple(
     859             :                                    std::forward<_Obj>(__obj)));
     860             :               return {__i, true};
     861             :             }
     862             :           (*__i).second = std::forward<_Obj>(__obj);
     863             :           return {__i, false};
     864             :         }
     865             : 
     866             :       /**
     867             :        *  @brief Attempts to insert or assign a std::pair into the %map.
     868             :        *  @param  __hint  An iterator that serves as a hint as to where the
     869             :        *                  pair should be inserted.
     870             :        *  @param __k    Key to use for finding a possibly existing pair in
     871             :        *                the map.
     872             :        *  @param __obj  Argument used to generate the .second for a pair 
     873             :        *                instance.
     874             :        *
     875             :        *  @return An iterator that points to the element with key of
     876             :        *           @a __x (may or may not be the %pair passed in).
     877             :        *
     878             :        *  This function attempts to insert a (key, value) %pair into the %map.
     879             :        *  A %map relies on unique keys and thus a %pair is only inserted if its
     880             :        *  first element (the key) is not already present in the %map.
     881             :        *  If the %pair was already in the %map, the .second of the %pair
     882             :        *  is assigned from __obj.
     883             :        *
     884             :        *  Insertion requires logarithmic time.
     885             :        */
     886             :       template <typename _Obj>
     887             :         iterator
     888             :         insert_or_assign(const_iterator __hint,
     889             :                          const key_type& __k, _Obj&& __obj)
     890             :         {
     891             :           iterator __i;
     892             :           auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);
     893             :           if (__true_hint.second)
     894             :             {
     895             :               return emplace_hint(iterator(__true_hint.second),
     896             :                                   std::piecewise_construct,
     897             :                                   std::forward_as_tuple(__k),
     898             :                                   std::forward_as_tuple(
     899             :                                     std::forward<_Obj>(__obj)));
     900             :             }
     901             :           __i = iterator(__true_hint.first);
     902             :           (*__i).second = std::forward<_Obj>(__obj);
     903             :           return __i;
     904             :         }
     905             : 
     906             :       // move-capable overload
     907             :       template <typename _Obj>
     908             :         iterator
     909             :         insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
     910             :         {
     911             :           iterator __i;
     912             :           auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);
     913             :           if (__true_hint.second)
     914             :             {
     915             :               return emplace_hint(iterator(__true_hint.second),
     916             :                                   std::piecewise_construct,
     917             :                                   std::forward_as_tuple(std::move(__k)),
     918             :                                   std::forward_as_tuple(
     919             :                                     std::forward<_Obj>(__obj)));
     920             :             }
     921             :           __i = iterator(__true_hint.first);
     922             :           (*__i).second = std::forward<_Obj>(__obj);
     923             :           return __i;
     924             :         }
     925             : #endif
     926             : 
     927             : #if __cplusplus >= 201103L
     928             :       // _GLIBCXX_RESOLVE_LIB_DEFECTS
     929             :       // DR 130. Associative erase should return an iterator.
     930             :       /**
     931             :        *  @brief Erases an element from a %map.
     932             :        *  @param  __position  An iterator pointing to the element to be erased.
     933             :        *  @return An iterator pointing to the element immediately following
     934             :        *          @a position prior to the element being erased. If no such 
     935             :        *          element exists, end() is returned.
     936             :        *
     937             :        *  This function erases an element, pointed to by the given
     938             :        *  iterator, from a %map.  Note that this function only erases
     939             :        *  the element, and that if the element is itself a pointer,
     940             :        *  the pointed-to memory is not touched in any way.  Managing
     941             :        *  the pointer is the user's responsibility.
     942             :        */
     943             :       iterator
     944             :       erase(const_iterator __position)
     945             :       { return _M_t.erase(__position); }
     946             : 
     947             :       // LWG 2059
     948             :       _GLIBCXX_ABI_TAG_CXX11
     949             :       iterator
     950             :       erase(iterator __position)
     951             :       { return _M_t.erase(__position); }
     952             : #else
     953             :       /**
     954             :        *  @brief Erases an element from a %map.
     955             :        *  @param  __position  An iterator pointing to the element to be erased.
     956             :        *
     957             :        *  This function erases an element, pointed to by the given
     958             :        *  iterator, from a %map.  Note that this function only erases
     959             :        *  the element, and that if the element is itself a pointer,
     960             :        *  the pointed-to memory is not touched in any way.  Managing
     961             :        *  the pointer is the user's responsibility.
     962             :        */
     963             :       void
     964             :       erase(iterator __position)
     965             :       { _M_t.erase(__position); }
     966             : #endif
     967             : 
     968             :       /**
     969             :        *  @brief Erases elements according to the provided key.
     970             :        *  @param  __x  Key of element to be erased.
     971             :        *  @return  The number of elements erased.
     972             :        *
     973             :        *  This function erases all the elements located by the given key from
     974             :        *  a %map.
     975             :        *  Note that this function only erases the element, and that if
     976             :        *  the element is itself a pointer, the pointed-to memory is not touched
     977             :        *  in any way.  Managing the pointer is the user's responsibility.
     978             :        */
     979             :       size_type
     980             :       erase(const key_type& __x)
     981             :       { return _M_t.erase(__x); }
     982             : 
     983             : #if __cplusplus >= 201103L
     984             :       // _GLIBCXX_RESOLVE_LIB_DEFECTS
     985             :       // DR 130. Associative erase should return an iterator.
     986             :       /**
     987             :        *  @brief Erases a [first,last) range of elements from a %map.
     988             :        *  @param  __first  Iterator pointing to the start of the range to be
     989             :        *                   erased.
     990             :        *  @param __last Iterator pointing to the end of the range to
     991             :        *                be erased.
     992             :        *  @return The iterator @a __last.
     993             :        *
     994             :        *  This function erases a sequence of elements from a %map.
     995             :        *  Note that this function only erases the element, and that if
     996             :        *  the element is itself a pointer, the pointed-to memory is not touched
     997             :        *  in any way.  Managing the pointer is the user's responsibility.
     998             :        */
     999             :       iterator
    1000             :       erase(const_iterator __first, const_iterator __last)
    1001             :       { return _M_t.erase(__first, __last); }
    1002             : #else
    1003             :       /**
    1004             :        *  @brief Erases a [__first,__last) range of elements from a %map.
    1005             :        *  @param  __first  Iterator pointing to the start of the range to be
    1006             :        *                   erased.
    1007             :        *  @param __last Iterator pointing to the end of the range to
    1008             :        *                be erased.
    1009             :        *
    1010             :        *  This function erases a sequence of elements from a %map.
    1011             :        *  Note that this function only erases the element, and that if
    1012             :        *  the element is itself a pointer, the pointed-to memory is not touched
    1013             :        *  in any way.  Managing the pointer is the user's responsibility.
    1014             :        */
    1015             :       void
    1016             :       erase(iterator __first, iterator __last)
    1017             :       { _M_t.erase(__first, __last); }
    1018             : #endif
    1019             : 
    1020             :       /**
    1021             :        *  @brief  Swaps data with another %map.
    1022             :        *  @param  __x  A %map of the same element and allocator types.
    1023             :        *
    1024             :        *  This exchanges the elements between two maps in constant
    1025             :        *  time.  (It is only swapping a pointer, an integer, and an
    1026             :        *  instance of the @c Compare type (which itself is often
    1027             :        *  stateless and empty), so it should be quite fast.)  Note
    1028             :        *  that the global std::swap() function is specialized such
    1029             :        *  that std::swap(m1,m2) will feed to this function.
    1030             :        */
    1031             :       void
    1032             :       swap(map& __x)
    1033             :       _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
    1034             :       { _M_t.swap(__x._M_t); }
    1035             : 
    1036             :       /**
    1037             :        *  Erases all elements in a %map.  Note that this function only
    1038             :        *  erases the elements, and that if the elements themselves are
    1039             :        *  pointers, the pointed-to memory is not touched in any way.
    1040             :        *  Managing the pointer is the user's responsibility.
    1041             :        */
    1042             :       void
    1043             :       clear() _GLIBCXX_NOEXCEPT
    1044             :       { _M_t.clear(); }
    1045             : 
    1046             :       // observers
    1047             :       /**
    1048             :        *  Returns the key comparison object out of which the %map was
    1049             :        *  constructed.
    1050             :        */
    1051             :       key_compare
    1052           0 :       key_comp() const
    1053           0 :       { return _M_t.key_comp(); }
    1054             : 
    1055             :       /**
    1056             :        *  Returns a value comparison object, built from the key comparison
    1057             :        *  object out of which the %map was constructed.
    1058             :        */
    1059             :       value_compare
    1060             :       value_comp() const
    1061             :       { return value_compare(_M_t.key_comp()); }
    1062             : 
    1063             :       // [23.3.1.3] map operations
    1064             : 
    1065             :       //@{
    1066             :       /**
    1067             :        *  @brief Tries to locate an element in a %map.
    1068             :        *  @param  __x  Key of (key, value) %pair to be located.
    1069             :        *  @return  Iterator pointing to sought-after element, or end() if not
    1070             :        *           found.
    1071             :        *
    1072             :        *  This function takes a key and tries to locate the element with which
    1073             :        *  the key matches.  If successful the function returns an iterator
    1074             :        *  pointing to the sought after %pair.  If unsuccessful it returns the
    1075             :        *  past-the-end ( @c end() ) iterator.
    1076             :        */
    1077             : 
    1078             :       iterator
    1079             :       find(const key_type& __x)
    1080             :       { return _M_t.find(__x); }
    1081             : 
    1082             : #if __cplusplus > 201103L
    1083             :       template<typename _Kt>
    1084             :         auto
    1085             :         find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x))
    1086             :         { return _M_t._M_find_tr(__x); }
    1087             : #endif
    1088             :       //@}
    1089             : 
    1090             :       //@{
    1091             :       /**
    1092             :        *  @brief Tries to locate an element in a %map.
    1093             :        *  @param  __x  Key of (key, value) %pair to be located.
    1094             :        *  @return  Read-only (constant) iterator pointing to sought-after
    1095             :        *           element, or end() if not found.
    1096             :        *
    1097             :        *  This function takes a key and tries to locate the element with which
    1098             :        *  the key matches.  If successful the function returns a constant
    1099             :        *  iterator pointing to the sought after %pair. If unsuccessful it
    1100             :        *  returns the past-the-end ( @c end() ) iterator.
    1101             :        */
    1102             : 
    1103             :       const_iterator
    1104           0 :       find(const key_type& __x) const
    1105           0 :       { return _M_t.find(__x); }
    1106             : 
    1107             : #if __cplusplus > 201103L
    1108             :       template<typename _Kt>
    1109             :         auto
    1110             :         find(const _Kt& __x) const -> decltype(_M_t._M_find_tr(__x))
    1111             :         { return _M_t._M_find_tr(__x); }
    1112             : #endif
    1113             :       //@}
    1114             : 
    1115             :       //@{
    1116             :       /**
    1117             :        *  @brief  Finds the number of elements with given key.
    1118             :        *  @param  __x  Key of (key, value) pairs to be located.
    1119             :        *  @return  Number of elements with specified key.
    1120             :        *
    1121             :        *  This function only makes sense for multimaps; for map the result will
    1122             :        *  either be 0 (not present) or 1 (present).
    1123             :        */
    1124             :       size_type
    1125             :       count(const key_type& __x) const
    1126             :       { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
    1127             : 
    1128             : #if __cplusplus > 201103L
    1129             :       template<typename _Kt>
    1130             :         auto
    1131             :         count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x))
    1132             :         { return _M_t._M_count_tr(__x); }
    1133             : #endif
    1134             :       //@}
    1135             : 
    1136             :       //@{
    1137             :       /**
    1138             :        *  @brief Finds the beginning of a subsequence matching given key.
    1139             :        *  @param  __x  Key of (key, value) pair to be located.
    1140             :        *  @return  Iterator pointing to first element equal to or greater
    1141             :        *           than key, or end().
    1142             :        *
    1143             :        *  This function returns the first element of a subsequence of elements
    1144             :        *  that matches the given key.  If unsuccessful it returns an iterator
    1145             :        *  pointing to the first element that has a greater value than given key
    1146             :        *  or end() if no such element exists.
    1147             :        */
    1148             :       iterator
    1149           0 :       lower_bound(const key_type& __x)
    1150           0 :       { return _M_t.lower_bound(__x); }
    1151             : 
    1152             : #if __cplusplus > 201103L
    1153             :       template<typename _Kt>
    1154             :         auto
    1155             :         lower_bound(const _Kt& __x)
    1156             :         -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
    1157             :         { return iterator(_M_t._M_lower_bound_tr(__x)); }
    1158             : #endif
    1159             :       //@}
    1160             : 
    1161             :       //@{
    1162             :       /**
    1163             :        *  @brief Finds the beginning of a subsequence matching given key.
    1164             :        *  @param  __x  Key of (key, value) pair to be located.
    1165             :        *  @return  Read-only (constant) iterator pointing to first element
    1166             :        *           equal to or greater than key, or end().
    1167             :        *
    1168             :        *  This function returns the first element of a subsequence of elements
    1169             :        *  that matches the given key.  If unsuccessful it returns an iterator
    1170             :        *  pointing to the first element that has a greater value than given key
    1171             :        *  or end() if no such element exists.
    1172             :        */
    1173             :       const_iterator
    1174             :       lower_bound(const key_type& __x) const
    1175             :       { return _M_t.lower_bound(__x); }
    1176             : 
    1177             : #if __cplusplus > 201103L
    1178             :       template<typename _Kt>
    1179             :         auto
    1180             :         lower_bound(const _Kt& __x) const
    1181             :         -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x)))
    1182             :         { return const_iterator(_M_t._M_lower_bound_tr(__x)); }
    1183             : #endif
    1184             :       //@}
    1185             : 
    1186             :       //@{
    1187             :       /**
    1188             :        *  @brief Finds the end of a subsequence matching given key.
    1189             :        *  @param  __x  Key of (key, value) pair to be located.
    1190             :        *  @return Iterator pointing to the first element
    1191             :        *          greater than key, or end().
    1192             :        */
    1193             :       iterator
    1194             :       upper_bound(const key_type& __x)
    1195             :       { return _M_t.upper_bound(__x); }
    1196             : 
    1197             : #if __cplusplus > 201103L
    1198             :       template<typename _Kt>
    1199             :         auto
    1200             :         upper_bound(const _Kt& __x)
    1201             :         -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
    1202             :         { return iterator(_M_t._M_upper_bound_tr(__x)); }
    1203             : #endif
    1204             :       //@}
    1205             : 
    1206             :       //@{
    1207             :       /**
    1208             :        *  @brief Finds the end of a subsequence matching given key.
    1209             :        *  @param  __x  Key of (key, value) pair to be located.
    1210             :        *  @return  Read-only (constant) iterator pointing to first iterator
    1211             :        *           greater than key, or end().
    1212             :        */
    1213             :       const_iterator
    1214             :       upper_bound(const key_type& __x) const
    1215             :       { return _M_t.upper_bound(__x); }
    1216             : 
    1217             : #if __cplusplus > 201103L
    1218             :       template<typename _Kt>
    1219             :         auto
    1220             :         upper_bound(const _Kt& __x) const
    1221             :         -> decltype(const_iterator(_M_t._M_upper_bound_tr(__x)))
    1222             :         { return const_iterator(_M_t._M_upper_bound_tr(__x)); }
    1223             : #endif
    1224             :       //@}
    1225             : 
    1226             :       //@{
    1227             :       /**
    1228             :        *  @brief Finds a subsequence matching given key.
    1229             :        *  @param  __x  Key of (key, value) pairs to be located.
    1230             :        *  @return  Pair of iterators that possibly points to the subsequence
    1231             :        *           matching given key.
    1232             :        *
    1233             :        *  This function is equivalent to
    1234             :        *  @code
    1235             :        *    std::make_pair(c.lower_bound(val),
    1236             :        *                   c.upper_bound(val))
    1237             :        *  @endcode
    1238             :        *  (but is faster than making the calls separately).
    1239             :        *
    1240             :        *  This function probably only makes sense for multimaps.
    1241             :        */
    1242             :       std::pair<iterator, iterator>
    1243             :       equal_range(const key_type& __x)
    1244             :       { return _M_t.equal_range(__x); }
    1245             : 
    1246             : #if __cplusplus > 201103L
    1247             :       template<typename _Kt>
    1248             :         auto
    1249             :         equal_range(const _Kt& __x)
    1250             :         -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)))
    1251             :         { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); }
    1252             : #endif
    1253             :       //@}
    1254             : 
    1255             :       //@{
    1256             :       /**
    1257             :        *  @brief Finds a subsequence matching given key.
    1258             :        *  @param  __x  Key of (key, value) pairs to be located.
    1259             :        *  @return  Pair of read-only (constant) iterators that possibly points
    1260             :        *           to the subsequence matching given key.
    1261             :        *
    1262             :        *  This function is equivalent to
    1263             :        *  @code
    1264             :        *    std::make_pair(c.lower_bound(val),
    1265             :        *                   c.upper_bound(val))
    1266             :        *  @endcode
    1267             :        *  (but is faster than making the calls separately).
    1268             :        *
    1269             :        *  This function probably only makes sense for multimaps.
    1270             :        */
    1271             :       std::pair<const_iterator, const_iterator>
    1272             :       equal_range(const key_type& __x) const
    1273             :       { return _M_t.equal_range(__x); }
    1274             : 
    1275             : #if __cplusplus > 201103L
    1276             :       template<typename _Kt>
    1277             :         auto
    1278             :         equal_range(const _Kt& __x) const
    1279             :         -> decltype(pair<const_iterator, const_iterator>(
    1280             :               _M_t._M_equal_range_tr(__x)))
    1281             :         {
    1282             :           return pair<const_iterator, const_iterator>(
    1283             :               _M_t._M_equal_range_tr(__x));
    1284             :         }
    1285             : #endif
    1286             :       //@}
    1287             : 
    1288             :       template<typename _K1, typename _T1, typename _C1, typename _A1>
    1289             :         friend bool
    1290             :         operator==(const map<_K1, _T1, _C1, _A1>&,
    1291             :                    const map<_K1, _T1, _C1, _A1>&);
    1292             : 
    1293             :       template<typename _K1, typename _T1, typename _C1, typename _A1>
    1294             :         friend bool
    1295             :         operator<(const map<_K1, _T1, _C1, _A1>&,
    1296             :                   const map<_K1, _T1, _C1, _A1>&);
    1297             :     };
    1298             : 
    1299             :   /**
    1300             :    *  @brief  Map equality comparison.
    1301             :    *  @param  __x  A %map.
    1302             :    *  @param  __y  A %map of the same type as @a x.
    1303             :    *  @return  True iff the size and elements of the maps are equal.
    1304             :    *
    1305             :    *  This is an equivalence relation.  It is linear in the size of the
    1306             :    *  maps.  Maps are considered equivalent if their sizes are equal,
    1307             :    *  and if corresponding elements compare equal.
    1308             :   */
    1309             :   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
    1310             :     inline bool
    1311             :     operator==(const map<_Key, _Tp, _Compare, _Alloc>& __x,
    1312             :                const map<_Key, _Tp, _Compare, _Alloc>& __y)
    1313             :     { return __x._M_t == __y._M_t; }
    1314             : 
    1315             :   /**
    1316             :    *  @brief  Map ordering relation.
    1317             :    *  @param  __x  A %map.
    1318             :    *  @param  __y  A %map of the same type as @a x.
    1319             :    *  @return  True iff @a x is lexicographically less than @a y.
    1320             :    *
    1321             :    *  This is a total ordering relation.  It is linear in the size of the
    1322             :    *  maps.  The elements must be comparable with @c <.
    1323             :    *
    1324             :    *  See std::lexicographical_compare() for how the determination is made.
    1325             :   */
    1326             :   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
    1327             :     inline bool
    1328             :     operator<(const map<_Key, _Tp, _Compare, _Alloc>& __x,
    1329             :               const map<_Key, _Tp, _Compare, _Alloc>& __y)
    1330             :     { return __x._M_t < __y._M_t; }
    1331             : 
    1332             :   /// Based on operator==
    1333             :   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
    1334             :     inline bool
    1335             :     operator!=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
    1336             :                const map<_Key, _Tp, _Compare, _Alloc>& __y)
    1337             :     { return !(__x == __y); }
    1338             : 
    1339             :   /// Based on operator<
    1340             :   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
    1341             :     inline bool
    1342             :     operator>(const map<_Key, _Tp, _Compare, _Alloc>& __x,
    1343             :               const map<_Key, _Tp, _Compare, _Alloc>& __y)
    1344             :     { return __y < __x; }
    1345             : 
    1346             :   /// Based on operator<
    1347             :   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
    1348             :     inline bool
    1349             :     operator<=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
    1350             :                const map<_Key, _Tp, _Compare, _Alloc>& __y)
    1351             :     { return !(__y < __x); }
    1352             : 
    1353             :   /// Based on operator<
    1354             :   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
    1355             :     inline bool
    1356             :     operator>=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
    1357             :                const map<_Key, _Tp, _Compare, _Alloc>& __y)
    1358             :     { return !(__x < __y); }
    1359             : 
    1360             :   /// See std::map::swap().
    1361             :   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
    1362             :     inline void
    1363             :     swap(map<_Key, _Tp, _Compare, _Alloc>& __x,
    1364             :          map<_Key, _Tp, _Compare, _Alloc>& __y)
    1365             :     _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
    1366             :     { __x.swap(__y); }
    1367             : 
    1368             : _GLIBCXX_END_NAMESPACE_CONTAINER
    1369             : } // namespace std
    1370             : 
    1371             : #endif /* _STL_MAP_H */

Generated by: LCOV version 1.13