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

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

// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2009, 2010, 2011, 2012
// 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_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 _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>,
      public __gnu_debug::_Safe_sequence<multiset<_Key, _Compare, _Allocator> >
    {
      typedef _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator> _Base;

      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:
      explicit multiset(const _Compare& __comp = _Compare(),
			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 multiset& __x)
      : _Base(__x) { }

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

#if __cplusplus >= 201103L
      multiset(multiset&& __x)
      noexcept(is_nothrow_copy_constructible<_Compare>::value)
      : _Base(std::move(__x))
      { this->_M_swap(__x); }

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

      ~multiset() _GLIBCXX_NOEXCEPT { }

      multiset&
      operator=(const multiset& __x)
      {
	*static_cast<_Base*>(this) = __x;
	this->_M_invalidate_all();
	return *this;
      }

#if __cplusplus >= 201103L
      multiset&
      operator=(multiset&& __x)
      {
	// NB: DR 1204.
	// NB: DR 675.
	__glibcxx_check_self_move_assign(__x);
	clear();
	swap(__x);
	return *this;
      }

      multiset&
      operator=(initializer_list<value_type> __l)
      {
	this->clear();
	this->insert(__l);
	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)
      {
	_Base::swap(__x);
	this->_M_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; }

    private:
      void
      _M_invalidate_all()
      {
	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
	this->_M_invalidate_if(_Not_equal(_Base::end()));
      }
    };

  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
739fd6a6	3	// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2009, 2010, 2011, 2012
285b36d6 BK	4	// Free Software Foundation, Inc.
	5	//
	6	// This file is part of the GNU ISO C++ Library. This library is free
	7	// software; you can redistribute it and/or modify it under the
	8	// terms of the GNU General Public License as published by the
748086b7	9	// Free Software Foundation; either version 3, or (at your option)
285b36d6 BK	10	// any later version.
	11
	12	// This library is distributed in the hope that it will be useful,
	13	// but WITHOUT ANY WARRANTY; without even the implied warranty of
	14	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	15	// GNU General Public License for more details.
	16
748086b7 JJ	17	// Under Section 7 of GPL version 3, you are granted additional
	18	// permissions described in the GCC Runtime Library Exception, version
	19	// 3.1, as published by the Free Software Foundation.
	20
	21	// You should have received a copy of the GNU General Public License and
	22	// a copy of the GCC Runtime Library Exception along with this program;
	23	// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
	24	// <http://www.gnu.org/licenses/>.
285b36d6	25
78a53887 BK	26	/** @file debug/multiset.h
	27	* This file is a GNU debug extension to the Standard C++ Library.
	28	*/
	29
285b36d6 BK	30	#ifndef _GLIBCXX_DEBUG_MULTISET_H
	31	#define _GLIBCXX_DEBUG_MULTISET_H 1
	32
	33	#include <debug/safe_sequence.h>
	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
12ffa228	45	: public _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>,
285b36d6 BK	46	public __gnu_debug::_Safe_sequence<multiset<_Key, _Compare, _Allocator> >
285b36d6 BK	47	{
12ffa228	48	typedef _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator> _Base;
285b36d6	49
afe96d41 FD	50	typedef typename _Base::const_iterator _Base_const_iterator;
	51	typedef typename _Base::iterator _Base_iterator;
	52	typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
285b36d6 BK	53	public:
285b36d6 BK	54	// types:
526da49c BI	55	typedef _Key key_type;
	56	typedef _Key value_type;
	57	typedef _Compare key_compare;
	58	typedef _Compare value_compare;
	59	typedef _Allocator allocator_type;
09952acc PC	60	typedef typename _Base::reference reference;
09952acc PC	61	typedef typename _Base::const_reference const_reference;
285b36d6	62
afe96d41	63	typedef __gnu_debug::_Safe_iterator<_Base_iterator, multiset>
285b36d6	64	iterator;
afe96d41	65	typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
285b36d6 BK	66	multiset> const_iterator;
	67
	68	typedef typename _Base::size_type size_type;
	69	typedef typename _Base::difference_type difference_type;
09952acc PC	70	typedef typename _Base::pointer pointer;
09952acc PC	71	typedef typename _Base::const_pointer const_pointer;
285b36d6 BK	72	typedef std::reverse_iterator<iterator> reverse_iterator;
	73	typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
	74
	75	// 23.3.3.1 construct/copy/destroy:
	76	explicit multiset(const _Compare& __comp = _Compare(),
	77	const _Allocator& __a = _Allocator())
	78	: _Base(__comp, __a) { }
	79
	80	template<typename _InputIterator>
	81	multiset(_InputIterator __first, _InputIterator __last,
	82	const _Compare& __comp = _Compare(),
	83	const _Allocator& __a = _Allocator())
1f5ca1a1 PC	84	: _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
	85	__last)),
	86	__gnu_debug::__base(__last),
