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

// Profiling set implementation -*- C++ -*-

// Copyright (C) 2009-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 profile/set.h
 *  This file is a GNU profile extension to the Standard C++ Library.
 */

#ifndef _GLIBCXX_PROFILE_SET_H
#define _GLIBCXX_PROFILE_SET_H 1

#include <profile/base.h>
#include <profile/ordered_base.h>

namespace std _GLIBCXX_VISIBILITY(default)
{
namespace __profile
{
  /// Class std::set wrapper with performance 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 _Ordered_profile<set<_Key, _Compare, _Allocator> >
    {
      typedef _GLIBCXX_STD_C::set<_Key, _Compare, _Allocator> _Base;

      typedef typename _Base::iterator			_Base_iterator;
      typedef typename _Base::const_iterator		_Base_const_iterator;

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

      typedef __iterator_tracker<_Base_iterator, set>	iterator;
      typedef __iterator_tracker<_Base_const_iterator,
				 set>			const_iterator;
      typedef std::reverse_iterator<iterator>		reverse_iterator;
      typedef std::reverse_iterator<const_iterator>	const_reverse_iterator;

      typedef typename _Base::size_type			size_type;
      typedef typename _Base::difference_type		difference_type;

      // 23.3.3.1 construct/copy/destroy:
#if __cplusplus < 201103L
      set()
      : _Base() { }
      set(const set& __x)
      : _Base(__x) { }
      ~set() { }
#else
      set() = default;
      set(const set&) = default;
      set(set&&) = default;
      ~set() = default;
#endif

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

#if __cplusplus >= 201103L
      template<typename _InputIterator,
	       typename = std::_RequireInputIter<_InputIterator>>
#else
      template<typename _InputIterator>
#endif
	set(_InputIterator __first, _InputIterator __last,
	    const _Compare& __comp = _Compare(),
	    const _Allocator& __a = _Allocator())
	: _Base(__first, __last, __comp, __a) { }

#if __cplusplus >= 201103L
      set(initializer_list<value_type> __l,
	  const _Compare& __comp = _Compare(),
	  const _Allocator& __a = _Allocator())
      : _Base(__l, __comp, __a) { }

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

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

      set(set&& __x, const _Allocator& __a)
      noexcept( noexcept(_Base(std::move(__x), __a)) )
      : _Base(std::move(__x), __a) { }

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

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

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

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

      set&
      operator=(set&&) = default;

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

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

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

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

      reverse_iterator
      rbegin() _GLIBCXX_NOEXCEPT
      {
	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
	return reverse_iterator(end());
      }

      const_reverse_iterator
      rbegin() const _GLIBCXX_NOEXCEPT
      {
	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
	return const_reverse_iterator(end());
      }

      reverse_iterator
      rend() _GLIBCXX_NOEXCEPT
      {
	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
	return reverse_iterator(begin());
      }

      const_reverse_iterator
      rend() const _GLIBCXX_NOEXCEPT
      {
	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
	return const_reverse_iterator(begin());
      }

#if __cplusplus >= 201103L
      const_reverse_iterator
      crbegin() const noexcept
      {
	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
	return const_reverse_iterator(cend());
      }

      const_reverse_iterator
      crend() const noexcept
      {
	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
	return const_reverse_iterator(cbegin());
      }
#endif

      void
      swap(set& __x)
      _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
      {
	_Base::swap(__x);
	this->_M_swap(__x);
      }

      // modifiers:
#if __cplusplus >= 201103L
      template<typename... _Args>
	std::pair<iterator, bool>
	emplace(_Args&&... __args)
	{
	  __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
	  auto __base_ret = _Base::emplace(std::forward<_Args>(__args)...);
	  return std::make_pair(iterator(__base_ret.first, this),
				__base_ret.second);
	}

      template<typename... _Args>
	iterator
	emplace_hint(const_iterator __pos, _Args&&... __args)
	{
	  auto size_before = this->size();
	  auto __res
	    = _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...);
	  __profcxx_map2umap_insert(this->_M_map2umap_info,
		size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
	  return iterator(__res, this);
	}
#endif

      std::pair<iterator, bool>
      insert(const value_type& __x)
      {
	__profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
	std::pair<_Base_iterator, bool> __base_ret = _Base::insert(__x);
	return std::make_pair(iterator(__base_ret.first, this),
			      __base_ret.second);
      }

#if __cplusplus >= 201103L
      std::pair<iterator, bool>
      insert(value_type&& __x)
      {
	__profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
	std::pair<_Base_iterator, bool> __base_ret
	  = _Base::insert(std::move(__x));
	return std::make_pair(iterator(__base_ret.first, this),
			      __base_ret.second);
      }
#endif

      iterator
      insert(const_iterator __pos, const value_type& __x)
      {
	size_type size_before = this->size();
	_Base_iterator __res = _Base::insert(__pos.base(), __x);
	__profcxx_map2umap_insert(this->_M_map2umap_info,
		size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
	return iterator(__res, this);
      }

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

      template<typename _InputIterator>
	void
	insert(_InputIterator __first, _InputIterator __last)
	{
	  for (; __first != __last; ++__first)
	    insert(*__first);
	}

#if __cplusplus >= 201103L
      void
      insert(initializer_list<value_type> __l)
      { insert(__l.begin(), __l.end()); }
#endif

#if __cplusplus >= 201103L
      iterator
      erase(const_iterator __pos)
      {
	__profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
	return iterator(_Base::erase(__pos.base()), this);
      }
#else
      void
      erase(iterator __pos)
      {
	__profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
	_Base::erase(__pos.base());
      }
#endif

      size_type
      erase(const key_type& __x)
      {
	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	__profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
	return _Base::erase(__x);
      }

#if __cplusplus >= 201103L
      iterator
      erase(const_iterator __first, const_iterator __last)
      {
	if (__first != __last)
	  {
	    iterator __ret;
	    for (; __first != __last;)
	      __ret = erase(__first++);
	    return __ret;
	  }

	return iterator(_Base::erase(__first.base(), __last.base()), this);
      }
#else
      void
      erase(iterator __first, iterator __last)
      {
	for (; __first != __last;)
	     erase(__first++);
      }
#endif

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

      size_type
      count(const key_type& __x) const
      {
	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	return _Base::count(__x);
      }

#if __cplusplus > 201103L
      template<typename _Kt,
	       typename _Req =
		 typename __has_is_transparent<_Compare, _Kt>::type>
	size_type
	count(const _Kt& __x) const
	{
	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	  return _Base::count(__x);
	}
#endif

      // set operations:
      iterator
      find(const key_type& __x)
      {
	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	return iterator(_Base::find(__x), this);
      }

      const_iterator
      find(const key_type& __x) const
      {
	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	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)
	{
	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	  return { _Base::find(__x), this };
	}

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

      iterator
      lower_bound(const key_type& __x)
      {
	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
	return iterator(_Base::lower_bound(__x), this);
      }

      const_iterator
      lower_bound(const key_type& __x) const
      {
	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
	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)
	{
	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
	  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
	{
	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
	  return { _Base::lower_bound(__x), this };
	}
#endif

      iterator
      upper_bound(const key_type& __x)
      {
	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
	return iterator(_Base::upper_bound(__x), this);
      }

      const_iterator
      upper_bound(const key_type& __x) const
      {
	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
	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)
	{
	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
	  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
	{
	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
	  return { _Base::upper_bound(__x), this };
	}
#endif

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

      std::pair<const_iterator, const_iterator>
      equal_range(const key_type& __x) const
      {
	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	std::pair<_Base_const_iterator, _Base_const_iterator> __base_ret
	  = _Base::equal_range(__x);
	return std::make_pair(const_iterator(__base_ret.first, this),
			      const_iterator(__base_ret.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)
	{
	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	  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
	{
	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	  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; }

    private:
      /** If hint is used we consider that the map and unordered_map
       * operations have equivalent insertion cost so we do not update metrics
       * about it.
       * Note that to find out if hint has been used is libstdc++
       * implementation dependent.
       */
      bool
      _M_hint_used(_Base_const_iterator __hint, _Base_iterator __res)
      {
	return (__hint == __res
		|| (__hint == _M_base().end() && ++__res == _M_base().end())
		|| (__hint != _M_base().end() && (++__hint == __res
						  || ++__res == --__hint)));
      }

      template<typename _K1, typename _C1, typename _A1>
	friend bool
	operator==(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);

      template<typename _K1, typename _C1, typename _A1>
	friend bool
	operator<(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);
    };

  template<typename _Key, typename _Compare, typename _Allocator>
    inline bool
    operator==(const set<_Key, _Compare, _Allocator>& __lhs,
	       const set<_Key, _Compare, _Allocator>& __rhs)
    {
      __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
      __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
      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)
    {
      __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
      __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
      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 == __rhs); }

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

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

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

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

} // namespace __profile
} // namespace std

#endif
Commit	Line	Data
c55dc904	1	// Profiling set implementation -- C++ --
c55dc904	2
f1717362	3	// Copyright (C) 2009-2016 Free Software Foundation, Inc.
c55dc904	4	//
	5	// This file is part of the GNU ISO C++ Library. This library is free
	6	// software; you can redistribute it and/or modify it under the
	7	// terms of the GNU General Public License as published by the
	8	// Free Software Foundation; either version 3, or (at your option)
	9	// any later version.
	10
	11	// This library is distributed in the hope that it will be useful,
	12	// but WITHOUT ANY WARRANTY; without even the implied warranty of
	13	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	14	// GNU General Public License for more details.
	15
	16	// Under Section 7 of GPL version 3, you are granted additional
	17	// permissions described in the GCC Runtime Library Exception, version
	18	// 3.1, as published by the Free Software Foundation.
	19
	20	// You should have received a copy of the GNU General Public License and
	21	// a copy of the GCC Runtime Library Exception along with this program;
	22	// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
	23	// <http://www.gnu.org/licenses/>.
	24
	25	/** @file profile/set.h
	26	* This file is a GNU profile extension to the Standard C++ Library.
	27	*/
	28
	29	#ifndef _GLIBCXX_PROFILE_SET_H
	30	#define _GLIBCXX_PROFILE_SET_H 1
	31
5f70fed5	32	#include <profile/base.h>
5f70fed5	33	#include <profile/ordered_base.h>
c55dc904	34
5f70fed5	35	namespace std _GLIBCXX_VISIBILITY(default)
c55dc904	36	{
	37	namespace __profile
	38	{
8b7c9a53	39	/// Class std::set wrapper with performance instrumentation.
c55dc904	40	template<typename _Key, typename _Compare = std::less<_Key>,
	41	typename _Allocator = std::allocator<_Key> >
	42	class set
5f70fed5	43	: public _GLIBCXX_STD_C::set<_Key,_Compare,_Allocator>,
5f70fed5	44	public _Ordered_profile<set<_Key, _Compare, _Allocator> >
c55dc904	45	{
2948dd21	46	typedef _GLIBCXX_STD_C::set<_Key, _Compare, _Allocator> _Base;
c55dc904	47
1675d1be	48	typedef typename _Base::iterator _Base_iterator;
1675d1be	49	typedef typename _Base::const_iterator _Base_const_iterator;
aac14b59	50
c55dc904	51	public:
c55dc904	52	// types:
5f70fed5	53	typedef _Key key_type;
	54	typedef _Key value_type;
	55	typedef _Compare key_compare;
	56	typedef _Compare value_compare;
	57	typedef typename _Base::reference reference;
	58	typedef typename _Base::const_reference const_reference;
	59
1675d1be	60	typedef __iterator_tracker<_Base_iterator, set> iterator;
	61	typedef __iterator_tracker<_Base_const_iterator,
	62	set> const_iterator;
	63	typedef std::reverse_iterator<iterator> reverse_iterator;
	64	typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
5f70fed5	65
	66	typedef typename _Base::size_type size_type;
	67	typedef typename _Base::difference_type difference_type;
c55dc904	68
c55dc904	69	// 23.3.3.1 construct/copy/destroy:
5f70fed5	70	#if __cplusplus < 201103L
36f540c7	71	set()
36f540c7	72	: _Base() { }
5f70fed5	73	set(const set& __x)
	74	: _Base(__x) { }
	75	~set() { }
	76	#else
	77	set() = default;
	78	set(const set&) = default;
	79	set(set&&) = default;
	80	~set() = default;
	81	#endif
36f540c7	82
36f540c7	83	explicit set(const _Compare& __comp,
c55dc904	84	const _Allocator& __a = _Allocator())
	85	: _Base(__comp, __a) { }
	86
0c8766b1	87	#if __cplusplus >= 201103L
3edec8c4	88	template<typename _InputIterator,
	89	typename = std::_RequireInputIter<_InputIterator>>
	90	#else
c55dc904	91	template<typename _InputIterator>
3edec8c4	92	#endif
5f70fed5	93	set(_InputIterator __first, _InputIterator __last,
c55dc904	94	const _Compare& __comp = _Compare(),
	95	const _Allocator& __a = _Allocator())
	96	: _Base(__first, __last, __comp, __a) { }
	97
5f70fed5	98	#if __cplusplus >= 201103L
c55dc904	99	set(initializer_list<value_type> __l,
c55dc904	100	const _Compare& __comp = _Compare(),
5f70fed5	101	const _Allocator& __a = _Allocator())
c55dc904	102	: _Base(__l, __comp, __a) { }
aac14b59	103
aac14b59	104	explicit
5f70fed5	105	set(const _Allocator& __a)
5f70fed5	106	: _Base(__a) { }
aac14b59	107
5f70fed5	108	set(const set& __x, const _Allocator& __a)
aac14b59	109	: _Base(__x, __a) { }
aac14b59	110
5f70fed5	111	set(set&& __x, const _Allocator& __a)
5f70fed5	112	noexcept( noexcept(_Base(std::move(__x), __a)) )
aac14b59	113	: _Base(std::move(__x), __a) { }
aac14b59	114
5f70fed5	115	set(initializer_list<value_type> __l, const _Allocator& __a)
aac14b59	116	: _Base(__l, __a) { }
	117
	118	template<typename _InputIterator>
5f70fed5	119	set(_InputIterator __first, _InputIterator __last,
	120	const _Allocator& __a)
	121	: _Base(__first, __last, __a) { }
c55dc904	122	#endif
c55dc904	123
aac14b59	124	set(const _Base& __x)
	125	: _Base(__x) { }
	126
aac14b59	127	#if __cplusplus < 201103L
c55dc904	128	set&
	129	operator=(const set& __x)
	130	{
1675d1be	131	this->_M_profile_destruct();
aac14b59	132	_M_base() = __x;
1675d1be	133	this->_M_profile_construct();
c55dc904	134	return *this;
c55dc904	135	}
aac14b59	136	#else
	137	set&
	138	operator=(const set&) = default;
c55dc904	139
c55dc904	140	set&
aac14b59	141	operator=(set&&) = default;
c55dc904	142
	143	set&
	144	operator=(initializer_list<value_type> __l)
	145	{
1675d1be	146	this->_M_profile_destruct();
aac14b59	147	_M_base() = __l;
1675d1be	148	this->_M_profile_construct();
c55dc904	149	return *this;
	150	}
	151	#endif
	152
1675d1be	153	// iterators
	154	iterator
	155	begin() _GLIBCXX_NOEXCEPT
	156	{ return iterator(_Base::begin(), this); }
	157
	158	const_iterator
	159	begin() const _GLIBCXX_NOEXCEPT
	160	{ return const_iterator(_Base::begin(), this); }
	161
	162	iterator
	163	end() _GLIBCXX_NOEXCEPT
	164	{ return iterator(_Base::end(), this); }
	165
	166	const_iterator
	167	end() const _GLIBCXX_NOEXCEPT
	168	{ return const_iterator(_Base::end(), this); }
	169
	170	#if __cplusplus >= 201103L
	171	const_iterator
	172	cbegin() const noexcept
	173	{ return const_iterator(_Base::cbegin(), this); }
	174
	175	const_iterator
	176	cend() const noexcept
	177	{ return const_iterator(_Base::cend(), this); }
	178	#endif
	179
c55dc904	180	reverse_iterator
7cd718fd	181	rbegin() _GLIBCXX_NOEXCEPT
5f70fed5	182	{
1675d1be	183	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
1675d1be	184	return reverse_iterator(end());
5f70fed5	185	}
c55dc904	186
c55dc904	187	const_reverse_iterator
7cd718fd	188	rbegin() const _GLIBCXX_NOEXCEPT
5f70fed5	189	{
1675d1be	190	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
1675d1be	191	return const_reverse_iterator(end());
5f70fed5	192	}
c55dc904	193
c55dc904	194	reverse_iterator
7cd718fd	195	rend() _GLIBCXX_NOEXCEPT
5f70fed5	196	{
1675d1be	197	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
1675d1be	198	return reverse_iterator(begin());
5f70fed5	199	}
c55dc904	200
c55dc904	201	const_reverse_iterator
7cd718fd	202	rend() const _GLIBCXX_NOEXCEPT
5f70fed5	203	{
1675d1be	204	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
1675d1be	205	return const_reverse_iterator(begin());
5f70fed5	206	}
c55dc904	207
0c8766b1	208	#if __cplusplus >= 201103L
c55dc904	209	const_reverse_iterator
7cd718fd	210	crbegin() const noexcept
5f70fed5	211	{
1675d1be	212	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
1675d1be	213	return const_reverse_iterator(cend());
5f70fed5	214	}
c55dc904	215
c55dc904	216	const_reverse_iterator
7cd718fd	217	crend() const noexcept
5f70fed5	218	{
1675d1be	219	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
1675d1be	220	return const_reverse_iterator(cbegin());
5f70fed5	221	}
c55dc904	222	#endif
c55dc904	223
1675d1be	224	void
1675d1be	225	swap(set& __x)
02769f1f	226	_GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
1675d1be	227	{
	228	_Base::swap(__x);
	229	this->_M_swap(__x);
	230	}
	231
c55dc904	232	// modifiers:
0c8766b1	233	#if __cplusplus >= 201103L
6b9314a8	234	template<typename... _Args>
	235	std::pair<iterator, bool>
	236	emplace(_Args&&... __args)
	237	{
1675d1be	238	__profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
	239	auto __base_ret = _Base::emplace(std::forward<_Args>(__args)...);
	240	return std::make_pair(iterator(__base_ret.first, this),
	241	__base_ret.second);
6b9314a8	242	}
	243
	244	template<typename... _Args>
	245	iterator
	246	emplace_hint(const_iterator __pos, _Args&&... __args)
	247	{
5f70fed5	248	auto size_before = this->size();
5f70fed5	249	auto __res
1675d1be	250	= _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...);
	251	__profcxx_map2umap_insert(this->_M_map2umap_info,
	252	size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
	253	return iterator(__res, this);
6b9314a8	254	}
	255	#endif
	256
c55dc904	257	std::pair<iterator, bool>
	258	insert(const value_type& __x)
	259	{
1675d1be	260	__profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
	261	std::pair<_Base_iterator, bool> __base_ret = _Base::insert(__x);
	262	return std::make_pair(iterator(__base_ret.first, this),
	263	__base_ret.second);
c55dc904	264	}
c55dc904	265
0c8766b1	266	#if __cplusplus >= 201103L
3e469200	267	std::pair<iterator, bool>
	268	insert(value_type&& __x)
	269	{
1675d1be	270	__profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
	271	std::pair<_Base_iterator, bool> __base_ret
	272	= _Base::insert(std::move(__x));
	273	return std::make_pair(iterator(__base_ret.first, this),
	274	__base_ret.second);
3e469200	275	}
	276	#endif
	277
c55dc904	278	iterator
5f70fed5	279	insert(const_iterator __pos, const value_type& __x)
	280	{
	281	size_type size_before = this->size();
1675d1be	282	_Base_iterator __res = _Base::insert(__pos.base(), __x);
	283	__profcxx_map2umap_insert(this->_M_map2umap_info,
	284	size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
	285	return iterator(__res, this);
5f70fed5	286	}
c55dc904	287
0c8766b1	288	#if __cplusplus >= 201103L
3e469200	289	iterator
1675d1be	290	insert(const_iterator __pos, value_type&& __x)
1675d1be	291	{ return iterator(_Base::insert(__pos.base(), std::move(__x)), this); }
3e469200	292	#endif
3e469200	293
3edec8c4	294	template<typename _InputIterator>
5f70fed5	295	void
	296	insert(_InputIterator __first, _InputIterator __last)
	297	{
	298	for (; __first != __last; ++__first)
	299	insert(*__first);
	300	}
c55dc904	301
0c8766b1	302	#if __cplusplus >= 201103L
c55dc904	303	void
c55dc904	304	insert(initializer_list<value_type> __l)
5f70fed5	305	{ insert(__l.begin(), __l.end()); }
c55dc904	306	#endif
c55dc904	307
0c8766b1	308	#if __cplusplus >= 201103L
c55dc904	309	iterator
5f70fed5	310	erase(const_iterator __pos)
5f70fed5	311	{
1675d1be	312	__profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
1675d1be	313	return iterator(_Base::erase(__pos.base()), this);
5f70fed5	314	}
c55dc904	315	#else
c55dc904	316	void
5f70fed5	317	erase(iterator __pos)
5f70fed5	318	{
1675d1be	319	__profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
1675d1be	320	_Base::erase(__pos.base());
5f70fed5	321	}
c55dc904	322	#endif
	323
	324	size_type
	325	erase(const key_type& __x)
	326	{
1675d1be	327	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
1675d1be	328	__profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
5f70fed5	329	return _Base::erase(__x);
c55dc904	330	}
c55dc904	331
0c8766b1	332	#if __cplusplus >= 201103L
26acfa1a	333	iterator
3b607c40	334	erase(const_iterator __first, const_iterator __last)
5f70fed5	335	{
	336	if (__first != __last)
	337	{
	338	iterator __ret;
	339	for (; __first != __last;)
	340	__ret = erase(__first++);
	341	return __ret;
	342	}
	343
1675d1be	344	return iterator(_Base::erase(__first.base(), __last.base()), this);
5f70fed5	345	}
26acfa1a	346	#else
c55dc904	347	void
c55dc904	348	erase(iterator __first, iterator __last)
5f70fed5	349	{
	350	for (; __first != __last;)
	351	erase(__first++);
	352	}
26acfa1a	353	#endif
c55dc904	354
c55dc904	355	void
1675d1be	356	clear() _GLIBCXX_NOEXCEPT
	357	{
	358	this->_M_profile_destruct();
	359	_Base::clear();
	360	this->_M_profile_construct();
	361	}
	362
	363	size_type
	364	count(const key_type& __x) const
	365	{
	366	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	367	return _Base::count(__x);
	368	}
c55dc904	369
e20e61b2	370	#if __cplusplus > 201103L
	371	template<typename _Kt,
	372	typename _Req =
	373	typename __has_is_transparent<_Compare, _Kt>::type>
	374	size_type
	375	count(const _Kt& __x) const
	376	{
	377	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	378	return _Base::count(__x);
	379	}
	380	#endif
	381
c55dc904	382	// set operations:
	383	iterator
	384	find(const key_type& __x)
5f70fed5	385	{
1675d1be	386	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
1675d1be	387	return iterator(_Base::find(__x), this);
5f70fed5	388	}
c55dc904	389
c55dc904	390	const_iterator
c55dc904	391	find(const key_type& __x) const
5f70fed5	392	{
1675d1be	393	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
1675d1be	394	return const_iterator(_Base::find(__x), this);
5f70fed5	395	}
c55dc904	396
e20e61b2	397	#if __cplusplus > 201103L
	398	template<typename _Kt,
	399	typename _Req =
	400	typename __has_is_transparent<_Compare, _Kt>::type>
	401	iterator
	402	find(const _Kt& __x)
	403	{
	404	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	405	return { _Base::find(__x), this };
	406	}
	407
	408	template<typename _Kt,
	409	typename _Req =
	410	typename __has_is_transparent<_Compare, _Kt>::type>
	411	const_iterator
	412	find(const _Kt& __x) const
	413	{
	414	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	415	return { _Base::find(__x), this };
	416	}
	417	#endif
	418
c55dc904	419	iterator
c55dc904	420	lower_bound(const key_type& __x)
5f70fed5	421	{
1675d1be	422	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	423	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
	424	return iterator(_Base::lower_bound(__x), this);
5f70fed5	425	}
c55dc904	426
c55dc904	427	const_iterator
c55dc904	428	lower_bound(const key_type& __x) const
5f70fed5	429	{
1675d1be	430	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	431	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
	432	return const_iterator(_Base::lower_bound(__x), this);
5f70fed5	433	}
c55dc904	434
e20e61b2	435	#if __cplusplus > 201103L
	436	template<typename _Kt,
	437	typename _Req =
	438	typename __has_is_transparent<_Compare, _Kt>::type>
	439	iterator
	440	lower_bound(const _Kt& __x)
	441	{
	442	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	443	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
	444	return { _Base::lower_bound(__x), this };
	445	}
	446
	447	template<typename _Kt,
	448	typename _Req =
	449	typename __has_is_transparent<_Compare, _Kt>::type>
	450	const_iterator
	451	lower_bound(const _Kt& __x) const
	452	{
	453	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	454	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
	455	return { _Base::lower_bound(__x), this };
	456	}
	457	#endif
	458
c55dc904	459	iterator
c55dc904	460	upper_bound(const key_type& __x)
5f70fed5	461	{
1675d1be	462	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	463	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
	464	return iterator(_Base::upper_bound(__x), this);
5f70fed5	465	}
c55dc904	466
c55dc904	467	const_iterator
c55dc904	468	upper_bound(const key_type& __x) const
5f70fed5	469	{
1675d1be	470	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	471	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
	472	return const_iterator(_Base::upper_bound(__x), this);
5f70fed5	473	}
c55dc904	474
e20e61b2	475	#if __cplusplus > 201103L
	476	template<typename _Kt,
	477	typename _Req =
	478	typename __has_is_transparent<_Compare, _Kt>::type>
	479	iterator
	480	upper_bound(const _Kt& __x)
	481	{
	482	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	483	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
	484	return { _Base::upper_bound(__x), this };
	485	}
	486
	487	template<typename _Kt,
	488	typename _Req =
	489	typename __has_is_transparent<_Compare, _Kt>::type>
	490	const_iterator
	491	upper_bound(const _Kt& __x) const
	492	{
	493	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	494	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
	495	return { _Base::upper_bound(__x), this };
	496	}
	497	#endif
	498
5f70fed5	499	std::pair<iterator, iterator>
c55dc904	500	equal_range(const key_type& __x)
c55dc904	501	{
1675d1be	502	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	503	std::pair<_Base_iterator, _Base_iterator> __base_ret
	504	= _Base::equal_range(__x);
	505	return std::make_pair(iterator(__base_ret.first, this),
	506	iterator(__base_ret.second, this));
c55dc904	507	}
c55dc904	508
5f70fed5	509	std::pair<const_iterator, const_iterator>
c55dc904	510	equal_range(const key_type& __x) const
c55dc904	511	{
1675d1be	512	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	513	std::pair<_Base_const_iterator, _Base_const_iterator> __base_ret
	514	= _Base::equal_range(__x);
	515	return std::make_pair(const_iterator(__base_ret.first, this),
	516	const_iterator(__base_ret.second, this));
c55dc904	517	}
c55dc904	518
e20e61b2	519	#if __cplusplus > 201103L
	520	template<typename _Kt,
	521	typename _Req =
	522	typename __has_is_transparent<_Compare, _Kt>::type>
	523	std::pair<iterator, iterator>
	524	equal_range(const _Kt& __x)
	525	{
	526	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	527	auto __res = _Base::equal_range(__x);
	528	return { { __res.first, this }, { __res.second, this } };
	529	}
	530
	531	template<typename _Kt,
	532	typename _Req =
	533	typename __has_is_transparent<_Compare, _Kt>::type>
	534	std::pair<const_iterator, const_iterator>
	535	equal_range(const _Kt& __x) const
	536	{
	537	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
	538	auto __res = _Base::equal_range(__x);
	539	return { { __res.first, this }, { __res.second, this } };
	540	}
	541	#endif
	542
c55dc904	543	_Base&
5f70fed5	544	_M_base() _GLIBCXX_NOEXCEPT { return *this; }
c55dc904	545
c55dc904	546	const _Base&
5f70fed5	547	_M_base() const _GLIBCXX_NOEXCEPT { return *this; }
	548
	549	private:
	550	/** If hint is used we consider that the map and unordered_map
	551	* operations have equivalent insertion cost so we do not update metrics
	552	* about it.
	553	* Note that to find out if hint has been used is libstdc++
ea160a81	554	* implementation dependent.
5f70fed5	555	*/
5f70fed5	556	bool
1675d1be	557	_M_hint_used(_Base_const_iterator __hint, _Base_iterator __res)
5f70fed5	558	{
ea160a81	559	return (__hint == __res
1675d1be	560	\|\| (__hint == _M_base().end() && ++__res == _M_base().end())
	561	\|\| (__hint != _M_base().end() && (++__hint == __res
	562	\|\| ++__res == --__hint)));
5f70fed5	563	}
1675d1be	564
	565	template<typename _K1, typename _C1, typename _A1>
	566	friend bool
	567	operator==(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);
	568
	569	template<typename _K1, typename _C1, typename _A1>
	570	friend bool
	571	operator<(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);
c55dc904	572	};
	573
	574	template<typename _Key, typename _Compare, typename _Allocator>
	575	inline bool
	576	operator==(const set<_Key, _Compare, _Allocator>& __lhs,
	577	const set<_Key, _Compare, _Allocator>& __rhs)
1675d1be	578	{
	579	__profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
	580	__profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
	581	return __lhs._M_base() == __rhs._M_base();
	582	}
c55dc904	583
	584	template<typename _Key, typename _Compare, typename _Allocator>
	585	inline bool
1675d1be	586	operator<(const set<_Key, _Compare, _Allocator>& __lhs,
	587	const set<_Key, _Compare, _Allocator>& __rhs)
	588	{
	589	__profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
	590	__profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
	591	return __lhs._M_base() < __rhs._M_base();
	592	}
c55dc904	593
	594	template<typename _Key, typename _Compare, typename _Allocator>
	595	inline bool
1675d1be	596	operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
	597	const set<_Key, _Compare, _Allocator>& __rhs)
	598	{ return !(__lhs == __rhs); }
c55dc904	599
	600	template<typename _Key, typename _Compare, typename _Allocator>
	601	inline bool
	602	operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
	603	const set<_Key, _Compare, _Allocator>& __rhs)
1675d1be	604	{ return !(__rhs < __lhs); }
c55dc904	605
	606	template<typename _Key, typename _Compare, typename _Allocator>
	607	inline bool
	608	operator>=(const set<_Key, _Compare, _Allocator>& __lhs,
	609	const set<_Key, _Compare, _Allocator>& __rhs)
1675d1be	610	{ return !(__lhs < __rhs); }
c55dc904	611
	612	template<typename _Key, typename _Compare, typename _Allocator>
	613	inline bool
	614	operator>(const set<_Key, _Compare, _Allocator>& __lhs,
	615	const set<_Key, _Compare, _Allocator>& __rhs)
1675d1be	616	{ return __rhs < __lhs; }
c55dc904	617
	618	template<typename _Key, typename _Compare, typename _Allocator>
	619	void
	620	swap(set<_Key, _Compare, _Allocator>& __x,
	621	set<_Key, _Compare, _Allocator>& __y)
02769f1f	622	_GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
c55dc904	623	{ return __x.swap(__y); }
	624
	625	} // namespace __profile
	626	} // namespace std
	627
	628	#endif