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

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

// Copyright (C) 2003-2016 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)
	{
	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
	  __glibcxx_check_valid_range2(__first, __last, __dist);

	  if (__dist.second >= __gnu_debug::__dp_sign)
	    _Base::insert(__gnu_debug::__unsafe(__first),
			  __gnu_debug::__unsafe(__last));
	  else
	    _Base::insert(__first, __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)
      _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
      {
	_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); }

#if __cplusplus > 201103L
      template<typename _Kt,
	       typename _Req =
		 typename __has_is_transparent<_Compare, _Kt>::type>
	iterator
	find(const _Kt& __x)
	{ return { _Base::find(__x), this }; }

      template<typename _Kt,
	       typename _Req =
		 typename __has_is_transparent<_Compare, _Kt>::type>
	const_iterator
	find(const _Kt& __x) const
	{ return { _Base::find(__x), this }; }
#endif

      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); }

#if __cplusplus > 201103L
      template<typename _Kt,
	       typename _Req =
		 typename __has_is_transparent<_Compare, _Kt>::type>
	iterator
	lower_bound(const _Kt& __x)
	{ return { _Base::lower_bound(__x), this }; }

      template<typename _Kt,
	       typename _Req =
		 typename __has_is_transparent<_Compare, _Kt>::type>
	const_iterator
	lower_bound(const _Kt& __x) const
	{ return { _Base::lower_bound(__x), this }; }
#endif

      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); }

#if __cplusplus > 201103L
      template<typename _Kt,
	       typename _Req =
		 typename __has_is_transparent<_Compare, _Kt>::type>
	iterator
	upper_bound(const _Kt& __x)
	{ return { _Base::upper_bound(__x), this }; }

      template<typename _Kt,
	       typename _Req =
		 typename __has_is_transparent<_Compare, _Kt>::type>
	const_iterator
	upper_bound(const _Kt& __x) const
	{ return { _Base::upper_bound(__x), this }; }
#endif

      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));
      }

#if __cplusplus > 201103L
      template<typename _Kt,
	       typename _Req =
		 typename __has_is_transparent<_Compare, _Kt>::type>
	std::pair<iterator, iterator>
	equal_range(const _Kt& __x)
	{
	  auto __res = _Base::equal_range(__x);
	  return { { __res.first, this }, { __res.second, this } };
	}

      template<typename _Kt,
	       typename _Req =
		 typename __has_is_transparent<_Compare, _Kt>::type>
	std::pair<const_iterator, const_iterator>
	equal_range(const _Kt& __x) const
	{
	  auto __res = _Base::equal_range(__x);
	  return { { __res.first, this }, { __res.second, this } };
	}
#endif

      _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)
    _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
    { return __x.swap(__y); }

} // namespace __debug
} // namespace std

#endif
Commit	Line	Data
d570f2e9	1	// Debugging multiset implementation -- C++ --
d570f2e9	2
f1717362	3	// Copyright (C) 2003-2016 Free Software Foundation, Inc.
d570f2e9	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
6bc9506f	8	// Free Software Foundation; either version 3, or (at your option)
d570f2e9	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
6bc9506f	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/>.
d570f2e9	24
0e014800	25	/** @file debug/multiset.h
	26	* This file is a GNU debug extension to the Standard C++ Library.
	27	*/
	28
d570f2e9	29	#ifndef _GLIBCXX_DEBUG_MULTISET_H
	30	#define _GLIBCXX_DEBUG_MULTISET_H 1
	31
	32	#include <debug/safe_sequence.h>
b25436b0	33	#include <debug/safe_container.h>
d570f2e9	34	#include <debug/safe_iterator.h>
	35	#include <utility>
	36
