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

// Debugging set 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/set.h
 *  This file is a GNU debug extension to the Standard C++ Library.
 */

#ifndef _GLIBCXX_DEBUG_SET_H
#define _GLIBCXX_DEBUG_SET_H 1

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

namespace std _GLIBCXX_VISIBILITY(default) 
{
namespace __debug
{
  /// Class std::set with safety/checking/debug instrumentation.
  template<typename _Key, typename _Compare = std::less<_Key>,
	   typename _Allocator = std::allocator<_Key> >
    class set
    : public _GLIBCXX_STD_C::set<_Key,_Compare,_Allocator>,
      public __gnu_debug::_Safe_sequence<set<_Key, _Compare, _Allocator> >
    {
      typedef _GLIBCXX_STD_C::set<_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;
#if __cplusplus >= 201103L
      typedef __gnu_cxx::__alloc_traits<typename
					_Base::allocator_type> _Alloc_traits;
#endif
    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, set>
                                                    iterator;
      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, set>
                                                    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 set(const _Compare& __comp = _Compare(),
		   const _Allocator& __a = _Allocator())
      : _Base(__comp, __a) { }

      template<typename _InputIterator>
        set(_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) { }

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

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

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

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

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

      set(const set& __x, const allocator_type& __a)
      : _Base(__x, __a) { }

      set(set&& __x, const allocator_type& __a)
      : _Base(std::move(__x._M_base()), __a) { }

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

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

      ~set() _GLIBCXX_NOEXCEPT { }

      set&
      operator=(const set& __x)
      {
	_M_base() = __x;
	this->_M_invalidate_all();
	return *this;
      }

#if __cplusplus >= 201103L
      set&
      operator=(set&& __x)
      noexcept(_Alloc_traits::_S_nothrow_move())
      {
	__glibcxx_check_self_move_assign(__x);
	bool xfer_memory = _Alloc_traits::_S_propagate_on_move_assign()
	    || __x.get_allocator() == this->get_allocator();
	_M_base() = std::move(__x._M_base());
	if (xfer_memory)
	  this->_M_swap(__x);
	else
	  this->_M_invalidate_all();
	__x._M_invalidate_all();
	return *this;
      }

      set&
      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>
	std::pair<iterator, bool>
	emplace(_Args&&... __args)
	{
	  auto __res = _Base::emplace(std::forward<_Args>(__args)...);
	  return std::pair<iterator, bool>(iterator(__res.first, this),
					   __res.second);
	}

      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

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

#if __cplusplus >= 201103L
      std::pair<iterator, bool>
      insert(value_type&& __x)
      {
	std::pair<_Base_iterator, bool> __res
	  = _Base::insert(std::move(__x));
	return std::pair<iterator, bool>(iterator(__res.first, this),
					 __res.second);
      }
#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)
      {
	_Base_iterator __victim = _Base::find(__x);
	if (__victim == _Base::end())
          return 0;
	else
	  {
	    this->_M_invalidate_if(_Equal(__victim));
	    _Base::erase(__victim);
	    return 1;
	  }
      }

#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(set& __x)
#if __cplusplus >= 201103L
      noexcept(_Alloc_traits::_S_nothrow_swap())
#endif
      {
#if __cplusplus >= 201103L
	if (!_Alloc_traits::_S_propagate_on_swap())
	  __glibcxx_check_equal_allocs(__x);
#endif
	_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;

      // set 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_iterator, _Base_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(_M_base().end()));
      }
    };

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

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

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

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

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

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

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

} // namespace __debug
} // namespace std

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