libstdc++
stl_multimap.h
Go to the documentation of this file.
1 // Multimap implementation -*- C++ -*-
2 
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
4 // 2011 Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
10 // any later version.
11 
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
16 
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20 
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
25 
26 /*
27  *
28  * Copyright (c) 1994
29  * Hewlett-Packard Company
30  *
31  * Permission to use, copy, modify, distribute and sell this software
32  * and its documentation for any purpose is hereby granted without fee,
33  * provided that the above copyright notice appear in all copies and
34  * that both that copyright notice and this permission notice appear
35  * in supporting documentation. Hewlett-Packard Company makes no
36  * representations about the suitability of this software for any
37  * purpose. It is provided "as is" without express or implied warranty.
38  *
39  *
40  * Copyright (c) 1996,1997
41  * Silicon Graphics Computer Systems, Inc.
42  *
43  * Permission to use, copy, modify, distribute and sell this software
44  * and its documentation for any purpose is hereby granted without fee,
45  * provided that the above copyright notice appear in all copies and
46  * that both that copyright notice and this permission notice appear
47  * in supporting documentation. Silicon Graphics makes no
48  * representations about the suitability of this software for any
49  * purpose. It is provided "as is" without express or implied warranty.
50  */
51 
52 /** @file bits/stl_multimap.h
53  * This is an internal header file, included by other library headers.
54  * Do not attempt to use it directly. @headername{map}
55  */
56 
57 #ifndef _STL_MULTIMAP_H
58 #define _STL_MULTIMAP_H 1
59 
60 #include <bits/concept_check.h>
61 #include <initializer_list>
62 
63 namespace std _GLIBCXX_VISIBILITY(default)
64 {
65 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
66 
67  /**
68  * @brief A standard container made up of (key,value) pairs, which can be
69  * retrieved based on a key, in logarithmic time.
70  *
71  * @ingroup associative_containers
72  *
73  * Meets the requirements of a <a href="tables.html#65">container</a>, a
74  * <a href="tables.html#66">reversible container</a>, and an
75  * <a href="tables.html#69">associative container</a> (using equivalent
76  * keys). For a @c multimap<Key,T> the key_type is Key, the mapped_type
77  * is T, and the value_type is std::pair<const Key,T>.
78  *
79  * Multimaps support bidirectional iterators.
80  *
81  * The private tree data is declared exactly the same way for map and
82  * multimap; the distinction is made entirely in how the tree functions are
83  * called (*_unique versus *_equal, same as the standard).
84  */
85  template <typename _Key, typename _Tp,
86  typename _Compare = std::less<_Key>,
87  typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
88  class multimap
89  {
90  public:
91  typedef _Key key_type;
92  typedef _Tp mapped_type;
94  typedef _Compare key_compare;
95  typedef _Alloc allocator_type;
96 
97  private:
98  // concept requirements
99  typedef typename _Alloc::value_type _Alloc_value_type;
100  __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
101  __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
102  _BinaryFunctionConcept)
103  __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept)
104 
105  public:
106  class value_compare
107  : public std::binary_function<value_type, value_type, bool>
108  {
109  friend class multimap<_Key, _Tp, _Compare, _Alloc>;
110  protected:
111  _Compare comp;
112 
113  value_compare(_Compare __c)
114  : comp(__c) { }
115 
116  public:
117  bool operator()(const value_type& __x, const value_type& __y) const
118  { return comp(__x.first, __y.first); }
119  };
120 
121  private:
122  /// This turns a red-black tree into a [multi]map.
123  typedef typename _Alloc::template rebind<value_type>::other
124  _Pair_alloc_type;
125 
126  typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
127  key_compare, _Pair_alloc_type> _Rep_type;
128  /// The actual tree structure.
129  _Rep_type _M_t;
130 
131  public:
132  // many of these are specified differently in ISO, but the following are
133  // "functionally equivalent"
134  typedef typename _Pair_alloc_type::pointer pointer;
135  typedef typename _Pair_alloc_type::const_pointer const_pointer;
136  typedef typename _Pair_alloc_type::reference reference;
137  typedef typename _Pair_alloc_type::const_reference const_reference;
138  typedef typename _Rep_type::iterator iterator;
139  typedef typename _Rep_type::const_iterator const_iterator;
140  typedef typename _Rep_type::size_type size_type;
141  typedef typename _Rep_type::difference_type difference_type;
144 
145  // [23.3.2] construct/copy/destroy
146  // (get_allocator() is also listed in this section)
147  /**
148  * @brief Default constructor creates no elements.
149  */
151  : _M_t() { }
152 
153  /**
154  * @brief Creates a %multimap with no elements.
155  * @param comp A comparison object.
156  * @param a An allocator object.
157  */
158  explicit
159  multimap(const _Compare& __comp,
160  const allocator_type& __a = allocator_type())
161  : _M_t(__comp, __a) { }
162 
163  /**
164  * @brief %Multimap copy constructor.
165  * @param x A %multimap of identical element and allocator types.
166  *
167  * The newly-created %multimap uses a copy of the allocation object
168  * used by @a x.
169  */
170  multimap(const multimap& __x)
171  : _M_t(__x._M_t) { }
172 
173 #ifdef __GXX_EXPERIMENTAL_CXX0X__
174  /**
175  * @brief %Multimap move constructor.
176  * @param x A %multimap of identical element and allocator types.
177  *
178  * The newly-created %multimap contains the exact contents of @a x.
179  * The contents of @a x are a valid, but unspecified %multimap.
180  */
182  : _M_t(std::move(__x._M_t)) { }
183 
184  /**
185  * @brief Builds a %multimap from an initializer_list.
186  * @param l An initializer_list.
187  * @param comp A comparison functor.
188  * @param a An allocator object.
189  *
190  * Create a %multimap consisting of copies of the elements from
191  * the initializer_list. This is linear in N if the list is already
192  * sorted, and NlogN otherwise (where N is @a __l.size()).
193  */
195  const _Compare& __comp = _Compare(),
196  const allocator_type& __a = allocator_type())
197  : _M_t(__comp, __a)
198  { _M_t._M_insert_equal(__l.begin(), __l.end()); }
199 #endif
200 
201  /**
202  * @brief Builds a %multimap from a range.
203  * @param first An input iterator.
204  * @param last An input iterator.
205  *
206  * Create a %multimap consisting of copies of the elements from
207  * [first,last). This is linear in N if the range is already sorted,
208  * and NlogN otherwise (where N is distance(first,last)).
209  */
210  template<typename _InputIterator>
211  multimap(_InputIterator __first, _InputIterator __last)
212  : _M_t()
213  { _M_t._M_insert_equal(__first, __last); }
214 
215  /**
216  * @brief Builds a %multimap from a range.
217  * @param first An input iterator.
218  * @param last An input iterator.
219  * @param comp A comparison functor.
220  * @param a An allocator object.
221  *
222  * Create a %multimap consisting of copies of the elements from
223  * [first,last). This is linear in N if the range is already sorted,
224  * and NlogN otherwise (where N is distance(first,last)).
225  */
226  template<typename _InputIterator>
227  multimap(_InputIterator __first, _InputIterator __last,
228  const _Compare& __comp,
229  const allocator_type& __a = allocator_type())
230  : _M_t(__comp, __a)
231  { _M_t._M_insert_equal(__first, __last); }
232 
233  // FIXME There is no dtor declared, but we should have something generated
234  // by Doxygen. I don't know what tags to add to this paragraph to make
235  // that happen:
236  /**
237  * The dtor only erases the elements, and note that if the elements
238  * themselves are pointers, the pointed-to memory is not touched in any
239  * way. Managing the pointer is the user's responsibility.
240  */
241 
242  /**
243  * @brief %Multimap assignment operator.
244  * @param x A %multimap of identical element and allocator types.
245  *
246  * All the elements of @a x are copied, but unlike the copy constructor,
247  * the allocator object is not copied.
248  */
249  multimap&
250  operator=(const multimap& __x)
251  {
252  _M_t = __x._M_t;
253  return *this;
254  }
255 
256 #ifdef __GXX_EXPERIMENTAL_CXX0X__
257  /**
258  * @brief %Multimap move assignment operator.
259  * @param x A %multimap of identical element and allocator types.
260  *
261  * The contents of @a x are moved into this multimap (without copying).
262  * @a x is a valid, but unspecified multimap.
263  */
264  multimap&
266  {
267  // NB: DR 1204.
268  // NB: DR 675.
269  this->clear();
270  this->swap(__x);
271  return *this;
272  }
273 
274  /**
275  * @brief %Multimap list assignment operator.
276  * @param l An initializer_list.
277  *
278  * This function fills a %multimap with copies of the elements
279  * in the initializer list @a l.
280  *
281  * Note that the assignment completely changes the %multimap and
282  * that the resulting %multimap's size is the same as the number
283  * of elements assigned. Old data may be lost.
284  */
285  multimap&
287  {
288  this->clear();
289  this->insert(__l.begin(), __l.end());
290  return *this;
291  }
292 #endif
293 
294  /// Get a copy of the memory allocation object.
295  allocator_type
297  { return _M_t.get_allocator(); }
298 
299  // iterators
300  /**
301  * Returns a read/write iterator that points to the first pair in the
302  * %multimap. Iteration is done in ascending order according to the
303  * keys.
304  */
305  iterator
307  { return _M_t.begin(); }
308 
309  /**
310  * Returns a read-only (constant) iterator that points to the first pair
311  * in the %multimap. Iteration is done in ascending order according to
312  * the keys.
313  */
314  const_iterator
315  begin() const
316  { return _M_t.begin(); }
317 
318  /**
319  * Returns a read/write iterator that points one past the last pair in
320  * the %multimap. Iteration is done in ascending order according to the
321  * keys.
322  */
323  iterator
324  end()
325  { return _M_t.end(); }
326 
327  /**
328  * Returns a read-only (constant) iterator that points one past the last
329  * pair in the %multimap. Iteration is done in ascending order according
330  * to the keys.
331  */
332  const_iterator
333  end() const
334  { return _M_t.end(); }
335 
336  /**
337  * Returns a read/write reverse iterator that points to the last pair in
338  * the %multimap. Iteration is done in descending order according to the
339  * keys.
340  */
343  { return _M_t.rbegin(); }
344 
345  /**
346  * Returns a read-only (constant) reverse iterator that points to the
347  * last pair in the %multimap. Iteration is done in descending order
348  * according to the keys.
349  */
350  const_reverse_iterator
351  rbegin() const
352  { return _M_t.rbegin(); }
353 
354  /**
355  * Returns a read/write reverse iterator that points to one before the
356  * first pair in the %multimap. Iteration is done in descending order
357  * according to the keys.
358  */
361  { return _M_t.rend(); }
362 
363  /**
364  * Returns a read-only (constant) reverse iterator that points to one
365  * before the first pair in the %multimap. Iteration is done in
366  * descending order according to the keys.
367  */
368  const_reverse_iterator
369  rend() const
370  { return _M_t.rend(); }
371 
372 #ifdef __GXX_EXPERIMENTAL_CXX0X__
373  /**
374  * Returns a read-only (constant) iterator that points to the first pair
375  * in the %multimap. Iteration is done in ascending order according to
376  * the keys.
377  */
378  const_iterator
379  cbegin() const
380  { return _M_t.begin(); }
381 
382  /**
383  * Returns a read-only (constant) iterator that points one past the last
384  * pair in the %multimap. Iteration is done in ascending order according
385  * to the keys.
386  */
387  const_iterator
388  cend() const
389  { return _M_t.end(); }
390 
391  /**
392  * Returns a read-only (constant) reverse iterator that points to the
393  * last pair in the %multimap. Iteration is done in descending order
394  * according to the keys.
395  */
396  const_reverse_iterator
397  crbegin() const
398  { return _M_t.rbegin(); }
399 
400  /**
401  * Returns a read-only (constant) reverse iterator that points to one
402  * before the first pair in the %multimap. Iteration is done in
403  * descending order according to the keys.
404  */
405  const_reverse_iterator
406  crend() const
407  { return _M_t.rend(); }
408 #endif
409 
410  // capacity
411  /** Returns true if the %multimap is empty. */
412  bool
413  empty() const
414  { return _M_t.empty(); }
415 
416  /** Returns the size of the %multimap. */
417  size_type
418  size() const
419  { return _M_t.size(); }
420 
421  /** Returns the maximum size of the %multimap. */
422  size_type
423  max_size() const
424  { return _M_t.max_size(); }
425 
426  // modifiers
427  /**
428  * @brief Inserts a std::pair into the %multimap.
429  * @param x Pair to be inserted (see std::make_pair for easy creation
430  * of pairs).
431  * @return An iterator that points to the inserted (key,value) pair.
432  *
433  * This function inserts a (key, value) pair into the %multimap.
434  * Contrary to a std::map the %multimap does not rely on unique keys and
435  * thus multiple pairs with the same key can be inserted.
436  *
437  * Insertion requires logarithmic time.
438  */
439  iterator
440  insert(const value_type& __x)
441  { return _M_t._M_insert_equal(__x); }
442 
443 #ifdef __GXX_EXPERIMENTAL_CXX0X__
444  template<typename _Pair, typename = typename
446  value_type>::value>::type>
447  iterator
448  insert(_Pair&& __x)
449  { return _M_t._M_insert_equal(std::forward<_Pair>(__x)); }
450 #endif
451 
452  /**
453  * @brief Inserts a std::pair into the %multimap.
454  * @param position An iterator that serves as a hint as to where the
455  * pair should be inserted.
456  * @param x Pair to be inserted (see std::make_pair for easy creation
457  * of pairs).
458  * @return An iterator that points to the inserted (key,value) pair.
459  *
460  * This function inserts a (key, value) pair into the %multimap.
461  * Contrary to a std::map the %multimap does not rely on unique keys and
462  * thus multiple pairs with the same key can be inserted.
463  * Note that the first parameter is only a hint and can potentially
464  * improve the performance of the insertion process. A bad hint would
465  * cause no gains in efficiency.
466  *
467  * For more on @a hinting, see:
468  * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
469  *
470  * Insertion requires logarithmic time (if the hint is not taken).
471  */
472  iterator
473 #ifdef __GXX_EXPERIMENTAL_CXX0X__
474  insert(const_iterator __position, const value_type& __x)
475 #else
476  insert(iterator __position, const value_type& __x)
477 #endif
478  { return _M_t._M_insert_equal_(__position, __x); }
479 
480 #ifdef __GXX_EXPERIMENTAL_CXX0X__
481  template<typename _Pair, typename = typename
483  value_type>::value>::type>
484  iterator
485  insert(const_iterator __position, _Pair&& __x)
486  { return _M_t._M_insert_equal_(__position,
487  std::forward<_Pair>(__x)); }
488 #endif
489 
490  /**
491  * @brief A template function that attempts to insert a range
492  * of elements.
493  * @param first Iterator pointing to the start of the range to be
494  * inserted.
495  * @param last Iterator pointing to the end of the range.
496  *
497  * Complexity similar to that of the range constructor.
498  */
499  template<typename _InputIterator>
500  void
501  insert(_InputIterator __first, _InputIterator __last)
502  { _M_t._M_insert_equal(__first, __last); }
503 
504 #ifdef __GXX_EXPERIMENTAL_CXX0X__
505  /**
506  * @brief Attempts to insert a list of std::pairs into the %multimap.
507  * @param list A std::initializer_list<value_type> of pairs to be
508  * inserted.
509  *
510  * Complexity similar to that of the range constructor.
511  */
512  void
514  { this->insert(__l.begin(), __l.end()); }
515 #endif
516 
517 #ifdef __GXX_EXPERIMENTAL_CXX0X__
518  // _GLIBCXX_RESOLVE_LIB_DEFECTS
519  // DR 130. Associative erase should return an iterator.
520  /**
521  * @brief Erases an element from a %multimap.
522  * @param position An iterator pointing to the element to be erased.
523  * @return An iterator pointing to the element immediately following
524  * @a position prior to the element being erased. If no such
525  * element exists, end() is returned.
526  *
527  * This function erases an element, pointed to by the given iterator,
528  * from a %multimap. Note that this function only erases the element,
529  * and that if the element is itself a pointer, the pointed-to memory is
530  * not touched in any way. Managing the pointer is the user's
531  * responsibility.
532  */
533  iterator
534  erase(const_iterator __position)
535  { return _M_t.erase(__position); }
536 
537  // LWG 2059.
538  iterator
539  erase(iterator __position)
540  { return _M_t.erase(__position); }
541 #else
542  /**
543  * @brief Erases an element from a %multimap.
544  * @param position An iterator pointing to the element to be erased.
545  *
546  * This function erases an element, pointed to by the given iterator,
547  * from a %multimap. Note that this function only erases the element,
548  * and that if the element is itself a pointer, the pointed-to memory is
549  * not touched in any way. Managing the pointer is the user's
550  * responsibility.
551  */
552  void
553  erase(iterator __position)
554  { _M_t.erase(__position); }
555 #endif
556 
557  /**
558  * @brief Erases elements according to the provided key.
559  * @param x Key of element to be erased.
560  * @return The number of elements erased.
561  *
562  * This function erases all elements located by the given key from a
563  * %multimap.
564  * Note that this function only erases the element, and that if
565  * the element is itself a pointer, the pointed-to memory is not touched
566  * in any way. Managing the pointer is the user's responsibility.
567  */
568  size_type
569  erase(const key_type& __x)
570  { return _M_t.erase(__x); }
571 
572 #ifdef __GXX_EXPERIMENTAL_CXX0X__
573  // _GLIBCXX_RESOLVE_LIB_DEFECTS
574  // DR 130. Associative erase should return an iterator.
575  /**
576  * @brief Erases a [first,last) range of elements from a %multimap.
577  * @param first Iterator pointing to the start of the range to be
578  * erased.
579  * @param last Iterator pointing to the end of the range to be erased.
580  * @return The iterator @a last.
581  *
582  * This function erases a sequence of elements from a %multimap.
583  * Note that this function only erases the elements, and that if
584  * the elements themselves are pointers, the pointed-to memory is not
585  * touched in any way. Managing the pointer is the user's
586  * responsibility.
587  */
588  iterator
589  erase(const_iterator __first, const_iterator __last)
590  { return _M_t.erase(__first, __last); }
591 #else
592  // _GLIBCXX_RESOLVE_LIB_DEFECTS
593  // DR 130. Associative erase should return an iterator.
594  /**
595  * @brief Erases a [first,last) range of elements from a %multimap.
596  * @param first Iterator pointing to the start of the range to be
597  * erased.
598  * @param last Iterator pointing to the end of the range to be erased.
599  *
600  * This function erases a sequence of elements from a %multimap.
601  * Note that this function only erases the elements, and that if
602  * the elements themselves are pointers, the pointed-to memory is not
603  * touched in any way. Managing the pointer is the user's
604  * responsibility.
605  */
606  void
607  erase(iterator __first, iterator __last)
608  { _M_t.erase(__first, __last); }
609 #endif
610 
611  /**
612  * @brief Swaps data with another %multimap.
613  * @param x A %multimap of the same element and allocator types.
614  *
615  * This exchanges the elements between two multimaps in constant time.
616  * (It is only swapping a pointer, an integer, and an instance of
617  * the @c Compare type (which itself is often stateless and empty), so it
618  * should be quite fast.)
619  * Note that the global std::swap() function is specialized such that
620  * std::swap(m1,m2) will feed to this function.
621  */
622  void
624  { _M_t.swap(__x._M_t); }
625 
626  /**
627  * Erases all elements in a %multimap. Note that this function only
628  * erases the elements, and that if the elements themselves are pointers,
629  * the pointed-to memory is not touched in any way. Managing the pointer
630  * is the user's responsibility.
631  */
632  void
634  { _M_t.clear(); }
635 
636  // observers
637  /**
638  * Returns the key comparison object out of which the %multimap
639  * was constructed.
640  */
641  key_compare
642  key_comp() const
643  { return _M_t.key_comp(); }
644 
645  /**
646  * Returns a value comparison object, built from the key comparison
647  * object out of which the %multimap was constructed.
648  */
649  value_compare
650  value_comp() const
651  { return value_compare(_M_t.key_comp()); }
652 
653  // multimap operations
654  /**
655  * @brief Tries to locate an element in a %multimap.
656  * @param x Key of (key, value) pair to be located.
657  * @return Iterator pointing to sought-after element,
658  * or end() if not found.
659  *
660  * This function takes a key and tries to locate the element with which
661  * the key matches. If successful the function returns an iterator
662  * pointing to the sought after %pair. If unsuccessful it returns the
663  * past-the-end ( @c end() ) iterator.
664  */
665  iterator
666  find(const key_type& __x)
667  { return _M_t.find(__x); }
668 
669  /**
670  * @brief Tries to locate an element in a %multimap.
671  * @param x Key of (key, value) pair to be located.
672  * @return Read-only (constant) iterator pointing to sought-after
673  * element, or end() if not found.
674  *
675  * This function takes a key and tries to locate the element with which
676  * the key matches. If successful the function returns a constant
677  * iterator pointing to the sought after %pair. If unsuccessful it
678  * returns the past-the-end ( @c end() ) iterator.
679  */
680  const_iterator
681  find(const key_type& __x) const
682  { return _M_t.find(__x); }
683 
684  /**
685  * @brief Finds the number of elements with given key.
686  * @param x Key of (key, value) pairs to be located.
687  * @return Number of elements with specified key.
688  */
689  size_type
690  count(const key_type& __x) const
691  { return _M_t.count(__x); }
692 
693  /**
694  * @brief Finds the beginning of a subsequence matching given key.
695  * @param x Key of (key, value) pair to be located.
696  * @return Iterator pointing to first element equal to or greater
697  * than key, or end().
698  *
699  * This function returns the first element of a subsequence of elements
700  * that matches the given key. If unsuccessful it returns an iterator
701  * pointing to the first element that has a greater value than given key
702  * or end() if no such element exists.
703  */
704  iterator
705  lower_bound(const key_type& __x)
706  { return _M_t.lower_bound(__x); }
707 
708  /**
709  * @brief Finds the beginning of a subsequence matching given key.
710  * @param x Key of (key, value) pair to be located.
711  * @return Read-only (constant) iterator pointing to first element
712  * equal to or greater than key, or end().
713  *
714  * This function returns the first element of a subsequence of elements
715  * that matches the given key. If unsuccessful the iterator will point
716  * to the next greatest element or, if no such greater element exists, to
717  * end().
718  */
719  const_iterator
720  lower_bound(const key_type& __x) const
721  { return _M_t.lower_bound(__x); }
722 
723  /**
724  * @brief Finds the end of a subsequence matching given key.
725  * @param x Key of (key, value) pair to be located.
726  * @return Iterator pointing to the first element
727  * greater than key, or end().
728  */
729  iterator
730  upper_bound(const key_type& __x)
731  { return _M_t.upper_bound(__x); }
732 
733  /**
734  * @brief Finds the end of a subsequence matching given key.
735  * @param x Key of (key, value) pair to be located.
736  * @return Read-only (constant) iterator pointing to first iterator
737  * greater than key, or end().
738  */
739  const_iterator
740  upper_bound(const key_type& __x) const
741  { return _M_t.upper_bound(__x); }
742 
743  /**
744  * @brief Finds a subsequence matching given key.
745  * @param x Key of (key, value) pairs to be located.
746  * @return Pair of iterators that possibly points to the subsequence
747  * matching given key.
748  *
749  * This function is equivalent to
750  * @code
751  * std::make_pair(c.lower_bound(val),
752  * c.upper_bound(val))
753  * @endcode
754  * (but is faster than making the calls separately).
755  */
757  equal_range(const key_type& __x)
758  { return _M_t.equal_range(__x); }
759 
760  /**
761  * @brief Finds a subsequence matching given key.
762  * @param x Key of (key, value) pairs to be located.
763  * @return Pair of read-only (constant) iterators that possibly points
764  * to the subsequence matching given key.
765  *
766  * This function is equivalent to
767  * @code
768  * std::make_pair(c.lower_bound(val),
769  * c.upper_bound(val))
770  * @endcode
771  * (but is faster than making the calls separately).
772  */
774  equal_range(const key_type& __x) const
775  { return _M_t.equal_range(__x); }
776 
777  template<typename _K1, typename _T1, typename _C1, typename _A1>
778  friend bool
781 
782  template<typename _K1, typename _T1, typename _C1, typename _A1>
783  friend bool
784  operator<(const multimap<_K1, _T1, _C1, _A1>&,
786  };
787 
788  /**
789  * @brief Multimap equality comparison.
790  * @param x A %multimap.
791  * @param y A %multimap of the same type as @a x.
792  * @return True iff the size and elements of the maps are equal.
793  *
794  * This is an equivalence relation. It is linear in the size of the
795  * multimaps. Multimaps are considered equivalent if their sizes are equal,
796  * and if corresponding elements compare equal.
797  */
798  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
799  inline bool
802  { return __x._M_t == __y._M_t; }
803 
804  /**
805  * @brief Multimap ordering relation.
806  * @param x A %multimap.
807  * @param y A %multimap of the same type as @a x.
808  * @return True iff @a x is lexicographically less than @a y.
809  *
810  * This is a total ordering relation. It is linear in the size of the
811  * multimaps. The elements must be comparable with @c <.
812  *
813  * See std::lexicographical_compare() for how the determination is made.
814  */
815  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
816  inline bool
817  operator<(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
819  { return __x._M_t < __y._M_t; }
820 
821  /// Based on operator==
822  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
823  inline bool
826  { return !(__x == __y); }
827 
828  /// Based on operator<
829  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
830  inline bool
833  { return __y < __x; }
834 
835  /// Based on operator<
836  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
837  inline bool
838  operator<=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
840  { return !(__y < __x); }
841 
842  /// Based on operator<
843  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
844  inline bool
847  { return !(__x < __y); }
848 
849  /// See std::multimap::swap().
850  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
851  inline void
854  { __x.swap(__y); }
855 
856 _GLIBCXX_END_NAMESPACE_CONTAINER
857 } // namespace std
858 
859 #endif /* _STL_MULTIMAP_H */
size_type max_size() const
Definition: stl_multimap.h:423
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:87
multimap(_InputIterator __first, _InputIterator __last)
Builds a multimap from a range.
Definition: stl_multimap.h:211
allocator_type get_allocator() const
Get a copy of the memory allocation object.
Definition: stl_multimap.h:296
_T1 first
second_type is the second bound type
Definition: stl_pair.h:92
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:194
reverse_iterator rend()
Definition: stl_multimap.h:360
const_reverse_iterator rend() const
Definition: stl_multimap.h:369
void swap(multimap &__x)
Swaps data with another multimap.
Definition: stl_multimap.h:623
multimap & operator=(multimap &&__x)
Multimap move assignment operator.
Definition: stl_multimap.h:265
const_reverse_iterator crend() const
Definition: stl_multimap.h:406
const_iterator end() const
Definition: stl_multimap.h:333
bool operator==(const multimap< _Key, _Tp, _Compare, _Alloc > &__x, const multimap< _Key, _Tp, _Compare, _Alloc > &__y)
Multimap equality comparison.
Definition: stl_multimap.h:800
size_type count(const key_type &__x) const
Finds the number of elements with given key.
Definition: stl_multimap.h:690
multimap & operator=(initializer_list< value_type > __l)
Multimap list assignment operator.
Definition: stl_multimap.h:286
void swap(multimap< _Key, _Tp, _Compare, _Alloc > &__x, multimap< _Key, _Tp, _Compare, _Alloc > &__y)
See std::multimap::swap().
Definition: stl_multimap.h:852
bool operator>(const multimap< _Key, _Tp, _Compare, _Alloc > &__x, const multimap< _Key, _Tp, _Compare, _Alloc > &__y)
Based on operator<.
Definition: stl_multimap.h:831
const_iterator begin() const
Definition: stl_multimap.h:315
const_reverse_iterator rbegin() const
Definition: stl_multimap.h:351
multimap(const multimap &__x)
Multimap copy constructor.
Definition: stl_multimap.h:170
multimap(const _Compare &__comp, const allocator_type &__a=allocator_type())
Creates a multimap with no elements.
Definition: stl_multimap.h:159
void insert(_InputIterator __first, _InputIterator __last)
A template function that attempts to insert a range of elements.
Definition: stl_multimap.h:501
const_iterator cend() const
Definition: stl_multimap.h:388
iterator lower_bound(const key_type &__x)
Finds the beginning of a subsequence matching given key.
Definition: stl_multimap.h:705
iterator erase(const_iterator __first, const_iterator __last)
Erases a [first,last) range of elements from a multimap.
Definition: stl_multimap.h:589
multimap & operator=(const multimap &__x)
Multimap assignment operator.
Definition: stl_multimap.h:250
key_compare key_comp() const
Definition: stl_multimap.h:642
bool operator>=(const multimap< _Key, _Tp, _Compare, _Alloc > &__x, const multimap< _Key, _Tp, _Compare, _Alloc > &__y)
Based on operator<.
Definition: stl_multimap.h:845
iterator insert(const value_type &__x)
Inserts a std::pair into the multimap.
Definition: stl_multimap.h:440
reverse_iterator rbegin()
Definition: stl_multimap.h:342
initializer_list
multimap()
Default constructor creates no elements.
Definition: stl_multimap.h:150
const_iterator cbegin() const
Definition: stl_multimap.h:379
const_iterator lower_bound(const key_type &__x) const
Finds the beginning of a subsequence matching given key.
Definition: stl_multimap.h:720
value_compare value_comp() const
Definition: stl_multimap.h:650
bool empty() const
Definition: stl_multimap.h:413
iterator upper_bound(const key_type &__x)
Finds the end of a subsequence matching given key.
Definition: stl_multimap.h:730
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
Definition: stl_multimap.h:757
void insert(initializer_list< value_type > __l)
Attempts to insert a list of std::pairs into the multimap.
Definition: stl_multimap.h:513
One of the comparison functors.
Definition: stl_function.h:232
iterator begin()
Definition: stl_multimap.h:306
const_iterator upper_bound(const key_type &__x) const
Finds the end of a subsequence matching given key.
Definition: stl_multimap.h:740
iterator insert(const_iterator __position, const value_type &__x)
Inserts a std::pair into the multimap.
Definition: stl_multimap.h:474
const_iterator find(const key_type &__x) const
Tries to locate an element in a multimap.
Definition: stl_multimap.h:681
iterator end()
Definition: stl_multimap.h:324
enable_if
Definition: type_traits:836
multimap(multimap &&__x)
Multimap move constructor.
Definition: stl_multimap.h:181
size_type size() const
Definition: stl_multimap.h:418
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
Definition: stl_multimap.h:774
size_type erase(const key_type &__x)
Erases elements according to the provided key.
Definition: stl_multimap.h:569
bool operator!=(const multimap< _Key, _Tp, _Compare, _Alloc > &__x, const multimap< _Key, _Tp, _Compare, _Alloc > &__y)
Based on operator==.
Definition: stl_multimap.h:824
multimap(_InputIterator __first, _InputIterator __last, const _Compare &__comp, const allocator_type &__a=allocator_type())
Builds a multimap from a range.
Definition: stl_multimap.h:227
Common iterator class.
const_reverse_iterator crbegin() const
Definition: stl_multimap.h:397
The standard allocator, as per [20.4].Further details: http://gcc.gnu.org/onlinedocs/libstdc++/manual...
Definition: allocator.h:66
iterator erase(const_iterator __position)
Erases an element from a multimap.
Definition: stl_multimap.h:534
iterator find(const key_type &__x)
Tries to locate an element in a multimap.
Definition: stl_multimap.h:666
is_convertible
Definition: type_traits:789
A standard container made up of (key,value) pairs, which can be retrieved based on a key...
Definition: stl_multimap.h:88