285b36d6 BK	87	__comp, __a) { }
285b36d6 BK	88
ed540c0a	89	multiset(const multiset& __x)
4c2d93db	90	: _Base(__x) { }
526da49c	91
ed540c0a	92	multiset(const _Base& __x)
4c2d93db	93	: _Base(__x) { }
ed540c0a	94
734f5023	95	#if __cplusplus >= 201103L
ed540c0a	96	multiset(multiset&& __x)
6f59ea25	97	noexcept(is_nothrow_copy_constructible<_Compare>::value)
4c2d93db	98	: _Base(std::move(__x))
ed540c0a	99	{ this->_M_swap(__x); }
988499f4 JM	100
	101	multiset(initializer_list<value_type> __l,
	102	const _Compare& __comp = _Compare(),
	103	const allocator_type& __a = allocator_type())
4c2d93db	104	: _Base(__l, __comp, __a) { }
ed540c0a	105	#endif
285b36d6	106
6f59ea25	107	~multiset() _GLIBCXX_NOEXCEPT { }
285b36d6	108
ed540c0a CJ	109	multiset&
ed540c0a CJ	110	operator=(const multiset& __x)
285b36d6 BK	111	{
	112	static_cast<_Base>(this) = __x;
	113	this->_M_invalidate_all();
	114	return *this;
	115	}
	116
734f5023	117	#if __cplusplus >= 201103L
ed540c0a CJ	118	multiset&
	119	operator=(multiset&& __x)
	120	{
0462fd5e PC	121	// NB: DR 1204.
0462fd5e PC	122	// NB: DR 675.
739fd6a6	123	__glibcxx_check_self_move_assign(__x);
0462fd5e PC	124	clear();
0462fd5e PC	125	swap(__x);
ed540c0a CJ	126	return *this;
ed540c0a CJ	127	}
988499f4 JM	128
	129	multiset&
	130	operator=(initializer_list<value_type> __l)
	131	{
	132	this->clear();
	133	this->insert(__l);
	134	return *this;
	135	}
ed540c0a CJ	136	#endif
ed540c0a CJ	137
285b36d6 BK	138	using _Base::get_allocator;
	139
	140	// iterators:
	141	iterator
d3677132	142	begin() _GLIBCXX_NOEXCEPT
285b36d6 BK	143	{ return iterator(_Base::begin(), this); }
285b36d6 BK	144
526da49c	145	const_iterator
d3677132	146	begin() const _GLIBCXX_NOEXCEPT
285b36d6 BK	147	{ return const_iterator(_Base::begin(), this); }
285b36d6 BK	148
526da49c	149	iterator
d3677132	150	end() _GLIBCXX_NOEXCEPT
285b36d6 BK	151	{ return iterator(_Base::end(), this); }
285b36d6 BK	152
526da49c	153	const_iterator
d3677132	154	end() const _GLIBCXX_NOEXCEPT
285b36d6 BK	155	{ return const_iterator(_Base::end(), this); }
285b36d6 BK	156
526da49c	157	reverse_iterator
d3677132	158	rbegin() _GLIBCXX_NOEXCEPT
285b36d6 BK	159	{ return reverse_iterator(end()); }
285b36d6 BK	160
526da49c	161	const_reverse_iterator
d3677132	162	rbegin() const _GLIBCXX_NOEXCEPT
285b36d6 BK	163	{ return const_reverse_iterator(end()); }
285b36d6 BK	164
526da49c	165	reverse_iterator
d3677132	166	rend() _GLIBCXX_NOEXCEPT
285b36d6 BK	167	{ return reverse_iterator(begin()); }
285b36d6 BK	168
526da49c	169	const_reverse_iterator
d3677132	170	rend() const _GLIBCXX_NOEXCEPT
285b36d6 BK	171	{ return const_reverse_iterator(begin()); }
285b36d6 BK	172
734f5023	173	#if __cplusplus >= 201103L
0cd50f89	174	const_iterator
d3677132	175	cbegin() const noexcept
0cd50f89 PC	176	{ return const_iterator(_Base::begin(), this); }
	177
	178	const_iterator
