[thirdparty/gcc.git] / libstdc++-v3 / include / debug / multiset.h

// Debugging multiset implementation -*- C++ -*-

// Copyright (C) 2003-2014 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/** @file debug/multiset.h
 *  This file is a GNU debug extension to the Standard C++ Library.
 */

#ifndef _GLIBCXX_DEBUG_MULTISET_H
#define _GLIBCXX_DEBUG_MULTISET_H 1

#include <debug/safe_sequence.h>
#include <debug/safe_container.h>
#include <debug/safe_iterator.h>
#include <utility>

namespace std _GLIBCXX_VISIBILITY(default)
{
namespace __debug
{
  /// Class std::multiset with safety/checking/debug instrumentation.
  template<typename _Key, typename _Compare = std::less<_Key>,
	   typename _Allocator = std::allocator<_Key> >
    class multiset
    : public __gnu_debug::_Safe_container<
	multiset<_Key, _Compare, _Allocator>, _Allocator,
	__gnu_debug::_Safe_node_sequence>,
      public _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>
    {
      typedef _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>	_Base;
      typedef __gnu_debug::_Safe_container<
	multiset, _Allocator, __gnu_debug::_Safe_node_sequence>		_Safe;

      typedef typename _Base::const_iterator	_Base_const_iterator;
      typedef typename _Base::iterator		_Base_iterator;
      typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;

    public:
      // types:
      typedef _Key					key_type;
      typedef _Key					value_type;
      typedef _Compare					key_compare;
      typedef _Compare					value_compare;
      typedef _Allocator				allocator_type;
      typedef typename _Base::reference			reference;
      typedef typename _Base::const_reference		const_reference;

      typedef __gnu_debug::_Safe_iterator<_Base_iterator, multiset>
							iterator;
      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
					  multiset>	const_iterator;

      typedef typename _Base::size_type			size_type;
      typedef typename _Base::difference_type		difference_type;
      typedef typename _Base::pointer			pointer;
      typedef typename _Base::const_pointer		const_pointer;
      typedef std::reverse_iterator<iterator>		reverse_iterator;
      typedef std::reverse_iterator<const_iterator>	const_reverse_iterator;

      // 23.3.3.1 construct/copy/destroy:

#if __cplusplus < 201103L
      multiset() : _Base() { }

      multiset(const multiset& __x)
      : _Base(__x) { }

      ~multiset() { }
#else
      multiset() = default;
      multiset(const multiset&) = default;
      multiset(multiset&&) = default;

      multiset(initializer_list<value_type> __l,
	       const _Compare& __comp = _Compare(),
	       const allocator_type& __a = allocator_type())
      : _Base(__l, __comp, __a) { }

      explicit
      multiset(const allocator_type& __a)
      : _Base(__a) { }

      multiset(const multiset& __m, const allocator_type& __a)
      : _Base(__m, __a) { }

      multiset(multiset&& __m, const allocator_type& __a)
      : _Safe(std::move(__m._M_safe()), __a),
	_Base(std::move(__m._M_base()), __a) { }

      multiset(initializer_list<value_type> __l, const allocator_type& __a)
	: _Base(__l, __a)
      { }

      template<typename _InputIterator>
	multiset(_InputIterator __first, _InputIterator __last,
		 const allocator_type& __a)
	: _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
								     __last)),
		__gnu_debug::__base(__last), __a) { }

      ~multiset() = default;
#endif

      explicit multiset(const _Compare& __comp,
			const _Allocator& __a = _Allocator())
      : _Base(__comp, __a) { }

      template<typename _InputIterator>
	multiset(_InputIterator __first, _InputIterator __last,
		 const _Compare& __comp = _Compare(),
		 const _Allocator& __a = _Allocator())
	: _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
								     __last)),
		__gnu_debug::__base(__last),
		__comp, __a) { }

      multiset(const _Base& __x)
      : _Base(__x) { }

#if __cplusplus < 201103L
      multiset&
      operator=(const multiset& __x)
      {
	this->_M_safe() = __x;
	_M_base() = __x;
	return *this;
      }
