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