d3677132	179	cend() const noexcept
0cd50f89 PC	180	{ return const_iterator(_Base::end(), this); }
	181
	182	const_reverse_iterator
d3677132	183	crbegin() const noexcept
0cd50f89 PC	184	{ return const_reverse_iterator(end()); }
	185
	186	const_reverse_iterator
d3677132	187	crend() const noexcept
0cd50f89 PC	188	{ return const_reverse_iterator(begin()); }
	189	#endif
	190
285b36d6 BK	191	// capacity:
	192	using _Base::empty;
	193	using _Base::size;
	194	using _Base::max_size;
	195
	196	// modifiers:
734f5023	197	#if __cplusplus >= 201103L
55826ab6 FD	198	template<typename... _Args>
	199	iterator
	200	emplace(_Args&&... __args)
	201	{
	202	return iterator(_Base::emplace(std::forward<_Args>(__args)...), this);
	203	}
	204
	205	template<typename... _Args>
	206	iterator
	207	emplace_hint(const_iterator __pos, _Args&&... __args)
	208	{
	209	__glibcxx_check_insert(__pos);
	210	return iterator(_Base::emplace_hint(__pos.base(),
	211	std::forward<_Args>(__args)...),
	212	this);
	213	}
	214	#endif
	215
526da49c	216	iterator
285b36d6 BK	217	insert(const value_type& __x)
	218	{ return iterator(_Base::insert(__x), this); }
	219
734f5023	220	#if __cplusplus >= 201103L
e6a05448 PC	221	iterator
	222	insert(value_type&& __x)
	223	{ return iterator(_Base::insert(std::move(__x)), this); }
	224	#endif
	225
526da49c	226	iterator
6b6d5d09	227	insert(const_iterator __position, const value_type& __x)
285b36d6 BK	228	{
	229	__glibcxx_check_insert(__position);
	230	return iterator(_Base::insert(__position.base(), __x), this);
	231	}
	232
734f5023	233	#if __cplusplus >= 201103L
e6a05448 PC	234	iterator
	235	insert(const_iterator __position, value_type&& __x)
	236	{
	237	__glibcxx_check_insert(__position);
	238	return iterator(_Base::insert(__position.base(), std::move(__x)),
	239	this);
	240	}
	241	#endif
	242
285b36d6	243	template<typename _InputIterator>
1f5ca1a1 PC	244	void
	245	insert(_InputIterator __first, _InputIterator __last)
	246	{
	247	__glibcxx_check_valid_range(__first, __last);
	248	_Base::insert(__gnu_debug::__base(__first),
	249	__gnu_debug::__base(__last));
	250	}
285b36d6	251
734f5023	252	#if __cplusplus >= 201103L
988499f4 JM	253	void
	254	insert(initializer_list<value_type> __l)
	255	{ _Base::insert(__l); }
	256	#endif
	257
734f5023	258	#if __cplusplus >= 201103L
5ab06c6d	259	iterator
6b6d5d09	260	erase(const_iterator __position)
5ab06c6d PC	261	{
5ab06c6d PC	262	__glibcxx_check_erase(__position);
afe96d41	263	this->_M_invalidate_if(_Equal(__position.base()));
5ab06c6d PC	264	return iterator(_Base::erase(__position.base()), this);
	265	}
	266	#else
