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