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