#else
      multiset&
      operator=(const multiset&) = default;

      multiset&
      operator=(multiset&&) = default;

      multiset&
      operator=(initializer_list<value_type> __l)
      {
	_M_base() = __l;
	this->_M_invalidate_all();
	return *this;
      }
#endif

      using _Base::get_allocator;

      // iterators:
      iterator
      begin() _GLIBCXX_NOEXCEPT
      { return iterator(_Base::begin(), this); }

      const_iterator
      begin() const _GLIBCXX_NOEXCEPT
      { return const_iterator(_Base::begin(), this); }

      iterator
      end() _GLIBCXX_NOEXCEPT
      { return iterator(_Base::end(), this); }

      const_iterator
      end() const _GLIBCXX_NOEXCEPT
      { return const_iterator(_Base::end(), this); }

      reverse_iterator
      rbegin() _GLIBCXX_NOEXCEPT
      { return reverse_iterator(end()); }

      const_reverse_iterator
      rbegin() const _GLIBCXX_NOEXCEPT
      { return const_reverse_iterator(end()); }

      reverse_iterator
      rend() _GLIBCXX_NOEXCEPT
      { return reverse_iterator(begin()); }

      const_reverse_iterator
      rend() const _GLIBCXX_NOEXCEPT
      { return const_reverse_iterator(begin()); }

#if __cplusplus >= 201103L
      const_iterator
      cbegin() const noexcept
      { return const_iterator(_Base::begin(), this); }

      const_iterator
      cend() const noexcept
      { return const_iterator(_Base::end(), this); }

      const_reverse_iterator
      crbegin() const noexcept
      { return const_reverse_iterator(end()); }

      const_reverse_iterator
      crend() const noexcept
      { return const_reverse_iterator(begin()); }
#endif

      // capacity:
      using _Base::empty;
      using _Base::size;
      using _Base::max_size;

      // modifiers:
#if __cplusplus >= 201103L
      template<typename... _Args>
	iterator
	emplace(_Args&&... __args)
	{
	  return iterator(_Base::emplace(std::forward<_Args>(__args)...),
			  this);
	}

      template<typename... _Args>
	iterator
	emplace_hint(const_iterator __pos, _Args&&... __args)
	{
	  __glibcxx_check_insert(__pos);
	  return iterator(_Base::emplace_hint(__pos.base(),
					      std::forward<_Args>(__args)...),
			  this);
	}
#endif

      iterator
      insert(const value_type& __x)
      { return iterator(_Base::insert(__x), this); }

#if __cplusplus >= 201103L
      iterator
      insert(value_type&& __x)
      { return iterator(_Base::insert(std::move(__x)), this); }
#endif

      iterator
      insert(const_iterator __position, const value_type& __x)
      {
	__glibcxx_check_insert(__position);
	return iterator(_Base::insert(__position.base(), __x), this);
      }

#if __cplusplus >= 201103L
      iterator
      insert(const_iterator __position, value_type&& __x)
      {
	__glibcxx_check_insert(__position);
	return iterator(_Base::insert(__position.base(), std::move(__x)),
			this);
      }
#endif

      template<typename _InputIterator>
	void
	insert(_InputIterator __first, _InputIterator __last)
	{
	  __glibcxx_check_valid_range(__first, __last);
	  _Base::insert(__gnu_debug::__base(__first),
			__gnu_debug::__base(__last));
	}

#if __cplusplus >= 201103L
      void
      insert(initializer_list<value_type> __l)
      { _Base::insert(__l); }
#endif

#if __cplusplus >= 201103L
      iterator
      erase(const_iterator __position)
      {
	__glibcxx_check_erase(__position);
	this->_M_invalidate_if(_Equal(__position.base()));
	return iterator(_Base::erase(__position.base()), this);
      }
#else
      void
      erase(iterator __position)
      {
	__glibcxx_check_erase(__position);
	this->_M_invalidate_if(_Equal(__position.base()));
	_Base::erase(__position.base());
      }
#endif

      size_type
      erase(const key_type& __x)
      {
	std::pair<_Base_iterator, _Base_iterator> __victims =
	  _Base::equal_range(__x);
	size_type __count = 0;
	_Base_iterator __victim = __victims.first;
	while (__victim != __victims.second)
	  {
	    this->_M_invalidate_if(_Equal(__victim));
	    _Base::erase(__victim++);
	    ++__count;
	  }
	return __count;
      }

