LCOV - code coverage report
Current view: top level - usr/include/c++/4.9/bits - stl_map.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 0 19 0.0 %
Date: 2016-12-01 18:45:36 Functions: 0 8 0.0 %

          Line data    Source code
       1             : // Map implementation -*- C++ -*-
       2             : 
       3             : // Copyright (C) 2001-2014 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           0 :       : _M_t() { }
     164             : 
     165             :       /**
     166             :        *  @brief  Creates a %map with no elements.
     167             :        *  @param  __comp  A comparison object.
     168             :        *  @param  __a  An allocator object.
     169             :        */
     170             :       explicit
     171             :       map(const _Compare& __comp,
     172             :           const allocator_type& __a = allocator_type())
     173             :       : _M_t(__comp, _Pair_alloc_type(__a)) { }
     174             : 
     175             :       /**
     176             :        *  @brief  %Map copy constructor.
     177             :        *  @param  __x  A %map of identical element and allocator types.
     178             :        *
     179             :        *  The newly-created %map uses a copy of the allocation object
     180             :        *  used by @a __x.
     181             :        */
     182             :       map(const map& __x)
     183             :       : _M_t(__x._M_t) { }
     184             : 
     185             : #if __cplusplus >= 201103L
     186             :       /**
     187             :        *  @brief  %Map move constructor.
     188             :        *  @param  __x  A %map of identical element and allocator types.
     189             :        *
     190             :        *  The newly-created %map contains the exact contents of @a __x.
     191             :        *  The contents of @a __x are a valid, but unspecified %map.
     192             :        */
     193             :       map(map&& __x)
     194             :       noexcept(is_nothrow_copy_constructible<_Compare>::value)
     195             :       : _M_t(std::move(__x._M_t)) { }
     196             : 
     197             :       /**
     198             :        *  @brief  Builds a %map from an initializer_list.
     199             :        *  @param  __l  An initializer_list.
     200             :        *  @param  __comp  A comparison object.
     201             :        *  @param  __a  An allocator object.
     202             :        *
     203             :        *  Create a %map consisting of copies of the elements in the
     204             :        *  initializer_list @a __l.
     205             :        *  This is linear in N if the range is already sorted, and NlogN
     206             :        *  otherwise (where N is @a __l.size()).
     207             :        */
     208             :       map(initializer_list<value_type> __l,
     209             :           const _Compare& __comp = _Compare(),
     210             :           const allocator_type& __a = allocator_type())
     211             :       : _M_t(__comp, _Pair_alloc_type(__a))
     212             :       { _M_t._M_insert_unique(__l.begin(), __l.end()); }
     213             : 
     214             :       /// Allocator-extended default constructor.
     215             :       explicit
     216             :       map(const allocator_type& __a)
     217             :       : _M_t(_Compare(), _Pair_alloc_type(__a)) { }
     218             : 
     219             :       /// Allocator-extended copy constructor.
     220             :       map(const map& __m, const allocator_type& __a)
     221             :       : _M_t(__m._M_t, _Pair_alloc_type(__a)) { }
     222             : 
     223             :       /// Allocator-extended move constructor.
     224             :       map(map&& __m, const allocator_type& __a)
     225             :       noexcept(is_nothrow_copy_constructible<_Compare>::value
     226             :                && _Alloc_traits::_S_always_equal())
     227             :       : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { }
     228             : 
     229             :       /// Allocator-extended initialier-list constructor.
     230             :       map(initializer_list<value_type> __l, const allocator_type& __a)
     231             :       : _M_t(_Compare(), _Pair_alloc_type(__a))
     232             :       { _M_t._M_insert_unique(__l.begin(), __l.end()); }
     233             : 
     234             :       /// Allocator-extended range constructor.
     235             :       template<typename _InputIterator>
     236             :         map(_InputIterator __first, _InputIterator __last,
     237             :             const allocator_type& __a)
     238             :         : _M_t(_Compare(), _Pair_alloc_type(__a))
     239             :         { _M_t._M_insert_unique(__first, __last); }
     240             : #endif
     241             : 
     242             :       /**
     243             :        *  @brief  Builds a %map from a range.
     244             :        *  @param  __first  An input iterator.
     245             :        *  @param  __last  An input iterator.
     246             :        *
     247             :        *  Create a %map consisting of copies of the elements from
     248             :        *  [__first,__last).  This is linear in N if the range is
     249             :        *  already sorted, and NlogN otherwise (where N is
     250             :        *  distance(__first,__last)).
     251             :        */
     252             :       template<typename _InputIterator>
     253             :         map(_InputIterator __first, _InputIterator __last)
     254             :         : _M_t()
     255             :         { _M_t._M_insert_unique(__first, __last); }
     256             : 
     257             :       /**
     258             :        *  @brief  Builds a %map from a range.
     259             :        *  @param  __first  An input iterator.
     260             :        *  @param  __last  An input iterator.
     261             :        *  @param  __comp  A comparison functor.
     262             :        *  @param  __a  An allocator object.
     263             :        *
     264             :        *  Create a %map consisting of copies of the elements from
     265             :        *  [__first,__last).  This is linear in N if the range is
     266             :        *  already sorted, and NlogN otherwise (where N is
     267             :        *  distance(__first,__last)).
     268             :        */
     269             :       template<typename _InputIterator>
     270             :         map(_InputIterator __first, _InputIterator __last,
     271             :             const _Compare& __comp,
     272             :             const allocator_type& __a = allocator_type())
     273             :         : _M_t(__comp, _Pair_alloc_type(__a))
     274             :         { _M_t._M_insert_unique(__first, __last); }
     275             : 
     276             :       // FIXME There is no dtor declared, but we should have something
     277             :       // generated by Doxygen.  I don't know what tags to add to this
     278             :       // paragraph to make that happen:
     279             :       /**
     280             :        *  The dtor only erases the elements, and note that if the elements
     281             :        *  themselves are pointers, the pointed-to memory is not touched in any
     282             :        *  way.  Managing the pointer is the user's responsibility.
     283             :        */
     284             : 
     285             :       /**
     286             :        *  @brief  %Map assignment operator.
     287             :        *  @param  __x  A %map of identical element and allocator types.
     288             :        *
     289             :        *  All the elements of @a __x are copied, but unlike the copy
     290             :        *  constructor, the allocator object is not copied.
     291             :        */
     292             :       map&
     293             :       operator=(const map& __x)
     294             :       {
     295             :         _M_t = __x._M_t;
     296             :         return *this;
     297             :       }
     298             : 
     299             : #if __cplusplus >= 201103L
     300             :       /**
     301             :        *  @brief  %Map move assignment operator.
     302             :        *  @param  __x  A %map of identical element and allocator types.
     303             :        *
     304             :        *  The contents of @a __x are moved into this map (without copying
     305             :        *  if the allocators compare equal or get moved on assignment).
     306             :        *  Afterwards @a __x is in a valid, but unspecified state.
     307             :        */
     308             :       map&
     309             :       operator=(map&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
     310             :       {
     311             :         if (!_M_t._M_move_assign(__x._M_t))
     312             :           {
     313             :             // The rvalue's allocator cannot be moved and is not equal,
     314             :             // so we need to individually move each element.
     315             :             clear();
     316             :             insert(std::__make_move_if_noexcept_iterator(__x.begin()),
     317             :                    std::__make_move_if_noexcept_iterator(__x.end()));
     318             :             __x.clear();
     319             :           }
     320             :         return *this;
     321             :       }
     322             : 
     323             :       /**
     324             :        *  @brief  %Map list assignment operator.
     325             :        *  @param  __l  An initializer_list.
     326             :        *
     327             :        *  This function fills a %map with copies of the elements in the
     328             :        *  initializer list @a __l.
     329             :        *
     330             :        *  Note that the assignment completely changes the %map and
     331             :        *  that the resulting %map's size is the same as the number
     332             :        *  of elements assigned.  Old data may be lost.
     333             :        */
     334             :       map&
     335             :       operator=(initializer_list<value_type> __l)
     336             :       {
     337             :         this->clear();
     338             :         this->insert(__l.begin(), __l.end());
     339             :         return *this;
     340             :       }
     341             : #endif
     342             : 
     343             :       /// Get a copy of the memory allocation object.
     344             :       allocator_type
     345             :       get_allocator() const _GLIBCXX_NOEXCEPT
     346             :       { return allocator_type(_M_t.get_allocator()); }
     347             : 
     348             :       // iterators
     349             :       /**
     350             :        *  Returns a read/write iterator that points to the first pair in the
     351             :        *  %map.
     352             :        *  Iteration is done in ascending order according to the keys.
     353             :        */
     354             :       iterator
     355             :       begin() _GLIBCXX_NOEXCEPT
     356             :       { return _M_t.begin(); }
     357             : 
     358             :       /**
     359             :        *  Returns a read-only (constant) iterator that points to the first pair
     360             :        *  in the %map.  Iteration is done in ascending order according to the
     361             :        *  keys.
     362             :        */
     363             :       const_iterator
     364             :       begin() const _GLIBCXX_NOEXCEPT
     365             :       { return _M_t.begin(); }
     366             : 
     367             :       /**
     368             :        *  Returns a read/write iterator that points one past the last
     369             :        *  pair in the %map.  Iteration is done in ascending order
     370             :        *  according to the keys.
     371             :        */
     372             :       iterator
     373           0 :       end() _GLIBCXX_NOEXCEPT
     374           0 :       { return _M_t.end(); }
     375             : 
     376             :       /**
     377             :        *  Returns a read-only (constant) iterator that points one past the last
     378             :        *  pair in the %map.  Iteration is done in ascending order according to
     379             :        *  the keys.
     380             :        */
     381             :       const_iterator
     382           0 :       end() const _GLIBCXX_NOEXCEPT
     383           0 :       { return _M_t.end(); }
     384             : 
     385             :       /**
     386             :        *  Returns a read/write reverse iterator that points to the last pair in
     387             :        *  the %map.  Iteration is done in descending order according to the
     388             :        *  keys.
     389             :        */
     390             :       reverse_iterator
     391             :       rbegin() _GLIBCXX_NOEXCEPT
     392             :       { return _M_t.rbegin(); }
     393             : 
     394             :       /**
     395             :        *  Returns a read-only (constant) reverse iterator that points to the
     396             :        *  last pair in the %map.  Iteration is done in descending order
     397             :        *  according to the keys.
     398             :        */
     399             :       const_reverse_iterator
     400             :       rbegin() const _GLIBCXX_NOEXCEPT
     401             :       { return _M_t.rbegin(); }
     402             : 
     403             :       /**
     404             :        *  Returns a read/write reverse iterator that points to one before the
     405             :        *  first pair in the %map.  Iteration is done in descending order
     406             :        *  according to the keys.
     407             :        */
     408             :       reverse_iterator
     409             :       rend() _GLIBCXX_NOEXCEPT
     410             :       { return _M_t.rend(); }
     411             : 
     412             :       /**
     413             :        *  Returns a read-only (constant) reverse iterator that points to one
     414             :        *  before the first pair in the %map.  Iteration is done in descending
     415             :        *  order according to the keys.
     416             :        */
     417             :       const_reverse_iterator
     418             :       rend() const _GLIBCXX_NOEXCEPT
     419             :       { return _M_t.rend(); }
     420             : 
     421             : #if __cplusplus >= 201103L
     422             :       /**
     423             :        *  Returns a read-only (constant) iterator that points to the first pair
     424             :        *  in the %map.  Iteration is done in ascending order according to the
     425             :        *  keys.
     426             :        */
     427             :       const_iterator
     428             :       cbegin() const noexcept
     429             :       { return _M_t.begin(); }
     430             : 
     431             :       /**
     432             :        *  Returns a read-only (constant) iterator that points one past the last
     433             :        *  pair in the %map.  Iteration is done in ascending order according to
     434             :        *  the keys.
     435             :        */
     436             :       const_iterator
     437             :       cend() const noexcept
     438             :       { return _M_t.end(); }
     439             : 
     440             :       /**
     441             :        *  Returns a read-only (constant) reverse iterator that points to the
     442             :        *  last pair in the %map.  Iteration is done in descending order
     443             :        *  according to the keys.
     444             :        */
     445             :       const_reverse_iterator
     446             :       crbegin() const noexcept
     447             :       { return _M_t.rbegin(); }
     448             : 
     449             :       /**
     450             :        *  Returns a read-only (constant) reverse iterator that points to one
     451             :        *  before the first pair in the %map.  Iteration is done in descending
     452             :        *  order according to the keys.
     453             :        */
     454             :       const_reverse_iterator
     455             :       crend() const noexcept
     456             :       { return _M_t.rend(); }
     457             : #endif
     458             : 
     459             :       // capacity
     460             :       /** Returns true if the %map is empty.  (Thus begin() would equal
     461             :        *  end().)
     462             :       */
     463             :       bool
     464             :       empty() const _GLIBCXX_NOEXCEPT
     465             :       { return _M_t.empty(); }
     466             : 
     467             :       /** Returns the size of the %map.  */
     468             :       size_type
     469             :       size() const _GLIBCXX_NOEXCEPT
     470             :       { return _M_t.size(); }
     471             : 
     472             :       /** Returns the maximum size of the %map.  */
     473             :       size_type
     474             :       max_size() const _GLIBCXX_NOEXCEPT
     475             :       { return _M_t.max_size(); }
     476             : 
     477             :       // [23.3.1.2] element access
     478             :       /**
     479             :        *  @brief  Subscript ( @c [] ) access to %map data.
     480             :        *  @param  __k  The key for which data should be retrieved.
     481             :        *  @return  A reference to the data of the (key,data) %pair.
     482             :        *
     483             :        *  Allows for easy lookup with the subscript ( @c [] )
     484             :        *  operator.  Returns data associated with the key specified in
     485             :        *  subscript.  If the key does not exist, a pair with that key
     486             :        *  is created using default values, which is then returned.
     487             :        *
     488             :        *  Lookup requires logarithmic time.
     489             :        */
     490             :       mapped_type&
     491             :       operator[](const key_type& __k)
     492             :       {
     493             :         // concept requirements
     494             :         __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)
     495             : 
     496             :         iterator __i = lower_bound(__k);
     497             :         // __i->first is greater than or equivalent to __k.
     498             :         if (__i == end() || key_comp()(__k, (*__i).first))
     499             : #if __cplusplus >= 201103L
     500             :           __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct,
     501             :                                             std::tuple<const key_type&>(__k),
     502             :                                             std::tuple<>());
     503             : #else
     504             :           __i = insert(__i, value_type(__k, mapped_type()));
     505             : #endif
     506             :         return (*__i).second;
     507             :       }
     508             : 
     509             : #if __cplusplus >= 201103L
     510             :       mapped_type&
     511           0 :       operator[](key_type&& __k)
     512             :       {
     513             :         // concept requirements
     514             :         __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)
     515             : 
     516           0 :         iterator __i = lower_bound(__k);
     517             :         // __i->first is greater than or equivalent to __k.
     518           0 :         if (__i == end() || key_comp()(__k, (*__i).first))
     519           0 :           __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct,
     520           0 :                                         std::forward_as_tuple(std::move(__k)),
     521             :                                         std::tuple<>());
     522           0 :         return (*__i).second;
     523             :       }
     524             : #endif
     525             : 
     526             :       // _GLIBCXX_RESOLVE_LIB_DEFECTS
     527             :       // DR 464. Suggestion for new member functions in standard containers.
     528             :       /**
     529             :        *  @brief  Access to %map data.
     530             :        *  @param  __k  The key for which data should be retrieved.
     531             :        *  @return  A reference to the data whose key is equivalent to @a __k, if
     532             :        *           such a data is present in the %map.
     533             :        *  @throw  std::out_of_range  If no such data is present.
     534             :        */
     535             :       mapped_type&
     536             :       at(const key_type& __k)
     537             :       {
     538             :         iterator __i = lower_bound(__k);
     539             :         if (__i == end() || key_comp()(__k, (*__i).first))
     540             :           __throw_out_of_range(__N("map::at"));
     541             :         return (*__i).second;
     542             :       }
     543             : 
     544             :       const mapped_type&
     545             :       at(const key_type& __k) const
     546             :       {
     547             :         const_iterator __i = lower_bound(__k);
     548             :         if (__i == end() || key_comp()(__k, (*__i).first))
     549             :           __throw_out_of_range(__N("map::at"));
     550             :         return (*__i).second;
     551             :       }
     552             : 
     553             :       // modifiers
     554             : #if __cplusplus >= 201103L
     555             :       /**
     556             :        *  @brief Attempts to build and insert a std::pair into the %map.
     557             :        *
     558             :        *  @param __args  Arguments used to generate a new pair instance (see
     559             :        *                std::piecewise_contruct for passing arguments to each
     560             :        *                part of the pair constructor).
     561             :        *
     562             :        *  @return  A pair, of which the first element is an iterator that points
     563             :        *           to the possibly inserted pair, and the second is a bool that
     564             :        *           is true if the pair was actually inserted.
     565             :        *
     566             :        *  This function attempts to build and insert a (key, value) %pair into
     567             :        *  the %map.
     568             :        *  A %map relies on unique keys and thus a %pair is only inserted if its
     569             :        *  first element (the key) is not already present in the %map.
     570             :        *
     571             :        *  Insertion requires logarithmic time.
     572             :        */
     573             :       template<typename... _Args>
     574             :         std::pair<iterator, bool>
     575             :         emplace(_Args&&... __args)
     576             :         { return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); }
     577             : 
     578             :       /**
     579             :        *  @brief Attempts to build and insert a std::pair into the %map.
     580             :        *
     581             :        *  @param  __pos  An iterator that serves as a hint as to where the pair
     582             :        *                should be inserted.
     583             :        *  @param  __args  Arguments used to generate a new pair instance (see
     584             :        *                 std::piecewise_contruct for passing arguments to each
     585             :        *                 part of the pair constructor).
     586             :        *  @return An iterator that points to the element with key of the
     587             :        *          std::pair built from @a __args (may or may not be that
     588             :        *          std::pair).
     589             :        *
     590             :        *  This function is not concerned about whether the insertion took place,
     591             :        *  and thus does not return a boolean like the single-argument emplace()
     592             :        *  does.
     593             :        *  Note that the first parameter is only a hint and can potentially
     594             :        *  improve the performance of the insertion process. A bad hint would
     595             :        *  cause no gains in efficiency.
     596             :        *
     597             :        *  See
     598             :        *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
     599             :        *  for more on @a hinting.
     600             :        *
     601             :        *  Insertion requires logarithmic time (if the hint is not taken).
     602             :        */
     603             :       template<typename... _Args>
     604             :         iterator
     605             :         emplace_hint(const_iterator __pos, _Args&&... __args)
     606             :         {
     607             :           return _M_t._M_emplace_hint_unique(__pos,
     608             :                                              std::forward<_Args>(__args)...);
     609             :         }
     610             : #endif
     611             : 
     612             :       /**
     613             :        *  @brief Attempts to insert a std::pair into the %map.
     614             : 
     615             :        *  @param __x Pair to be inserted (see std::make_pair for easy
     616             :        *             creation of pairs).
     617             :        *
     618             :        *  @return  A pair, of which the first element is an iterator that 
     619             :        *           points to the possibly inserted pair, and the second is 
     620             :        *           a bool that is true if the pair was actually inserted.
     621             :        *
     622             :        *  This function attempts to insert a (key, value) %pair into the %map.
     623             :        *  A %map relies on unique keys and thus a %pair is only inserted if its
     624             :        *  first element (the key) is not already present in the %map.
     625             :        *
     626             :        *  Insertion requires logarithmic time.
     627             :        */
     628             :       std::pair<iterator, bool>
     629             :       insert(const value_type& __x)
     630             :       { return _M_t._M_insert_unique(__x); }
     631             : 
     632             : #if __cplusplus >= 201103L
     633             :       template<typename _Pair, typename = typename
     634             :                std::enable_if<std::is_constructible<value_type,
     635             :                                                     _Pair&&>::value>::type>
     636             :         std::pair<iterator, bool>
     637             :         insert(_Pair&& __x)
     638             :         { return _M_t._M_insert_unique(std::forward<_Pair>(__x)); }
     639             : #endif
     640             : 
     641             : #if __cplusplus >= 201103L
     642             :       /**
     643             :        *  @brief Attempts to insert a list of std::pairs into the %map.
     644             :        *  @param  __list  A std::initializer_list<value_type> of pairs to be
     645             :        *                  inserted.
     646             :        *
     647             :        *  Complexity similar to that of the range constructor.
     648             :        */
     649             :       void
     650             :       insert(std::initializer_list<value_type> __list)
     651             :       { insert(__list.begin(), __list.end()); }
     652             : #endif
     653             : 
     654             :       /**
     655             :        *  @brief Attempts to insert a std::pair into the %map.
     656             :        *  @param  __position  An iterator that serves as a hint as to where the
     657             :        *                    pair should be inserted.
     658             :        *  @param  __x  Pair to be inserted (see std::make_pair for easy creation
     659             :        *               of pairs).
     660             :        *  @return An iterator that points to the element with key of
     661             :        *           @a __x (may or may not be the %pair passed in).
     662             :        *
     663             : 
     664             :        *  This function is not concerned about whether the insertion
     665             :        *  took place, and thus does not return a boolean like the
     666             :        *  single-argument insert() does.  Note that the first
     667             :        *  parameter is only a hint and can potentially improve the
     668             :        *  performance of the insertion process.  A bad hint would
     669             :        *  cause no gains in efficiency.
     670             :        *
     671             :        *  See
     672             :        *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
     673             :        *  for more on @a hinting.
     674             :        *
     675             :        *  Insertion requires logarithmic time (if the hint is not taken).
     676             :        */
     677             :       iterator
     678             : #if __cplusplus >= 201103L
     679             :       insert(const_iterator __position, const value_type& __x)
     680             : #else
     681             :       insert(iterator __position, const value_type& __x)
     682             : #endif
     683             :       { return _M_t._M_insert_unique_(__position, __x); }
     684             : 
     685             : #if __cplusplus >= 201103L
     686             :       template<typename _Pair, typename = typename
     687             :                std::enable_if<std::is_constructible<value_type,
     688             :                                                     _Pair&&>::value>::type>
     689             :         iterator
     690             :         insert(const_iterator __position, _Pair&& __x)
     691             :         { return _M_t._M_insert_unique_(__position,
     692             :                                         std::forward<_Pair>(__x)); }
     693             : #endif
     694             : 
     695             :       /**
     696             :        *  @brief Template function that attempts to insert a range of elements.
     697             :        *  @param  __first  Iterator pointing to the start of the range to be
     698             :        *                   inserted.
     699             :        *  @param  __last  Iterator pointing to the end of the range.
     700             :        *
     701             :        *  Complexity similar to that of the range constructor.
     702             :        */
     703             :       template<typename _InputIterator>
     704             :         void
     705             :         insert(_InputIterator __first, _InputIterator __last)
     706             :         { _M_t._M_insert_unique(__first, __last); }
     707             : 
     708             : #if __cplusplus >= 201103L
     709             :       // _GLIBCXX_RESOLVE_LIB_DEFECTS
     710             :       // DR 130. Associative erase should return an iterator.
     711             :       /**
     712             :        *  @brief Erases an element from a %map.
     713             :        *  @param  __position  An iterator pointing to the element to be erased.
     714             :        *  @return An iterator pointing to the element immediately following
     715             :        *          @a position prior to the element being erased. If no such 
     716             :        *          element exists, end() is returned.
     717             :        *
     718             :        *  This function erases an element, pointed to by the given
     719             :        *  iterator, from a %map.  Note that this function only erases
     720             :        *  the element, and that if the element is itself a pointer,
     721             :        *  the pointed-to memory is not touched in any way.  Managing
     722             :        *  the pointer is the user's responsibility.
     723             :        */
     724             :       iterator
     725             :       erase(const_iterator __position)
     726             :       { return _M_t.erase(__position); }
     727             : 
     728             :       // LWG 2059
     729             :       _GLIBCXX_ABI_TAG_CXX11
     730             :       iterator
     731             :       erase(iterator __position)
     732             :       { return _M_t.erase(__position); }
     733             : #else
     734             :       /**
     735             :        *  @brief Erases an element from a %map.
     736             :        *  @param  __position  An iterator pointing to the element to be erased.
     737             :        *
     738             :        *  This function erases an element, pointed to by the given
     739             :        *  iterator, from a %map.  Note that this function only erases
     740             :        *  the element, and that if the element is itself a pointer,
     741             :        *  the pointed-to memory is not touched in any way.  Managing
     742             :        *  the pointer is the user's responsibility.
     743             :        */
     744             :       void
     745             :       erase(iterator __position)
     746             :       { _M_t.erase(__position); }
     747             : #endif
     748             : 
     749             :       /**
     750             :        *  @brief Erases elements according to the provided key.
     751             :        *  @param  __x  Key of element to be erased.
     752             :        *  @return  The number of elements erased.
     753             :        *
     754             :        *  This function erases all the elements located by the given key from
     755             :        *  a %map.
     756             :        *  Note that this function only erases the element, and that if
     757             :        *  the element is itself a pointer, the pointed-to memory is not touched
     758             :        *  in any way.  Managing the pointer is the user's responsibility.
     759             :        */
     760             :       size_type
     761             :       erase(const key_type& __x)
     762             :       { return _M_t.erase(__x); }
     763             : 
     764             : #if __cplusplus >= 201103L
     765             :       // _GLIBCXX_RESOLVE_LIB_DEFECTS
     766             :       // DR 130. Associative erase should return an iterator.
     767             :       /**
     768             :        *  @brief Erases a [first,last) range of elements from a %map.
     769             :        *  @param  __first  Iterator pointing to the start of the range to be
     770             :        *                   erased.
     771             :        *  @param __last Iterator pointing to the end of the range to
     772             :        *                be erased.
     773             :        *  @return The iterator @a __last.
     774             :        *
     775             :        *  This function erases a sequence of elements from a %map.
     776             :        *  Note that this function only erases the element, and that if
     777             :        *  the element is itself a pointer, the pointed-to memory is not touched
     778             :        *  in any way.  Managing the pointer is the user's responsibility.
     779             :        */
     780             :       iterator
     781             :       erase(const_iterator __first, const_iterator __last)
     782             :       { return _M_t.erase(__first, __last); }
     783             : #else
     784             :       /**
     785             :        *  @brief Erases a [__first,__last) range of elements from a %map.
     786             :        *  @param  __first  Iterator pointing to the start of the range to be
     787             :        *                   erased.
     788             :        *  @param __last Iterator pointing to the end of the range to
     789             :        *                be erased.
     790             :        *
     791             :        *  This function erases a sequence of elements from a %map.
     792             :        *  Note that this function only erases the element, and that if
     793             :        *  the element is itself a pointer, the pointed-to memory is not touched
     794             :        *  in any way.  Managing the pointer is the user's responsibility.
     795             :        */
     796             :       void
     797             :       erase(iterator __first, iterator __last)
     798             :       { _M_t.erase(__first, __last); }
     799             : #endif
     800             : 
     801             :       /**
     802             :        *  @brief  Swaps data with another %map.
     803             :        *  @param  __x  A %map of the same element and allocator types.
     804             :        *
     805             :        *  This exchanges the elements between two maps in constant
     806             :        *  time.  (It is only swapping a pointer, an integer, and an
     807             :        *  instance of the @c Compare type (which itself is often
     808             :        *  stateless and empty), so it should be quite fast.)  Note
     809             :        *  that the global std::swap() function is specialized such
     810             :        *  that std::swap(m1,m2) will feed to this function.
     811             :        */
     812             :       void
     813             :       swap(map& __x)
     814             : #if __cplusplus >= 201103L
     815             :       noexcept(_Alloc_traits::_S_nothrow_swap())
     816             : #endif
     817             :       { _M_t.swap(__x._M_t); }
     818             : 
     819             :       /**
     820             :        *  Erases all elements in a %map.  Note that this function only
     821             :        *  erases the elements, and that if the elements themselves are
     822             :        *  pointers, the pointed-to memory is not touched in any way.
     823             :        *  Managing the pointer is the user's responsibility.
     824             :        */
     825             :       void
     826             :       clear() _GLIBCXX_NOEXCEPT
     827             :       { _M_t.clear(); }
     828             : 
     829             :       // observers
     830             :       /**
     831             :        *  Returns the key comparison object out of which the %map was
     832             :        *  constructed.
     833             :        */
     834             :       key_compare
     835           0 :       key_comp() const
     836           0 :       { return _M_t.key_comp(); }
     837             : 
     838             :       /**
     839             :        *  Returns a value comparison object, built from the key comparison
     840             :        *  object out of which the %map was constructed.
     841             :        */
     842             :       value_compare
     843             :       value_comp() const
     844             :       { return value_compare(_M_t.key_comp()); }
     845             : 
     846             :       // [23.3.1.3] map operations
     847             :       /**
     848             :        *  @brief Tries to locate an element in a %map.
     849             :        *  @param  __x  Key of (key, value) %pair to be located.
     850             :        *  @return  Iterator pointing to sought-after element, or end() if not
     851             :        *           found.
     852             :        *
     853             :        *  This function takes a key and tries to locate the element with which
     854             :        *  the key matches.  If successful the function returns an iterator
     855             :        *  pointing to the sought after %pair.  If unsuccessful it returns the
     856             :        *  past-the-end ( @c end() ) iterator.
     857             :        */
     858             :       iterator
     859             :       find(const key_type& __x)
     860             :       { return _M_t.find(__x); }
     861             : 
     862             :       /**
     863             :        *  @brief Tries to locate an element in a %map.
     864             :        *  @param  __x  Key of (key, value) %pair to be located.
     865             :        *  @return  Read-only (constant) iterator pointing to sought-after
     866             :        *           element, or end() if not found.
     867             :        *
     868             :        *  This function takes a key and tries to locate the element with which
     869             :        *  the key matches.  If successful the function returns a constant
     870             :        *  iterator pointing to the sought after %pair. If unsuccessful it
     871             :        *  returns the past-the-end ( @c end() ) iterator.
     872             :        */
     873             :       const_iterator
     874           0 :       find(const key_type& __x) const
     875           0 :       { return _M_t.find(__x); }
     876             : 
     877             :       /**
     878             :        *  @brief  Finds the number of elements with given key.
     879             :        *  @param  __x  Key of (key, value) pairs to be located.
     880             :        *  @return  Number of elements with specified key.
     881             :        *
     882             :        *  This function only makes sense for multimaps; for map the result will
     883             :        *  either be 0 (not present) or 1 (present).
     884             :        */
     885             :       size_type
     886             :       count(const key_type& __x) const
     887             :       { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
     888             : 
     889             :       /**
     890             :        *  @brief Finds the beginning of a subsequence matching given key.
     891             :        *  @param  __x  Key of (key, value) pair to be located.
     892             :        *  @return  Iterator pointing to first element equal to or greater
     893             :        *           than key, or end().
     894             :        *
     895             :        *  This function returns the first element of a subsequence of elements
     896             :        *  that matches the given key.  If unsuccessful it returns an iterator
     897             :        *  pointing to the first element that has a greater value than given key
     898             :        *  or end() if no such element exists.
     899             :        */
     900             :       iterator
     901           0 :       lower_bound(const key_type& __x)
     902           0 :       { return _M_t.lower_bound(__x); }
     903             : 
     904             :       /**
     905             :        *  @brief Finds the beginning of a subsequence matching given key.
     906             :        *  @param  __x  Key of (key, value) pair to be located.
     907             :        *  @return  Read-only (constant) iterator pointing to first element
     908             :        *           equal to or greater than key, or end().
     909             :        *
     910             :        *  This function returns the first element of a subsequence of elements
     911             :        *  that matches the given key.  If unsuccessful it returns an iterator
     912             :        *  pointing to the first element that has a greater value than given key
     913             :        *  or end() if no such element exists.
     914             :        */
     915             :       const_iterator
     916             :       lower_bound(const key_type& __x) const
     917             :       { return _M_t.lower_bound(__x); }
     918             : 
     919             :       /**
     920             :        *  @brief Finds the end of a subsequence matching given key.
     921             :        *  @param  __x  Key of (key, value) pair to be located.
     922             :        *  @return Iterator pointing to the first element
     923             :        *          greater than key, or end().
     924             :        */
     925             :       iterator
     926             :       upper_bound(const key_type& __x)
     927             :       { return _M_t.upper_bound(__x); }
     928             : 
     929             :       /**
     930             :        *  @brief Finds the end of a subsequence matching given key.
     931             :        *  @param  __x  Key of (key, value) pair to be located.
     932             :        *  @return  Read-only (constant) iterator pointing to first iterator
     933             :        *           greater than key, or end().
     934             :        */
     935             :       const_iterator
     936             :       upper_bound(const key_type& __x) const
     937             :       { return _M_t.upper_bound(__x); }
     938             : 
     939             :       /**
     940             :        *  @brief Finds a subsequence matching given key.
     941             :        *  @param  __x  Key of (key, value) pairs to be located.
     942             :        *  @return  Pair of iterators that possibly points to the subsequence
     943             :        *           matching given key.
     944             :        *
     945             :        *  This function is equivalent to
     946             :        *  @code
     947             :        *    std::make_pair(c.lower_bound(val),
     948             :        *                   c.upper_bound(val))
     949             :        *  @endcode
     950             :        *  (but is faster than making the calls separately).
     951             :        *
     952             :        *  This function probably only makes sense for multimaps.
     953             :        */
     954             :       std::pair<iterator, iterator>
     955             :       equal_range(const key_type& __x)
     956             :       { return _M_t.equal_range(__x); }
     957             : 
     958             :       /**
     959             :        *  @brief Finds a subsequence matching given key.
     960             :        *  @param  __x  Key of (key, value) pairs to be located.
     961             :        *  @return  Pair of read-only (constant) iterators that possibly points
     962             :        *           to the subsequence matching given key.
     963             :        *
     964             :        *  This function is equivalent to
     965             :        *  @code
     966             :        *    std::make_pair(c.lower_bound(val),
     967             :        *                   c.upper_bound(val))
     968             :        *  @endcode
     969             :        *  (but is faster than making the calls separately).
     970             :        *
     971             :        *  This function probably only makes sense for multimaps.
     972             :        */
     973             :       std::pair<const_iterator, const_iterator>
     974             :       equal_range(const key_type& __x) const
     975             :       { return _M_t.equal_range(__x); }
     976             : 
     977             :       template<typename _K1, typename _T1, typename _C1, typename _A1>
     978             :         friend bool
     979             :         operator==(const map<_K1, _T1, _C1, _A1>&,
     980             :                    const map<_K1, _T1, _C1, _A1>&);
     981             : 
     982             :       template<typename _K1, typename _T1, typename _C1, typename _A1>
     983             :         friend bool
     984             :         operator<(const map<_K1, _T1, _C1, _A1>&,
     985             :                   const map<_K1, _T1, _C1, _A1>&);
     986             :     };
     987             : 
     988             :   /**
     989             :    *  @brief  Map equality comparison.
     990             :    *  @param  __x  A %map.
     991             :    *  @param  __y  A %map of the same type as @a x.
     992             :    *  @return  True iff the size and elements of the maps are equal.
     993             :    *
     994             :    *  This is an equivalence relation.  It is linear in the size of the
     995             :    *  maps.  Maps are considered equivalent if their sizes are equal,
     996             :    *  and if corresponding elements compare equal.
     997             :   */
     998             :   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
     999             :     inline bool
    1000             :     operator==(const map<_Key, _Tp, _Compare, _Alloc>& __x,
    1001             :                const map<_Key, _Tp, _Compare, _Alloc>& __y)
    1002             :     { return __x._M_t == __y._M_t; }
    1003             : 
    1004             :   /**
    1005             :    *  @brief  Map ordering relation.
    1006             :    *  @param  __x  A %map.
    1007             :    *  @param  __y  A %map of the same type as @a x.
    1008             :    *  @return  True iff @a x is lexicographically less than @a y.
    1009             :    *
    1010             :    *  This is a total ordering relation.  It is linear in the size of the
    1011             :    *  maps.  The elements must be comparable with @c <.
    1012             :    *
    1013             :    *  See std::lexicographical_compare() for how the determination is made.
    1014             :   */
    1015             :   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
    1016             :     inline bool
    1017             :     operator<(const map<_Key, _Tp, _Compare, _Alloc>& __x,
    1018             :               const map<_Key, _Tp, _Compare, _Alloc>& __y)
    1019             :     { return __x._M_t < __y._M_t; }
    1020             : 
    1021             :   /// Based on operator==
    1022             :   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
    1023             :     inline bool
    1024             :     operator!=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
    1025             :                const map<_Key, _Tp, _Compare, _Alloc>& __y)
    1026             :     { return !(__x == __y); }
    1027             : 
    1028             :   /// Based on operator<
    1029             :   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
    1030             :     inline bool
    1031             :     operator>(const map<_Key, _Tp, _Compare, _Alloc>& __x,
    1032             :               const map<_Key, _Tp, _Compare, _Alloc>& __y)
    1033             :     { return __y < __x; }
    1034             : 
    1035             :   /// Based on operator<
    1036             :   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
    1037             :     inline bool
    1038             :     operator<=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
    1039             :                const map<_Key, _Tp, _Compare, _Alloc>& __y)
    1040             :     { return !(__y < __x); }
    1041             : 
    1042             :   /// Based on operator<
    1043             :   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
    1044             :     inline bool
    1045             :     operator>=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
    1046             :                const map<_Key, _Tp, _Compare, _Alloc>& __y)
    1047             :     { return !(__x < __y); }
    1048             : 
    1049             :   /// See std::map::swap().
    1050             :   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
    1051             :     inline void
    1052             :     swap(map<_Key, _Tp, _Compare, _Alloc>& __x,
    1053             :          map<_Key, _Tp, _Compare, _Alloc>& __y)
    1054             :     { __x.swap(__y); }
    1055             : 
    1056             : _GLIBCXX_END_NAMESPACE_CONTAINER
    1057             : } // namespace std
    1058             : 
    1059             : #endif /* _STL_MAP_H */

Generated by: LCOV version 1.11