1 // Multiset implementation -*- C++ -*-
2 
3 // Copyright (C) 2001-2016 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 
_GLIBCXX_VISIBILITY(default)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 __gnu_cxx::__alloc_traits<_Alloc>::template
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 
119       typedef __gnu_cxx::__alloc_traits<_Key_alloc_type> _Alloc_traits;
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;
131       typedef typename _Rep_type::const_reverse_iterator    reverse_iterator;
132       typedef typename _Rep_type::const_reverse_iterator const_reverse_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        */
140       multiset()
141       _GLIBCXX_NOEXCEPT_IF(
142 	  is_nothrow_default_constructible<allocator_type>::value
143 	  && is_nothrow_default_constructible<key_compare>::value)
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        */
206       multiset(multiset&& __x)
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
408       swap(multiset& __x)
409       _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
410       { _M_t.swap(__x._M_t); }
411 
412       // insert/erase
413 #if __cplusplus >= 201103L
414       /**
415        *  @brief Builds and inserts an element into the %multiset.
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        *  Insertion requires logarithmic time.
425        */
426       template<typename... _Args>
427 	iterator
428 	emplace(_Args&&... __args)
429 	{ return _M_t._M_emplace_equal(std::forward<_Args>(__args)...); }
430 
431       /**
432        *  @brief Builds and inserts an element into the %multiset.
433        *  @param  __pos  An iterator that serves as a hint as to where the
434        *                element should be inserted.
435        *  @param  __args  Arguments used to generate the element instance to be
436        *                 inserted.
437        *  @return An iterator that points to the inserted element.
438        *
439        *  This function inserts an element into the %multiset.  Contrary
440        *  to a std::set the %multiset does not rely on unique keys and thus
441        *  multiple copies of the same element can be inserted.
442        *
443        *  Note that the first parameter is only a hint and can potentially
444        *  improve the performance of the insertion process.  A bad hint would
445        *  cause no gains in efficiency.
446        *
447        *  See https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
448        *  for more on @a hinting.
449        *
450        *  Insertion requires logarithmic time (if the hint is not taken).
451        */
452       template<typename... _Args>
453 	iterator
454 	emplace_hint(const_iterator __pos, _Args&&... __args)
455 	{
456 	  return _M_t._M_emplace_hint_equal(__pos,
457 					    std::forward<_Args>(__args)...);
458 	}
459 #endif
460 
461       /**
462        *  @brief Inserts an element into the %multiset.
463        *  @param  __x  Element to be inserted.
464        *  @return An iterator that points to the inserted element.
465        *
466        *  This function inserts an element into the %multiset.  Contrary
467        *  to a std::set the %multiset does not rely on unique keys and thus
468        *  multiple copies of the same element can be inserted.
469        *
470        *  Insertion requires logarithmic time.
471        */
472       iterator
473       insert(const value_type& __x)
474       { return _M_t._M_insert_equal(__x); }
475 
476 #if __cplusplus >= 201103L
477       iterator
478       insert(value_type&& __x)
479       { return _M_t._M_insert_equal(std::move(__x)); }
480 #endif
481 
482       /**
483        *  @brief Inserts an element into the %multiset.
484        *  @param  __position  An iterator that serves as a hint as to where the
485        *                    element should be inserted.
486        *  @param  __x  Element to be inserted.
487        *  @return An iterator that points to the inserted element.
488        *
489        *  This function inserts an element into the %multiset.  Contrary
490        *  to a std::set the %multiset does not rely on unique keys and thus
491        *  multiple copies of the same element can be inserted.
492        *
493        *  Note that the first parameter is only a hint and can potentially
494        *  improve the performance of the insertion process.  A bad hint would
495        *  cause no gains in efficiency.
496        *
497        *  See https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
498        *  for more on @a hinting.
499        *
500        *  Insertion requires logarithmic time (if the hint is not taken).
501        */
502       iterator
503       insert(const_iterator __position, const value_type& __x)
504       { return _M_t._M_insert_equal_(__position, __x); }
505 
506 #if __cplusplus >= 201103L
507       iterator
508       insert(const_iterator __position, value_type&& __x)
509       { return _M_t._M_insert_equal_(__position, std::move(__x)); }
510 #endif
511 
512       /**
513        *  @brief A template function that tries to insert a range of elements.
514        *  @param  __first  Iterator pointing to the start of the range to be
515        *                   inserted.
516        *  @param  __last  Iterator pointing to the end of the range.
517        *
518        *  Complexity similar to that of the range constructor.
519        */
520       template<typename _InputIterator>
521         void
522         insert(_InputIterator __first, _InputIterator __last)
523         { _M_t._M_insert_equal(__first, __last); }
524 
525 #if __cplusplus >= 201103L
526       /**
527        *  @brief Attempts to insert a list of elements into the %multiset.
528        *  @param  __l  A std::initializer_list<value_type> of elements
529        *               to be inserted.
530        *
531        *  Complexity similar to that of the range constructor.
532        */
533       void
534       insert(initializer_list<value_type> __l)
535       { this->insert(__l.begin(), __l.end()); }
536 #endif
537 
538 #if __cplusplus >= 201103L
539       // _GLIBCXX_RESOLVE_LIB_DEFECTS
540       // DR 130. Associative erase should return an iterator.
541       /**
542        *  @brief Erases an element from a %multiset.
543        *  @param  __position  An iterator pointing to the element to be erased.
544        *  @return An iterator pointing to the element immediately following
545        *          @a position prior to the element being erased. If no such
546        *          element exists, end() is returned.
547        *
548        *  This function erases an element, pointed to by the given iterator,
549        *  from a %multiset.  Note that this function only erases the element,
550        *  and that if the element is itself a pointer, the pointed-to memory is
551        *  not touched in any way.  Managing the pointer is the user's
552        *  responsibility.
553        */
554       _GLIBCXX_ABI_TAG_CXX11
555       iterator
556       erase(const_iterator __position)
557       { return _M_t.erase(__position); }
558 #else
559       /**
560        *  @brief Erases an element from a %multiset.
561        *  @param  __position  An iterator pointing to the element to be erased.
562        *
563        *  This function erases an element, pointed to by the given iterator,
564        *  from a %multiset.  Note that this function only erases the element,
565        *  and that if the element is itself a pointer, the pointed-to memory is
566        *  not touched in any way.  Managing the pointer is the user's
567        *  responsibility.
568        */
569       void
570       erase(iterator __position)
571       { _M_t.erase(__position); }
572 #endif
573 
574       /**
575        *  @brief Erases elements according to the provided key.
576        *  @param  __x  Key of element to be erased.
577        *  @return  The number of elements erased.
578        *
579        *  This function erases all elements located by the given key from a
580        *  %multiset.
581        *  Note that this function only erases the element, and that if
582        *  the element is itself a pointer, the pointed-to memory is not touched
583        *  in any way.  Managing the pointer is the user's responsibility.
584        */
585       size_type
586       erase(const key_type& __x)
587       { return _M_t.erase(__x); }
588 
589 #if __cplusplus >= 201103L
590       // _GLIBCXX_RESOLVE_LIB_DEFECTS
591       // DR 130. Associative erase should return an iterator.
592       /**
593        *  @brief Erases a [first,last) range of elements from a %multiset.
594        *  @param  __first  Iterator pointing to the start of the range to be
595        *                   erased.
596        *  @param __last Iterator pointing to the end of the range to
597        *                be erased.
598        *  @return The iterator @a last.
599        *
600        *  This function erases a sequence of elements from a %multiset.
601        *  Note that this function only erases the elements, and that if
602        *  the elements themselves are pointers, the pointed-to memory is not
603        *  touched in any way.  Managing the pointer is the user's
604        *  responsibility.
605        */
606       _GLIBCXX_ABI_TAG_CXX11
607       iterator
608       erase(const_iterator __first, const_iterator __last)
609       { return _M_t.erase(__first, __last); }
610 #else
611       /**
612        *  @brief Erases a [first,last) range of elements from a %multiset.
613        *  @param  first  Iterator pointing to the start of the range to be
614        *                 erased.
615        *  @param  last  Iterator pointing to the end of the range to be erased.
616        *
617        *  This function erases a sequence of elements from a %multiset.
618        *  Note that this function only erases the elements, and that if
619        *  the elements themselves are pointers, the pointed-to memory is not
620        *  touched in any way.  Managing the pointer is the user's
621        *  responsibility.
622        */
623       void
624       erase(iterator __first, iterator __last)
625       { _M_t.erase(__first, __last); }
626 #endif
627 
628       /**
629        *  Erases all elements in a %multiset.  Note that this function only
630        *  erases the elements, and that if the elements themselves are pointers,
631        *  the pointed-to memory is not touched in any way.  Managing the pointer
632        *  is the user's responsibility.
633        */
634       void
635       clear() _GLIBCXX_NOEXCEPT
636       { _M_t.clear(); }
637 
638       // multiset operations:
639 
640       //@{
641       /**
642        *  @brief Finds the number of elements with given key.
643        *  @param  __x  Key of elements to be located.
644        *  @return Number of elements with specified key.
645        */
646       size_type
647       count(const key_type& __x) const
648       { return _M_t.count(__x); }
649 
650 #if __cplusplus > 201103L
651       template<typename _Kt>
652 	auto
653 	count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x))
654 	{ return _M_t._M_count_tr(__x); }
655 #endif
656       //@}
657 
658       // _GLIBCXX_RESOLVE_LIB_DEFECTS
659       // 214.  set::find() missing const overload
660       //@{
661       /**
662        *  @brief Tries to locate an element in a %set.
663        *  @param  __x  Element to be located.
664        *  @return  Iterator pointing to sought-after element, or end() if not
665        *           found.
666        *
667        *  This function takes a key and tries to locate the element with which
668        *  the key matches.  If successful the function returns an iterator
669        *  pointing to the sought after element.  If unsuccessful it returns the
670        *  past-the-end ( @c end() ) iterator.
671        */
672       iterator
673       find(const key_type& __x)
674       { return _M_t.find(__x); }
675 
676       const_iterator
677       find(const key_type& __x) const
678       { return _M_t.find(__x); }
679 
680 #if __cplusplus > 201103L
681       template<typename _Kt>
682 	auto
683 	find(const _Kt& __x)
684 	-> decltype(iterator{_M_t._M_find_tr(__x)})
685 	{ return iterator{_M_t._M_find_tr(__x)}; }
686 
687       template<typename _Kt>
688 	auto
689 	find(const _Kt& __x) const
690 	-> decltype(const_iterator{_M_t._M_find_tr(__x)})
691 	{ return const_iterator{_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(iterator(_M_t._M_lower_bound_tr(__x)))
720 	{ return iterator(_M_t._M_lower_bound_tr(__x)); }
721 
722       template<typename _Kt>
723 	auto
724 	lower_bound(const _Kt& __x) const
725 	-> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
726 	{ return iterator(_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(iterator(_M_t._M_upper_bound_tr(__x)))
750 	{ return iterator(_M_t._M_upper_bound_tr(__x)); }
751 
752       template<typename _Kt>
753 	auto
754 	upper_bound(const _Kt& __x) const
755 	-> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
756 	{ return iterator(_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        */
776       std::pair<iterator, iterator>
777       equal_range(const key_type& __x)
778       { return _M_t.equal_range(__x); }
779 
780       std::pair<const_iterator, const_iterator>
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(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)))
789 	{ return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); }
790 
791       template<typename _Kt>
792 	auto
793 	equal_range(const _Kt& __x) const
794 	-> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)))
795 	{ return pair<iterator, iterator>(_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,
824 	       const multiset<_Key, _Compare, _Alloc>& __y)
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,
841 	      const multiset<_Key, _Compare, _Alloc>& __y)
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,
848 	       const multiset<_Key, _Compare, _Alloc>& __y)
849     { return !(__x == __y); }
850 
851   ///  Returns y < x.
852   template<typename _Key, typename _Compare, typename _Alloc>
853     inline bool
854     operator>(const multiset<_Key,_Compare,_Alloc>& __x,
855 	      const multiset<_Key,_Compare,_Alloc>& __y)
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,
862 	       const multiset<_Key, _Compare, _Alloc>& __y)
863     { return !(__y < __x); }
864 
865   ///  Returns !(x < y)
866   template<typename _Key, typename _Compare, typename _Alloc>
867     inline bool
868     operator>=(const multiset<_Key, _Compare, _Alloc>& __x,
869 	       const multiset<_Key, _Compare, _Alloc>& __y)
870     { return !(__x < __y); }
871 
872   /// See std::multiset::swap().
873   template<typename _Key, typename _Compare, typename _Alloc>
874     inline void
875     swap(multiset<_Key, _Compare, _Alloc>& __x,
876 	 multiset<_Key, _Compare, _Alloc>& __y)
877     _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
878     { __x.swap(__y); }
879 
880 _GLIBCXX_END_NAMESPACE_CONTAINER
881 } // namespace std
882 
883 #endif /* _STL_MULTISET_H */
884