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