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