#if __cplusplus >= 201103L
      iterator
      erase(const_iterator __first, const_iterator __last)
      {
	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	// 151. can't currently clear() empty container
	__glibcxx_check_erase_range(__first, __last);
	for (_Base_const_iterator __victim = __first.base();
	     __victim != __last.base(); ++__victim)
	  {
	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
				  _M_message(__gnu_debug::__msg_valid_range)
				  ._M_iterator(__first, "first")
				  ._M_iterator(__last, "last"));
	    this->_M_invalidate_if(_Equal(__victim));
	  }
	return iterator(_Base::erase(__first.base(), __last.base()), this);
      }
#else
      void
      erase(iterator __first, iterator __last)
      {
	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	// 151. can't currently clear() empty container
	__glibcxx_check_erase_range(__first, __last);
	for (_Base_iterator __victim = __first.base();
	     __victim != __last.base(); ++__victim)
	  {
	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
				  _M_message(__gnu_debug::__msg_valid_range)
				  ._M_iterator(__first, "first")
				  ._M_iterator(__last, "last"));
	    this->_M_invalidate_if(_Equal(__victim));
	  }
	_Base::erase(__first.base(), __last.base());
      }
#endif

      void
      swap(multiset& __x)
#if __cplusplus >= 201103L
	noexcept( noexcept(declval<_Base>().swap(__x)) )
#endif
      {
	_Safe::_M_swap(__x);
	_Base::swap(__x);
      }

      void
      clear() _GLIBCXX_NOEXCEPT
      {
	this->_M_invalidate_all();
	_Base::clear();
      }

      // observers:
      using _Base::key_comp;
      using _Base::value_comp;

      // multiset operations:
      iterator
      find(const key_type& __x)
      { return iterator(_Base::find(__x), this); }

      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 214. set::find() missing const overload
      const_iterator
      find(const key_type& __x) const
      { return const_iterator(_Base::find(__x), this); }

      using _Base::count;

      iterator
      lower_bound(const key_type& __x)
      { return iterator(_Base::lower_bound(__x), this); }

      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 214. set::find() missing const overload
      const_iterator
      lower_bound(const key_type& __x) const
      { return const_iterator(_Base::lower_bound(__x), this); }

      iterator
      upper_bound(const key_type& __x)
      { return iterator(_Base::upper_bound(__x), this); }

      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 214. set::find() missing const overload
      const_iterator
      upper_bound(const key_type& __x) const
      { return const_iterator(_Base::upper_bound(__x), this); }

      std::pair<iterator,iterator>
      equal_range(const key_type& __x)
      {
	std::pair<_Base_iterator, _Base_iterator> __res =
	  _Base::equal_range(__x);
	return std::make_pair(iterator(__res.first, this),
			      iterator(__res.second, this));
      }

      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 214. set::find() missing const overload
      std::pair<const_iterator,const_iterator>
      equal_range(const key_type& __x) const
      {
	std::pair<_Base_const_iterator, _Base_const_iterator> __res =
	  _Base::equal_range(__x);
	return std::make_pair(const_iterator(__res.first, this),
			      const_iterator(__res.second, this));
      }

      _Base&
      _M_base() _GLIBCXX_NOEXCEPT { return *this; }

      const _Base&
      _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
    };

  template<typename _Key, typename _Compare, typename _Allocator>
    inline bool
    operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
	       const multiset<_Key, _Compare, _Allocator>& __rhs)
    { return __lhs._M_base() == __rhs._M_base(); }

  template<typename _Key, typename _Compare, typename _Allocator>
    inline bool
    operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
	       const multiset<_Key, _Compare, _Allocator>& __rhs)
    { return __lhs._M_base() != __rhs._M_base(); }

  template<typename _Key, typename _Compare, typename _Allocator>
    inline bool
    operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
	      const multiset<_Key, _Compare, _Allocator>& __rhs)
    { return __lhs._M_base() < __rhs._M_base(); }

  template<typename _Key, typename _Compare, typename _Allocator>
    inline bool
    operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
	       const multiset<_Key, _Compare, _Allocator>& __rhs)
    { return __lhs._M_base() <= __rhs._M_base(); }

  template<typename _Key, typename _Compare, typename _Allocator>
    inline bool
    operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
	       const multiset<_Key, _Compare, _Allocator>& __rhs)
    { return __lhs._M_base() >= __rhs._M_base(); }

  template<typename _Key, typename _Compare, typename _Allocator>
    inline bool
    operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
	      const multiset<_Key, _Compare, _Allocator>& __rhs)
    { return __lhs._M_base() > __rhs._M_base(); }

  template<typename _Key, typename _Compare, typename _Allocator>
    void
    swap(multiset<_Key, _Compare, _Allocator>& __x,
	 multiset<_Key, _Compare, _Allocator>& __y)
    { return __x.swap(__y); }

} // namespace __debug
} // namespace std

