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