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