#endif
Commit	Line	Data
285b36d6 BK	1	// Debugging multiset implementation -- C++ --
285b36d6 BK	2
aa118a03	3	// Copyright (C) 2003-2014 Free Software Foundation, Inc.
285b36d6 BK	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
748086b7	8	// Free Software Foundation; either version 3, or (at your option)
285b36d6 BK	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
748086b7 JJ	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/>.
285b36d6	24
78a53887 BK	25	/** @file debug/multiset.h
	26	* This file is a GNU debug extension to the Standard C++ Library.
	27	*/
	28
285b36d6 BK	29	#ifndef _GLIBCXX_DEBUG_MULTISET_H
	30	#define _GLIBCXX_DEBUG_MULTISET_H 1
	31
	32	#include <debug/safe_sequence.h>
15ee1a77	33	#include <debug/safe_container.h>
285b36d6 BK	34	#include <debug/safe_iterator.h>
	35	#include <utility>
	36
12ffa228	37	namespace std _GLIBCXX_VISIBILITY(default)
3cbc7af0	38	{
45f388bb	39	namespace __debug
285b36d6	40	{
1ceb9e06	41	/// Class std::multiset with safety/checking/debug instrumentation.
285b36d6 BK	42	template<typename _Key, typename _Compare = std::less<_Key>,
285b36d6 BK	43	typename _Allocator = std::allocator<_Key> >
526da49c	44	class multiset
15ee1a77 FD	45	: public __gnu_debug::_Safe_container<
	46	multiset<_Key, _Compare, _Allocator>, _Allocator,
	47	__gnu_debug::_Safe_node_sequence>,
	48	public _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>
285b36d6	49	{
15ee1a77 FD	50	typedef _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator> _Base;
	51	typedef __gnu_debug::_Safe_container<
	52	multiset, _Allocator, __gnu_debug::_Safe_node_sequence> _Safe;
285b36d6	53
15ee1a77 FD	54	typedef typename _Base::const_iterator _Base_const_iterator;
15ee1a77 FD	55	typedef typename _Base::iterator _Base_iterator;
afe96d41	56	typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
51835a80	57
285b36d6 BK	58	public:
285b36d6 BK	59	// types:
15ee1a77 FD	60	typedef _Key key_type;
	61	typedef _Key value_type;
	62	typedef _Compare key_compare;
	63	typedef _Compare value_compare;
	64	typedef _Allocator allocator_type;
	65	typedef typename _Base::reference reference;
	66	typedef typename _Base::const_reference const_reference;
285b36d6	67
afe96d41	68	typedef __gnu_debug::_Safe_iterator<_Base_iterator, multiset>
15ee1a77	69	iterator;
afe96d41	70	typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
15ee1a77	71	multiset> const_iterator;
285b36d6	72
15ee1a77 FD	73	typedef typename _Base::size_type size_type;
	74	typedef typename _Base::difference_type difference_type;
	75	typedef typename _Base::pointer pointer;
	76	typedef typename _Base::const_pointer const_pointer;
	77	typedef std::reverse_iterator<iterator> reverse_iterator;
	78	typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
285b36d6 BK	79
285b36d6 BK	80	// 23.3.3.1 construct/copy/destroy:
c3cdd71f	81
15ee1a77	82	#if __cplusplus < 201103L
c3cdd71f JW	83	multiset() : _Base() { }
c3cdd71f JW	84
ed540c0a	85	multiset(const multiset& __x)
4c2d93db	86	: _Base(__x) { }
526da49c	87
15ee1a77 FD	88	~multiset() { }
	89	#else
	90	multiset() = default;
	91	multiset(const multiset&) = default;
	92	multiset(multiset&&) = default;
988499f4 JM	93
	94	multiset(initializer_list<value_type> __l,
	95	const _Compare& __comp = _Compare(),
	96	const allocator_type& __a = allocator_type())
4c2d93db	97	: _Base(__l, __comp, __a) { }
51835a80 FD	98
	99	explicit
	100	multiset(const allocator_type& __a)
	101	: _Base(__a) { }
	102
	103	multiset(const multiset& __m, const allocator_type& __a)
	104	: _Base(__m, __a) { }
	105
	106	multiset(multiset&& __m, const allocator_type& __a)
15ee1a77 FD	107	: _Safe(std::move(__m._M_safe()), __a),
15ee1a77 FD	108	_Base(std::move(__m._M_base()), __a) { }
51835a80 FD	109
	110	multiset(initializer_list<value_type> __l, const allocator_type& __a)
	111	: _Base(__l, __a)
	112	{ }
	113
	114	template<typename _InputIterator>
15ee1a77	115	multiset(_InputIterator __first, _InputIterator __last,
51835a80	116	const allocator_type& __a)
15ee1a77 FD	117	: _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
	118	__last)),
	119	__gnu_debug::__base(__last), __a) { }
	120
	121	~multiset() = default;
