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