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