ed540c0a	122	#endif
285b36d6	123
15ee1a77 FD	124	explicit multiset(const _Compare& __comp,
	125	const _Allocator& __a = _Allocator())
	126	: _Base(__comp, __a) { }
	127
	128	template<typename _InputIterator>
	129	multiset(_InputIterator __first, _InputIterator __last,
	130	const _Compare& __comp = _Compare(),
	131	const _Allocator& __a = _Allocator())
	132	: _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
	133	__last)),
	134	__gnu_debug::__base(__last),
	135	__comp, __a) { }
	136
	137	multiset(const _Base& __x)
	138	: _Base(__x) { }
285b36d6	139
15ee1a77	140	#if __cplusplus < 201103L
ed540c0a CJ	141	multiset&
ed540c0a CJ	142	operator=(const multiset& __x)
285b36d6	143	{
15ee1a77	144	this->_M_safe() = __x;
51835a80	145	_M_base() = __x;
285b36d6 BK	146	return *this;
285b36d6 BK	147	}
15ee1a77 FD	148	#else
	149	multiset&
	150	operator=(const multiset&) = default;
285b36d6	151
ed540c0a	152	multiset&
15ee1a77	153	operator=(multiset&&) = default;
988499f4 JM	154
	155	multiset&
	156	operator=(initializer_list<value_type> __l)
	157	{
51835a80 FD	158	_M_base() = __l;
51835a80 FD	159	this->_M_invalidate_all();
988499f4 JM	160	return *this;
988499f4 JM	161	}
ed540c0a CJ	162	#endif
ed540c0a CJ	163
285b36d6 BK	164	using _Base::get_allocator;
	165
	166	// iterators:
	167	iterator
