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