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