526da49c	267	void
285b36d6 BK	268	erase(iterator __position)
	269	{
	270	__glibcxx_check_erase(__position);
afe96d41	271	this->_M_invalidate_if(_Equal(__position.base()));
285b36d6 BK	272	_Base::erase(__position.base());
285b36d6 BK	273	}
5ab06c6d	274	#endif
285b36d6 BK	275
	276	size_type
	277	erase(const key_type& __x)
	278	{
afe96d41 FD	279	std::pair<_Base_iterator, _Base_iterator> __victims =
afe96d41 FD	280	_Base::equal_range(__x);
285b36d6	281	size_type __count = 0;
afe96d41 FD	282	_Base_iterator __victim = __victims.first;
	283	while (__victim != __victims.second)
	284	{
	285	this->_M_invalidate_if(_Equal(__victim));
	286	_Base::erase(__victim++);
	287	++__count;
	288	}
285b36d6 BK	289	return __count;
	290	}
	291
734f5023	292	#if __cplusplus >= 201103L
5ab06c6d	293	iterator
6b6d5d09	294	erase(const_iterator __first, const_iterator __last)
5ab06c6d PC	295	{
	296	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	297	// 151. can't currently clear() empty container
	298	__glibcxx_check_erase_range(__first, __last);
afe96d41 FD	299	for (_Base_const_iterator __victim = __first.base();
	300	__victim != __last.base(); ++__victim)
	301	{
	302	_GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
	303	_M_message(__gnu_debug::__msg_valid_range)
	304	._M_iterator(__first, "first")
	305	._M_iterator(__last, "last"));
	306	this->_M_invalidate_if(_Equal(__victim));
	307	}
	308	return iterator(_Base::erase(__first.base(), __last.base()), this);
5ab06c6d PC	309	}
5ab06c6d PC	310	#else
526da49c	311	void
285b36d6 BK	312	erase(iterator __first, iterator __last)
	313	{
	314	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	315	// 151. can't currently clear() empty container
	316	__glibcxx_check_erase_range(__first, __last);
afe96d41 FD	317	for (_Base_iterator __victim = __first.base();
	318	__victim != __last.base(); ++__victim)
	319	{
	320	_GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
	321	_M_message(__gnu_debug::__msg_valid_range)
	322	._M_iterator(__first, "first")
	323	._M_iterator(__last, "last"));
	324	this->_M_invalidate_if(_Equal(__victim));
	325	}
	326	_Base::erase(__first.base(), __last.base());
285b36d6	327	}
5ab06c6d	328	#endif
285b36d6	329
526da49c	330	void
ed540c0a	331	swap(multiset& __x)
285b36d6 BK	332	{
	333	_Base::swap(__x);
	334	this->_M_swap(__x);
	335	}
	336
526da49c	337	void
d3677132	338	clear() _GLIBCXX_NOEXCEPT
afe96d41 FD	339	{
	340	this->_M_invalidate_all();
	341	_Base::clear();
	342	}
285b36d6 BK	343
	344	// observers:
	345	using _Base::key_comp;
	346	using _Base::value_comp;
	347
	348	// multiset operations:
526da49c	349	iterator
285b36d6 BK	350	find(const key_type& __x)
	351	{ return iterator(_Base::find(__x), this); }
	352
	353	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	354	// 214. set::find() missing const overload
526da49c	355	const_iterator
285b36d6 BK	356	find(const key_type& __x) const
	357	{ return const_iterator(_Base::find(__x), this); }
	358
	359	using _Base::count;
	360
526da49c	361	iterator
285b36d6 BK	362	lower_bound(const key_type& __x)
	363	{ return iterator(_Base::lower_bound(__x), this); }
	364
	365	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	366	// 214. set::find() missing const overload
526da49c	367	const_iterator
285b36d6 BK	368	lower_bound(const key_type& __x) const
	369	{ return const_iterator(_Base::lower_bound(__x), this); }
	370
526da49c	371	iterator
285b36d6 BK	372	upper_bound(const key_type& __x)
	373	{ return iterator(_Base::upper_bound(__x), this); }
	374
	375	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	376	// 214. set::find() missing const overload
