The C and C++ Include Header Files

/usr/include/c++/11/bits/stl_map.h


$ cat -n /usr/include/c++/11/bits/stl_map.h

     1	// Map implementation -*- C++ -*-
     2	
     3	// Copyright (C) 2001-2021 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_VERSION
    69	_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
    70	
    71	  template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
    72	    class multimap;
    73	
    74	  /**
    75	   *  @brief A standard container made up of (key,value) pairs, which can be
    76	   *  retrieved based on a key, in logarithmic time.
    77	   *
    78	   *  @ingroup associative_containers
    79	   *
    80	   *  @tparam _Key  Type of key objects.
    81	   *  @tparam  _Tp  Type of mapped objects.
    82	   *  @tparam _Compare  Comparison function object type, defaults to less<_Key>.
    83	   *  @tparam _Alloc  Allocator type, defaults to
    84	   *                  allocator<pair<const _Key, _Tp>.
    85	   *
    86	   *  Meets the requirements of a <a href="tables.html#65">container</a>, a
    87	   *  <a href="tables.html#66">reversible container</a>, and an
    88	   *  <a href="tables.html#69">associative container</a> (using unique keys).
    89	   *  For a @c map<Key,T> the key_type is Key, the mapped_type is T, and the
    90	   *  value_type is std::pair<const Key,T>.
    91	   *
    92	   *  Maps support bidirectional iterators.
    93	   *
    94	   *  The private tree data is declared exactly the same way for map and
    95	   *  multimap; the distinction is made entirely in how the tree functions are
    96	   *  called (*_unique versus *_equal, same as the standard).
    97	  */
    98	  template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
    99		    typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
   100	    class map
   101	    {
   102	    public:
   103	      typedef _Key					key_type;
   104	      typedef _Tp					mapped_type;
   105	      typedef std::pair<const _Key, _Tp>		value_type;
   106	      typedef _Compare					key_compare;
   107	      typedef _Alloc					allocator_type;
   108	
   109	    private:
   110	#ifdef _GLIBCXX_CONCEPT_CHECKS
   111	      // concept requirements
   112	      typedef typename _Alloc::value_type		_Alloc_value_type;
   113	# if __cplusplus < 201103L
   114	      __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
   115	# endif
   116	      __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
   117					_BinaryFunctionConcept)
   118	      __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept)
   119	#endif
   120	
   121	#if __cplusplus >= 201103L
   122	#if __cplusplus > 201703L || defined __STRICT_ANSI__
   123	      static_assert(is_same<typename _Alloc::value_type, value_type>::value,
   124		  "std::map must have the same value_type as its allocator");
   125	#endif
   126	#endif
   127	
   128	    public:
   129	      class value_compare
   130	      : public std::binary_function<value_type, value_type, bool>
   131	      {
   132		friend class map<_Key, _Tp, _Compare, _Alloc>;
   133	      protected:
   134		_Compare comp;
   135	
   136		value_compare(_Compare __c)
   137		: comp(__c) { }
   138	
   139	      public:
   140		bool operator()(const value_type& __x, const value_type& __y) const
   141		{ return comp(__x.first, __y.first); }
   142	      };
   143	
   144	    private:
   145	      /// This turns a red-black tree into a [multi]map.
   146	      typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
   147		rebind<value_type>::other _Pair_alloc_type;
   148	
   149	      typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
   150			       key_compare, _Pair_alloc_type> _Rep_type;
   151	
   152	      /// The actual tree structure.
   153	      _Rep_type _M_t;
   154	
   155	      typedef __gnu_cxx::__alloc_traits<_Pair_alloc_type> _Alloc_traits;
   156	
   157	    public:
   158	      // many of these are specified differently in ISO, but the following are
   159	      // "functionally equivalent"
   160	      typedef typename _Alloc_traits::pointer		 pointer;
   161	      typedef typename _Alloc_traits::const_pointer	 const_pointer;
   162	      typedef typename _Alloc_traits::reference		 reference;
   163	      typedef typename _Alloc_traits::const_reference	 const_reference;
   164	      typedef typename _Rep_type::iterator		 iterator;
   165	      typedef typename _Rep_type::const_iterator	 const_iterator;
   166	      typedef typename _Rep_type::size_type		 size_type;
   167	      typedef typename _Rep_type::difference_type	 difference_type;
   168	      typedef typename _Rep_type::reverse_iterator	 reverse_iterator;
   169	      typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
   170	
   171	#if __cplusplus > 201402L
   172	      using node_type = typename _Rep_type::node_type;
   173	      using insert_return_type = typename _Rep_type::insert_return_type;
   174	#endif
   175	
   176	      // [23.3.1.1] construct/copy/destroy
   177	      // (get_allocator() is also listed in this section)
   178	
   179	      /**
   180	       *  @brief  Default constructor creates no elements.
   181	       */
   182	#if __cplusplus < 201103L
   183	      map() : _M_t() { }
   184	#else
   185	      map() = default;
   186	#endif
   187	
   188	      /**
   189	       *  @brief  Creates a %map with no elements.
   190	       *  @param  __comp  A comparison object.
   191	       *  @param  __a  An allocator object.
   192	       */
   193	      explicit
   194	      map(const _Compare& __comp,
   195		  const allocator_type& __a = allocator_type())
   196	      : _M_t(__comp, _Pair_alloc_type(__a)) { }
   197	
   198	      /**
   199	       *  @brief  %Map copy constructor.
   200	       *
   201	       *  Whether the allocator is copied depends on the allocator traits.
   202	       */
   203	#if __cplusplus < 201103L
   204	      map(const map& __x)
   205	      : _M_t(__x._M_t) { }
   206	#else
   207	      map(const map&) = default;
   208	
   209	      /**
   210	       *  @brief  %Map move constructor.
   211	       *
   212	       *  The newly-created %map contains the exact contents of the moved
   213	       *  instance. The moved instance is a valid, but unspecified, %map.
   214	       */
   215	      map(map&&) = default;
   216	
   217	      /**
   218	       *  @brief  Builds a %map from an initializer_list.
   219	       *  @param  __l  An initializer_list.
   220	       *  @param  __comp  A comparison object.
   221	       *  @param  __a  An allocator object.
   222	       *
   223	       *  Create a %map consisting of copies of the elements in the
   224	       *  initializer_list @a __l.
   225	       *  This is linear in N if the range is already sorted, and NlogN
   226	       *  otherwise (where N is @a __l.size()).
   227	       */
   228	      map(initializer_list<value_type> __l,
   229		  const _Compare& __comp = _Compare(),
   230		  const allocator_type& __a = allocator_type())
   231	      : _M_t(__comp, _Pair_alloc_type(__a))
   232	      { _M_t._M_insert_range_unique(__l.begin(), __l.end()); }
   233	
   234	      /// Allocator-extended default constructor.
   235	      explicit
   236	      map(const allocator_type& __a)
   237	      : _M_t(_Pair_alloc_type(__a)) { }
   238	
   239	      /// Allocator-extended copy constructor.
   240	      map(const map& __m, const allocator_type& __a)
   241	      : _M_t(__m._M_t, _Pair_alloc_type(__a)) { }
   242	
   243	      /// Allocator-extended move constructor.
   244	      map(map&& __m, const allocator_type& __a)
   245	      noexcept(is_nothrow_copy_constructible<_Compare>::value
   246		       && _Alloc_traits::_S_always_equal())
   247	      : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { }
   248	
   249	      /// Allocator-extended initialier-list constructor.
   250	      map(initializer_list<value_type> __l, const allocator_type& __a)
   251	      : _M_t(_Pair_alloc_type(__a))
   252	      { _M_t._M_insert_range_unique(__l.begin(), __l.end()); }
   253	
   254	      /// Allocator-extended range constructor.
   255	      template<typename _InputIterator>
   256		map(_InputIterator __first, _InputIterator __last,
   257		    const allocator_type& __a)
   258		: _M_t(_Pair_alloc_type(__a))
   259		{ _M_t._M_insert_range_unique(__first, __last); }
   260	#endif
   261	
   262	      /**
   263	       *  @brief  Builds a %map from a range.
   264	       *  @param  __first  An input iterator.
   265	       *  @param  __last  An input iterator.
   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		: _M_t()
   275		{ _M_t._M_insert_range_unique(__first, __last); }
   276	
   277	      /**
   278	       *  @brief  Builds a %map from a range.
   279	       *  @param  __first  An input iterator.
   280	       *  @param  __last  An input iterator.
   281	       *  @param  __comp  A comparison functor.
   282	       *  @param  __a  An allocator object.
   283	       *
   284	       *  Create a %map consisting of copies of the elements from
   285	       *  [__first,__last).  This is linear in N if the range is
   286	       *  already sorted, and NlogN otherwise (where N is
   287	       *  distance(__first,__last)).
   288	       */
   289	      template<typename _InputIterator>
   290		map(_InputIterator __first, _InputIterator __last,
   291		    const _Compare& __comp,
   292		    const allocator_type& __a = allocator_type())
   293		: _M_t(__comp, _Pair_alloc_type(__a))
   294		{ _M_t._M_insert_range_unique(__first, __last); }
   295	
   296	#if __cplusplus >= 201103L
   297	      /**
   298	       *  The dtor only erases the elements, and note that if the elements
   299	       *  themselves are pointers, the pointed-to memory is not touched in any
   300	       *  way.  Managing the pointer is the user's responsibility.
   301	       */
   302	      ~map() = default;
   303	#endif
   304	
   305	      /**
   306	       *  @brief  %Map assignment operator.
   307	       *
   308	       *  Whether the allocator is copied depends on the allocator traits.
   309	       */
   310	#if __cplusplus < 201103L
   311	      map&
   312	      operator=(const map& __x)
   313	      {
   314		_M_t = __x._M_t;
   315		return *this;
   316	      }
   317	#else
   318	      map&
   319	      operator=(const map&) = default;
   320	
   321	      /// Move assignment operator.
   322	      map&
   323	      operator=(map&&) = default;
   324	
   325	      /**
   326	       *  @brief  %Map list assignment operator.
   327	       *  @param  __l  An initializer_list.
   328	       *
   329	       *  This function fills a %map with copies of the elements in the
   330	       *  initializer list @a __l.
   331	       *
   332	       *  Note that the assignment completely changes the %map and
   333	       *  that the resulting %map's size is the same as the number
   334	       *  of elements assigned.
   335	       */
   336	      map&
   337	      operator=(initializer_list<value_type> __l)
   338	      {
   339		_M_t._M_assign_unique(__l.begin(), __l.end());
   340		return *this;
   341	      }
   342	#endif
   343	
   344	      /// Get a copy of the memory allocation object.
   345	      allocator_type
   346	      get_allocator() const _GLIBCXX_NOEXCEPT
   347	      { return allocator_type(_M_t.get_allocator()); }
   348	
   349	      // iterators
   350	      /**
   351	       *  Returns a read/write iterator that points to the first pair in the
   352	       *  %map.
   353	       *  Iteration is done in ascending order according to the keys.
   354	       */
   355	      iterator
   356	      begin() _GLIBCXX_NOEXCEPT
   357	      { return _M_t.begin(); }
   358	
   359	      /**
   360	       *  Returns a read-only (constant) iterator that points to the first pair
   361	       *  in the %map.  Iteration is done in ascending order according to the
   362	       *  keys.
   363	       */
   364	      const_iterator
   365	      begin() const _GLIBCXX_NOEXCEPT
   366	      { return _M_t.begin(); }
   367	
   368	      /**
   369	       *  Returns a read/write iterator that points one past the last
   370	       *  pair in the %map.  Iteration is done in ascending order
   371	       *  according to the keys.
   372	       */
   373	      iterator
   374	      end() _GLIBCXX_NOEXCEPT
   375	      { return _M_t.end(); }
   376	
   377	      /**
   378	       *  Returns a read-only (constant) iterator that points one past the last
   379	       *  pair in the %map.  Iteration is done in ascending order according to
   380	       *  the keys.
   381	       */
   382	      const_iterator
   383	      end() const _GLIBCXX_NOEXCEPT
   384	      { return _M_t.end(); }
   385	
   386	      /**
   387	       *  Returns a read/write reverse iterator that points to the last pair in
   388	       *  the %map.  Iteration is done in descending order according to the
   389	       *  keys.
   390	       */
   391	      reverse_iterator
   392	      rbegin() _GLIBCXX_NOEXCEPT
   393	      { return _M_t.rbegin(); }
   394	
   395	      /**
   396	       *  Returns a read-only (constant) reverse iterator that points to the
   397	       *  last pair in the %map.  Iteration is done in descending order
   398	       *  according to the keys.
   399	       */
   400	      const_reverse_iterator
   401	      rbegin() const _GLIBCXX_NOEXCEPT
   402	      { return _M_t.rbegin(); }
   403	
   404	      /**
   405	       *  Returns a read/write reverse iterator that points to one before the
   406	       *  first pair in the %map.  Iteration is done in descending order
   407	       *  according to the keys.
   408	       */
   409	      reverse_iterator
   410	      rend() _GLIBCXX_NOEXCEPT
   411	      { return _M_t.rend(); }
   412	
   413	      /**
   414	       *  Returns a read-only (constant) reverse iterator that points to one
   415	       *  before the first pair in the %map.  Iteration is done in descending
   416	       *  order according to the keys.
   417	       */
   418	      const_reverse_iterator
   419	      rend() const _GLIBCXX_NOEXCEPT
   420	      { return _M_t.rend(); }
   421	
   422	#if __cplusplus >= 201103L
   423	      /**
   424	       *  Returns a read-only (constant) iterator that points to the first pair
   425	       *  in the %map.  Iteration is done in ascending order according to the
   426	       *  keys.
   427	       */
   428	      const_iterator
   429	      cbegin() const noexcept
   430	      { return _M_t.begin(); }
   431	
   432	      /**
   433	       *  Returns a read-only (constant) iterator that points one past the last
   434	       *  pair in the %map.  Iteration is done in ascending order according to
   435	       *  the keys.
   436	       */
   437	      const_iterator
   438	      cend() const noexcept
   439	      { return _M_t.end(); }
   440	
   441	      /**
   442	       *  Returns a read-only (constant) reverse iterator that points to the
   443	       *  last pair in the %map.  Iteration is done in descending order
   444	       *  according to the keys.
   445	       */
   446	      const_reverse_iterator
   447	      crbegin() const noexcept
   448	      { return _M_t.rbegin(); }
   449	
   450	      /**
   451	       *  Returns a read-only (constant) reverse iterator that points to one
   452	       *  before the first pair in the %map.  Iteration is done in descending
   453	       *  order according to the keys.
   454	       */
   455	      const_reverse_iterator
   456	      crend() const noexcept
   457	      { return _M_t.rend(); }
   458	#endif
   459	
   460	      // capacity
   461	      /** Returns true if the %map is empty.  (Thus begin() would equal
   462	       *  end().)
   463	      */
   464	      _GLIBCXX_NODISCARD bool
   465	      empty() const _GLIBCXX_NOEXCEPT
   466	      { return _M_t.empty(); }
   467	
   468	      /** Returns the size of the %map.  */
   469	      size_type
   470	      size() const _GLIBCXX_NOEXCEPT
   471	      { return _M_t.size(); }
   472	
   473	      /** Returns the maximum size of the %map.  */
   474	      size_type
   475	      max_size() const _GLIBCXX_NOEXCEPT
   476	      { return _M_t.max_size(); }
   477	
   478	      // [23.3.1.2] element access
   479	      /**
   480	       *  @brief  Subscript ( @c [] ) access to %map data.
   481	       *  @param  __k  The key for which data should be retrieved.
   482	       *  @return  A reference to the data of the (key,data) %pair.
   483	       *
   484	       *  Allows for easy lookup with the subscript ( @c [] )
   485	       *  operator.  Returns data associated with the key specified in
   486	       *  subscript.  If the key does not exist, a pair with that key
   487	       *  is created using default values, which is then returned.
   488	       *
   489	       *  Lookup requires logarithmic time.
   490	       */
   491	      mapped_type&
   492	      operator[](const key_type& __k)
   493	      {
   494		// concept requirements
   495		__glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)
   496	
   497		iterator __i = lower_bound(__k);
   498		// __i->first is greater than or equivalent to __k.
   499		if (__i == end() || key_comp()(__k, (*__i).first))
   500	#if __cplusplus >= 201103L
   501		  __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct,
   502						    std::tuple<const key_type&>(__k),
   503						    std::tuple<>());
   504	#else
   505		  __i = insert(__i, value_type(__k, mapped_type()));
   506	#endif
   507		return (*__i).second;
   508	      }
   509	
   510	#if __cplusplus >= 201103L
   511	      mapped_type&
   512	      operator[](key_type&& __k)
   513	      {
   514		// concept requirements
   515		__glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)
   516	
   517		iterator __i = lower_bound(__k);
   518		// __i->first is greater than or equivalent to __k.
   519		if (__i == end() || key_comp()(__k, (*__i).first))
   520		  __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct,
   521						std::forward_as_tuple(std::move(__k)),
   522						std::tuple<>());
   523		return (*__i).second;
   524	      }
   525	#endif
   526	
   527	      // _GLIBCXX_RESOLVE_LIB_DEFECTS
   528	      // DR 464. Suggestion for new member functions in standard containers.
   529	      /**
   530	       *  @brief  Access to %map data.
   531	       *  @param  __k  The key for which data should be retrieved.
   532	       *  @return  A reference to the data whose key is equivalent to @a __k, if
   533	       *           such a data is present in the %map.
   534	       *  @throw  std::out_of_range  If no such data is present.
   535	       */
   536	      mapped_type&
   537	      at(const key_type& __k)
   538	      {
   539		iterator __i = lower_bound(__k);
   540		if (__i == end() || key_comp()(__k, (*__i).first))
   541		  __throw_out_of_range(__N("map::at"));
   542		return (*__i).second;
   543	      }
   544	
   545	      const mapped_type&
   546	      at(const key_type& __k) const
   547	      {
   548		const_iterator __i = lower_bound(__k);
   549		if (__i == end() || key_comp()(__k, (*__i).first))
   550		  __throw_out_of_range(__N("map::at"));
   551		return (*__i).second;
   552	      }
   553	
   554	      // modifiers
   555	#if __cplusplus >= 201103L
   556	      /**
   557	       *  @brief Attempts to build and insert a std::pair into the %map.
   558	       *
   559	       *  @param __args  Arguments used to generate a new pair instance (see
   560	       *	        std::piecewise_contruct for passing arguments to each
   561	       *	        part of the pair constructor).
   562	       *
   563	       *  @return  A pair, of which the first element is an iterator that points
   564	       *           to the possibly inserted pair, and the second is a bool that
   565	       *           is true if the pair was actually inserted.
   566	       *
   567	       *  This function attempts to build and insert a (key, value) %pair into
   568	       *  the %map.
   569	       *  A %map relies on unique keys and thus a %pair is only inserted if its
   570	       *  first element (the key) is not already present in the %map.
   571	       *
   572	       *  Insertion requires logarithmic time.
   573	       */
   574	      template<typename... _Args>
   575		std::pair<iterator, bool>
   576		emplace(_Args&&... __args)
   577		{ return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); }
   578	
   579	      /**
   580	       *  @brief Attempts to build and insert a std::pair into the %map.
   581	       *
   582	       *  @param  __pos  An iterator that serves as a hint as to where the pair
   583	       *                should be inserted.
   584	       *  @param  __args  Arguments used to generate a new pair instance (see
   585	       *	         std::piecewise_contruct for passing arguments to each
   586	       *	         part of the pair constructor).
   587	       *  @return An iterator that points to the element with key of the
   588	       *          std::pair built from @a __args (may or may not be that
   589	       *          std::pair).
   590	       *
   591	       *  This function is not concerned about whether the insertion took place,
   592	       *  and thus does not return a boolean like the single-argument emplace()
   593	       *  does.
   594	       *  Note that the first parameter is only a hint and can potentially
   595	       *  improve the performance of the insertion process. A bad hint would
   596	       *  cause no gains in efficiency.
   597	       *
   598	       *  See
   599	       *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
   600	       *  for more on @a hinting.
   601	       *
   602	       *  Insertion requires logarithmic time (if the hint is not taken).
   603	       */
   604	      template<typename... _Args>
   605		iterator
   606		emplace_hint(const_iterator __pos, _Args&&... __args)
   607		{
   608		  return _M_t._M_emplace_hint_unique(__pos,
   609						     std::forward<_Args>(__args)...);
   610		}
   611	#endif
   612	
   613	#if __cplusplus > 201402L
   614	      /// Extract a node.
   615	      node_type
   616	      extract(const_iterator __pos)
   617	      {
   618		__glibcxx_assert(__pos != end());
   619		return _M_t.extract(__pos);
   620	      }
   621	
   622	      /// Extract a node.
   623	      node_type
   624	      extract(const key_type& __x)
   625	      { return _M_t.extract(__x); }
   626	
   627	      /// Re-insert an extracted node.
   628	      insert_return_type
   629	      insert(node_type&& __nh)
   630	      { return _M_t._M_reinsert_node_unique(std::move(__nh)); }
   631	
   632	      /// Re-insert an extracted node.
   633	      iterator
   634	      insert(const_iterator __hint, node_type&& __nh)
   635	      { return _M_t._M_reinsert_node_hint_unique(__hint, std::move(__nh)); }
   636	
   637	      template<typename, typename>
   638		friend struct std::_Rb_tree_merge_helper;
   639	
   640	      template<typename _Cmp2>
   641		void
   642		merge(map<_Key, _Tp, _Cmp2, _Alloc>& __source)
   643		{
   644		  using _Merge_helper = _Rb_tree_merge_helper<map, _Cmp2>;
   645		  _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source));
   646		}
   647	
   648	      template<typename _Cmp2>
   649		void
   650		merge(map<_Key, _Tp, _Cmp2, _Alloc>&& __source)
   651		{ merge(__source); }
   652	
   653	      template<typename _Cmp2>
   654		void
   655		merge(multimap<_Key, _Tp, _Cmp2, _Alloc>& __source)
   656		{
   657		  using _Merge_helper = _Rb_tree_merge_helper<map, _Cmp2>;
   658		  _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source));
   659		}
   660	
   661	      template<typename _Cmp2>
   662		void
   663		merge(multimap<_Key, _Tp, _Cmp2, _Alloc>&& __source)
   664		{ merge(__source); }
   665	#endif // C++17
   666	
   667	#if __cplusplus > 201402L
   668	#define __cpp_lib_map_try_emplace 201411
   669	      /**
   670	       *  @brief Attempts to build and insert a std::pair into the %map.
   671	       *
   672	       *  @param __k    Key to use for finding a possibly existing pair in
   673	       *                the map.
   674	       *  @param __args  Arguments used to generate the .second for a new pair
   675	       *                instance.
   676	       *
   677	       *  @return  A pair, of which the first element is an iterator that points
   678	       *           to the possibly inserted pair, and the second is a bool that
   679	       *           is true if the pair was actually inserted.
   680	       *
   681	       *  This function attempts to build and insert a (key, value) %pair into
   682	       *  the %map.
   683	       *  A %map relies on unique keys and thus a %pair is only inserted if its
   684	       *  first element (the key) is not already present in the %map.
   685	       *  If a %pair is not inserted, this function has no effect.
   686	       *
   687	       *  Insertion requires logarithmic time.
   688	       */
   689	      template <typename... _Args>
   690		pair<iterator, bool>
   691		try_emplace(const key_type& __k, _Args&&... __args)
   692		{
   693		  iterator __i = lower_bound(__k);
   694		  if (__i == end() || key_comp()(__k, (*__i).first))
   695		    {
   696		      __i = emplace_hint(__i, std::piecewise_construct,
   697					 std::forward_as_tuple(__k),
   698					 std::forward_as_tuple(
   699					   std::forward<_Args>(__args)...));
   700		      return {__i, true};
   701		    }
   702		  return {__i, false};
   703		}
   704	
   705	      // move-capable overload
   706	      template <typename... _Args>
   707		pair<iterator, bool>
   708		try_emplace(key_type&& __k, _Args&&... __args)
   709		{
   710		  iterator __i = lower_bound(__k);
   711		  if (__i == end() || key_comp()(__k, (*__i).first))
   712		    {
   713		      __i = emplace_hint(__i, std::piecewise_construct,
   714					 std::forward_as_tuple(std::move(__k)),
   715					 std::forward_as_tuple(
   716					   std::forward<_Args>(__args)...));
   717		      return {__i, true};
   718		    }
   719		  return {__i, false};
   720		}
   721	
   722	      /**
   723	       *  @brief Attempts to build and insert a std::pair into the %map.
   724	       *
   725	       *  @param  __hint  An iterator that serves as a hint as to where the
   726	       *                  pair should be inserted.
   727	       *  @param __k    Key to use for finding a possibly existing pair in
   728	       *                the map.
   729	       *  @param __args  Arguments used to generate the .second for a new pair
   730	       *                instance.
   731	       *  @return An iterator that points to the element with key of the
   732	       *          std::pair built from @a __args (may or may not be that
   733	       *          std::pair).
   734	       *
   735	       *  This function is not concerned about whether the insertion took place,
   736	       *  and thus does not return a boolean like the single-argument
   737	       *  try_emplace() does. However, if insertion did not take place,
   738	       *  this function has no effect.
   739	       *  Note that the first parameter is only a hint and can potentially
   740	       *  improve the performance of the insertion process. A bad hint would
   741	       *  cause no gains in efficiency.
   742	       *
   743	       *  See
   744	       *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
   745	       *  for more on @a hinting.
   746	       *
   747	       *  Insertion requires logarithmic time (if the hint is not taken).
   748	       */
   749	      template <typename... _Args>
   750		iterator
   751		try_emplace(const_iterator __hint, const key_type& __k,
   752			    _Args&&... __args)
   753		{
   754		  iterator __i;
   755		  auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);
   756		  if (__true_hint.second)
   757		    __i = emplace_hint(iterator(__true_hint.second),
   758				       std::piecewise_construct,
   759				       std::forward_as_tuple(__k),
   760				       std::forward_as_tuple(
   761					 std::forward<_Args>(__args)...));
   762		  else
   763		    __i = iterator(__true_hint.first);
   764		  return __i;
   765		}
   766	
   767	      // move-capable overload
   768	      template <typename... _Args>
   769		iterator
   770		try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
   771		{
   772		  iterator __i;
   773		  auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);
   774		  if (__true_hint.second)
   775		    __i = emplace_hint(iterator(__true_hint.second),
   776				       std::piecewise_construct,
   777				       std::forward_as_tuple(std::move(__k)),
   778				       std::forward_as_tuple(
   779					 std::forward<_Args>(__args)...));
   780		  else
   781		    __i = iterator(__true_hint.first);
   782		  return __i;
   783		}
   784	#endif
   785	
   786	      /**
   787	       *  @brief Attempts to insert a std::pair into the %map.
   788	       *  @param __x Pair to be inserted (see std::make_pair for easy
   789	       *	     creation of pairs).
   790	       *
   791	       *  @return  A pair, of which the first element is an iterator that
   792	       *           points to the possibly inserted pair, and the second is
   793	       *           a bool that is true if the pair was actually inserted.
   794	       *
   795	       *  This function attempts to insert a (key, value) %pair into the %map.
   796	       *  A %map relies on unique keys and thus a %pair is only inserted if its
   797	       *  first element (the key) is not already present in the %map.
   798	       *
   799	       *  Insertion requires logarithmic time.
   800	       *  @{
   801	       */
   802	      std::pair<iterator, bool>
   803	      insert(const value_type& __x)
   804	      { return _M_t._M_insert_unique(__x); }
   805	
   806	#if __cplusplus >= 201103L
   807	      // _GLIBCXX_RESOLVE_LIB_DEFECTS
   808	      // 2354. Unnecessary copying when inserting into maps with braced-init
   809	      std::pair<iterator, bool>
   810	      insert(value_type&& __x)
   811	      { return _M_t._M_insert_unique(std::move(__x)); }
   812	
   813	      template<typename _Pair>
   814		__enable_if_t<is_constructible<value_type, _Pair>::value,
   815			      pair<iterator, bool>>
   816		insert(_Pair&& __x)
   817		{ return _M_t._M_emplace_unique(std::forward<_Pair>(__x)); }
   818	#endif
   819	      /// @}
   820	
   821	#if __cplusplus >= 201103L
   822	      /**
   823	       *  @brief Attempts to insert a list of std::pairs into the %map.
   824	       *  @param  __list  A std::initializer_list<value_type> of pairs to be
   825	       *                  inserted.
   826	       *
   827	       *  Complexity similar to that of the range constructor.
   828	       */
   829	      void
   830	      insert(std::initializer_list<value_type> __list)
   831	      { insert(__list.begin(), __list.end()); }
   832	#endif
   833	
   834	      /**
   835	       *  @brief Attempts to insert a std::pair into the %map.
   836	       *  @param  __position  An iterator that serves as a hint as to where the
   837	       *                    pair should be inserted.
   838	       *  @param  __x  Pair to be inserted (see std::make_pair for easy creation
   839	       *               of pairs).
   840	       *  @return An iterator that points to the element with key of
   841	       *           @a __x (may or may not be the %pair passed in).
   842	       *
   843	
   844	       *  This function is not concerned about whether the insertion
   845	       *  took place, and thus does not return a boolean like the
   846	       *  single-argument insert() does.  Note that the first
   847	       *  parameter is only a hint and can potentially improve the
   848	       *  performance of the insertion process.  A bad hint would
   849	       *  cause no gains in efficiency.
   850	       *
   851	       *  See
   852	       *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
   853	       *  for more on @a hinting.
   854	       *
   855	       *  Insertion requires logarithmic time (if the hint is not taken).
   856	       *  @{
   857	       */
   858	      iterator
   859	#if __cplusplus >= 201103L
   860	      insert(const_iterator __position, const value_type& __x)
   861	#else
   862	      insert(iterator __position, const value_type& __x)
   863	#endif
   864	      { return _M_t._M_insert_unique_(__position, __x); }
   865	
   866	#if __cplusplus >= 201103L
   867	      // _GLIBCXX_RESOLVE_LIB_DEFECTS
   868	      // 2354. Unnecessary copying when inserting into maps with braced-init
   869	      iterator
   870	      insert(const_iterator __position, value_type&& __x)
   871	      { return _M_t._M_insert_unique_(__position, std::move(__x)); }
   872	
   873	      template<typename _Pair>
   874		__enable_if_t<is_constructible<value_type, _Pair>::value, iterator>
   875		insert(const_iterator __position, _Pair&& __x)
   876		{
   877		  return _M_t._M_emplace_hint_unique(__position,
   878						     std::forward<_Pair>(__x));
   879		}
   880	#endif
   881	      /// @}
   882	
   883	      /**
   884	       *  @brief Template function that attempts to insert a range of elements.
   885	       *  @param  __first  Iterator pointing to the start of the range to be
   886	       *                   inserted.
   887	       *  @param  __last  Iterator pointing to the end of the range.
   888	       *
   889	       *  Complexity similar to that of the range constructor.
   890	       */
   891	      template<typename _InputIterator>
   892		void
   893		insert(_InputIterator __first, _InputIterator __last)
   894		{ _M_t._M_insert_range_unique(__first, __last); }
   895	
   896	#if __cplusplus > 201402L
   897	      /**
   898	       *  @brief Attempts to insert or assign a std::pair into the %map.
   899	       *  @param __k    Key to use for finding a possibly existing pair in
   900	       *                the map.
   901	       *  @param __obj  Argument used to generate the .second for a pair
   902	       *                instance.
   903	       *
   904	       *  @return  A pair, of which the first element is an iterator that
   905	       *           points to the possibly inserted pair, and the second is
   906	       *           a bool that is true if the pair was actually inserted.
   907	       *
   908	       *  This function attempts to insert a (key, value) %pair into the %map.
   909	       *  A %map relies on unique keys and thus a %pair is only inserted if its
   910	       *  first element (the key) is not already present in the %map.
   911	       *  If the %pair was already in the %map, the .second of the %pair
   912	       *  is assigned from __obj.
   913	       *
   914	       *  Insertion requires logarithmic time.
   915	       */
   916	      template <typename _Obj>
   917		pair<iterator, bool>
   918		insert_or_assign(const key_type& __k, _Obj&& __obj)
   919		{
   920		  iterator __i = lower_bound(__k);
   921		  if (__i == end() || key_comp()(__k, (*__i).first))
   922		    {
   923		      __i = emplace_hint(__i, std::piecewise_construct,
   924					 std::forward_as_tuple(__k),
   925					 std::forward_as_tuple(
   926					   std::forward<_Obj>(__obj)));
   927		      return {__i, true};
   928		    }
   929		  (*__i).second = std::forward<_Obj>(__obj);
   930		  return {__i, false};
   931		}
   932	
   933	      // move-capable overload
   934	      template <typename _Obj>
   935		pair<iterator, bool>
   936		insert_or_assign(key_type&& __k, _Obj&& __obj)
   937		{
   938		  iterator __i = lower_bound(__k);
   939		  if (__i == end() || key_comp()(__k, (*__i).first))
   940		    {
   941		      __i = emplace_hint(__i, std::piecewise_construct,
   942					 std::forward_as_tuple(std::move(__k)),
   943					 std::forward_as_tuple(
   944					   std::forward<_Obj>(__obj)));
   945		      return {__i, true};
   946		    }
   947		  (*__i).second = std::forward<_Obj>(__obj);
   948		  return {__i, false};
   949		}
   950	
   951	      /**
   952	       *  @brief Attempts to insert or assign a std::pair into the %map.
   953	       *  @param  __hint  An iterator that serves as a hint as to where the
   954	       *                  pair should be inserted.
   955	       *  @param __k    Key to use for finding a possibly existing pair in
   956	       *                the map.
   957	       *  @param __obj  Argument used to generate the .second for a pair
   958	       *                instance.
   959	       *
   960	       *  @return An iterator that points to the element with key of
   961	       *           @a __x (may or may not be the %pair passed in).
   962	       *
   963	       *  This function attempts to insert a (key, value) %pair into the %map.
   964	       *  A %map relies on unique keys and thus a %pair is only inserted if its
   965	       *  first element (the key) is not already present in the %map.
   966	       *  If the %pair was already in the %map, the .second of the %pair
   967	       *  is assigned from __obj.
   968	       *
   969	       *  Insertion requires logarithmic time.
   970	       */
   971	      template <typename _Obj>
   972		iterator
   973		insert_or_assign(const_iterator __hint,
   974				 const key_type& __k, _Obj&& __obj)
   975		{
   976		  iterator __i;
   977		  auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);
   978		  if (__true_hint.second)
   979		    {
   980		      return emplace_hint(iterator(__true_hint.second),
   981					  std::piecewise_construct,
   982					  std::forward_as_tuple(__k),
   983					  std::forward_as_tuple(
   984					    std::forward<_Obj>(__obj)));
   985		    }
   986		  __i = iterator(__true_hint.first);
   987		  (*__i).second = std::forward<_Obj>(__obj);
   988		  return __i;
   989		}
   990	
   991	      // move-capable overload
   992	      template <typename _Obj>
   993		iterator
   994		insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
   995		{
   996		  iterator __i;
   997		  auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);
   998		  if (__true_hint.second)
   999		    {
  1000		      return emplace_hint(iterator(__true_hint.second),
  1001					  std::piecewise_construct,
  1002					  std::forward_as_tuple(std::move(__k)),
  1003					  std::forward_as_tuple(
  1004					    std::forward<_Obj>(__obj)));
  1005		    }
  1006		  __i = iterator(__true_hint.first);
  1007		  (*__i).second = std::forward<_Obj>(__obj);
  1008		  return __i;
  1009		}
  1010	#endif
  1011	
  1012	#if __cplusplus >= 201103L
  1013	      // _GLIBCXX_RESOLVE_LIB_DEFECTS
  1014	      // DR 130. Associative erase should return an iterator.
  1015	      /**
  1016	       *  @brief Erases an element from a %map.
  1017	       *  @param  __position  An iterator pointing to the element to be erased.
  1018	       *  @return An iterator pointing to the element immediately following
  1019	       *          @a position prior to the element being erased. If no such
  1020	       *          element exists, end() is returned.
  1021	       *
  1022	       *  This function erases an element, pointed to by the given
  1023	       *  iterator, from a %map.  Note that this function only erases
  1024	       *  the element, and that if the element is itself a pointer,
  1025	       *  the pointed-to memory is not touched in any way.  Managing
  1026	       *  the pointer is the user's responsibility.
  1027	       *
  1028	       *  @{
  1029	       */
  1030	      iterator
  1031	      erase(const_iterator __position)
  1032	      { return _M_t.erase(__position); }
  1033	
  1034	      // LWG 2059
  1035	      _GLIBCXX_ABI_TAG_CXX11
  1036	      iterator
  1037	      erase(iterator __position)
  1038	      { return _M_t.erase(__position); }
  1039	      /// @}
  1040	#else
  1041	      /**
  1042	       *  @brief Erases an element from a %map.
  1043	       *  @param  __position  An iterator pointing to the element to be erased.
  1044	       *
  1045	       *  This function erases an element, pointed to by the given
  1046	       *  iterator, from a %map.  Note that this function only erases
  1047	       *  the element, and that if the element is itself a pointer,
  1048	       *  the pointed-to memory is not touched in any way.  Managing
  1049	       *  the pointer is the user's responsibility.
  1050	       */
  1051	      void
  1052	      erase(iterator __position)
  1053	      { _M_t.erase(__position); }
  1054	#endif
  1055	
  1056	      /**
  1057	       *  @brief Erases elements according to the provided key.
  1058	       *  @param  __x  Key of element to be erased.
  1059	       *  @return  The number of elements erased.
  1060	       *
  1061	       *  This function erases all the elements located by the given key from
  1062	       *  a %map.
  1063	       *  Note that this function only erases the element, and that if
  1064	       *  the element is itself a pointer, the pointed-to memory is not touched
  1065	       *  in any way.  Managing the pointer is the user's responsibility.
  1066	       */
  1067	      size_type
  1068	      erase(const key_type& __x)
  1069	      { return _M_t.erase(__x); }
  1070	
  1071	#if __cplusplus >= 201103L
  1072	      // _GLIBCXX_RESOLVE_LIB_DEFECTS
  1073	      // DR 130. Associative erase should return an iterator.
  1074	      /**
  1075	       *  @brief Erases a [first,last) range of elements from a %map.
  1076	       *  @param  __first  Iterator pointing to the start of the range to be
  1077	       *                   erased.
  1078	       *  @param __last Iterator pointing to the end of the range to
  1079	       *                be erased.
  1080	       *  @return The iterator @a __last.
  1081	       *
  1082	       *  This function erases a sequence of elements from a %map.
  1083	       *  Note that this function only erases the element, and that if
  1084	       *  the element is itself a pointer, the pointed-to memory is not touched
  1085	       *  in any way.  Managing the pointer is the user's responsibility.
  1086	       */
  1087	      iterator
  1088	      erase(const_iterator __first, const_iterator __last)
  1089	      { return _M_t.erase(__first, __last); }
  1090	#else
  1091	      /**
  1092	       *  @brief Erases a [__first,__last) range of elements from a %map.
  1093	       *  @param  __first  Iterator pointing to the start of the range to be
  1094	       *                   erased.
  1095	       *  @param __last Iterator pointing to the end of the range to
  1096	       *                be erased.
  1097	       *
  1098	       *  This function erases a sequence of elements from a %map.
  1099	       *  Note that this function only erases the element, and that if
  1100	       *  the element is itself a pointer, the pointed-to memory is not touched
  1101	       *  in any way.  Managing the pointer is the user's responsibility.
  1102	       */
  1103	      void
  1104	      erase(iterator __first, iterator __last)
  1105	      { _M_t.erase(__first, __last); }
  1106	#endif
  1107	
  1108	      /**
  1109	       *  @brief  Swaps data with another %map.
  1110	       *  @param  __x  A %map of the same element and allocator types.
  1111	       *
  1112	       *  This exchanges the elements between two maps in constant
  1113	       *  time.  (It is only swapping a pointer, an integer, and an
  1114	       *  instance of the @c Compare type (which itself is often
  1115	       *  stateless and empty), so it should be quite fast.)  Note
  1116	       *  that the global std::swap() function is specialized such
  1117	       *  that std::swap(m1,m2) will feed to this function.
  1118	       *
  1119	       *  Whether the allocators are swapped depends on the allocator traits.
  1120	       */
  1121	      void
  1122	      swap(map& __x)
  1123	      _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
  1124	      { _M_t.swap(__x._M_t); }
  1125	
  1126	      /**
  1127	       *  Erases all elements in a %map.  Note that this function only
  1128	       *  erases the elements, and that if the elements themselves are
  1129	       *  pointers, the pointed-to memory is not touched in any way.
  1130	       *  Managing the pointer is the user's responsibility.
  1131	       */
  1132	      void
  1133	      clear() _GLIBCXX_NOEXCEPT
  1134	      { _M_t.clear(); }
  1135	
  1136	      // observers
  1137	      /**
  1138	       *  Returns the key comparison object out of which the %map was
  1139	       *  constructed.
  1140	       */
  1141	      key_compare
  1142	      key_comp() const
  1143	      { return _M_t.key_comp(); }
  1144	
  1145	      /**
  1146	       *  Returns a value comparison object, built from the key comparison
  1147	       *  object out of which the %map was constructed.
  1148	       */
  1149	      value_compare
  1150	      value_comp() const
  1151	      { return value_compare(_M_t.key_comp()); }
  1152	
  1153	      // [23.3.1.3] map operations
  1154	
  1155	      ///@{
  1156	      /**
  1157	       *  @brief Tries to locate an element in a %map.
  1158	       *  @param  __x  Key of (key, value) %pair to be located.
  1159	       *  @return  Iterator pointing to sought-after element, or end() if not
  1160	       *           found.
  1161	       *
  1162	       *  This function takes a key and tries to locate the element with which
  1163	       *  the key matches.  If successful the function returns an iterator
  1164	       *  pointing to the sought after %pair.  If unsuccessful it returns the
  1165	       *  past-the-end ( @c end() ) iterator.
  1166	       */
  1167	
  1168	      iterator
  1169	      find(const key_type& __x)
  1170	      { return _M_t.find(__x); }
  1171	
  1172	#if __cplusplus > 201103L
  1173	      template<typename _Kt>
  1174		auto
  1175		find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x))
  1176		{ return _M_t._M_find_tr(__x); }
  1177	#endif
  1178	      ///@}
  1179	
  1180	      ///@{
  1181	      /**
  1182	       *  @brief Tries to locate an element in a %map.
  1183	       *  @param  __x  Key of (key, value) %pair to be located.
  1184	       *  @return  Read-only (constant) iterator pointing to sought-after
  1185	       *           element, or end() if not found.
  1186	       *
  1187	       *  This function takes a key and tries to locate the element with which
  1188	       *  the key matches.  If successful the function returns a constant
  1189	       *  iterator pointing to the sought after %pair. If unsuccessful it
  1190	       *  returns the past-the-end ( @c end() ) iterator.
  1191	       */
  1192	
  1193	      const_iterator
  1194	      find(const key_type& __x) const
  1195	      { return _M_t.find(__x); }
  1196	
  1197	#if __cplusplus > 201103L
  1198	      template<typename _Kt>
  1199		auto
  1200		find(const _Kt& __x) const -> decltype(_M_t._M_find_tr(__x))
  1201		{ return _M_t._M_find_tr(__x); }
  1202	#endif
  1203	      ///@}
  1204	
  1205	      ///@{
  1206	      /**
  1207	       *  @brief  Finds the number of elements with given key.
  1208	       *  @param  __x  Key of (key, value) pairs to be located.
  1209	       *  @return  Number of elements with specified key.
  1210	       *
  1211	       *  This function only makes sense for multimaps; for map the result will
  1212	       *  either be 0 (not present) or 1 (present).
  1213	       */
  1214	      size_type
  1215	      count(const key_type& __x) const
  1216	      { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
  1217	
  1218	#if __cplusplus > 201103L
  1219	      template<typename _Kt>
  1220		auto
  1221		count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x))
  1222		{ return _M_t._M_count_tr(__x); }
  1223	#endif
  1224	      ///@}
  1225	
  1226	#if __cplusplus > 201703L
  1227	      ///@{
  1228	      /**
  1229	       *  @brief  Finds whether an element with the given key exists.
  1230	       *  @param  __x  Key of (key, value) pairs to be located.
  1231	       *  @return  True if there is an element with the specified key.
  1232	       */
  1233	      bool
  1234	      contains(const key_type& __x) const
  1235	      { return _M_t.find(__x) != _M_t.end(); }
  1236	
  1237	      template<typename _Kt>
  1238		auto
  1239		contains(const _Kt& __x) const
  1240		-> decltype(_M_t._M_find_tr(__x), void(), true)
  1241		{ return _M_t._M_find_tr(__x) != _M_t.end(); }
  1242	      ///@}
  1243	#endif
  1244	
  1245	      ///@{
  1246	      /**
  1247	       *  @brief Finds the beginning of a subsequence matching given key.
  1248	       *  @param  __x  Key of (key, value) pair to be located.
  1249	       *  @return  Iterator pointing to first element equal to or greater
  1250	       *           than key, or end().
  1251	       *
  1252	       *  This function returns the first element of a subsequence of elements
  1253	       *  that matches the given key.  If unsuccessful it returns an iterator
  1254	       *  pointing to the first element that has a greater value than given key
  1255	       *  or end() if no such element exists.
  1256	       */
  1257	      iterator
  1258	      lower_bound(const key_type& __x)
  1259	      { return _M_t.lower_bound(__x); }
  1260	
  1261	#if __cplusplus > 201103L
  1262	      template<typename _Kt>
  1263		auto
  1264		lower_bound(const _Kt& __x)
  1265		-> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
  1266		{ return iterator(_M_t._M_lower_bound_tr(__x)); }
  1267	#endif
  1268	      ///@}
  1269	
  1270	      ///@{
  1271	      /**
  1272	       *  @brief Finds the beginning of a subsequence matching given key.
  1273	       *  @param  __x  Key of (key, value) pair to be located.
  1274	       *  @return  Read-only (constant) iterator pointing to first element
  1275	       *           equal to or greater than key, or end().
  1276	       *
  1277	       *  This function returns the first element of a subsequence of elements
  1278	       *  that matches the given key.  If unsuccessful it returns an iterator
  1279	       *  pointing to the first element that has a greater value than given key
  1280	       *  or end() if no such element exists.
  1281	       */
  1282	      const_iterator
  1283	      lower_bound(const key_type& __x) const
  1284	      { return _M_t.lower_bound(__x); }
  1285	
  1286	#if __cplusplus > 201103L
  1287	      template<typename _Kt>
  1288		auto
  1289		lower_bound(const _Kt& __x) const
  1290		-> decltype(const_iterator(_M_t._M_lower_bound_tr(__x)))
  1291		{ return const_iterator(_M_t._M_lower_bound_tr(__x)); }
  1292	#endif
  1293	      ///@}
  1294	
  1295	      ///@{
  1296	      /**
  1297	       *  @brief Finds the end of a subsequence matching given key.
  1298	       *  @param  __x  Key of (key, value) pair to be located.
  1299	       *  @return Iterator pointing to the first element
  1300	       *          greater than key, or end().
  1301	       */
  1302	      iterator
  1303	      upper_bound(const key_type& __x)
  1304	      { return _M_t.upper_bound(__x); }
  1305	
  1306	#if __cplusplus > 201103L
  1307	      template<typename _Kt>
  1308		auto
  1309		upper_bound(const _Kt& __x)
  1310		-> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
  1311		{ return iterator(_M_t._M_upper_bound_tr(__x)); }
  1312	#endif
  1313	      ///@}
  1314	
  1315	      ///@{
  1316	      /**
  1317	       *  @brief Finds the end of a subsequence matching given key.
  1318	       *  @param  __x  Key of (key, value) pair to be located.
  1319	       *  @return  Read-only (constant) iterator pointing to first iterator
  1320	       *           greater than key, or end().
  1321	       */
  1322	      const_iterator
  1323	      upper_bound(const key_type& __x) const
  1324	      { return _M_t.upper_bound(__x); }
  1325	
  1326	#if __cplusplus > 201103L
  1327	      template<typename _Kt>
  1328		auto
  1329		upper_bound(const _Kt& __x) const
  1330		-> decltype(const_iterator(_M_t._M_upper_bound_tr(__x)))
  1331		{ return const_iterator(_M_t._M_upper_bound_tr(__x)); }
  1332	#endif
  1333	      ///@}
  1334	
  1335	      ///@{
  1336	      /**
  1337	       *  @brief Finds a subsequence matching given key.
  1338	       *  @param  __x  Key of (key, value) pairs to be located.
  1339	       *  @return  Pair of iterators that possibly points to the subsequence
  1340	       *           matching given key.
  1341	       *
  1342	       *  This function is equivalent to
  1343	       *  @code
  1344	       *    std::make_pair(c.lower_bound(val),
  1345	       *                   c.upper_bound(val))
  1346	       *  @endcode
  1347	       *  (but is faster than making the calls separately).
  1348	       *
  1349	       *  This function probably only makes sense for multimaps.
  1350	       */
  1351	      std::pair<iterator, iterator>
  1352	      equal_range(const key_type& __x)
  1353	      { return _M_t.equal_range(__x); }
  1354	
  1355	#if __cplusplus > 201103L
  1356	      template<typename _Kt>
  1357		auto
  1358		equal_range(const _Kt& __x)
  1359		-> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)))
  1360		{ return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); }
  1361	#endif
  1362	      ///@}
  1363	
  1364	      ///@{
  1365	      /**
  1366	       *  @brief Finds a subsequence matching given key.
  1367	       *  @param  __x  Key of (key, value) pairs to be located.
  1368	       *  @return  Pair of read-only (constant) iterators that possibly points
  1369	       *           to the subsequence matching given key.
  1370	       *
  1371	       *  This function is equivalent to
  1372	       *  @code
  1373	       *    std::make_pair(c.lower_bound(val),
  1374	       *                   c.upper_bound(val))
  1375	       *  @endcode
  1376	       *  (but is faster than making the calls separately).
  1377	       *
  1378	       *  This function probably only makes sense for multimaps.
  1379	       */
  1380	      std::pair<const_iterator, const_iterator>
  1381	      equal_range(const key_type& __x) const
  1382	      { return _M_t.equal_range(__x); }
  1383	
  1384	#if __cplusplus > 201103L
  1385	      template<typename _Kt>
  1386		auto
  1387		equal_range(const _Kt& __x) const
  1388		-> decltype(pair<const_iterator, const_iterator>(
  1389		      _M_t._M_equal_range_tr(__x)))
  1390		{
  1391		  return pair<const_iterator, const_iterator>(
  1392		      _M_t._M_equal_range_tr(__x));
  1393		}
  1394	#endif
  1395	      ///@}
  1396	
  1397	      template<typename _K1, typename _T1, typename _C1, typename _A1>
  1398		friend bool
  1399		operator==(const map<_K1, _T1, _C1, _A1>&,
  1400			   const map<_K1, _T1, _C1, _A1>&);
  1401	
  1402	#if __cpp_lib_three_way_comparison
  1403	      template<typename _K1, typename _T1, typename _C1, typename _A1>
  1404		friend __detail::__synth3way_t<pair<const _K1, _T1>>
  1405		operator<=>(const map<_K1, _T1, _C1, _A1>&,
  1406			    const map<_K1, _T1, _C1, _A1>&);
  1407	#else
  1408	      template<typename _K1, typename _T1, typename _C1, typename _A1>
  1409		friend bool
  1410		operator<(const map<_K1, _T1, _C1, _A1>&,
  1411			  const map<_K1, _T1, _C1, _A1>&);
  1412	#endif
  1413	    };
  1414	
  1415	
  1416	#if __cpp_deduction_guides >= 201606
  1417	
  1418	  template<typename _InputIterator,
  1419		   typename _Compare = less<__iter_key_t<_InputIterator>>,
  1420		   typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
  1421		   typename = _RequireInputIter<_InputIterator>,
  1422		   typename = _RequireNotAllocator<_Compare>,
  1423		   typename = _RequireAllocator<_Allocator>>
  1424	    map(_InputIterator, _InputIterator,
  1425		_Compare = _Compare(), _Allocator = _Allocator())
  1426	    -> map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
  1427		   _Compare, _Allocator>;
  1428	
  1429	  template<typename _Key, typename _Tp, typename _Compare = less<_Key>,
  1430		   typename _Allocator = allocator<pair<const _Key, _Tp>>,
  1431		   typename = _RequireNotAllocator<_Compare>,
  1432		   typename = _RequireAllocator<_Allocator>>
  1433	    map(initializer_list<pair<_Key, _Tp>>,
  1434		_Compare = _Compare(), _Allocator = _Allocator())
  1435	    -> map<_Key, _Tp, _Compare, _Allocator>;
  1436	
  1437	  template <typename _InputIterator, typename _Allocator,
  1438		    typename = _RequireInputIter<_InputIterator>,
  1439		    typename = _RequireAllocator<_Allocator>>
  1440	    map(_InputIterator, _InputIterator, _Allocator)
  1441	    -> map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
  1442		   less<__iter_key_t<_InputIterator>>, _Allocator>;
  1443	
  1444	  template<typename _Key, typename _Tp, typename _Allocator,
  1445		   typename = _RequireAllocator<_Allocator>>
  1446	    map(initializer_list<pair<_Key, _Tp>>, _Allocator)
  1447	    -> map<_Key, _Tp, less<_Key>, _Allocator>;
  1448	
  1449	#endif // deduction guides
  1450	
  1451	  /**
  1452	   *  @brief  Map equality comparison.
  1453	   *  @param  __x  A %map.
  1454	   *  @param  __y  A %map of the same type as @a x.
  1455	   *  @return  True iff the size and elements of the maps are equal.
  1456	   *
  1457	   *  This is an equivalence relation.  It is linear in the size of the
  1458	   *  maps.  Maps are considered equivalent if their sizes are equal,
  1459	   *  and if corresponding elements compare equal.
  1460	  */
  1461	  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
  1462	    inline bool
  1463	    operator==(const map<_Key, _Tp, _Compare, _Alloc>& __x,
  1464		       const map<_Key, _Tp, _Compare, _Alloc>& __y)
  1465	    { return __x._M_t == __y._M_t; }
  1466	
  1467	#if __cpp_lib_three_way_comparison
  1468	  /**
  1469	   *  @brief  Map ordering relation.
  1470	   *  @param  __x  A `map`.
  1471	   *  @param  __y  A `map` of the same type as `x`.
  1472	   *  @return  A value indicating whether `__x` is less than, equal to,
  1473	   *           greater than, or incomparable with `__y`.
  1474	   *
  1475	   *  This is a total ordering relation.  It is linear in the size of the
  1476	   *  maps.  The elements must be comparable with @c <.
  1477	   *
  1478	   *  See `std::lexicographical_compare_three_way()` for how the determination
  1479	   *  is made. This operator is used to synthesize relational operators like
  1480	   *  `<` and `>=` etc.
  1481	  */
  1482	  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
  1483	    inline __detail::__synth3way_t<pair<const _Key, _Tp>>
  1484	    operator<=>(const map<_Key, _Tp, _Compare, _Alloc>& __x,
  1485			const map<_Key, _Tp, _Compare, _Alloc>& __y)
  1486	    { return __x._M_t <=> __y._M_t; }
  1487	#else
  1488	  /**
  1489	   *  @brief  Map ordering relation.
  1490	   *  @param  __x  A %map.
  1491	   *  @param  __y  A %map of the same type as @a x.
  1492	   *  @return  True iff @a x is lexicographically less than @a y.
  1493	   *
  1494	   *  This is a total ordering relation.  It is linear in the size of the
  1495	   *  maps.  The elements must be comparable with @c <.
  1496	   *
  1497	   *  See std::lexicographical_compare() for how the determination is made.
  1498	  */
  1499	  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
  1500	    inline bool
  1501	    operator<(const map<_Key, _Tp, _Compare, _Alloc>& __x,
  1502		      const map<_Key, _Tp, _Compare, _Alloc>& __y)
  1503	    { return __x._M_t < __y._M_t; }
  1504	
  1505	  /// Based on operator==
  1506	  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
  1507	    inline bool
  1508	    operator!=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
  1509		       const map<_Key, _Tp, _Compare, _Alloc>& __y)
  1510	    { return !(__x == __y); }
  1511	
  1512	  /// Based on operator<
  1513	  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
  1514	    inline bool
  1515	    operator>(const map<_Key, _Tp, _Compare, _Alloc>& __x,
  1516		      const map<_Key, _Tp, _Compare, _Alloc>& __y)
  1517	    { return __y < __x; }
  1518	
  1519	  /// Based on operator<
  1520	  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
  1521	    inline bool
  1522	    operator<=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
  1523		       const map<_Key, _Tp, _Compare, _Alloc>& __y)
  1524	    { return !(__y < __x); }
  1525	
  1526	  /// Based on operator<
  1527	  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
  1528	    inline bool
  1529	    operator>=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
  1530		       const map<_Key, _Tp, _Compare, _Alloc>& __y)
  1531	    { return !(__x < __y); }
  1532	#endif // three-way comparison
  1533	
  1534	  /// See std::map::swap().
  1535	  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
  1536	    inline void
  1537	    swap(map<_Key, _Tp, _Compare, _Alloc>& __x,
  1538		 map<_Key, _Tp, _Compare, _Alloc>& __y)
  1539	    _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
  1540	    { __x.swap(__y); }
  1541	
  1542	_GLIBCXX_END_NAMESPACE_CONTAINER
  1543	
  1544	#if __cplusplus > 201402L
  1545	  // Allow std::map access to internals of compatible maps.
  1546	  template<typename _Key, typename _Val, typename _Cmp1, typename _Alloc,
  1547		   typename _Cmp2>
  1548	    struct
  1549	    _Rb_tree_merge_helper<_GLIBCXX_STD_C::map<_Key, _Val, _Cmp1, _Alloc>,
  1550				  _Cmp2>
  1551	    {
  1552	    private:
  1553	      friend class _GLIBCXX_STD_C::map<_Key, _Val, _Cmp1, _Alloc>;
  1554	
  1555	      static auto&
  1556	      _S_get_tree(_GLIBCXX_STD_C::map<_Key, _Val, _Cmp2, _Alloc>& __map)
  1557	      { return __map._M_t; }
  1558	
  1559	      static auto&
  1560	      _S_get_tree(_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp2, _Alloc>& __map)
  1561	      { return __map._M_t; }
  1562	    };
  1563	#endif // C++17
  1564	
  1565	_GLIBCXX_END_NAMESPACE_VERSION
  1566	} // namespace std
  1567	
  1568	#endif /* _STL_MAP_H */