d3677132	168	begin() _GLIBCXX_NOEXCEPT
285b36d6 BK	169	{ return iterator(_Base::begin(), this); }
285b36d6 BK	170
526da49c	171	const_iterator
d3677132	172	begin() const _GLIBCXX_NOEXCEPT
285b36d6 BK	173	{ return const_iterator(_Base::begin(), this); }
285b36d6 BK	174
526da49c	175	iterator
d3677132	176	end() _GLIBCXX_NOEXCEPT
285b36d6 BK	177	{ return iterator(_Base::end(), this); }
285b36d6 BK	178
526da49c	179	const_iterator
d3677132	180	end() const _GLIBCXX_NOEXCEPT
285b36d6 BK	181	{ return const_iterator(_Base::end(), this); }
285b36d6 BK	182
526da49c	183	reverse_iterator
d3677132	184	rbegin() _GLIBCXX_NOEXCEPT
285b36d6 BK	185	{ return reverse_iterator(end()); }
285b36d6 BK	186
526da49c	187	const_reverse_iterator
d3677132	188	rbegin() const _GLIBCXX_NOEXCEPT
285b36d6 BK	189	{ return const_reverse_iterator(end()); }
285b36d6 BK	190
526da49c	191	reverse_iterator
d3677132	192	rend() _GLIBCXX_NOEXCEPT
285b36d6 BK	193	{ return reverse_iterator(begin()); }
285b36d6 BK	194
526da49c	195	const_reverse_iterator
d3677132	196	rend() const _GLIBCXX_NOEXCEPT
285b36d6 BK	197	{ return const_reverse_iterator(begin()); }
285b36d6 BK	198
734f5023	199	#if __cplusplus >= 201103L
0cd50f89	200	const_iterator
d3677132	201	cbegin() const noexcept
0cd50f89 PC	202	{ return const_iterator(_Base::begin(), this); }
	203
	204	const_iterator
d3677132	205	cend() const noexcept
0cd50f89 PC	206	{ return const_iterator(_Base::end(), this); }
	207
	208	const_reverse_iterator
d3677132	209	crbegin() const noexcept
0cd50f89 PC	210	{ return const_reverse_iterator(end()); }
	211
	212	const_reverse_iterator
d3677132	213	crend() const noexcept
0cd50f89 PC	214	{ return const_reverse_iterator(begin()); }
	215	#endif
	216
285b36d6 BK	217	// capacity:
	218	using _Base::empty;
	219	using _Base::size;
	220	using _Base::max_size;
	221
	222	// modifiers:
734f5023	223	#if __cplusplus >= 201103L
55826ab6 FD	224	template<typename... _Args>
	225	iterator
	226	emplace(_Args&&... __args)
	227	{
15ee1a77 FD	228	return iterator(_Base::emplace(std::forward<_Args>(__args)...),
15ee1a77 FD	229	this);
55826ab6 FD	230	}
	231
	232	template<typename... _Args>
	233	iterator
	234	emplace_hint(const_iterator __pos, _Args&&... __args)
	235	{
	236	__glibcxx_check_insert(__pos);
	237	return iterator(_Base::emplace_hint(__pos.base(),
	238	std::forward<_Args>(__args)...),
	239	this);
	240	}
	241	#endif
	242
526da49c	243	iterator
285b36d6 BK	244	insert(const value_type& __x)
	245	{ return iterator(_Base::insert(__x), this); }
	246
734f5023	247	#if __cplusplus >= 201103L
e6a05448 PC	248	iterator
	249	insert(value_type&& __x)
	250	{ return iterator(_Base::insert(std::move(__x)), this); }
	251	#endif
	252
526da49c	253	iterator
6b6d5d09	254	insert(const_iterator __position, const value_type& __x)
285b36d6 BK	255	{
	256	__glibcxx_check_insert(__position);
	257	return iterator(_Base::insert(__position.base(), __x), this);
	258	}
	259
734f5023	260	#if __cplusplus >= 201103L
e6a05448 PC	261	iterator
	262	insert(const_iterator __position, value_type&& __x)
	263	{
	264	__glibcxx_check_insert(__position);
	265	return iterator(_Base::insert(__position.base(), std::move(__x)),
	266	this);
	267	}
	268	#endif
	269
285b36d6	270	template<typename _InputIterator>
1f5ca1a1 PC	271	void
	272	insert(_InputIterator __first, _InputIterator __last)
	273	{
	274	__glibcxx_check_valid_range(__first, __last);
	275	_Base::insert(__gnu_debug::__base(__first),
	276	__gnu_debug::__base(__last));
	277	}
285b36d6	278
734f5023	279	#if __cplusplus >= 201103L
988499f4 JM	280	void
	281	insert(initializer_list<value_type> __l)
	282	{ _Base::insert(__l); }
	283	#endif
	284
734f5023	285	#if __cplusplus >= 201103L
5ab06c6d	286	iterator
6b6d5d09	287	erase(const_iterator __position)
5ab06c6d PC	288	{
5ab06c6d PC	289	__glibcxx_check_erase(__position);
afe96d41	290	this->_M_invalidate_if(_Equal(__position.base()));
5ab06c6d PC	291	return iterator(_Base::erase(__position.base()), this);
	292	}
	293	#else