2948dd21	37	namespace std _GLIBCXX_VISIBILITY(default)
1069247d	38	{
10c73e3f	39	namespace __debug
d570f2e9	40	{
5cb6199d	41	/// Class std::multiset with safety/checking/debug instrumentation.
d570f2e9	42	template<typename _Key, typename _Compare = std::less<_Key>,
d570f2e9	43	typename _Allocator = std::allocator<_Key> >
6a299e0b	44	class multiset
b25436b0	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>
d570f2e9	49	{
b25436b0	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;
d570f2e9	53
b25436b0	54	typedef typename _Base::const_iterator _Base_const_iterator;
b25436b0	55	typedef typename _Base::iterator _Base_iterator;
8e9bca59	56	typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
85676e50	57
d570f2e9	58	public:
d570f2e9	59	// types:
b25436b0	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;
d570f2e9	67
8e9bca59	68	typedef __gnu_debug::_Safe_iterator<_Base_iterator, multiset>
b25436b0	69	iterator;
8e9bca59	70	typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
b25436b0	71	multiset> const_iterator;
d570f2e9	72
b25436b0	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;
d570f2e9	79
d570f2e9	80	// 23.3.3.1 construct/copy/destroy:
36f540c7	81
b25436b0	82	#if __cplusplus < 201103L
36f540c7	83	multiset() : _Base() { }
36f540c7	84
41854acb	85	multiset(const multiset& __x)
ad86ca1a	86	: _Base(__x) { }
6a299e0b	87
b25436b0	88	~multiset() { }
	89	#else
	90	multiset() = default;
	91	multiset(const multiset&) = default;
	92	multiset(multiset&&) = default;
b23fdac1	93
	94	multiset(initializer_list<value_type> __l,
	95	const _Compare& __comp = _Compare(),
	96	const allocator_type& __a = allocator_type())
ad86ca1a	97	: _Base(__l, __comp, __a) { }
85676e50	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)
b25436b0	107	: _Safe(std::move(__m._M_safe()), __a),
b25436b0	108	_Base(std::move(__m._M_base()), __a) { }
85676e50	109
	110	multiset(initializer_list<value_type> __l, const allocator_type& __a)
	111	: _Base(__l, __a)
	112	{ }
	113
	114	template<typename _InputIterator>
b25436b0	115	multiset(_InputIterator __first, _InputIterator __last,
85676e50	116	const allocator_type& __a)
b25436b0	117	: _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
	118	__last)),
	119	__gnu_debug::__base(__last), __a) { }
	120
	121	~multiset() = default;
41854acb	122	#endif
d570f2e9	123
b25436b0	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) { }
d570f2e9	139
b25436b0	140	#if __cplusplus < 201103L
41854acb	141	multiset&
41854acb	142	operator=(const multiset& __x)
d570f2e9	143	{
b25436b0	144	this->_M_safe() = __x;
85676e50	145	_M_base() = __x;
d570f2e9	146	return *this;
d570f2e9	147	}
b25436b0	148	#else
	149	multiset&
	150	operator=(const multiset&) = default;
d570f2e9	151
41854acb	152	multiset&
b25436b0	153	operator=(multiset&&) = default;
b23fdac1	154
	155	multiset&
	156	operator=(initializer_list<value_type> __l)
	157	{
85676e50	158	_M_base() = __l;
85676e50	159	this->_M_invalidate_all();
b23fdac1	160	return *this;
b23fdac1	161	}
41854acb	162	#endif
41854acb	163
d570f2e9	164	using _Base::get_allocator;
	165
	166	// iterators:
	167	iterator
7cd718fd	168	begin() _GLIBCXX_NOEXCEPT
d570f2e9	169	{ return iterator(_Base::begin(), this); }
d570f2e9	170
6a299e0b	171	const_iterator
7cd718fd	172	begin() const _GLIBCXX_NOEXCEPT
d570f2e9	173	{ return const_iterator(_Base::begin(), this); }
d570f2e9	174
6a299e0b	175	iterator
7cd718fd	176	end() _GLIBCXX_NOEXCEPT
d570f2e9	177	{ return iterator(_Base::end(), this); }
d570f2e9	178
6a299e0b	179	const_iterator
7cd718fd	180	end() const _GLIBCXX_NOEXCEPT
d570f2e9	181	{ return const_iterator(_Base::end(), this); }
d570f2e9	182
6a299e0b	183	reverse_iterator
7cd718fd	184	rbegin() _GLIBCXX_NOEXCEPT
d570f2e9	185	{ return reverse_iterator(end()); }
d570f2e9	186
6a299e0b	187	const_reverse_iterator
7cd718fd	188	rbegin() const _GLIBCXX_NOEXCEPT
d570f2e9	189	{ return const_reverse_iterator(end()); }
d570f2e9	190
6a299e0b	191	reverse_iterator
7cd718fd	192	rend() _GLIBCXX_NOEXCEPT
d570f2e9	193	{ return reverse_iterator(begin()); }
d570f2e9	194
6a299e0b	195	const_reverse_iterator
7cd718fd	196	rend() const _GLIBCXX_NOEXCEPT
d570f2e9	197	{ return const_reverse_iterator(begin()); }
d570f2e9	198
0c8766b1	199	#if __cplusplus >= 201103L
c40b2e37	200	const_iterator
7cd718fd	201	cbegin() const noexcept
c40b2e37	202	{ return const_iterator(_Base::begin(), this); }
	203
	204	const_iterator