526da49c	377	const_iterator
285b36d6 BK	378	upper_bound(const key_type& __x) const
	379	{ return const_iterator(_Base::upper_bound(__x), this); }
	380
	381	std::pair<iterator,iterator>
	382	equal_range(const key_type& __x)
	383	{
285b36d6	384	std::pair<_Base_iterator, _Base_iterator> __res =
afe96d41	385	_Base::equal_range(__x);
285b36d6 BK	386	return std::make_pair(iterator(__res.first, this),
	387	iterator(__res.second, this));
	388	}
	389
	390	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	391	// 214. set::find() missing const overload
	392	std::pair<const_iterator,const_iterator>
	393	equal_range(const key_type& __x) const
	394	{
afe96d41 FD	395	std::pair<_Base_const_iterator, _Base_const_iterator> __res =
afe96d41 FD	396	_Base::equal_range(__x);
285b36d6 BK	397	return std::make_pair(const_iterator(__res.first, this),
	398	const_iterator(__res.second, this));
	399	}
	400
526da49c	401	_Base&
d3677132	402	_M_base() _GLIBCXX_NOEXCEPT { return *this; }
285b36d6	403
526da49c	404	const _Base&
d3677132	405	_M_base() const _GLIBCXX_NOEXCEPT { return *this; }
526da49c	406
285b36d6	407	private:
526da49c	408	void
285b36d6 BK	409	_M_invalidate_all()
285b36d6 BK	410	{
285b36d6	411	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
afe96d41	412	this->_M_invalidate_if(_Not_equal(_Base::end()));
285b36d6 BK	413	}
	414	};
	415
	416	template<typename _Key, typename _Compare, typename _Allocator>
526da49c	417	inline bool
ed540c0a CJ	418	operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
ed540c0a CJ	419	const multiset<_Key, _Compare, _Allocator>& __rhs)
285b36d6 BK	420	{ return __lhs._M_base() == __rhs._M_base(); }
	421
	422	template<typename _Key, typename _Compare, typename _Allocator>
526da49c	423	inline bool
ed540c0a CJ	424	operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
ed540c0a CJ	425	const multiset<_Key, _Compare, _Allocator>& __rhs)
285b36d6 BK	426	{ return __lhs._M_base() != __rhs._M_base(); }
	427
	428	template<typename _Key, typename _Compare, typename _Allocator>
526da49c	429	inline bool
ed540c0a CJ	430	operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
ed540c0a CJ	431	const multiset<_Key, _Compare, _Allocator>& __rhs)
285b36d6 BK	432	{ return __lhs._M_base() < __rhs._M_base(); }
	433
	434	template<typename _Key, typename _Compare, typename _Allocator>
526da49c	435	inline bool
ed540c0a CJ	436	operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
ed540c0a CJ	437	const multiset<_Key, _Compare, _Allocator>& __rhs)
285b36d6 BK	438	{ return __lhs._M_base() <= __rhs._M_base(); }
	439
	440	template<typename _Key, typename _Compare, typename _Allocator>
526da49c	441	inline bool
ed540c0a CJ	442	operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
ed540c0a CJ	443	const multiset<_Key, _Compare, _Allocator>& __rhs)
285b36d6 BK	444	{ return __lhs._M_base() >= __rhs._M_base(); }
	445
	446	template<typename _Key, typename _Compare, typename _Allocator>
526da49c	447	inline bool
ed540c0a CJ	448	operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
ed540c0a CJ	449	const multiset<_Key, _Compare, _Allocator>& __rhs)
285b36d6 BK	450	{ return __lhs._M_base() > __rhs._M_base(); }
	451
	452	template<typename _Key, typename _Compare, typename _Allocator>
	453	void
ed540c0a CJ	454	swap(multiset<_Key, _Compare, _Allocator>& __x,
ed540c0a CJ	455	multiset<_Key, _Compare, _Allocator>& __y)
285b36d6	456	{ return __x.swap(__y); }
ed540c0a	457
45f388bb	458	} // namespace __debug
3cbc7af0	459	} // namespace std
285b36d6 BK	460
285b36d6 BK	461	#endif