526da49c	294	void
285b36d6 BK	295	erase(iterator __position)
	296	{
	297	__glibcxx_check_erase(__position);
afe96d41	298	this->_M_invalidate_if(_Equal(__position.base()));
285b36d6 BK	299	_Base::erase(__position.base());
285b36d6 BK	300	}
5ab06c6d	301	#endif
285b36d6 BK	302
	303	size_type
	304	erase(const key_type& __x)
	305	{
afe96d41 FD	306	std::pair<_Base_iterator, _Base_iterator> __victims =
afe96d41 FD	307	_Base::equal_range(__x);
285b36d6	308	size_type __count = 0;
afe96d41 FD	309	_Base_iterator __victim = __victims.first;
	310	while (__victim != __victims.second)
	311	{
	312	this->_M_invalidate_if(_Equal(__victim));
	313	_Base::erase(__victim++);
	314	++__count;
	315	}
285b36d6 BK	316	return __count;
	317	}
	318
734f5023	319	#if __cplusplus >= 201103L
5ab06c6d	320	iterator
6b6d5d09	321	erase(const_iterator __first, const_iterator __last)
5ab06c6d PC	322	{
	323	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	324	// 151. can't currently clear() empty container
	325	__glibcxx_check_erase_range(__first, __last);
afe96d41 FD	326	for (_Base_const_iterator __victim = __first.base();
	327	__victim != __last.base(); ++__victim)
	328	{
	329	_GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
	330	_M_message(__gnu_debug::__msg_valid_range)
	331	._M_iterator(__first, "first")
	332	._M_iterator(__last, "last"));
	333	this->_M_invalidate_if(_Equal(__victim));
	334	}
	335	return iterator(_Base::erase(__first.base(), __last.base()), this);
5ab06c6d PC	336	}
5ab06c6d PC	337	#else
526da49c	338	void
285b36d6 BK	339	erase(iterator __first, iterator __last)
	340	{
	341	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	342	// 151. can't currently clear() empty container
	343	__glibcxx_check_erase_range(__first, __last);
afe96d41 FD	344	for (_Base_iterator __victim = __first.base();
	345	__victim != __last.base(); ++__victim)
	346	{
	347	_GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
	348	_M_message(__gnu_debug::__msg_valid_range)
	349	._M_iterator(__first, "first")
	350	._M_iterator(__last, "last"));
	351	this->_M_invalidate_if(_Equal(__victim));
	352	}
	353	_Base::erase(__first.base(), __last.base());
285b36d6	354	}
5ab06c6d	355	#endif
285b36d6	356
526da49c	357	void
ed540c0a	358	swap(multiset& __x)
51835a80	359	#if __cplusplus >= 201103L
15ee1a77	360	noexcept( noexcept(declval<_Base>().swap(__x)) )
51835a80	361	#endif
285b36d6	362	{
15ee1a77	363	_Safe::_M_swap(__x);
285b36d6	364	_Base::swap(__x);
285b36d6 BK	365	}
285b36d6 BK	366
526da49c	367	void
d3677132	368	clear() _GLIBCXX_NOEXCEPT
afe96d41 FD	369	{
	370	this->_M_invalidate_all();
	371	_Base::clear();
	372	}
285b36d6 BK	373
	374	// observers:
	375	using _Base::key_comp;
	376	using _Base::value_comp;
	377
	378	// multiset operations:
526da49c	379	iterator
285b36d6 BK	380	find(const key_type& __x)
	381	{ return iterator(_Base::find(__x), this); }
	382
	383	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	384	// 214. set::find() missing const overload
526da49c	385	const_iterator
285b36d6 BK	386	find(const key_type& __x) const
	387	{ return const_iterator(_Base::find(__x), this); }
	388
	389	using _Base::count;
	390
526da49c	391	iterator
285b36d6 BK	392	lower_bound(const key_type& __x)
	393	{ return iterator(_Base::lower_bound(__x), this); }
	394
	395	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	396	// 214. set::find() missing const overload
