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

// Profiling map implementation -*- C++ -*-

// Copyright (C) 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 along
// with this library; see the file COPYING3.  If not see
// <http://www.gnu.org/licenses/>.

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

#ifndef _GLIBCXX_PROFILE_MAP_H
#define _GLIBCXX_PROFILE_MAP_H 1

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

namespace std _GLIBCXX_VISIBILITY(default)
{
namespace __profile
{
  /// Class std::map wrapper with performance instrumentation.
  template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
	   typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
    class map
    : public _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator>
    {
      typedef _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator> _Base;

    public:
      // types:
      typedef _Key                                  key_type;
      typedef _Tp                                   mapped_type;
      typedef std::pair<const _Key, _Tp>            value_type;
      typedef _Compare                              key_compare;
      typedef _Allocator                            allocator_type;
      typedef typename _Base::reference             reference;
      typedef typename _Base::const_reference       const_reference;

      typedef typename _Base::iterator       iterator;
      typedef typename _Base::const_iterator       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.1.1 construct/copy/destroy:
      explicit
      map(const _Compare& __comp = _Compare(),
	  const _Allocator& __a = _Allocator())
      : _Base(__comp, __a)
      { __profcxx_map_to_unordered_map_construct(this); }

#ifdef __GXX_EXPERIMENTAL_CXX0X__
      template<typename _InputIterator,
	       typename = std::_RequireInputIter<_InputIterator>>
#else
      template<typename _InputIterator>
#endif
        map(_InputIterator __first, _InputIterator __last,
	    const _Compare& __comp = _Compare(),
	    const _Allocator& __a = _Allocator())
	: _Base(__first, __last, __comp, __a)
        { __profcxx_map_to_unordered_map_construct(this); }

      map(const map& __x)
      : _Base(__x)
      { __profcxx_map_to_unordered_map_construct(this); }

      map(const _Base& __x)
      : _Base(__x)
      { __profcxx_map_to_unordered_map_construct(this); }

#ifdef __GXX_EXPERIMENTAL_CXX0X__
      map(map&& __x)
      noexcept(is_nothrow_copy_constructible<_Compare>::value)
      : _Base(std::move(__x))
      { }

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

      ~map() _GLIBCXX_NOEXCEPT
      { __profcxx_map_to_unordered_map_destruct(this); }

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

#ifdef __GXX_EXPERIMENTAL_CXX0X__
      map&
      operator=(map&& __x)
      {
	// NB: DR 1204.
	// NB: DR 675.
	this->clear();
	this->swap(__x);
	return *this;
      }

      map&
      operator=(initializer_list<value_type> __l)
      {
	this->clear();
	this->insert(__l);
	return *this;
      }
#endif

      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 133. map missing get_allocator()
      using _Base::get_allocator;

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

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

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

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

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

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

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

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

#ifdef __GXX_EXPERIMENTAL_CXX0X__
      const_iterator
      cbegin() const noexcept
      { return const_iterator(_Base::begin()); }

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

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

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

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

      // 23.3.1.2 element access:
      mapped_type&
      operator[](const key_type& __k)
      {
        __profcxx_map_to_unordered_map_find(this, size());
        return _Base::operator[](__k);
      }

#ifdef __GXX_EXPERIMENTAL_CXX0X__
      mapped_type&
      operator[](key_type&& __k)
      {
        __profcxx_map_to_unordered_map_find(this, size());
        return _Base::operator[](std::move(__k));
      }
#endif

      mapped_type&
      at(const key_type& __k)
      {
        __profcxx_map_to_unordered_map_find(this, size());
        return _Base::at(__k);
      }

      const mapped_type&
      at(const key_type& __k) const
      {
        __profcxx_map_to_unordered_map_find(this, size());
        return _Base::at(__k);
      }

      // modifiers:
#ifdef __GXX_EXPERIMENTAL_CXX0X__
      template<typename... _Args>
	std::pair<iterator, bool>
	emplace(_Args&&... __args)
	{
	  __profcxx_map_to_unordered_map_insert(this, size(), 1);
	  auto __res = _Base::emplace(std::forward<_Args>(__args)...);
	  return std::pair<iterator, bool>(iterator(__res.first),
					   __res.second);
	}

      template<typename... _Args>
	iterator
	emplace_hint(const_iterator __pos, _Args&&... __args)
	{
	  size_type size_before = size();
	  auto __res = _Base::emplace_hint(__pos,
					   std::forward<_Args>(__args)...);
	  __profcxx_map_to_unordered_map_insert(this, size_before,
						size() - size_before);
	  return __res;
	}
#endif

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

#ifdef __GXX_EXPERIMENTAL_CXX0X__
      template<typename _Pair, typename = typename
	       std::enable_if<std::is_constructible<value_type,
						    _Pair&&>::value>::type>
        std::pair<iterator, bool>
        insert(_Pair&& __x)
        {
	  __profcxx_map_to_unordered_map_insert(this, size(), 1);
	  typedef typename _Base::iterator _Base_iterator;
	  std::pair<_Base_iterator, bool> __res
	    = _Base::insert(std::forward<_Pair>(__x));
	  return std::pair<iterator, bool>(iterator(__res.first),
					   __res.second);
	}
#endif

#ifdef __GXX_EXPERIMENTAL_CXX0X__
      void
      insert(std::initializer_list<value_type> __list)
      { 
        size_type size_before = size();
        _Base::insert(__list); 
        __profcxx_map_to_unordered_map_insert(this, size_before, 
					      size() - size_before);
      }
#endif

      iterator
#ifdef __GXX_EXPERIMENTAL_CXX0X__
      insert(const_iterator __position, const value_type& __x)
#else
      insert(iterator __position, const value_type& __x)
#endif
      {
        size_type size_before = size();
	iterator __i = iterator(_Base::insert(__position, __x));
        __profcxx_map_to_unordered_map_insert(this, size_before,
					      size() - size_before);
	return __i;
      }

#ifdef __GXX_EXPERIMENTAL_CXX0X__
      template<typename _Pair, typename = typename
	       std::enable_if<std::is_constructible<value_type,
						    _Pair&&>::value>::type>
        iterator
        insert(const_iterator __position, _Pair&& __x)
        {
	  size_type size_before = size();
	  iterator __i
	    = iterator(_Base::insert(__position, std::forward<_Pair>(__x)));
	  __profcxx_map_to_unordered_map_insert(this, size_before, 
						size() - size_before);
	  return __i;
      }
#endif

#ifdef __GXX_EXPERIMENTAL_CXX0X__
      template<typename _InputIterator,
	       typename = std::_RequireInputIter<_InputIterator>>
#else
      template<typename _InputIterator>
#endif
        void
        insert(_InputIterator __first, _InputIterator __last)
        {
          size_type size_before = size();
	  _Base::insert(__first, __last);
          __profcxx_map_to_unordered_map_insert(this, size_before, 
                                                size() - size_before);
	}

#ifdef __GXX_EXPERIMENTAL_CXX0X__
      iterator
      erase(const_iterator __position)
      {
	iterator __i = _Base::erase(__position);
        __profcxx_map_to_unordered_map_erase(this, size(), 1);
        return __i;
      }

      iterator
      erase(iterator __position)
      { return erase(const_iterator(__position)); }
#else
      void
      erase(iterator __position)
      {
	_Base::erase(__position);
        __profcxx_map_to_unordered_map_erase(this, size(), 1);
      }
#endif

      size_type
      erase(const key_type& __x)
      {
	iterator __victim = find(__x);
	if (__victim == end())
	  return 0;
	else
	{
	  _Base::erase(__victim);
	  return 1;
	}
      }

#ifdef __GXX_EXPERIMENTAL_CXX0X__
      iterator
      erase(const_iterator __first, const_iterator __last)
      { return iterator(_Base::erase(__first, __last)); }
#else
      void
      erase(iterator __first, iterator __last)
      { _Base::erase(__first, __last); }
#endif

      void
      swap(map& __x)
      { _Base::swap(__x); }

      void
      clear() _GLIBCXX_NOEXCEPT
      { this->erase(begin(), end()); }

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

      // 23.3.1.3 map operations:
      iterator
      find(const key_type& __x)
      {
        __profcxx_map_to_unordered_map_find(this, size());
        return iterator(_Base::find(__x));
      }

      const_iterator
      find(const key_type& __x) const
      {
        __profcxx_map_to_unordered_map_find(this, size());
        return const_iterator(_Base::find(__x));
      }

      size_type
      count(const key_type& __x) const
      {
        __profcxx_map_to_unordered_map_find(this, size());
        return _Base::count(__x);
      }

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

      const_iterator
      lower_bound(const key_type& __x) const
      { 
        __profcxx_map_to_unordered_map_invalidate(this);
        return const_iterator(_Base::lower_bound(__x)); 
      }

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

      const_iterator
      upper_bound(const key_type& __x) const
      { 
        __profcxx_map_to_unordered_map_invalidate(this);
        return const_iterator(_Base::upper_bound(__x)); 
      }

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

      std::pair<const_iterator,const_iterator>
      equal_range(const key_type& __x) const
      {
        __profcxx_map_to_unordered_map_find(this, size());
	typedef typename _Base::const_iterator _Base_const_iterator;
	std::pair<_Base_const_iterator, _Base_const_iterator> __res =
	_Base::equal_range(__x);
	return std::make_pair(const_iterator(__res.first),
			      const_iterator(__res.second));
      }

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

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

    };

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

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

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

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

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

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

