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