526da49c	397	const_iterator
285b36d6 BK	398	lower_bound(const key_type& __x) const
	399	{ return const_iterator(_Base::lower_bound(__x), this); }
	400
526da49c	401	iterator
285b36d6 BK	402	upper_bound(const key_type& __x)
	403	{ return iterator(_Base::upper_bound(__x), this); }
	404
	405	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	406	// 214. set::find() missing const overload
526da49c	407	const_iterator
285b36d6 BK	408	upper_bound(const key_type& __x) const
	409	{ return const_iterator(_Base::upper_bound(__x), this); }
	410
	411	std::pair<iterator,iterator>
	412	equal_range(const key_type& __x)
	413	{
285b36d6	414	std::pair<_Base_iterator, _Base_iterator> __res =
afe96d41	415	_Base::equal_range(__x);
285b36d6 BK	416	return std::make_pair(iterator(__res.first, this),
	417	iterator(__res.second, this));
	418	}
	419
	420	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	421	// 214. set::find() missing const overload
	422	std::pair<const_iterator,const_iterator>
	423	equal_range(const key_type& __x) const
	424	{
afe96d41 FD	425	std::pair<_Base_const_iterator, _Base_const_iterator> __res =
afe96d41 FD	426	_Base::equal_range(__x);
285b36d6 BK	427	return std::make_pair(const_iterator(__res.first, this),
	428	const_iterator(__res.second, this));
	429	}
	430
526da49c	431	_Base&
15ee1a77	432	_M_base() _GLIBCXX_NOEXCEPT { return *this; }
285b36d6	433
526da49c	434	const _Base&
d3677132	435	_M_base() const _GLIBCXX_NOEXCEPT { return *this; }
285b36d6 BK	436	};
	437
	438	template<typename _Key, typename _Compare, typename _Allocator>
526da49c	439	inline bool
ed540c0a CJ	440	operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
ed540c0a CJ	441	const multiset<_Key, _Compare, _Allocator>& __rhs)
285b36d6 BK	442	{ return __lhs._M_base() == __rhs._M_base(); }
	443
	444	template<typename _Key, typename _Compare, typename _Allocator>
526da49c	445	inline bool
ed540c0a CJ	446	operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
ed540c0a CJ	447	const multiset<_Key, _Compare, _Allocator>& __rhs)
285b36d6 BK	448	{ return __lhs._M_base() != __rhs._M_base(); }
	449
	450	template<typename _Key, typename _Compare, typename _Allocator>
526da49c	451	inline bool
ed540c0a CJ	452	operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
ed540c0a CJ	453	const multiset<_Key, _Compare, _Allocator>& __rhs)
285b36d6 BK	454	{ return __lhs._M_base() < __rhs._M_base(); }
	455
	456	template<typename _Key, typename _Compare, typename _Allocator>
526da49c	457	inline bool
ed540c0a CJ	458	operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
ed540c0a CJ	459	const multiset<_Key, _Compare, _Allocator>& __rhs)
285b36d6 BK	460	{ return __lhs._M_base() <= __rhs._M_base(); }
	461
	462	template<typename _Key, typename _Compare, typename _Allocator>
526da49c	463	inline bool
ed540c0a CJ	464	operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
ed540c0a CJ	465	const multiset<_Key, _Compare, _Allocator>& __rhs)
285b36d6 BK	466	{ return __lhs._M_base() >= __rhs._M_base(); }
	467
	468	template<typename _Key, typename _Compare, typename _Allocator>
526da49c	469	inline bool
ed540c0a CJ	470	operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
ed540c0a CJ	471	const multiset<_Key, _Compare, _Allocator>& __rhs)
285b36d6 BK	472	{ return __lhs._M_base() > __rhs._M_base(); }
	473
	474	template<typename _Key, typename _Compare, typename _Allocator>
	475	void
ed540c0a CJ	476	swap(multiset<_Key, _Compare, _Allocator>& __x,
ed540c0a CJ	477	multiset<_Key, _Compare, _Allocator>& __y)
285b36d6	478	{ return __x.swap(__y); }
ed540c0a	479
45f388bb	480	} // namespace __debug
3cbc7af0	481	} // namespace std
285b36d6 BK	482
285b36d6 BK	483	#endif