  template<typename _Key, typename _Tp,
	   typename _Compare, typename _Allocator>
    inline void
    swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs,
	 map<_Key, _Tp, _Compare, _Allocator>& __rhs)
    { __lhs.swap(__rhs); }

} // namespace __profile
} // namespace std

#endif
Commit	Line	Data
1218d701 SR	1	// Profiling map implementation -- C++ --
1218d701 SR	2
57cee56a	3	// Copyright (C) 2009, 2010, 2011, 2012 Free Software Foundation, Inc.
1218d701 SR	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
4bee90f7	8	// Free Software Foundation; either version 3, or (at your option)
1218d701	9	// any later version.
4bee90f7	10	//
1218d701 SR	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.
1889b253 PC	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
1218d701	20	// You should have received a copy of the GNU General Public License along
4bee90f7 PC	21	// with this library; see the file COPYING3. If not see
4bee90f7 PC	22	// <http://www.gnu.org/licenses/>.
1218d701 SR	23
	24	/** @file profile/map.h
	25	* This file is a GNU profile extension to the Standard C++ Library.
	26	*/
	27
	28	#ifndef _GLIBCXX_PROFILE_MAP_H
	29	#define _GLIBCXX_PROFILE_MAP_H 1
	30
	31	#include <utility>
	32	#include <profile/base.h>
	33
