1    	// Multimap 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_multimap.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_MULTIMAP_H
57   	#define _STL_MULTIMAP_H 1
58   	
59   	#include <bits/concept_check.h>
60   	#if __cplusplus >= 201103L
61   	#include <initializer_list>
62   	#endif
63   	
64   	namespace std _GLIBCXX_VISIBILITY(default)
65   	{
66   	_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
67   	
68   	  template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
69   	    class map;
70   	
71   	  /**
72   	   *  @brief A standard container made up of (key,value) pairs, which can be
73   	   *  retrieved based on a key, in logarithmic time.
74   	   *
75   	   *  @ingroup associative_containers
76   	   *
77   	   *  @tparam _Key  Type of key objects.
78   	   *  @tparam  _Tp  Type of mapped objects.
79   	   *  @tparam _Compare  Comparison function object type, defaults to less<_Key>.
80   	   *  @tparam _Alloc  Allocator type, defaults to
81   	   *                  allocator<pair<const _Key, _Tp>.
82   	   *
83   	   *  Meets the requirements of a <a href="tables.html#65">container</a>, a
84   	   *  <a href="tables.html#66">reversible container</a>, and an
85   	   *  <a href="tables.html#69">associative container</a> (using equivalent
86   	   *  keys).  For a @c multimap<Key,T> the key_type is Key, the mapped_type
87   	   *  is T, and the value_type is std::pair<const Key,T>.
88   	   *
89   	   *  Multimaps support bidirectional iterators.
90   	   *
91   	   *  The private tree data is declared exactly the same way for map and
92   	   *  multimap; the distinction is made entirely in how the tree functions are
93   	   *  called (*_unique versus *_equal, same as the standard).
94   	  */
95   	  template <typename _Key, typename _Tp,
96   		    typename _Compare = std::less<_Key>,
97   		    typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
98   	    class multimap
99   	    {
100  	    public:
101  	      typedef _Key					key_type;
102  	      typedef _Tp					mapped_type;
103  	      typedef std::pair<const _Key, _Tp>		value_type;
104  	      typedef _Compare					key_compare;
105  	      typedef _Alloc					allocator_type;
106  	
107  	    private:
108  	#ifdef _GLIBCXX_CONCEPT_CHECKS
109  	      // concept requirements
110  	      typedef typename _Alloc::value_type		_Alloc_value_type;
111  	# if __cplusplus < 201103L
112  	      __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
113  	# endif
114  	      __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
115  					_BinaryFunctionConcept)
116  	      __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept)
117  	#endif
118  	
119  	    public:
120  	      class value_compare
121  	      : public std::binary_function<value_type, value_type, bool>
122  	      {
123  		friend class multimap<_Key, _Tp, _Compare, _Alloc>;
124  	      protected:
125  		_Compare comp;
126  	
127  		value_compare(_Compare __c)
128  		: comp(__c) { }
129  	
130  	      public:
131  		bool operator()(const value_type& __x, const value_type& __y) const
132  		{ return comp(__x.first, __y.first); }
133  	      };
134  	
135  	    private:
136  	      /// This turns a red-black tree into a [multi]map.
137  	      typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
138  		rebind<value_type>::other _Pair_alloc_type;
139  	
140  	      typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
141  			       key_compare, _Pair_alloc_type> _Rep_type;
142  	      /// The actual tree structure.
143  	      _Rep_type _M_t;
144  	
145  	      typedef __gnu_cxx::__alloc_traits<_Pair_alloc_type> _Alloc_traits;
146  	
147  	    public:
148  	      // many of these are specified differently in ISO, but the following are
149  	      // "functionally equivalent"
150  	      typedef typename _Alloc_traits::pointer		 pointer;
151  	      typedef typename _Alloc_traits::const_pointer	 const_pointer;
152  	      typedef typename _Alloc_traits::reference		 reference;
153  	      typedef typename _Alloc_traits::const_reference	 const_reference;
154  	      typedef typename _Rep_type::iterator		 iterator;
155  	      typedef typename _Rep_type::const_iterator	 const_iterator;
156  	      typedef typename _Rep_type::size_type		 size_type;
157  	      typedef typename _Rep_type::difference_type	 difference_type;
158  	      typedef typename _Rep_type::reverse_iterator	 reverse_iterator;
159  	      typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
160  	
161  	#if __cplusplus > 201402L
162  	      using node_type = typename _Rep_type::node_type;
163  	#endif
164  	
165  	      // [23.3.2] construct/copy/destroy
166  	      // (get_allocator() is also listed in this section)
167  	
168  	      /**
169  	       *  @brief  Default constructor creates no elements.
170  	       */
171  	#if __cplusplus < 201103L
172  	      multimap() : _M_t() { }
173  	#else
174  	      multimap() = default;
175  	#endif
176  	
177  	      /**
178  	       *  @brief  Creates a %multimap with no elements.
179  	       *  @param  __comp  A comparison object.
180  	       *  @param  __a  An allocator object.
181  	       */
182  	      explicit
183  	      multimap(const _Compare& __comp,
184  		       const allocator_type& __a = allocator_type())
185  	      : _M_t(__comp, _Pair_alloc_type(__a)) { }
186  	
187  	      /**
188  	       *  @brief  %Multimap copy constructor.
189  	       *
190  	       *  Whether the allocator is copied depends on the allocator traits.
191  	       */
192  	#if __cplusplus < 201103L
193  	      multimap(const multimap& __x)
194  	      : _M_t(__x._M_t) { }
195  	#else
196  	      multimap(const multimap&) = default;
197  	
198  	      /**
199  	       *  @brief  %Multimap move constructor.
200  	       *
201  	       *  The newly-created %multimap contains the exact contents of the
202  	       *  moved instance. The moved instance is a valid, but unspecified
203  	       *  %multimap.
204  	       */
205  	      multimap(multimap&&) = default;
206  	
207  	      /**
208  	       *  @brief  Builds a %multimap from an initializer_list.
209  	       *  @param  __l  An initializer_list.
210  	       *  @param  __comp  A comparison functor.
211  	       *  @param  __a  An allocator object.
212  	       *
213  	       *  Create a %multimap consisting of copies of the elements from
214  	       *  the initializer_list.  This is linear in N if the list is already
215  	       *  sorted, and NlogN otherwise (where N is @a __l.size()).
216  	       */
217  	      multimap(initializer_list<value_type> __l,
218  		       const _Compare& __comp = _Compare(),
219  		       const allocator_type& __a = allocator_type())
220  	      : _M_t(__comp, _Pair_alloc_type(__a))
221  	      { _M_t._M_insert_equal(__l.begin(), __l.end()); }
222  	
223  	      /// Allocator-extended default constructor.
224  	      explicit
225  	      multimap(const allocator_type& __a)
226  	      : _M_t(_Compare(), _Pair_alloc_type(__a)) { }
227  	
228  	      /// Allocator-extended copy constructor.
229  	      multimap(const multimap& __m, const allocator_type& __a)
230  	      : _M_t(__m._M_t, _Pair_alloc_type(__a)) { }
231  	
232  	      /// Allocator-extended move constructor.
233  	      multimap(multimap&& __m, const allocator_type& __a)
234  	      noexcept(is_nothrow_copy_constructible<_Compare>::value
235  		       && _Alloc_traits::_S_always_equal())
236  	      : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { }
237  	
238  	      /// Allocator-extended initialier-list constructor.
239  	      multimap(initializer_list<value_type> __l, const allocator_type& __a)
240  	      : _M_t(_Compare(), _Pair_alloc_type(__a))
241  	      { _M_t._M_insert_equal(__l.begin(), __l.end()); }
242  	
243  	      /// Allocator-extended range constructor.
244  	      template<typename _InputIterator>
245  		multimap(_InputIterator __first, _InputIterator __last,
246  			 const allocator_type& __a)
247  		: _M_t(_Compare(), _Pair_alloc_type(__a))
248  		{ _M_t._M_insert_equal(__first, __last); }
249  	#endif
250  	
251  	      /**
252  	       *  @brief  Builds a %multimap from a range.
253  	       *  @param  __first  An input iterator.
254  	       *  @param  __last  An input iterator.
255  	       *
256  	       *  Create a %multimap consisting of copies of the elements from
257  	       *  [__first,__last).  This is linear in N if the range is already sorted,
258  	       *  and NlogN otherwise (where N is distance(__first,__last)).
259  	       */
260  	      template<typename _InputIterator>
261  		multimap(_InputIterator __first, _InputIterator __last)
262  		: _M_t()
263  		{ _M_t._M_insert_equal(__first, __last); }
264  	
265  	      /**
266  	       *  @brief  Builds a %multimap from a range.
267  	       *  @param  __first  An input iterator.
268  	       *  @param  __last  An input iterator.
269  	       *  @param  __comp  A comparison functor.
270  	       *  @param  __a  An allocator object.
271  	       *
272  	       *  Create a %multimap consisting of copies of the elements from
273  	       *  [__first,__last).  This is linear in N if the range is already sorted,
274  	       *  and NlogN otherwise (where N is distance(__first,__last)).
275  	       */
276  	      template<typename _InputIterator>
277  		multimap(_InputIterator __first, _InputIterator __last,
278  			 const _Compare& __comp,
279  			 const allocator_type& __a = allocator_type())
280  		: _M_t(__comp, _Pair_alloc_type(__a))
281  		{ _M_t._M_insert_equal(__first, __last); }
282  	
283  	#if __cplusplus >= 201103L
284  	      /**
285  	       *  The dtor only erases the elements, and note that if the elements
286  	       *  themselves are pointers, the pointed-to memory is not touched in any
287  	       *  way. Managing the pointer is the user's responsibility.
288  	       */
289  	      ~multimap() = default;
290  	#endif
291  	
292  	      /**
293  	       *  @brief  %Multimap assignment operator.
294  	       *
295  	       *  Whether the allocator is copied depends on the allocator traits.
296  	       */
297  	#if __cplusplus < 201103L
298  	      multimap&
299  	      operator=(const multimap& __x)
300  	      {
301  		_M_t = __x._M_t;
302  		return *this;
303  	      }
304  	#else
305  	      multimap&
306  	      operator=(const multimap&) = default;
307  	
308  	      /// Move assignment operator.
309  	      multimap&
310  	      operator=(multimap&&) = default;
311  	
312  	      /**
313  	       *  @brief  %Multimap list assignment operator.
314  	       *  @param  __l  An initializer_list.
315  	       *
316  	       *  This function fills a %multimap with copies of the elements
317  	       *  in the initializer list @a __l.
318  	       *
319  	       *  Note that the assignment completely changes the %multimap and
320  	       *  that the resulting %multimap's size is the same as the number
321  	       *  of elements assigned.
322  	       */
323  	      multimap&
324  	      operator=(initializer_list<value_type> __l)
325  	      {
326  		_M_t._M_assign_equal(__l.begin(), __l.end());
327  		return *this;
328  	      }
329  	#endif
330  	
331  	      /// Get a copy of the memory allocation object.
332  	      allocator_type
333  	      get_allocator() const _GLIBCXX_NOEXCEPT
334  	      { return allocator_type(_M_t.get_allocator()); }
335  	
336  	      // iterators
337  	      /**
338  	       *  Returns a read/write iterator that points to the first pair in the
339  	       *  %multimap.  Iteration is done in ascending order according to the
340  	       *  keys.
341  	       */
342  	      iterator
343  	      begin() _GLIBCXX_NOEXCEPT
344  	      { return _M_t.begin(); }
345  	
346  	      /**
347  	       *  Returns a read-only (constant) iterator that points to the first pair
348  	       *  in the %multimap.  Iteration is done in ascending order according to
349  	       *  the keys.
350  	       */
351  	      const_iterator
352  	      begin() const _GLIBCXX_NOEXCEPT
353  	      { return _M_t.begin(); }
354  	
355  	      /**
356  	       *  Returns a read/write iterator that points one past the last pair in
357  	       *  the %multimap.  Iteration is done in ascending order according to the
358  	       *  keys.
359  	       */
360  	      iterator
361  	      end() _GLIBCXX_NOEXCEPT
362  	      { return _M_t.end(); }
363  	
364  	      /**
365  	       *  Returns a read-only (constant) iterator that points one past the last
366  	       *  pair in the %multimap.  Iteration is done in ascending order according
367  	       *  to the keys.
368  	       */
369  	      const_iterator
370  	      end() const _GLIBCXX_NOEXCEPT
371  	      { return _M_t.end(); }
372  	
373  	      /**
374  	       *  Returns a read/write reverse iterator that points to the last pair in
375  	       *  the %multimap.  Iteration is done in descending order according to the
376  	       *  keys.
377  	       */
378  	      reverse_iterator
379  	      rbegin() _GLIBCXX_NOEXCEPT
380  	      { return _M_t.rbegin(); }
381  	
382  	      /**
383  	       *  Returns a read-only (constant) reverse iterator that points to the
384  	       *  last pair in the %multimap.  Iteration is done in descending order
385  	       *  according to the keys.
386  	       */
387  	      const_reverse_iterator
388  	      rbegin() const _GLIBCXX_NOEXCEPT
389  	      { return _M_t.rbegin(); }
390  	
391  	      /**
392  	       *  Returns a read/write reverse iterator that points to one before the
393  	       *  first pair in the %multimap.  Iteration is done in descending order
394  	       *  according to the keys.
395  	       */
396  	      reverse_iterator
397  	      rend() _GLIBCXX_NOEXCEPT
398  	      { return _M_t.rend(); }
399  	
400  	      /**
401  	       *  Returns a read-only (constant) reverse iterator that points to one
402  	       *  before the first pair in the %multimap.  Iteration is done in
403  	       *  descending order according to the keys.
404  	       */
405  	      const_reverse_iterator
406  	      rend() const _GLIBCXX_NOEXCEPT
407  	      { return _M_t.rend(); }
408  	
409  	#if __cplusplus >= 201103L
410  	      /**
411  	       *  Returns a read-only (constant) iterator that points to the first pair
412  	       *  in the %multimap.  Iteration is done in ascending order according to
413  	       *  the keys.
414  	       */
415  	      const_iterator
416  	      cbegin() const noexcept
417  	      { return _M_t.begin(); }
418  	
419  	      /**
420  	       *  Returns a read-only (constant) iterator that points one past the last
421  	       *  pair in the %multimap.  Iteration is done in ascending order according
422  	       *  to the keys.
423  	       */
424  	      const_iterator
425  	      cend() const noexcept
426  	      { return _M_t.end(); }
427  	
428  	      /**
429  	       *  Returns a read-only (constant) reverse iterator that points to the
430  	       *  last pair in the %multimap.  Iteration is done in descending order
431  	       *  according to the keys.
432  	       */
433  	      const_reverse_iterator
434  	      crbegin() const noexcept
435  	      { return _M_t.rbegin(); }
436  	
437  	      /**
438  	       *  Returns a read-only (constant) reverse iterator that points to one
439  	       *  before the first pair in the %multimap.  Iteration is done in
440  	       *  descending order according to the keys.
441  	       */
442  	      const_reverse_iterator
443  	      crend() const noexcept
444  	      { return _M_t.rend(); }
445  	#endif
446  	
447  	      // capacity
448  	      /** Returns true if the %multimap is empty.  */
449  	      bool
450  	      empty() const _GLIBCXX_NOEXCEPT
451  	      { return _M_t.empty(); }
452  	
453  	      /** Returns the size of the %multimap.  */
454  	      size_type
455  	      size() const _GLIBCXX_NOEXCEPT
456  	      { return _M_t.size(); }
457  	
458  	      /** Returns the maximum size of the %multimap.  */
459  	      size_type
460  	      max_size() const _GLIBCXX_NOEXCEPT
461  	      { return _M_t.max_size(); }
462  	
463  	      // modifiers
464  	#if __cplusplus >= 201103L
465  	      /**
466  	       *  @brief Build and insert a std::pair into the %multimap.
467  	       *
468  	       *  @param __args  Arguments used to generate a new pair instance (see
469  	       *	        std::piecewise_contruct for passing arguments to each
470  	       *	        part of the pair constructor).
471  	       *
472  	       *  @return An iterator that points to the inserted (key,value) pair.
473  	       *
474  	       *  This function builds and inserts a (key, value) %pair into the
475  	       *  %multimap.
476  	       *  Contrary to a std::map the %multimap does not rely on unique keys and
477  	       *  thus multiple pairs with the same key can be inserted.
478  	       *
479  	       *  Insertion requires logarithmic time.
480  	       */
481  	      template<typename... _Args>
482  		iterator
483  		emplace(_Args&&... __args)
484  		{ return _M_t._M_emplace_equal(std::forward<_Args>(__args)...); }
485  	
486  	      /**
487  	       *  @brief Builds and inserts a std::pair into the %multimap.
488  	       *
489  	       *  @param  __pos  An iterator that serves as a hint as to where the pair
490  	       *                should be inserted.
491  	       *  @param  __args  Arguments used to generate a new pair instance (see
492  	       *	         std::piecewise_contruct for passing arguments to each
493  	       *	         part of the pair constructor).
494  	       *  @return An iterator that points to the inserted (key,value) pair.
495  	       *
496  	       *  This function inserts a (key, value) pair into the %multimap.
497  	       *  Contrary to a std::map the %multimap does not rely on unique keys and
498  	       *  thus multiple pairs with the same key can be inserted.
499  	       *  Note that the first parameter is only a hint and can potentially
500  	       *  improve the performance of the insertion process.  A bad hint would
501  	       *  cause no gains in efficiency.
502  	       *
503  	       *  For more on @a hinting, see:
504  	       *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
505  	       *
506  	       *  Insertion requires logarithmic time (if the hint is not taken).
507  	       */
508  	      template<typename... _Args>
509  		iterator
510  		emplace_hint(const_iterator __pos, _Args&&... __args)
511  		{
512  		  return _M_t._M_emplace_hint_equal(__pos,
513  						    std::forward<_Args>(__args)...);
514  		}
515  	#endif
516  	
517  	      /**
518  	       *  @brief Inserts a std::pair into the %multimap.
519  	       *  @param  __x  Pair to be inserted (see std::make_pair for easy creation
520  	       *             of pairs).
521  	       *  @return An iterator that points to the inserted (key,value) pair.
522  	       *
523  	       *  This function inserts a (key, value) pair into the %multimap.
524  	       *  Contrary to a std::map the %multimap does not rely on unique keys and
525  	       *  thus multiple pairs with the same key can be inserted.
526  	       *
527  	       *  Insertion requires logarithmic time.
528  	       *  @{
529  	       */
530  	      iterator
531  	      insert(const value_type& __x)
532  	      { return _M_t._M_insert_equal(__x); }
533  	
534  	#if __cplusplus >= 201103L
535  	      // _GLIBCXX_RESOLVE_LIB_DEFECTS
536  	      // 2354. Unnecessary copying when inserting into maps with braced-init
537  	      iterator
538  	      insert(value_type&& __x)
539  	      { return _M_t._M_insert_equal(std::move(__x)); }
540  	
541  	      template<typename _Pair>
542  		__enable_if_t<is_constructible<value_type, _Pair>::value, iterator>
543  		insert(_Pair&& __x)
544  		{ return _M_t._M_emplace_equal(std::forward<_Pair>(__x)); }
545  	#endif
546  	      // @}
547  	
548  	      /**
549  	       *  @brief Inserts a std::pair into the %multimap.
550  	       *  @param  __position  An iterator that serves as a hint as to where the
551  	       *                      pair should be inserted.
552  	       *  @param  __x  Pair to be inserted (see std::make_pair for easy creation
553  	       *               of pairs).
554  	       *  @return An iterator that points to the inserted (key,value) pair.
555  	       *
556  	       *  This function inserts a (key, value) pair into the %multimap.
557  	       *  Contrary to a std::map the %multimap does not rely on unique keys and
558  	       *  thus multiple pairs with the same key can be inserted.
559  	       *  Note that the first parameter is only a hint and can potentially
560  	       *  improve the performance of the insertion process.  A bad hint would
561  	       *  cause no gains in efficiency.
562  	       *
563  	       *  For more on @a hinting, see:
564  	       *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
565  	       *
566  	       *  Insertion requires logarithmic time (if the hint is not taken).
567  	       * @{
568  	       */
569  	      iterator
570  	#if __cplusplus >= 201103L
571  	      insert(const_iterator __position, const value_type& __x)
572  	#else
573  	      insert(iterator __position, const value_type& __x)
574  	#endif
575  	      { return _M_t._M_insert_equal_(__position, __x); }
576  	
577  	#if __cplusplus >= 201103L
578  	      // _GLIBCXX_RESOLVE_LIB_DEFECTS
579  	      // 2354. Unnecessary copying when inserting into maps with braced-init
580  	      iterator
581  	      insert(const_iterator __position, value_type&& __x)
582  	      { return _M_t._M_insert_equal_(__position, std::move(__x)); }
583  	
584  	      template<typename _Pair>
585  		__enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
586  		insert(const_iterator __position, _Pair&& __x)
587  		{
588  		  return _M_t._M_emplace_hint_equal(__position,
589  						    std::forward<_Pair>(__x));
590  		}
591  	#endif
592  	      // @}
593  	
594  	      /**
595  	       *  @brief A template function that attempts to insert a range
596  	       *  of elements.
597  	       *  @param  __first  Iterator pointing to the start of the range to be
598  	       *                   inserted.
599  	       *  @param  __last  Iterator pointing to the end of the range.
600  	       *
601  	       *  Complexity similar to that of the range constructor.
602  	       */
603  	      template<typename _InputIterator>
604  		void
605  		insert(_InputIterator __first, _InputIterator __last)
606  		{ _M_t._M_insert_equal(__first, __last); }
607  	
608  	#if __cplusplus >= 201103L
609  	      /**
610  	       *  @brief Attempts to insert a list of std::pairs into the %multimap.
611  	       *  @param  __l  A std::initializer_list<value_type> of pairs to be
612  	       *               inserted.
613  	       *
614  	       *  Complexity similar to that of the range constructor.
615  	       */
616  	      void
617  	      insert(initializer_list<value_type> __l)
618  	      { this->insert(__l.begin(), __l.end()); }
619  	#endif
620  	
621  	#if __cplusplus > 201402L
622  	      /// Extract a node.
623  	      node_type
624  	      extract(const_iterator __pos)
625  	      {
626  		__glibcxx_assert(__pos != end());
627  		return _M_t.extract(__pos);
628  	      }
629  	
630  	      /// Extract a node.
631  	      node_type
632  	      extract(const key_type& __x)
633  	      { return _M_t.extract(__x); }
634  	
635  	      /// Re-insert an extracted node.
636  	      iterator
637  	      insert(node_type&& __nh)
638  	      { return _M_t._M_reinsert_node_equal(std::move(__nh)); }
639  	
640  	      /// Re-insert an extracted node.
641  	      iterator
642  	      insert(const_iterator __hint, node_type&& __nh)
643  	      { return _M_t._M_reinsert_node_hint_equal(__hint, std::move(__nh)); }
644  	
645  	      template<typename, typename>
646  		friend class _Rb_tree_merge_helper;
647  	
648  	      template<typename _C2>
649  		void
650  		merge(multimap<_Key, _Tp, _C2, _Alloc>& __source)
651  		{
652  		  using _Merge_helper = _Rb_tree_merge_helper<multimap, _C2>;
653  		  _M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source));
654  		}
655  	
656  	      template<typename _C2>
657  		void
658  		merge(multimap<_Key, _Tp, _C2, _Alloc>&& __source)
659  		{ merge(__source); }
660  	
661  	      template<typename _C2>
662  		void
663  		merge(map<_Key, _Tp, _C2, _Alloc>& __source)
664  		{
665  		  using _Merge_helper = _Rb_tree_merge_helper<multimap, _C2>;
666  		  _M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source));
667  		}
668  	
669  	      template<typename _C2>
670  		void
671  		merge(map<_Key, _Tp, _C2, _Alloc>&& __source)
672  		{ merge(__source); }
673  	#endif // C++17
674  	
675  	#if __cplusplus >= 201103L
676  	      // _GLIBCXX_RESOLVE_LIB_DEFECTS
677  	      // DR 130. Associative erase should return an iterator.
678  	      /**
679  	       *  @brief Erases an element from a %multimap.
680  	       *  @param  __position  An iterator pointing to the element to be erased.
681  	       *  @return An iterator pointing to the element immediately following
682  	       *          @a position prior to the element being erased. If no such
683  	       *          element exists, end() is returned.
684  	       *
685  	       *  This function erases an element, pointed to by the given iterator,
686  	       *  from a %multimap.  Note that this function only erases the element,
687  	       *  and that if the element is itself a pointer, the pointed-to memory is
688  	       *  not touched in any way.  Managing the pointer is the user's
689  	       *  responsibility.
690  	       *
691  	       * @{
692  	       */
693  	      iterator
694  	      erase(const_iterator __position)
695  	      { return _M_t.erase(__position); }
696  	
697  	      // LWG 2059.
698  	      _GLIBCXX_ABI_TAG_CXX11
699  	      iterator
700  	      erase(iterator __position)
701  	      { return _M_t.erase(__position); }
702  	      // @}
703  	#else
704  	      /**
705  	       *  @brief Erases an element from a %multimap.
706  	       *  @param  __position  An iterator pointing to the element to be erased.
707  	       *
708  	       *  This function erases an element, pointed to by the given iterator,
709  	       *  from a %multimap.  Note that this function only erases the element,
710  	       *  and that if the element is itself a pointer, the pointed-to memory is
711  	       *  not touched in any way.  Managing the pointer is the user's
712  	       *  responsibility.
713  	       */
714  	      void
715  	      erase(iterator __position)
716  	      { _M_t.erase(__position); }
717  	#endif
718  	
719  	      /**
720  	       *  @brief Erases elements according to the provided key.
721  	       *  @param  __x  Key of element to be erased.
722  	       *  @return  The number of elements erased.
723  	       *
724  	       *  This function erases all elements located by the given key from a
725  	       *  %multimap.
726  	       *  Note that this function only erases the element, and that if
727  	       *  the element is itself a pointer, the pointed-to memory is not touched
728  	       *  in any way.  Managing the pointer is the user's responsibility.
729  	       */
730  	      size_type
731  	      erase(const key_type& __x)
732  	      { return _M_t.erase(__x); }
733  	
734  	#if __cplusplus >= 201103L
735  	      // _GLIBCXX_RESOLVE_LIB_DEFECTS
736  	      // DR 130. Associative erase should return an iterator.
737  	      /**
738  	       *  @brief Erases a [first,last) range of elements from a %multimap.
739  	       *  @param  __first  Iterator pointing to the start of the range to be
740  	       *                   erased.
741  	       *  @param __last Iterator pointing to the end of the range to be
742  	       *                erased .
743  	       *  @return The iterator @a __last.
744  	       *
745  	       *  This function erases a sequence of elements from a %multimap.
746  	       *  Note that this function only erases the elements, and that if
747  	       *  the elements themselves are pointers, the pointed-to memory is not
748  	       *  touched in any way.  Managing the pointer is the user's
749  	       *  responsibility.
750  	       */
751  	      iterator
752  	      erase(const_iterator __first, const_iterator __last)
753  	      { return _M_t.erase(__first, __last); }
754  	#else
755  	      // _GLIBCXX_RESOLVE_LIB_DEFECTS
756  	      // DR 130. Associative erase should return an iterator.
757  	      /**
758  	       *  @brief Erases a [first,last) range of elements from a %multimap.
759  	       *  @param  __first  Iterator pointing to the start of the range to be
760  	       *                 erased.
761  	       *  @param __last Iterator pointing to the end of the range to
762  	       *                be erased.
763  	       *
764  	       *  This function erases a sequence of elements from a %multimap.
765  	       *  Note that this function only erases the elements, and that if
766  	       *  the elements themselves are pointers, the pointed-to memory is not
767  	       *  touched in any way.  Managing the pointer is the user's
768  	       *  responsibility.
769  	       */
770  	      void
771  	      erase(iterator __first, iterator __last)
772  	      { _M_t.erase(__first, __last); }
773  	#endif
774  	
775  	      /**
776  	       *  @brief  Swaps data with another %multimap.
777  	       *  @param  __x  A %multimap of the same element and allocator types.
778  	       *
779  	       *  This exchanges the elements between two multimaps in constant time.
780  	       *  (It is only swapping a pointer, an integer, and an instance of
781  	       *  the @c Compare type (which itself is often stateless and empty), so it
782  	       *  should be quite fast.)
783  	       *  Note that the global std::swap() function is specialized such that
784  	       *  std::swap(m1,m2) will feed to this function.
785  	       *
786  	       *  Whether the allocators are swapped depends on the allocator traits.
787  	       */
788  	      void
789  	      swap(multimap& __x)
790  	      _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
791  	      { _M_t.swap(__x._M_t); }
792  	
793  	      /**
794  	       *  Erases all elements in a %multimap.  Note that this function only
795  	       *  erases the elements, and that if the elements themselves are pointers,
796  	       *  the pointed-to memory is not touched in any way.  Managing the pointer
797  	       *  is the user's responsibility.
798  	       */
799  	      void
800  	      clear() _GLIBCXX_NOEXCEPT
801  	      { _M_t.clear(); }
802  	
803  	      // observers
804  	      /**
805  	       *  Returns the key comparison object out of which the %multimap
806  	       *  was constructed.
807  	       */
808  	      key_compare
809  	      key_comp() const
810  	      { return _M_t.key_comp(); }
811  	
812  	      /**
813  	       *  Returns a value comparison object, built from the key comparison
814  	       *  object out of which the %multimap was constructed.
815  	       */
816  	      value_compare
817  	      value_comp() const
818  	      { return value_compare(_M_t.key_comp()); }
819  	
820  	      // multimap operations
821  	
822  	      //@{
823  	      /**
824  	       *  @brief Tries to locate an element in a %multimap.
825  	       *  @param  __x  Key of (key, value) pair to be located.
826  	       *  @return  Iterator pointing to sought-after element,
827  	       *           or end() if not found.
828  	       *
829  	       *  This function takes a key and tries to locate the element with which
830  	       *  the key matches.  If successful the function returns an iterator
831  	       *  pointing to the sought after %pair.  If unsuccessful it returns the
832  	       *  past-the-end ( @c end() ) iterator.
833  	       */
834  	      iterator
835  	      find(const key_type& __x)
836  	      { return _M_t.find(__x); }
837  	
838  	#if __cplusplus > 201103L
839  	      template<typename _Kt>
840  		auto
841  		find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x))
842  		{ return _M_t._M_find_tr(__x); }
843  	#endif
844  	      //@}
845  	
846  	      //@{
847  	      /**
848  	       *  @brief Tries to locate an element in a %multimap.
849  	       *  @param  __x  Key of (key, value) pair to be located.
850  	       *  @return  Read-only (constant) iterator pointing to sought-after
851  	       *           element, or end() if not found.
852  	       *
853  	       *  This function takes a key and tries to locate the element with which
854  	       *  the key matches.  If successful the function returns a constant
855  	       *  iterator pointing to the sought after %pair.  If unsuccessful it
856  	       *  returns the past-the-end ( @c end() ) iterator.
857  	       */
858  	      const_iterator
859  	      find(const key_type& __x) const
860  	      { return _M_t.find(__x); }
861  	
862  	#if __cplusplus > 201103L
863  	      template<typename _Kt>
864  		auto
865  		find(const _Kt& __x) const -> decltype(_M_t._M_find_tr(__x))
866  		{ return _M_t._M_find_tr(__x); }
867  	#endif
868  	      //@}
869  	
870  	      //@{
871  	      /**
872  	       *  @brief Finds the number of elements with given key.
873  	       *  @param  __x  Key of (key, value) pairs to be located.
874  	       *  @return Number of elements with specified key.
875  	       */
876  	      size_type
877  	      count(const key_type& __x) const
878  	      { return _M_t.count(__x); }
879  	
880  	#if __cplusplus > 201103L
881  	      template<typename _Kt>
882  		auto
883  		count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x))
884  		{ return _M_t._M_count_tr(__x); }
885  	#endif
886  	      //@}
887  	
888  	      //@{
889  	      /**
890  	       *  @brief Finds the beginning of a subsequence matching given key.
891  	       *  @param  __x  Key of (key, value) pair to be located.
892  	       *  @return  Iterator pointing to first element equal to or greater
893  	       *           than key, or end().
894  	       *
895  	       *  This function returns the first element of a subsequence of elements
896  	       *  that matches the given key.  If unsuccessful it returns an iterator
897  	       *  pointing to the first element that has a greater value than given key
898  	       *  or end() if no such element exists.
899  	       */
900  	      iterator
901  	      lower_bound(const key_type& __x)
902  	      { return _M_t.lower_bound(__x); }
903  	
904  	#if __cplusplus > 201103L
905  	      template<typename _Kt>
906  		auto
907  		lower_bound(const _Kt& __x)
908  		-> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
909  		{ return iterator(_M_t._M_lower_bound_tr(__x)); }
910  	#endif
911  	      //@}
912  	
913  	      //@{
914  	      /**
915  	       *  @brief Finds the beginning of a subsequence matching given key.
916  	       *  @param  __x  Key of (key, value) pair to be located.
917  	       *  @return  Read-only (constant) iterator pointing to first element
918  	       *           equal to or greater than key, or end().
919  	       *
920  	       *  This function returns the first element of a subsequence of
921  	       *  elements that matches the given key.  If unsuccessful the
922  	       *  iterator will point to the next greatest element or, if no
923  	       *  such greater element exists, to end().
924  	       */
925  	      const_iterator
926  	      lower_bound(const key_type& __x) const
927  	      { return _M_t.lower_bound(__x); }
928  	
929  	#if __cplusplus > 201103L
930  	      template<typename _Kt>
931  		auto
932  		lower_bound(const _Kt& __x) const
933  		-> decltype(const_iterator(_M_t._M_lower_bound_tr(__x)))
934  		{ return const_iterator(_M_t._M_lower_bound_tr(__x)); }
935  	#endif
936  	      //@}
937  	
938  	      //@{
939  	      /**
940  	       *  @brief Finds the end of a subsequence matching given key.
941  	       *  @param  __x  Key of (key, value) pair to be located.
942  	       *  @return Iterator pointing to the first element
943  	       *          greater than key, or end().
944  	       */
945  	      iterator
946  	      upper_bound(const key_type& __x)
947  	      { return _M_t.upper_bound(__x); }
948  	
949  	#if __cplusplus > 201103L
950  	      template<typename _Kt>
951  		auto
952  		upper_bound(const _Kt& __x)
953  		-> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
954  		{ return iterator(_M_t._M_upper_bound_tr(__x)); }
955  	#endif
956  	      //@}
957  	
958  	      //@{
959  	      /**
960  	       *  @brief Finds the end of a subsequence matching given key.
961  	       *  @param  __x  Key of (key, value) pair to be located.
962  	       *  @return  Read-only (constant) iterator pointing to first iterator
963  	       *           greater than key, or end().
964  	       */
965  	      const_iterator
966  	      upper_bound(const key_type& __x) const
967  	      { return _M_t.upper_bound(__x); }
968  	
969  	#if __cplusplus > 201103L
970  	      template<typename _Kt>
971  		auto
972  		upper_bound(const _Kt& __x) const
973  		-> decltype(const_iterator(_M_t._M_upper_bound_tr(__x)))
974  		{ return const_iterator(_M_t._M_upper_bound_tr(__x)); }
975  	#endif
976  	      //@}
977  	
978  	      //@{
979  	      /**
980  	       *  @brief Finds a subsequence matching given key.
981  	       *  @param  __x  Key of (key, value) pairs to be located.
982  	       *  @return  Pair of iterators that possibly points to the subsequence
983  	       *           matching given key.
984  	       *
985  	       *  This function is equivalent to
986  	       *  @code
987  	       *    std::make_pair(c.lower_bound(val),
988  	       *                   c.upper_bound(val))
989  	       *  @endcode
990  	       *  (but is faster than making the calls separately).
991  	       */
992  	      std::pair<iterator, iterator>
993  	      equal_range(const key_type& __x)
994  	      { return _M_t.equal_range(__x); }
995  	
996  	#if __cplusplus > 201103L
997  	      template<typename _Kt>
998  		auto
999  		equal_range(const _Kt& __x)
1000 		-> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)))
1001 		{ return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); }
1002 	#endif
1003 	      //@}
1004 	
1005 	      //@{
1006 	      /**
1007 	       *  @brief Finds a subsequence matching given key.
1008 	       *  @param  __x  Key of (key, value) pairs to be located.
1009 	       *  @return  Pair of read-only (constant) iterators that possibly points
1010 	       *           to the subsequence matching given key.
1011 	       *
1012 	       *  This function is equivalent to
1013 	       *  @code
1014 	       *    std::make_pair(c.lower_bound(val),
1015 	       *                   c.upper_bound(val))
1016 	       *  @endcode
1017 	       *  (but is faster than making the calls separately).
1018 	       */
1019 	      std::pair<const_iterator, const_iterator>
1020 	      equal_range(const key_type& __x) const
1021 	      { return _M_t.equal_range(__x); }
1022 	
1023 	#if __cplusplus > 201103L
1024 	      template<typename _Kt>
1025 		auto
1026 		equal_range(const _Kt& __x) const
1027 		-> decltype(pair<const_iterator, const_iterator>(
1028 		      _M_t._M_equal_range_tr(__x)))
1029 		{
1030 		  return pair<const_iterator, const_iterator>(
1031 		      _M_t._M_equal_range_tr(__x));
1032 		}
1033 	#endif
1034 	      //@}
1035 	
1036 	      template<typename _K1, typename _T1, typename _C1, typename _A1>
1037 		friend bool
1038 		operator==(const multimap<_K1, _T1, _C1, _A1>&,
1039 			   const multimap<_K1, _T1, _C1, _A1>&);
1040 	
1041 	      template<typename _K1, typename _T1, typename _C1, typename _A1>
1042 		friend bool
1043 		operator<(const multimap<_K1, _T1, _C1, _A1>&,
1044 			  const multimap<_K1, _T1, _C1, _A1>&);
1045 	  };
1046 	
1047 	  /**
1048 	   *  @brief  Multimap equality comparison.
1049 	   *  @param  __x  A %multimap.
1050 	   *  @param  __y  A %multimap of the same type as @a __x.
1051 	   *  @return  True iff the size and elements of the maps are equal.
1052 	   *
1053 	   *  This is an equivalence relation.  It is linear in the size of the
1054 	   *  multimaps.  Multimaps are considered equivalent if their sizes are equal,
1055 	   *  and if corresponding elements compare equal.
1056 	  */
1057 	  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1058 	    inline bool
1059 	    operator==(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1060 		       const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1061 	    { return __x._M_t == __y._M_t; }
1062 	
1063 	  /**
1064 	   *  @brief  Multimap ordering relation.
1065 	   *  @param  __x  A %multimap.
1066 	   *  @param  __y  A %multimap of the same type as @a __x.
1067 	   *  @return  True iff @a x is lexicographically less than @a y.
1068 	   *
1069 	   *  This is a total ordering relation.  It is linear in the size of the
1070 	   *  multimaps.  The elements must be comparable with @c <.
1071 	   *
1072 	   *  See std::lexicographical_compare() for how the determination is made.
1073 	  */
1074 	  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1075 	    inline bool
1076 	    operator<(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1077 		      const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1078 	    { return __x._M_t < __y._M_t; }
1079 	
1080 	  /// Based on operator==
1081 	  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1082 	    inline bool
1083 	    operator!=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1084 		       const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1085 	    { return !(__x == __y); }
1086 	
1087 	  /// Based on operator<
1088 	  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1089 	    inline bool
1090 	    operator>(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1091 		      const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1092 	    { return __y < __x; }
1093 	
1094 	  /// Based on operator<
1095 	  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1096 	    inline bool
1097 	    operator<=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1098 		       const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1099 	    { return !(__y < __x); }
1100 	
1101 	  /// Based on operator<
1102 	  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1103 	    inline bool
1104 	    operator>=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1105 		       const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1106 	    { return !(__x < __y); }
1107 	
1108 	  /// See std::multimap::swap().
1109 	  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1110 	    inline void
1111 	    swap(multimap<_Key, _Tp, _Compare, _Alloc>& __x,
1112 		 multimap<_Key, _Tp, _Compare, _Alloc>& __y)
1113 	    _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
1114 	    { __x.swap(__y); }
1115 	
1116 	_GLIBCXX_END_NAMESPACE_CONTAINER
1117 	
1118 	#if __cplusplus > 201402L
1119 	_GLIBCXX_BEGIN_NAMESPACE_VERSION
1120 	  // Allow std::multimap access to internals of compatible maps.
1121 	  template<typename _Key, typename _Val, typename _Cmp1, typename _Alloc,
1122 		   typename _Cmp2>
1123 	    struct
1124 	    _Rb_tree_merge_helper<_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp1, _Alloc>,
1125 				  _Cmp2>
1126 	    {
1127 	    private:
1128 	      friend class _GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp1, _Alloc>;
1129 	
1130 	      static auto&
1131 	      _S_get_tree(_GLIBCXX_STD_C::map<_Key, _Val, _Cmp2, _Alloc>& __map)
1132 	      { return __map._M_t; }
1133 	
1134 	      static auto&
1135 	      _S_get_tree(_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp2, _Alloc>& __map)
1136 	      { return __map._M_t; }
1137 	    };
1138 	_GLIBCXX_END_NAMESPACE_VERSION
1139 	#endif // C++17
1140 	
1141 	} // namespace std
1142 	
1143 	#endif /* _STL_MULTIMAP_H */
1144