7cd718fd	205	cend() const noexcept
c40b2e37	206	{ return const_iterator(_Base::end(), this); }
	207
	208	const_reverse_iterator
7cd718fd	209	crbegin() const noexcept
c40b2e37	210	{ return const_reverse_iterator(end()); }
	211
	212	const_reverse_iterator
7cd718fd	213	crend() const noexcept
c40b2e37	214	{ return const_reverse_iterator(begin()); }
	215	#endif
	216
d570f2e9	217	// capacity:
	218	using _Base::empty;
	219	using _Base::size;
	220	using _Base::max_size;
	221
	222	// modifiers:
0c8766b1	223	#if __cplusplus >= 201103L
6b9314a8	224	template<typename... _Args>
	225	iterator
	226	emplace(_Args&&... __args)
	227	{
b25436b0	228	return iterator(_Base::emplace(std::forward<_Args>(__args)...),
b25436b0	229	this);
6b9314a8	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
6a299e0b	243	iterator
d570f2e9	244	insert(const value_type& __x)
	245	{ return iterator(_Base::insert(__x), this); }
	246
0c8766b1	247	#if __cplusplus >= 201103L
3e469200	248	iterator
	249	insert(value_type&& __x)
	250	{ return iterator(_Base::insert(std::move(__x)), this); }
	251	#endif
	252
6a299e0b	253	iterator
b3bea0f2	254	insert(const_iterator __position, const value_type& __x)
d570f2e9	255	{
	256	__glibcxx_check_insert(__position);
	257	return iterator(_Base::insert(__position.base(), __x), this);
	258	}
	259
0c8766b1	260	#if __cplusplus >= 201103L
3e469200	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
d570f2e9	270	template<typename _InputIterator>
ec940cbb	271	void
	272	insert(_InputIterator __first, _InputIterator __last)
	273	{
d9ba0dd6	274	typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
	275	__glibcxx_check_valid_range2(__first, __last, __dist);
	276
	277	if (__dist.second >= __gnu_debug::__dp_sign)
	278	_Base::insert(__gnu_debug::__unsafe(__first),
	279	__gnu_debug::__unsafe(__last));
	280	else
	281	_Base::insert(__first, __last);
ec940cbb	282	}
d570f2e9	283
0c8766b1	284	#if __cplusplus >= 201103L
b23fdac1	285	void
	286	insert(initializer_list<value_type> __l)
	287	{ _Base::insert(__l); }
	288	#endif
	289
0c8766b1	290	#if __cplusplus >= 201103L
26acfa1a	291	iterator
b3bea0f2	292	erase(const_iterator __position)
26acfa1a	293	{
26acfa1a	294	__glibcxx_check_erase(__position);
8e9bca59	295	this->_M_invalidate_if(_Equal(__position.base()));
26acfa1a	296	return iterator(_Base::erase(__position.base()), this);
	297	}
	298	#else
6a299e0b	299	void
d570f2e9	300	erase(iterator __position)
	301	{
	302	__glibcxx_check_erase(__position);
8e9bca59	303	this->_M_invalidate_if(_Equal(__position.base()));
d570f2e9	304	_Base::erase(__position.base());
d570f2e9	305	}
26acfa1a	306	#endif
d570f2e9	307
	308	size_type
	309	erase(const key_type& __x)
	310	{
8e9bca59	311	std::pair<_Base_iterator, _Base_iterator> __victims =
8e9bca59	312	_Base::equal_range(__x);
d570f2e9	313	size_type __count = 0;
8e9bca59	314	_Base_iterator __victim = __victims.first;
	315	while (__victim != __victims.second)
	316	{
	317	this->_M_invalidate_if(_Equal(__victim));
	318	_Base::erase(__victim++);
	319	++__count;
	320	}
d570f2e9	321	return __count;
	322	}
	323
0c8766b1	324	#if __cplusplus >= 201103L
26acfa1a	325	iterator
b3bea0f2	326	erase(const_iterator __first, const_iterator __last)
26acfa1a	327	{
	328	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	329	// 151. can't currently clear() empty container
	330	__glibcxx_check_erase_range(__first, __last);
8e9bca59	331	for (_Base_const_iterator __victim = __first.base();
	332	__victim != __last.base(); ++__victim)
	333	{
	334	_GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
	335	_M_message(__gnu_debug::__msg_valid_range)
	336	._M_iterator(__first, "first")
	337	._M_iterator(__last, "last"));
	338	this->_M_invalidate_if(_Equal(__victim));
	339	}
	340	return iterator(_Base::erase(__first.base(), __last.base()), this);
26acfa1a	341	}
26acfa1a	342	#else
6a299e0b	343	void
d570f2e9	344	erase(iterator __first, iterator __last)
	345	{
	346	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	347	// 151. can't currently clear() empty container
	348	__glibcxx_check_erase_range(__first, __last);
8e9bca59	349	for (_Base_iterator __victim = __first.base();
	350	__victim != __last.base(); ++__victim)
	351	{
	352	_GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
	353	_M_message(__gnu_debug::__msg_valid_range)
	354	._M_iterator(__first, "first")
	355	._M_iterator(__last, "last"));
	356	this->_M_invalidate_if(_Equal(__victim));
	357	}
	358	_Base::erase(__first.base(), __last.base());