12ffa228	34	namespace std _GLIBCXX_VISIBILITY(default)
1218d701 SR	35	{
	36	namespace __profile
	37	{
9ee6a740	38	/// Class std::map wrapper with performance instrumentation.
1218d701 SR	39	template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
	40	typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
	41	class map
12ffa228	42	: public _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator>
1218d701	43	{
12ffa228	44	typedef _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator> _Base;
1218d701 SR	45
	46	public:
	47	// types:
	48	typedef _Key key_type;
	49	typedef _Tp mapped_type;
	50	typedef std::pair<const _Key, _Tp> value_type;
	51	typedef _Compare key_compare;
	52	typedef _Allocator allocator_type;
	53	typedef typename _Base::reference reference;
	54	typedef typename _Base::const_reference const_reference;
	55
	56	typedef typename _Base::iterator iterator;
	57	typedef typename _Base::const_iterator const_iterator;
	58	typedef typename _Base::size_type size_type;
	59	typedef typename _Base::difference_type difference_type;
	60	typedef typename _Base::pointer pointer;
	61	typedef typename _Base::const_pointer const_pointer;
	62	typedef std::reverse_iterator<iterator> reverse_iterator;
	63	typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
	64
1218d701	65	// 23.3.1.1 construct/copy/destroy:
c7d42abb PC	66	explicit
	67	map(const _Compare& __comp = _Compare(),
	68	const _Allocator& __a = _Allocator())
	69	: _Base(__comp, __a)
	70	{ __profcxx_map_to_unordered_map_construct(this); }
1218d701	71
3c7d8b03 JW	72	#ifdef __GXX_EXPERIMENTAL_CXX0X__
	73	template<typename _InputIterator,
	74	typename = std::_RequireInputIter<_InputIterator>>
	75	#else
1218d701	76	template<typename _InputIterator>
3c7d8b03	77	#endif
1218d701 SR	78	map(_InputIterator __first, _InputIterator __last,
	79	const _Compare& __comp = _Compare(),
	80	const _Allocator& __a = _Allocator())
c7d42abb PC	81	: _Base(__first, __last, __comp, __a)
c7d42abb PC	82	{ __profcxx_map_to_unordered_map_construct(this); }
1218d701 SR	83
1218d701 SR	84	map(const map& __x)
c7d42abb PC	85	: _Base(__x)
c7d42abb PC	86	{ __profcxx_map_to_unordered_map_construct(this); }
1218d701 SR	87
1218d701 SR	88	map(const _Base& __x)
c7d42abb PC	89	: _Base(__x)
c7d42abb PC	90	{ __profcxx_map_to_unordered_map_construct(this); }
1218d701 SR	91
	92	#ifdef __GXX_EXPERIMENTAL_CXX0X__
	93	map(map&& __x)
6f59ea25	94	noexcept(is_nothrow_copy_constructible<_Compare>::value)
5f1fd346	95	: _Base(std::move(__x))
1218d701 SR	96	{ }
	97
	98	map(initializer_list<value_type> __l,
	99	const _Compare& __c = _Compare(),
	100	const allocator_type& __a = allocator_type())
	101	: _Base(__l, __c, __a) { }
	102	#endif
	103
6f59ea25	104	~map() _GLIBCXX_NOEXCEPT
c7d42abb	105	{ __profcxx_map_to_unordered_map_destruct(this); }
1218d701 SR	106
	107	map&
	108	operator=(const map& __x)
	109	{
	110	static_cast<_Base>(this) = __x;
	111	return *this;
	112	}
	113
	114	#ifdef __GXX_EXPERIMENTAL_CXX0X__
	115	map&
	116	operator=(map&& __x)
	117	{
0462fd5e PC	118	// NB: DR 1204.
	119	// NB: DR 675.
	120	this->clear();
	121	this->swap(__x);
1218d701 SR	122	return *this;
	123	}
	124
	125	map&
	126	operator=(initializer_list<value_type> __l)
	127	{
	128	this->clear();
	129	this->insert(__l);
	130	return *this;
	131	}
	132	#endif
	133
	134	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	135	// 133. map missing get_allocator()
	136	using _Base::get_allocator;
	137
	138	// iterators:
	139	iterator
d3677132	140	begin() _GLIBCXX_NOEXCEPT
1218d701 SR	141	{ return _Base::begin(); }
	142
	143	const_iterator
d3677132	144	begin() const _GLIBCXX_NOEXCEPT
1218d701 SR	145	{ return _Base::begin(); }
	146
	147	iterator
d3677132	148	end() _GLIBCXX_NOEXCEPT
1218d701 SR	149	{ return _Base::end(); }
	150
	151	const_iterator
d3677132	152	end() const _GLIBCXX_NOEXCEPT
1218d701 SR	153	{ return _Base::end(); }
	154
	155	reverse_iterator
d3677132	156	rbegin() _GLIBCXX_NOEXCEPT
1218d701 SR	157	{
	158	__profcxx_map_to_unordered_map_invalidate(this);
	159	return reverse_iterator(end());
	160	}
	161
	162	const_reverse_iterator
d3677132	163	rbegin() const _GLIBCXX_NOEXCEPT
1218d701 SR	164	{
	165	__profcxx_map_to_unordered_map_invalidate(this);
	166	return const_reverse_iterator(end());
	167	}
	168
	169	reverse_iterator
d3677132	170	rend() _GLIBCXX_NOEXCEPT
1218d701 SR	171	{
	172	__profcxx_map_to_unordered_map_invalidate(this);
	173	return reverse_iterator(begin());
	174	}
	175
	176	const_reverse_iterator
d3677132	177	rend() const _GLIBCXX_NOEXCEPT
1218d701 SR	178	{
	179	__profcxx_map_to_unordered_map_invalidate(this);
	180	return const_reverse_iterator(begin());
	181	}
	182
	183	#ifdef __GXX_EXPERIMENTAL_CXX0X__
	184	const_iterator
d3677132	185	cbegin() const noexcept
1218d701 SR	186	{ return const_iterator(_Base::begin()); }
	187
	188	const_iterator
d3677132	189	cend() const noexcept
1218d701 SR	190	{ return const_iterator(_Base::end()); }
	191
	192	const_reverse_iterator
d3677132	193	crbegin() const noexcept
1218d701 SR	194	{
	195	__profcxx_map_to_unordered_map_invalidate(this);
	196	return const_reverse_iterator(end());
	197	}
	198
	199	const_reverse_iterator
d3677132	200	crend() const noexcept
1218d701 SR	201	{
	202	__profcxx_map_to_unordered_map_invalidate(this);
	203	return const_reverse_iterator(begin());
	204	}
	205	#endif
	206
	207	// capacity:
	208	using _Base::empty;
	209	using _Base::size;
	210	using _Base::max_size;
	211
	212	// 23.3.1.2 element access:
	213	mapped_type&
	214	operator[](const key_type& __k)
	215	{
	216	__profcxx_map_to_unordered_map_find(this, size());
	217	return _Base::operator[](__k);
	218	}
	219
e6a05448 PC	220	#ifdef __GXX_EXPERIMENTAL_CXX0X__
	221	mapped_type&
	222	operator[](key_type&& __k)
	223	{
	224	__profcxx_map_to_unordered_map_find(this, size());
	225	return _Base::operator[](std::move(__k));
	226	}
	227	#endif
	228
1218d701 SR	229	mapped_type&
	230	at(const key_type& __k)
	231	{
	232	__profcxx_map_to_unordered_map_find(this, size());
	233	return _Base::at(__k);
	234	}
	235
	236	const mapped_type&
	237	at(const key_type& __k) const
	238	{
	239	__profcxx_map_to_unordered_map_find(this, size());
	240	return _Base::at(__k);
	241	}
	242
	243	// modifiers:
55826ab6 FD	244	#ifdef __GXX_EXPERIMENTAL_CXX0X__
	245	template<typename... _Args>
	246	std::pair<iterator, bool>
	247	emplace(_Args&&... __args)
	248	{
	249	__profcxx_map_to_unordered_map_insert(this, size(), 1);
	250	auto __res = _Base::emplace(std::forward<_Args>(__args)...);
	251	return std::pair<iterator, bool>(iterator(__res.first),
	252	__res.second);
	253	}
	254
	255	template<typename... _Args>
	256	iterator
	257	emplace_hint(const_iterator __pos, _Args&&... __args)
	258	{
	259	size_type size_before = size();
3c7d8b03	260	auto __res = _Base::emplace_hint(__pos,
0a011b17	261	std::forward<_Args>(__args)...);
55826ab6 FD	262	__profcxx_map_to_unordered_map_insert(this, size_before,
55826ab6 FD	263	size() - size_before);
31828bd3	264	return __res;
55826ab6 FD	265	}
	266	#endif
	267
1218d701 SR	268	std::pair<iterator, bool>
	269	insert(const value_type& __x)
	270	{
	271	__profcxx_map_to_unordered_map_insert(this, size(), 1);
	272	typedef typename _Base::iterator _Base_iterator;
	273	std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
	274	return std::pair<iterator, bool>(iterator(__res.first),
	275	__res.second);
	276	}
	277
e6a05448 PC	278	#ifdef __GXX_EXPERIMENTAL_CXX0X__
e6a05448 PC	279	template<typename _Pair, typename = typename
57cee56a PC	280	std::enable_if<std::is_constructible<value_type,
57cee56a PC	281	_Pair&&>::value>::type>
e6a05448 PC	282	std::pair<iterator, bool>
	283	insert(_Pair&& __x)
	284	{
	285	__profcxx_map_to_unordered_map_insert(this, size(), 1);
	286	typedef typename _Base::iterator _Base_iterator;
	287	std::pair<_Base_iterator, bool> __res
	288	= _Base::insert(std::forward<_Pair>(__x));
	289	return std::pair<iterator, bool>(iterator(__res.first),
	290	__res.second);
	291	}
	292	#endif
	293
1218d701 SR	294	#ifdef __GXX_EXPERIMENTAL_CXX0X__
	295	void
	296	insert(std::initializer_list<value_type> __list)
	297	{
	298	size_type size_before = size();
	299	_Base::insert(__list);
	300	__profcxx_map_to_unordered_map_insert(this, size_before,
7606bd11	301	size() - size_before);
1218d701 SR	302	}
	303	#endif
	304
	305	iterator
7606bd11 PC	306	#ifdef __GXX_EXPERIMENTAL_CXX0X__
	307	insert(const_iterator __position, const value_type& __x)
	308	#else
1218d701	309	insert(iterator __position, const value_type& __x)
7606bd11	310	#endif
1218d701 SR	311	{
1218d701 SR	312	size_type size_before = size();
7606bd11	313	iterator __i = iterator(_Base::insert(__position, __x));
55826ab6	314	__profcxx_map_to_unordered_map_insert(this, size_before,
7606bd11 PC	315	size() - size_before);
7606bd11 PC	316	return __i;
1218d701 SR	317	}
1218d701 SR	318
e6a05448 PC	319	#ifdef __GXX_EXPERIMENTAL_CXX0X__
e6a05448 PC	320	template<typename _Pair, typename = typename
57cee56a PC	321	std::enable_if<std::is_constructible<value_type,
57cee56a PC	322	_Pair&&>::value>::type>
e6a05448 PC	323	iterator
	324	insert(const_iterator __position, _Pair&& __x)
	325	{
	326	size_type size_before = size();
	327	iterator __i
	328	= iterator(_Base::insert(__position, std::forward<_Pair>(__x)));
	329	__profcxx_map_to_unordered_map_insert(this, size_before,
	330	size() - size_before);
	331	return __i;
	332	}
	333	#endif
	334
3c7d8b03 JW	335	#ifdef __GXX_EXPERIMENTAL_CXX0X__
	336	template<typename _InputIterator,
	337	typename = std::_RequireInputIter<_InputIterator>>
	338	#else
1218d701	339	template<typename _InputIterator>
3c7d8b03	340	#endif
1218d701 SR	341	void
	342	insert(_InputIterator __first, _InputIterator __last)
	343	{
	344	size_type size_before = size();
	345	_Base::insert(__first, __last);
	346	__profcxx_map_to_unordered_map_insert(this, size_before,
	347	size() - size_before);
	348	}
	349
	350	#ifdef __GXX_EXPERIMENTAL_CXX0X__
	351	iterator
7606bd11	352	erase(const_iterator __position)
1218d701 SR	353	{
	354	iterator __i = _Base::erase(__position);
	355	__profcxx_map_to_unordered_map_erase(this, size(), 1);
	356	return __i;
	357	}
6dc88283 PC	358
	359	iterator
	360	erase(iterator __position)
	361	{ return erase(const_iterator(__position)); }
1218d701 SR	362	#else
	363	void
	364	erase(iterator __position)
	365	{
	366	_Base::erase(__position);
	367	__profcxx_map_to_unordered_map_erase(this, size(), 1);
	368	}
	369	#endif
	370
	371	size_type
	372	erase(const key_type& __x)
	373	{
	374	iterator __victim = find(__x);
	375	if (__victim == end())
	376	return 0;
	377	else
	378	{
	379	_Base::erase(__victim);
	380	return 1;
	381	}
	382	}
	383
5ab06c6d PC	384	#ifdef __GXX_EXPERIMENTAL_CXX0X__
5ab06c6d PC	385	iterator
7606bd11 PC	386	erase(const_iterator __first, const_iterator __last)
7606bd11 PC	387	{ return iterator(_Base::erase(__first, __last)); }
5ab06c6d	388	#else
1218d701 SR	389	void
1218d701 SR	390	erase(iterator __first, iterator __last)
7606bd11	391	{ _Base::erase(__first, __last); }
5ab06c6d	392	#endif
1218d701 SR	393
1218d701 SR	394	void
1218d701	395	swap(map& __x)
7606bd11	396	{ _Base::swap(__x); }
1218d701 SR	397
1218d701 SR	398	void
d3677132	399	clear() _GLIBCXX_NOEXCEPT
1218d701 SR	400	{ this->erase(begin(), end()); }
	401
	402	// observers:
	403	using _Base::key_comp;
	404	using _Base::value_comp;
	405
	406	// 23.3.1.3 map operations:
	407	iterator
	408	find(const key_type& __x)
	409	{
	410	__profcxx_map_to_unordered_map_find(this, size());
	411	return iterator(_Base::find(__x));
	412	}
	413
	414	const_iterator
	415	find(const key_type& __x) const
	416	{
	417	__profcxx_map_to_unordered_map_find(this, size());
	418	return const_iterator(_Base::find(__x));
	419	}
	420
	421	size_type
	422	count(const key_type& __x) const
	423	{
	424	__profcxx_map_to_unordered_map_find(this, size());
	425	return _Base::count(__x);
	426	}
	427
	428	iterator
	429	lower_bound(const key_type& __x)
	430	{
	431	__profcxx_map_to_unordered_map_invalidate(this);
	432	return iterator(_Base::lower_bound(__x));
	433	}
	434
	435	const_iterator
	436	lower_bound(const key_type& __x) const
	437	{
	438	__profcxx_map_to_unordered_map_invalidate(this);
	439	return const_iterator(_Base::lower_bound(__x));
	440	}
	441
	442	iterator
	443	upper_bound(const key_type& __x)
	444	{
	445	__profcxx_map_to_unordered_map_invalidate(this);
	446	return iterator(_Base::upper_bound(__x));
	447	}
	448
	449	const_iterator
	450	upper_bound(const key_type& __x) const
	451	{
	452	__profcxx_map_to_unordered_map_invalidate(this);
	453	return const_iterator(_Base::upper_bound(__x));
	454	}
	455
	456	std::pair<iterator,iterator>
	457	equal_range(const key_type& __x)
	458	{
	459	typedef typename _Base::iterator _Base_iterator;
	460	std::pair<_Base_iterator, _Base_iterator> __res =
	461	_Base::equal_range(__x);
	462	return std::make_pair(iterator(__res.first),
	463	iterator(__res.second));
464	}
465
466	std::pair<const_iterator,const_iterator>
467	equal_range(const key_type& __x) const
468	{
469	__profcxx_map_to_unordered_map_find(this, size());
470	typedef typename _Base::const_iterator _Base_const_iterator;
471	std::pair<_Base_const_iterator, _Base_const_iterator> __res =
472	_Base::equal_range(__x);
473	return std::make_pair(const_iterator(__res.first),
474	const_iterator(__res.second));
475	}
476
477	_Base&
d3677132	478	_M_base() _GLIBCXX_NOEXCEPT { return *this; }
1218d701 SR	479
1218d701 SR	480	const _Base&
d3677132	481	_M_base() const _GLIBCXX_NOEXCEPT { return *this; }
1218d701 SR	482
	483	};
	484
	485	template<typename _Key, typename _Tp,
	486	typename _Compare, typename _Allocator>
	487	inline bool
	488	operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
	489	const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
	490	{
	491	__profcxx_map_to_unordered_map_invalidate(&__lhs);
	492	__profcxx_map_to_unordered_map_invalidate(&__rhs);
	493	return __lhs._M_base() == __rhs._M_base();
	494	}
	495
	496	template<typename _Key, typename _Tp,
	497	typename _Compare, typename _Allocator>
	498	inline bool
	499	operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
	500	const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
	501	{
	502	__profcxx_map_to_unordered_map_invalidate(&__lhs);
	503	__profcxx_map_to_unordered_map_invalidate(&__rhs);
	504	return __lhs._M_base() != __rhs._M_base();
	505	}
	506
	507	template<typename _Key, typename _Tp,
	508	typename _Compare, typename _Allocator>
	509	inline bool
	510	operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
	511	const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
	512	{
	513	__profcxx_map_to_unordered_map_invalidate(&__lhs);
	514	__profcxx_map_to_unordered_map_invalidate(&__rhs);
	515	return __lhs._M_base() < __rhs._M_base();
	516	}
	517
	518	template<typename _Key, typename _Tp,
	519	typename _Compare, typename _Allocator>
	520	inline bool
	521	operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
	522	const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
	523	{
	524	__profcxx_map_to_unordered_map_invalidate(&__lhs);
	525	__profcxx_map_to_unordered_map_invalidate(&__rhs);
	526	return __lhs._M_base() <= __rhs._M_base();
	527	}
	528
	529	template<typename _Key, typename _Tp,
	530	typename _Compare, typename _Allocator>
	531	inline bool
	532	operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
	533	const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
	534	{
	535	__profcxx_map_to_unordered_map_invalidate(&__lhs);
	536	__profcxx_map_to_unordered_map_invalidate(&__rhs);
	537	return __lhs._M_base() >= __rhs._M_base();
	538	}
	539
	540	template<typename _Key, typename _Tp,
	541	typename _Compare, typename _Allocator>
	542	inline bool
	543	operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
	544	const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
	545	{
546	__profcxx_map_to_unordered_map_invalidate(&__lhs);
547	__profcxx_map_to_unordered_map_invalidate(&__rhs);
548	return __lhs._M_base() > __rhs._M_base();
549	}
550
551	template<typename _Key, typename _Tp,
552	typename _Compare, typename _Allocator>
553	inline void
554	swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs,
555	map<_Key, _Tp, _Compare, _Allocator>& __rhs)
556	{ __lhs.swap(__rhs); }
557
558	} // namespace __profile
559	} // namespace std
560
561	#endif