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

// Debugging multimap implementation -*- C++ -*-

// Copyright (C) 2003-2015 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/multimap.h
 *  This file is a GNU debug extension to the Standard C++ Library.
 */

#ifndef _GLIBCXX_DEBUG_MULTIMAP_H
#define _GLIBCXX_DEBUG_MULTIMAP_H 1

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

namespace std _GLIBCXX_VISIBILITY(default)
{
namespace __debug
{
  /// Class std::multimap with safety/checking/debug instrumentation.
  template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
	   typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
    class multimap
      : public __gnu_debug::_Safe_container<
	multimap<_Key, _Tp, _Compare, _Allocator>, _Allocator,
	__gnu_debug::_Safe_node_sequence>,
	public _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator>
    {
      typedef _GLIBCXX_STD_C::multimap<
	_Key, _Tp, _Compare, _Allocator>			_Base;
      typedef __gnu_debug::_Safe_container<
	multimap, _Allocator, __gnu_debug::_Safe_node_sequence>	_Safe;

      typedef typename _Base::const_iterator	_Base_const_iterator;
      typedef typename _Base::iterator		_Base_iterator;
      typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;

    public:
      // types:
      typedef _Key					key_type;
      typedef _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 __gnu_debug::_Safe_iterator<_Base_iterator, multimap>
							iterator;
      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
					  multimap>	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:

#if __cplusplus < 201103L
      multimap() : _Base() { }

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

      ~multimap() { }
#else
      multimap() = default;
      multimap(const multimap&) = default;
      multimap(multimap&&) = default;

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

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

      multimap(const multimap& __m, const allocator_type& __a)
      : _Base(__m, __a) { }

      multimap(multimap&& __m, const allocator_type& __a)
      : _Safe(std::move(__m._M_safe()), __a),
	_Base(std::move(__m._M_base()), __a) { }

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

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

      ~multimap() = default;
#endif

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

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

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

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

      multimap&
      operator=(multimap&&) = default;

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

      using _Base::get_allocator;

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

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

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

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

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

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

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

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

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

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

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

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

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

      // modifiers:
#if __cplusplus >= 201103L
      template<typename... _Args>
	iterator
	emplace(_Args&&... __args)
	{
	  return iterator(_Base::emplace(std::forward<_Args>(__args)...), this);
	}

      template<typename... _Args>
	iterator
	emplace_hint(const_iterator __pos, _Args&&... __args)
	{
	  __glibcxx_check_insert(__pos);
	  return iterator(_Base::emplace_hint(__pos.base(),
					      std::forward<_Args>(__args)...),
			  this);
	}
#endif

      iterator
      insert(const value_type& __x)
      { return iterator(_Base::insert(__x), this); }

#if __cplusplus >= 201103L
      template<typename _Pair, typename = typename
	       std::enable_if<std::is_constructible<value_type,
						    _Pair&&>::value>::type>
	iterator
	insert(_Pair&& __x)
	{ return iterator(_Base::insert(std::forward<_Pair>(__x)), this); }
#endif

#if __cplusplus >= 201103L
      void
      insert(std::initializer_list<value_type> __list)
      { _Base::insert(__list); }
#endif

      iterator
#if __cplusplus >= 201103L
      insert(const_iterator __position, const value_type& __x)
#else
      insert(iterator __position, const value_type& __x)
#endif
      {
	__glibcxx_check_insert(__position);
	return iterator(_Base::insert(__position.base(), __x), this);
      }

#if __cplusplus >= 201103L
      template<typename _Pair, typename = typename
	       std::enable_if<std::is_constructible<value_type,
						    _Pair&&>::value>::type>
	iterator
	insert(const_iterator __position, _Pair&& __x)
	{
	  __glibcxx_check_insert(__position);
	  return iterator(_Base::insert(__position.base(),
					std::forward<_Pair>(__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
      iterator
      erase(const_iterator __position)
      {
	__glibcxx_check_erase(__position);
	this->_M_invalidate_if(_Equal(__position.base()));
	return iterator(_Base::erase(__position.base()), this);
      }

      iterator
      erase(iterator __position)
      { return erase(const_iterator(__position)); }
#else
      void
      erase(iterator __position)
      {
	__glibcxx_check_erase(__position);
	this->_M_invalidate_if(_Equal(__position.base()));
	_Base::erase(__position.base());
      }
#endif

      size_type
      erase(const key_type& __x)
      {
	std::pair<_Base_iterator, _Base_iterator> __victims =
	  _Base::equal_range(__x);
	size_type __count = 0;
	_Base_iterator __victim = __victims.first;
	while (__victim !=  __victims.second)
	  {
	    this->_M_invalidate_if(_Equal(__victim));
	    _Base::erase(__victim++);
	    ++__count;
	  }
	return __count;
      }

#if __cplusplus >= 201103L
      iterator
      erase(const_iterator __first, const_iterator __last)
      {
	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	// 151. can't currently clear() empty container
	__glibcxx_check_erase_range(__first, __last);
	for (_Base_const_iterator __victim = __first.base();
	     __victim != __last.base(); ++__victim)
	  {
	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
				  _M_message(__gnu_debug::__msg_valid_range)
				  ._M_iterator(__first, "first")
				  ._M_iterator(__last, "last"));
	    this->_M_invalidate_if(_Equal(__victim));
	  }
	return iterator(_Base::erase(__first.base(), __last.base()), this);
      }
#else
      void
      erase(iterator __first, iterator __last)
      {
	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	// 151. can't currently clear() empty container
	__glibcxx_check_erase_range(__first, __last);
	for (_Base_iterator __victim = __first.base();
	     __victim != __last.base(); ++__victim)
	  {
	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
				  _M_message(__gnu_debug::__msg_valid_range)
				  ._M_iterator(__first, "first")
				  ._M_iterator(__last, "last"));
	    this->_M_invalidate_if(_Equal(__victim));
	  }
	_Base::erase(__first.base(), __last.base());
      }
#endif

      void
      swap(multimap& __x)
#if __cplusplus >= 201103L
	noexcept( noexcept(declval<_Base>().swap(__x)) )
#endif
      {
	_Safe::_M_swap(__x);
	_Base::swap(__x);
      }

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

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

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

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

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

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

      using _Base::count;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

} // namespace __debug
} // namespace std

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