d570f2e9	359	}
26acfa1a	360	#endif
d570f2e9	361
6a299e0b	362	void
41854acb	363	swap(multiset& __x)
02769f1f	364	_GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
d570f2e9	365	{
b25436b0	366	_Safe::_M_swap(__x);
d570f2e9	367	_Base::swap(__x);
d570f2e9	368	}
d570f2e9	369
6a299e0b	370	void
7cd718fd	371	clear() _GLIBCXX_NOEXCEPT
8e9bca59	372	{
	373	this->_M_invalidate_all();
	374	_Base::clear();
	375	}
d570f2e9	376
	377	// observers:
	378	using _Base::key_comp;
	379	using _Base::value_comp;
	380
	381	// multiset operations:
6a299e0b	382	iterator
d570f2e9	383	find(const key_type& __x)
	384	{ return iterator(_Base::find(__x), this); }
	385
	386	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	387	// 214. set::find() missing const overload
6a299e0b	388	const_iterator
d570f2e9	389	find(const key_type& __x) const
	390	{ return const_iterator(_Base::find(__x), this); }
	391
e20e61b2	392	#if __cplusplus > 201103L
	393	template<typename _Kt,
	394	typename _Req =
	395	typename __has_is_transparent<_Compare, _Kt>::type>
	396	iterator
	397	find(const _Kt& __x)
	398	{ return { _Base::find(__x), this }; }
	399
	400	template<typename _Kt,
	401	typename _Req =
	402	typename __has_is_transparent<_Compare, _Kt>::type>
	403	const_iterator
	404	find(const _Kt& __x) const
	405	{ return { _Base::find(__x), this }; }
	406	#endif
	407
d570f2e9	408	using _Base::count;
d570f2e9	409
6a299e0b	410	iterator
d570f2e9	411	lower_bound(const key_type& __x)
	412	{ return iterator(_Base::lower_bound(__x), this); }
	413
	414	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	415	// 214. set::find() missing const overload
6a299e0b	416	const_iterator
d570f2e9	417	lower_bound(const key_type& __x) const
	418	{ return const_iterator(_Base::lower_bound(__x), this); }
	419
e20e61b2	420	#if __cplusplus > 201103L
	421	template<typename _Kt,
	422	typename _Req =
	423	typename __has_is_transparent<_Compare, _Kt>::type>
	424	iterator
	425	lower_bound(const _Kt& __x)
	426	{ return { _Base::lower_bound(__x), this }; }
	427
	428	template<typename _Kt,
	429	typename _Req =
	430	typename __has_is_transparent<_Compare, _Kt>::type>
	431	const_iterator
	432	lower_bound(const _Kt& __x) const
	433	{ return { _Base::lower_bound(__x), this }; }
	434	#endif
	435
6a299e0b	436	iterator
d570f2e9	437	upper_bound(const key_type& __x)
	438	{ return iterator(_Base::upper_bound(__x), this); }
	439
	440	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	441	// 214. set::find() missing const overload
6a299e0b	442	const_iterator
d570f2e9	443	upper_bound(const key_type& __x) const
	444	{ return const_iterator(_Base::upper_bound(__x), this); }
	445
e20e61b2	446	#if __cplusplus > 201103L
	447	template<typename _Kt,
	448	typename _Req =
	449	typename __has_is_transparent<_Compare, _Kt>::type>
	450	iterator
	451	upper_bound(const _Kt& __x)
	452	{ return { _Base::upper_bound(__x), this }; }
	453
	454	template<typename _Kt,
	455	typename _Req =
	456	typename __has_is_transparent<_Compare, _Kt>::type>
	457	const_iterator
	458	upper_bound(const _Kt& __x) const
	459	{ return { _Base::upper_bound(__x), this }; }
	460	#endif
	461
