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