d570f2e9	462	std::pair<iterator,iterator>
	463	equal_range(const key_type& __x)
	464	{
d570f2e9	465	std::pair<_Base_iterator, _Base_iterator> __res =
8e9bca59	466	_Base::equal_range(__x);
d570f2e9	467	return std::make_pair(iterator(__res.first, this),
	468	iterator(__res.second, this));
	469	}
	470
	471	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	472	// 214. set::find() missing const overload
	473	std::pair<const_iterator,const_iterator>
	474	equal_range(const key_type& __x) const
	475	{
8e9bca59	476	std::pair<_Base_const_iterator, _Base_const_iterator> __res =
8e9bca59	477	_Base::equal_range(__x);
d570f2e9	478	return std::make_pair(const_iterator(__res.first, this),
	479	const_iterator(__res.second, this));
	480	}
	481
e20e61b2	482	#if __cplusplus > 201103L
	483	template<typename _Kt,
	484	typename _Req =
	485	typename __has_is_transparent<_Compare, _Kt>::type>
	486	std::pair<iterator, iterator>
	487	equal_range(const _Kt& __x)
	488	{
	489	auto __res = _Base::equal_range(__x);
	490	return { { __res.first, this }, { __res.second, this } };
	491	}
	492
	493	template<typename _Kt,
	494	typename _Req =
	495	typename __has_is_transparent<_Compare, _Kt>::type>
	496	std::pair<const_iterator, const_iterator>
	497	equal_range(const _Kt& __x) const
	498	{
	499	auto __res = _Base::equal_range(__x);
	500	return { { __res.first, this }, { __res.second, this } };
	501	}
	502	#endif
	503
6a299e0b	504	_Base&
b25436b0	505	_M_base() _GLIBCXX_NOEXCEPT { return *this; }
d570f2e9	506
6a299e0b	507	const _Base&
7cd718fd	508	_M_base() const _GLIBCXX_NOEXCEPT { return *this; }
d570f2e9	509	};
	510
	511	template<typename _Key, typename _Compare, typename _Allocator>
6a299e0b	512	inline bool
41854acb	513	operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
41854acb	514	const multiset<_Key, _Compare, _Allocator>& __rhs)
d570f2e9	515	{ return __lhs._M_base() == __rhs._M_base(); }
	516
	517	template<typename _Key, typename _Compare, typename _Allocator>
6a299e0b	518	inline bool
41854acb	519	operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
41854acb	520	const multiset<_Key, _Compare, _Allocator>& __rhs)
d570f2e9	521	{ return __lhs._M_base() != __rhs._M_base(); }
	522
	523	template<typename _Key, typename _Compare, typename _Allocator>
6a299e0b	524	inline bool
41854acb	525	operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
41854acb	526	const multiset<_Key, _Compare, _Allocator>& __rhs)
d570f2e9	527	{ return __lhs._M_base() < __rhs._M_base(); }
	528
	529	template<typename _Key, typename _Compare, typename _Allocator>
6a299e0b	530	inline bool
41854acb	531	operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
41854acb	532	const multiset<_Key, _Compare, _Allocator>& __rhs)
d570f2e9	533	{ return __lhs._M_base() <= __rhs._M_base(); }
	534
	535	template<typename _Key, typename _Compare, typename _Allocator>
6a299e0b	536	inline bool
41854acb	537	operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
41854acb	538	const multiset<_Key, _Compare, _Allocator>& __rhs)
d570f2e9	539	{ return __lhs._M_base() >= __rhs._M_base(); }
	540
	541	template<typename _Key, typename _Compare, typename _Allocator>
6a299e0b	542	inline bool
41854acb	543	operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
41854acb	544	const multiset<_Key, _Compare, _Allocator>& __rhs)
d570f2e9	545	{ return __lhs._M_base() > __rhs._M_base(); }
	546
	547	template<typename _Key, typename _Compare, typename _Allocator>
	548	void
41854acb	549	swap(multiset<_Key, _Compare, _Allocator>& __x,
41854acb	550	multiset<_Key, _Compare, _Allocator>& __y)
02769f1f	551	_GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
d570f2e9	552	{ return __x.swap(__y); }
41854acb	553
10c73e3f	554	} // namespace __debug
1069247d	555	} // namespace std
d570f2e9	556
d570f2e9	557	#endif