xref: /dflybsd-src/contrib/gcc-8.0/libstdc++-v3/include/debug/map.h (revision 95059079af47f9a66a175f374f2da1a5020e3255)
138fd1498Szrj // Debugging map implementation -*- C++ -*-
238fd1498Szrj 
338fd1498Szrj // Copyright (C) 2003-2018 Free Software Foundation, Inc.
438fd1498Szrj //
538fd1498Szrj // This file is part of the GNU ISO C++ Library.  This library is free
638fd1498Szrj // software; you can redistribute it and/or modify it under the
738fd1498Szrj // terms of the GNU General Public License as published by the
838fd1498Szrj // Free Software Foundation; either version 3, or (at your option)
938fd1498Szrj // any later version.
1038fd1498Szrj 
1138fd1498Szrj // This library is distributed in the hope that it will be useful,
1238fd1498Szrj // but WITHOUT ANY WARRANTY; without even the implied warranty of
1338fd1498Szrj // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
1438fd1498Szrj // GNU General Public License for more details.
1538fd1498Szrj 
1638fd1498Szrj // Under Section 7 of GPL version 3, you are granted additional
1738fd1498Szrj // permissions described in the GCC Runtime Library Exception, version
1838fd1498Szrj // 3.1, as published by the Free Software Foundation.
1938fd1498Szrj 
2038fd1498Szrj // You should have received a copy of the GNU General Public License and
2138fd1498Szrj // a copy of the GCC Runtime Library Exception along with this program;
2238fd1498Szrj // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
2338fd1498Szrj // <http://www.gnu.org/licenses/>.
2438fd1498Szrj 
2538fd1498Szrj /** @file debug/map.h
2638fd1498Szrj  *  This file is a GNU debug extension to the Standard C++ Library.
2738fd1498Szrj  */
2838fd1498Szrj 
2938fd1498Szrj #ifndef _GLIBCXX_DEBUG_MAP_H
3038fd1498Szrj #define _GLIBCXX_DEBUG_MAP_H 1
3138fd1498Szrj 
3238fd1498Szrj #include <debug/safe_sequence.h>
3338fd1498Szrj #include <debug/safe_container.h>
3438fd1498Szrj #include <debug/safe_iterator.h>
3538fd1498Szrj #include <utility>
3638fd1498Szrj 
_GLIBCXX_VISIBILITY(default)3738fd1498Szrj namespace std _GLIBCXX_VISIBILITY(default)
3838fd1498Szrj {
3938fd1498Szrj namespace __debug
4038fd1498Szrj {
4138fd1498Szrj   /// Class std::map with safety/checking/debug instrumentation.
4238fd1498Szrj   template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
4338fd1498Szrj 	   typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
4438fd1498Szrj     class map
4538fd1498Szrj     : public __gnu_debug::_Safe_container<
4638fd1498Szrj 	map<_Key, _Tp, _Compare, _Allocator>, _Allocator,
4738fd1498Szrj 	__gnu_debug::_Safe_node_sequence>,
4838fd1498Szrj       public _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator>
4938fd1498Szrj     {
5038fd1498Szrj       typedef _GLIBCXX_STD_C::map<
5138fd1498Szrj 	_Key, _Tp, _Compare, _Allocator>			_Base;
5238fd1498Szrj       typedef __gnu_debug::_Safe_container<
5338fd1498Szrj 	map, _Allocator, __gnu_debug::_Safe_node_sequence>	_Safe;
5438fd1498Szrj 
5538fd1498Szrj       typedef typename _Base::const_iterator	_Base_const_iterator;
5638fd1498Szrj       typedef typename _Base::iterator		_Base_iterator;
5738fd1498Szrj       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
5838fd1498Szrj 
5938fd1498Szrj     public:
6038fd1498Szrj       // types:
6138fd1498Szrj       typedef _Key					key_type;
6238fd1498Szrj       typedef _Tp					mapped_type;
6338fd1498Szrj       typedef std::pair<const _Key, _Tp>		value_type;
6438fd1498Szrj       typedef _Compare					key_compare;
6538fd1498Szrj       typedef _Allocator				allocator_type;
6638fd1498Szrj       typedef typename _Base::reference			reference;
6738fd1498Szrj       typedef typename _Base::const_reference		const_reference;
6838fd1498Szrj 
6938fd1498Szrj       typedef __gnu_debug::_Safe_iterator<_Base_iterator, map>
7038fd1498Szrj 							iterator;
7138fd1498Szrj       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, map>
7238fd1498Szrj 							const_iterator;
7338fd1498Szrj 
7438fd1498Szrj       typedef typename _Base::size_type			size_type;
7538fd1498Szrj       typedef typename _Base::difference_type		difference_type;
7638fd1498Szrj       typedef typename _Base::pointer			pointer;
7738fd1498Szrj       typedef typename _Base::const_pointer		const_pointer;
7838fd1498Szrj       typedef std::reverse_iterator<iterator>		reverse_iterator;
7938fd1498Szrj       typedef std::reverse_iterator<const_iterator>	const_reverse_iterator;
8038fd1498Szrj 
8138fd1498Szrj       // 23.3.1.1 construct/copy/destroy:
8238fd1498Szrj 
8338fd1498Szrj #if __cplusplus < 201103L
8438fd1498Szrj       map() : _Base() { }
8538fd1498Szrj 
8638fd1498Szrj       map(const map& __x)
8738fd1498Szrj       : _Base(__x) { }
8838fd1498Szrj 
8938fd1498Szrj       ~map() { }
9038fd1498Szrj #else
9138fd1498Szrj       map() = default;
9238fd1498Szrj       map(const map&) = default;
9338fd1498Szrj       map(map&&) = default;
9438fd1498Szrj 
9538fd1498Szrj       map(initializer_list<value_type> __l,
9638fd1498Szrj 	  const _Compare& __c = _Compare(),
9738fd1498Szrj 	  const allocator_type& __a = allocator_type())
9838fd1498Szrj       : _Base(__l, __c, __a) { }
9938fd1498Szrj 
10038fd1498Szrj       explicit
10138fd1498Szrj       map(const allocator_type& __a)
10238fd1498Szrj       : _Base(__a) { }
10338fd1498Szrj 
10438fd1498Szrj       map(const map& __m, const allocator_type& __a)
10538fd1498Szrj       : _Base(__m, __a) { }
10638fd1498Szrj 
10738fd1498Szrj       map(map&& __m, const allocator_type& __a)
108*58e805e6Szrj       noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) )
10938fd1498Szrj       : _Safe(std::move(__m._M_safe()), __a),
11038fd1498Szrj 	_Base(std::move(__m._M_base()), __a) { }
11138fd1498Szrj 
11238fd1498Szrj       map(initializer_list<value_type> __l, const allocator_type& __a)
11338fd1498Szrj       : _Base(__l, __a) { }
11438fd1498Szrj 
11538fd1498Szrj       template<typename _InputIterator>
11638fd1498Szrj 	map(_InputIterator __first, _InputIterator __last,
11738fd1498Szrj 	    const allocator_type& __a)
11838fd1498Szrj 	: _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
11938fd1498Szrj 								     __last)),
12038fd1498Szrj 		__gnu_debug::__base(__last), __a)
12138fd1498Szrj 	{ }
12238fd1498Szrj 
12338fd1498Szrj       ~map() = default;
12438fd1498Szrj #endif
12538fd1498Szrj 
12638fd1498Szrj       map(const _Base& __x)
12738fd1498Szrj       : _Base(__x) { }
12838fd1498Szrj 
12938fd1498Szrj       explicit map(const _Compare& __comp,
13038fd1498Szrj 		   const _Allocator& __a = _Allocator())
13138fd1498Szrj       : _Base(__comp, __a) { }
13238fd1498Szrj 
13338fd1498Szrj       template<typename _InputIterator>
13438fd1498Szrj 	map(_InputIterator __first, _InputIterator __last,
13538fd1498Szrj 	    const _Compare& __comp = _Compare(),
13638fd1498Szrj 	    const _Allocator& __a = _Allocator())
13738fd1498Szrj 	: _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
13838fd1498Szrj 								     __last)),
13938fd1498Szrj 		__gnu_debug::__base(__last),
14038fd1498Szrj 		__comp, __a) { }
14138fd1498Szrj 
14238fd1498Szrj #if __cplusplus < 201103L
14338fd1498Szrj       map&
14438fd1498Szrj       operator=(const map& __x)
14538fd1498Szrj       {
14638fd1498Szrj 	this->_M_safe() = __x;
14738fd1498Szrj 	_M_base() = __x;
14838fd1498Szrj 	return *this;
14938fd1498Szrj       }
15038fd1498Szrj #else
15138fd1498Szrj       map&
15238fd1498Szrj       operator=(const map&) = default;
15338fd1498Szrj 
15438fd1498Szrj       map&
15538fd1498Szrj       operator=(map&&) = default;
15638fd1498Szrj 
15738fd1498Szrj       map&
15838fd1498Szrj       operator=(initializer_list<value_type> __l)
15938fd1498Szrj       {
16038fd1498Szrj 	_M_base() = __l;
16138fd1498Szrj 	this->_M_invalidate_all();
16238fd1498Szrj 	return *this;
16338fd1498Szrj       }
16438fd1498Szrj #endif
16538fd1498Szrj 
16638fd1498Szrj       // _GLIBCXX_RESOLVE_LIB_DEFECTS
16738fd1498Szrj       // 133. map missing get_allocator()
16838fd1498Szrj       using _Base::get_allocator;
16938fd1498Szrj 
17038fd1498Szrj       // iterators:
17138fd1498Szrj       iterator
17238fd1498Szrj       begin() _GLIBCXX_NOEXCEPT
17338fd1498Szrj       { return iterator(_Base::begin(), this); }
17438fd1498Szrj 
17538fd1498Szrj       const_iterator
17638fd1498Szrj       begin() const _GLIBCXX_NOEXCEPT
17738fd1498Szrj       { return const_iterator(_Base::begin(), this); }
17838fd1498Szrj 
17938fd1498Szrj       iterator
18038fd1498Szrj       end() _GLIBCXX_NOEXCEPT
18138fd1498Szrj       { return iterator(_Base::end(), this); }
18238fd1498Szrj 
18338fd1498Szrj       const_iterator
18438fd1498Szrj       end() const _GLIBCXX_NOEXCEPT
18538fd1498Szrj       { return const_iterator(_Base::end(), this); }
18638fd1498Szrj 
18738fd1498Szrj       reverse_iterator
18838fd1498Szrj       rbegin() _GLIBCXX_NOEXCEPT
18938fd1498Szrj       { return reverse_iterator(end()); }
19038fd1498Szrj 
19138fd1498Szrj       const_reverse_iterator
19238fd1498Szrj       rbegin() const _GLIBCXX_NOEXCEPT
19338fd1498Szrj       { return const_reverse_iterator(end()); }
19438fd1498Szrj 
19538fd1498Szrj       reverse_iterator
19638fd1498Szrj       rend() _GLIBCXX_NOEXCEPT
19738fd1498Szrj       { return reverse_iterator(begin()); }
19838fd1498Szrj 
19938fd1498Szrj       const_reverse_iterator
20038fd1498Szrj       rend() const _GLIBCXX_NOEXCEPT
20138fd1498Szrj       { return const_reverse_iterator(begin()); }
20238fd1498Szrj 
20338fd1498Szrj #if __cplusplus >= 201103L
20438fd1498Szrj       const_iterator
20538fd1498Szrj       cbegin() const noexcept
20638fd1498Szrj       { return const_iterator(_Base::begin(), this); }
20738fd1498Szrj 
20838fd1498Szrj       const_iterator
20938fd1498Szrj       cend() const noexcept
21038fd1498Szrj       { return const_iterator(_Base::end(), this); }
21138fd1498Szrj 
21238fd1498Szrj       const_reverse_iterator
21338fd1498Szrj       crbegin() const noexcept
21438fd1498Szrj       { return const_reverse_iterator(end()); }
21538fd1498Szrj 
21638fd1498Szrj       const_reverse_iterator
21738fd1498Szrj       crend() const noexcept
21838fd1498Szrj       { return const_reverse_iterator(begin()); }
21938fd1498Szrj #endif
22038fd1498Szrj 
22138fd1498Szrj       // capacity:
22238fd1498Szrj       using _Base::empty;
22338fd1498Szrj       using _Base::size;
22438fd1498Szrj       using _Base::max_size;
22538fd1498Szrj 
22638fd1498Szrj       // 23.3.1.2 element access:
22738fd1498Szrj       using _Base::operator[];
22838fd1498Szrj 
22938fd1498Szrj       // _GLIBCXX_RESOLVE_LIB_DEFECTS
23038fd1498Szrj       // DR 464. Suggestion for new member functions in standard containers.
23138fd1498Szrj       using _Base::at;
23238fd1498Szrj 
23338fd1498Szrj       // modifiers:
23438fd1498Szrj #if __cplusplus >= 201103L
23538fd1498Szrj       template<typename... _Args>
23638fd1498Szrj 	std::pair<iterator, bool>
23738fd1498Szrj 	emplace(_Args&&... __args)
23838fd1498Szrj 	{
23938fd1498Szrj 	  auto __res = _Base::emplace(std::forward<_Args>(__args)...);
24038fd1498Szrj 	  return std::pair<iterator, bool>(iterator(__res.first, this),
24138fd1498Szrj 					   __res.second);
24238fd1498Szrj 	}
24338fd1498Szrj 
24438fd1498Szrj       template<typename... _Args>
24538fd1498Szrj 	iterator
24638fd1498Szrj 	emplace_hint(const_iterator __pos, _Args&&... __args)
24738fd1498Szrj 	{
24838fd1498Szrj 	  __glibcxx_check_insert(__pos);
24938fd1498Szrj 	  return iterator(_Base::emplace_hint(__pos.base(),
25038fd1498Szrj 					      std::forward<_Args>(__args)...),
25138fd1498Szrj 			  this);
25238fd1498Szrj 	}
25338fd1498Szrj #endif
25438fd1498Szrj 
25538fd1498Szrj       std::pair<iterator, bool>
25638fd1498Szrj       insert(const value_type& __x)
25738fd1498Szrj       {
25838fd1498Szrj 	std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
25938fd1498Szrj 	return std::pair<iterator, bool>(iterator(__res.first, this),
26038fd1498Szrj 					 __res.second);
26138fd1498Szrj       }
26238fd1498Szrj 
26338fd1498Szrj #if __cplusplus >= 201103L
26438fd1498Szrj       // _GLIBCXX_RESOLVE_LIB_DEFECTS
26538fd1498Szrj       // 2354. Unnecessary copying when inserting into maps with braced-init
26638fd1498Szrj       std::pair<iterator, bool>
26738fd1498Szrj       insert(value_type&& __x)
26838fd1498Szrj       {
26938fd1498Szrj 	auto __res = _Base::insert(std::move(__x));
27038fd1498Szrj 	return { iterator(__res.first, this), __res.second };
27138fd1498Szrj       }
27238fd1498Szrj 
27338fd1498Szrj       template<typename _Pair, typename = typename
27438fd1498Szrj 	       std::enable_if<std::is_constructible<value_type,
27538fd1498Szrj 						    _Pair&&>::value>::type>
27638fd1498Szrj 	std::pair<iterator, bool>
27738fd1498Szrj 	insert(_Pair&& __x)
27838fd1498Szrj 	{
27938fd1498Szrj 	  std::pair<_Base_iterator, bool> __res
28038fd1498Szrj 	    = _Base::insert(std::forward<_Pair>(__x));
28138fd1498Szrj 	  return std::pair<iterator, bool>(iterator(__res.first, this),
28238fd1498Szrj 					   __res.second);
28338fd1498Szrj 	}
28438fd1498Szrj #endif
28538fd1498Szrj 
28638fd1498Szrj #if __cplusplus >= 201103L
28738fd1498Szrj       void
28838fd1498Szrj       insert(std::initializer_list<value_type> __list)
28938fd1498Szrj       { _Base::insert(__list); }
29038fd1498Szrj #endif
29138fd1498Szrj 
29238fd1498Szrj       iterator
29338fd1498Szrj #if __cplusplus >= 201103L
29438fd1498Szrj       insert(const_iterator __position, const value_type& __x)
29538fd1498Szrj #else
29638fd1498Szrj       insert(iterator __position, const value_type& __x)
29738fd1498Szrj #endif
29838fd1498Szrj       {
29938fd1498Szrj 	__glibcxx_check_insert(__position);
30038fd1498Szrj 	return iterator(_Base::insert(__position.base(), __x), this);
30138fd1498Szrj       }
30238fd1498Szrj 
30338fd1498Szrj #if __cplusplus >= 201103L
30438fd1498Szrj       // _GLIBCXX_RESOLVE_LIB_DEFECTS
30538fd1498Szrj       // 2354. Unnecessary copying when inserting into maps with braced-init
30638fd1498Szrj       iterator
30738fd1498Szrj       insert(const_iterator __position, value_type&& __x)
30838fd1498Szrj       {
30938fd1498Szrj 	__glibcxx_check_insert(__position);
31038fd1498Szrj 	return { _Base::insert(__position.base(), std::move(__x)), this };
31138fd1498Szrj       }
31238fd1498Szrj 
31338fd1498Szrj       template<typename _Pair, typename = typename
31438fd1498Szrj 	       std::enable_if<std::is_constructible<value_type,
31538fd1498Szrj 						    _Pair&&>::value>::type>
31638fd1498Szrj 	iterator
31738fd1498Szrj 	insert(const_iterator __position, _Pair&& __x)
31838fd1498Szrj 	{
31938fd1498Szrj 	  __glibcxx_check_insert(__position);
32038fd1498Szrj 	  return iterator(_Base::insert(__position.base(),
32138fd1498Szrj 					std::forward<_Pair>(__x)), this);
32238fd1498Szrj 	}
32338fd1498Szrj #endif
32438fd1498Szrj 
32538fd1498Szrj       template<typename _InputIterator>
32638fd1498Szrj 	void
32738fd1498Szrj 	insert(_InputIterator __first, _InputIterator __last)
32838fd1498Szrj 	{
32938fd1498Szrj 	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
33038fd1498Szrj 	  __glibcxx_check_valid_range2(__first, __last, __dist);
33138fd1498Szrj 
33238fd1498Szrj 	  if (__dist.second >= __gnu_debug::__dp_sign)
33338fd1498Szrj 	    _Base::insert(__gnu_debug::__unsafe(__first),
33438fd1498Szrj 			  __gnu_debug::__unsafe(__last));
33538fd1498Szrj 	  else
33638fd1498Szrj 	    _Base::insert(__first, __last);
33738fd1498Szrj 	}
33838fd1498Szrj 
33938fd1498Szrj 
34038fd1498Szrj #if __cplusplus > 201402L
34138fd1498Szrj       template <typename... _Args>
34238fd1498Szrj         pair<iterator, bool>
34338fd1498Szrj         try_emplace(const key_type& __k, _Args&&... __args)
34438fd1498Szrj         {
34538fd1498Szrj 	  auto __res = _Base::try_emplace(__k,
34638fd1498Szrj 					  std::forward<_Args>(__args)...);
34738fd1498Szrj 	  return { iterator(__res.first, this), __res.second };
34838fd1498Szrj 	}
34938fd1498Szrj 
35038fd1498Szrj       template <typename... _Args>
35138fd1498Szrj         pair<iterator, bool>
35238fd1498Szrj         try_emplace(key_type&& __k, _Args&&... __args)
35338fd1498Szrj         {
35438fd1498Szrj 	  auto __res = _Base::try_emplace(std::move(__k),
35538fd1498Szrj 					  std::forward<_Args>(__args)...);
35638fd1498Szrj 	  return { iterator(__res.first, this), __res.second };
35738fd1498Szrj 	}
35838fd1498Szrj 
35938fd1498Szrj       template <typename... _Args>
36038fd1498Szrj         iterator
36138fd1498Szrj         try_emplace(const_iterator __hint, const key_type& __k,
36238fd1498Szrj                     _Args&&... __args)
36338fd1498Szrj         {
36438fd1498Szrj 	  __glibcxx_check_insert(__hint);
36538fd1498Szrj 	  return iterator(_Base::try_emplace(__hint.base(), __k,
36638fd1498Szrj 					     std::forward<_Args>(__args)...),
36738fd1498Szrj 			  this);
36838fd1498Szrj 	}
36938fd1498Szrj 
37038fd1498Szrj       template <typename... _Args>
37138fd1498Szrj         iterator
37238fd1498Szrj         try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
37338fd1498Szrj         {
37438fd1498Szrj 	  __glibcxx_check_insert(__hint);
37538fd1498Szrj 	  return iterator(_Base::try_emplace(__hint.base(), std::move(__k),
37638fd1498Szrj 					     std::forward<_Args>(__args)...),
37738fd1498Szrj 			  this);
37838fd1498Szrj 	}
37938fd1498Szrj 
38038fd1498Szrj       template <typename _Obj>
38138fd1498Szrj         std::pair<iterator, bool>
38238fd1498Szrj         insert_or_assign(const key_type& __k, _Obj&& __obj)
38338fd1498Szrj 	{
38438fd1498Szrj 	  auto __res = _Base::insert_or_assign(__k,
38538fd1498Szrj 					       std::forward<_Obj>(__obj));
38638fd1498Szrj 	  return { iterator(__res.first, this), __res.second };
38738fd1498Szrj 	}
38838fd1498Szrj 
38938fd1498Szrj       template <typename _Obj>
39038fd1498Szrj         std::pair<iterator, bool>
39138fd1498Szrj         insert_or_assign(key_type&& __k, _Obj&& __obj)
39238fd1498Szrj 	{
39338fd1498Szrj 	  auto __res = _Base::insert_or_assign(std::move(__k),
39438fd1498Szrj 					       std::forward<_Obj>(__obj));
39538fd1498Szrj 	  return { iterator(__res.first, this), __res.second };
39638fd1498Szrj 	}
39738fd1498Szrj 
39838fd1498Szrj       template <typename _Obj>
39938fd1498Szrj         iterator
40038fd1498Szrj         insert_or_assign(const_iterator __hint,
40138fd1498Szrj                          const key_type& __k, _Obj&& __obj)
40238fd1498Szrj 	{
40338fd1498Szrj 	  __glibcxx_check_insert(__hint);
40438fd1498Szrj 	  return iterator(_Base::insert_or_assign(__hint.base(), __k,
40538fd1498Szrj 						  std::forward<_Obj>(__obj)),
40638fd1498Szrj 			  this);
40738fd1498Szrj 	}
40838fd1498Szrj 
40938fd1498Szrj       template <typename _Obj>
41038fd1498Szrj         iterator
41138fd1498Szrj         insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
41238fd1498Szrj         {
41338fd1498Szrj 	  __glibcxx_check_insert(__hint);
41438fd1498Szrj 	  return iterator(_Base::insert_or_assign(__hint.base(),
41538fd1498Szrj 						  std::move(__k),
41638fd1498Szrj 						  std::forward<_Obj>(__obj)),
41738fd1498Szrj 			  this);
41838fd1498Szrj 	}
41938fd1498Szrj #endif // C++17
42038fd1498Szrj 
42138fd1498Szrj #if __cplusplus > 201402L
42238fd1498Szrj       using node_type = typename _Base::node_type;
42338fd1498Szrj       using insert_return_type = _Node_insert_return<iterator, node_type>;
42438fd1498Szrj 
42538fd1498Szrj       node_type
42638fd1498Szrj       extract(const_iterator __position)
42738fd1498Szrj       {
42838fd1498Szrj 	__glibcxx_check_erase(__position);
42938fd1498Szrj 	this->_M_invalidate_if(_Equal(__position.base()));
43038fd1498Szrj 	return _Base::extract(__position.base());
43138fd1498Szrj       }
43238fd1498Szrj 
43338fd1498Szrj       node_type
43438fd1498Szrj       extract(const key_type& __key)
43538fd1498Szrj       {
43638fd1498Szrj 	const auto __position = find(__key);
43738fd1498Szrj 	if (__position != end())
43838fd1498Szrj 	  return extract(__position);
43938fd1498Szrj 	return {};
44038fd1498Szrj       }
44138fd1498Szrj 
44238fd1498Szrj       insert_return_type
44338fd1498Szrj       insert(node_type&& __nh)
44438fd1498Szrj       {
44538fd1498Szrj 	auto __ret = _Base::insert(std::move(__nh));
44638fd1498Szrj 	iterator __pos = iterator(__ret.position, this);
44738fd1498Szrj 	return { __pos, __ret.inserted, std::move(__ret.node) };
44838fd1498Szrj       }
44938fd1498Szrj 
45038fd1498Szrj       iterator
45138fd1498Szrj       insert(const_iterator __hint, node_type&& __nh)
45238fd1498Szrj       {
45338fd1498Szrj 	__glibcxx_check_insert(__hint);
45438fd1498Szrj 	return iterator(_Base::insert(__hint.base(), std::move(__nh)), this);
45538fd1498Szrj       }
45638fd1498Szrj 
45738fd1498Szrj       using _Base::merge;
45838fd1498Szrj #endif // C++17
45938fd1498Szrj 
46038fd1498Szrj #if __cplusplus >= 201103L
46138fd1498Szrj       iterator
46238fd1498Szrj       erase(const_iterator __position)
46338fd1498Szrj       {
46438fd1498Szrj 	__glibcxx_check_erase(__position);
46538fd1498Szrj 	this->_M_invalidate_if(_Equal(__position.base()));
46638fd1498Szrj 	return iterator(_Base::erase(__position.base()), this);
46738fd1498Szrj       }
46838fd1498Szrj 
46938fd1498Szrj       iterator
47038fd1498Szrj       erase(iterator __position)
47138fd1498Szrj       { return erase(const_iterator(__position)); }
47238fd1498Szrj #else
47338fd1498Szrj       void
47438fd1498Szrj       erase(iterator __position)
47538fd1498Szrj       {
47638fd1498Szrj 	__glibcxx_check_erase(__position);
47738fd1498Szrj 	this->_M_invalidate_if(_Equal(__position.base()));
47838fd1498Szrj 	_Base::erase(__position.base());
47938fd1498Szrj       }
48038fd1498Szrj #endif
48138fd1498Szrj 
48238fd1498Szrj       size_type
48338fd1498Szrj       erase(const key_type& __x)
48438fd1498Szrj       {
48538fd1498Szrj 	_Base_iterator __victim = _Base::find(__x);
48638fd1498Szrj 	if (__victim == _Base::end())
48738fd1498Szrj 	  return 0;
48838fd1498Szrj 	else
48938fd1498Szrj 	  {
49038fd1498Szrj 	    this->_M_invalidate_if(_Equal(__victim));
49138fd1498Szrj 	    _Base::erase(__victim);
49238fd1498Szrj 	    return 1;
49338fd1498Szrj 	  }
49438fd1498Szrj       }
49538fd1498Szrj 
49638fd1498Szrj #if __cplusplus >= 201103L
49738fd1498Szrj       iterator
49838fd1498Szrj       erase(const_iterator __first, const_iterator __last)
49938fd1498Szrj       {
50038fd1498Szrj 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
50138fd1498Szrj 	// 151. can't currently clear() empty container
50238fd1498Szrj 	__glibcxx_check_erase_range(__first, __last);
50338fd1498Szrj 	for (_Base_const_iterator __victim = __first.base();
50438fd1498Szrj 	     __victim != __last.base(); ++__victim)
50538fd1498Szrj 	  {
50638fd1498Szrj 	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
50738fd1498Szrj 				  _M_message(__gnu_debug::__msg_valid_range)
50838fd1498Szrj 				  ._M_iterator(__first, "first")
50938fd1498Szrj 				  ._M_iterator(__last, "last"));
51038fd1498Szrj 	    this->_M_invalidate_if(_Equal(__victim));
51138fd1498Szrj 	  }
51238fd1498Szrj 	return iterator(_Base::erase(__first.base(), __last.base()), this);
51338fd1498Szrj       }
51438fd1498Szrj #else
51538fd1498Szrj       void
51638fd1498Szrj       erase(iterator __first, iterator __last)
51738fd1498Szrj       {
51838fd1498Szrj 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
51938fd1498Szrj 	// 151. can't currently clear() empty container
52038fd1498Szrj 	__glibcxx_check_erase_range(__first, __last);
52138fd1498Szrj 	for (_Base_iterator __victim = __first.base();
52238fd1498Szrj 	     __victim != __last.base(); ++__victim)
52338fd1498Szrj 	  {
52438fd1498Szrj 	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
52538fd1498Szrj 				  _M_message(__gnu_debug::__msg_valid_range)
52638fd1498Szrj 				  ._M_iterator(__first, "first")
52738fd1498Szrj 				  ._M_iterator(__last, "last"));
52838fd1498Szrj 	    this->_M_invalidate_if(_Equal(__victim));
52938fd1498Szrj 	  }
53038fd1498Szrj 	_Base::erase(__first.base(), __last.base());
53138fd1498Szrj       }
53238fd1498Szrj #endif
53338fd1498Szrj 
53438fd1498Szrj       void
53538fd1498Szrj       swap(map& __x)
53638fd1498Szrj       _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
53738fd1498Szrj       {
53838fd1498Szrj 	_Safe::_M_swap(__x);
53938fd1498Szrj 	_Base::swap(__x);
54038fd1498Szrj       }
54138fd1498Szrj 
54238fd1498Szrj       void
54338fd1498Szrj       clear() _GLIBCXX_NOEXCEPT
54438fd1498Szrj       {
54538fd1498Szrj 	this->_M_invalidate_all();
54638fd1498Szrj 	_Base::clear();
54738fd1498Szrj       }
54838fd1498Szrj 
54938fd1498Szrj       // observers:
55038fd1498Szrj       using _Base::key_comp;
55138fd1498Szrj       using _Base::value_comp;
55238fd1498Szrj 
55338fd1498Szrj       // 23.3.1.3 map operations:
55438fd1498Szrj       iterator
55538fd1498Szrj       find(const key_type& __x)
55638fd1498Szrj       { return iterator(_Base::find(__x), this); }
55738fd1498Szrj 
55838fd1498Szrj #if __cplusplus > 201103L
55938fd1498Szrj       template<typename _Kt,
56038fd1498Szrj 	       typename _Req =
56138fd1498Szrj 		 typename __has_is_transparent<_Compare, _Kt>::type>
56238fd1498Szrj 	iterator
56338fd1498Szrj 	find(const _Kt& __x)
56438fd1498Szrj 	{ return { _Base::find(__x), this }; }
56538fd1498Szrj #endif
56638fd1498Szrj 
56738fd1498Szrj       const_iterator
56838fd1498Szrj       find(const key_type& __x) const
56938fd1498Szrj       { return const_iterator(_Base::find(__x), this); }
57038fd1498Szrj 
57138fd1498Szrj #if __cplusplus > 201103L
57238fd1498Szrj       template<typename _Kt,
57338fd1498Szrj 	       typename _Req =
57438fd1498Szrj 		 typename __has_is_transparent<_Compare, _Kt>::type>
57538fd1498Szrj 	const_iterator
57638fd1498Szrj 	find(const _Kt& __x) const
57738fd1498Szrj 	{ return { _Base::find(__x), this }; }
57838fd1498Szrj #endif
57938fd1498Szrj 
58038fd1498Szrj       using _Base::count;
58138fd1498Szrj 
58238fd1498Szrj       iterator
58338fd1498Szrj       lower_bound(const key_type& __x)
58438fd1498Szrj       { return iterator(_Base::lower_bound(__x), this); }
58538fd1498Szrj 
58638fd1498Szrj #if __cplusplus > 201103L
58738fd1498Szrj       template<typename _Kt,
58838fd1498Szrj 	       typename _Req =
58938fd1498Szrj 		 typename __has_is_transparent<_Compare, _Kt>::type>
59038fd1498Szrj 	iterator
59138fd1498Szrj 	lower_bound(const _Kt& __x)
59238fd1498Szrj 	{ return { _Base::lower_bound(__x), this }; }
59338fd1498Szrj #endif
59438fd1498Szrj 
59538fd1498Szrj       const_iterator
59638fd1498Szrj       lower_bound(const key_type& __x) const
59738fd1498Szrj       { return const_iterator(_Base::lower_bound(__x), this); }
59838fd1498Szrj 
59938fd1498Szrj #if __cplusplus > 201103L
60038fd1498Szrj       template<typename _Kt,
60138fd1498Szrj 	       typename _Req =
60238fd1498Szrj 		 typename __has_is_transparent<_Compare, _Kt>::type>
60338fd1498Szrj 	const_iterator
60438fd1498Szrj 	lower_bound(const _Kt& __x) const
60538fd1498Szrj 	{ return { _Base::lower_bound(__x), this }; }
60638fd1498Szrj #endif
60738fd1498Szrj 
60838fd1498Szrj       iterator
60938fd1498Szrj       upper_bound(const key_type& __x)
61038fd1498Szrj       { return iterator(_Base::upper_bound(__x), this); }
61138fd1498Szrj 
61238fd1498Szrj #if __cplusplus > 201103L
61338fd1498Szrj       template<typename _Kt,
61438fd1498Szrj 	       typename _Req =
61538fd1498Szrj 		 typename __has_is_transparent<_Compare, _Kt>::type>
61638fd1498Szrj 	iterator
61738fd1498Szrj 	upper_bound(const _Kt& __x)
61838fd1498Szrj 	{ return { _Base::upper_bound(__x), this }; }
61938fd1498Szrj #endif
62038fd1498Szrj 
62138fd1498Szrj       const_iterator
62238fd1498Szrj       upper_bound(const key_type& __x) const
62338fd1498Szrj       { return const_iterator(_Base::upper_bound(__x), this); }
62438fd1498Szrj 
62538fd1498Szrj #if __cplusplus > 201103L
62638fd1498Szrj       template<typename _Kt,
62738fd1498Szrj 	       typename _Req =
62838fd1498Szrj 		 typename __has_is_transparent<_Compare, _Kt>::type>
62938fd1498Szrj 	const_iterator
63038fd1498Szrj 	upper_bound(const _Kt& __x) const
63138fd1498Szrj 	{ return { _Base::upper_bound(__x), this }; }
63238fd1498Szrj #endif
63338fd1498Szrj 
63438fd1498Szrj       std::pair<iterator,iterator>
63538fd1498Szrj       equal_range(const key_type& __x)
63638fd1498Szrj       {
63738fd1498Szrj 	std::pair<_Base_iterator, _Base_iterator> __res =
63838fd1498Szrj 	_Base::equal_range(__x);
63938fd1498Szrj 	return std::make_pair(iterator(__res.first, this),
64038fd1498Szrj 			      iterator(__res.second, this));
64138fd1498Szrj       }
64238fd1498Szrj 
64338fd1498Szrj #if __cplusplus > 201103L
64438fd1498Szrj       template<typename _Kt,
64538fd1498Szrj 	       typename _Req =
64638fd1498Szrj 		 typename __has_is_transparent<_Compare, _Kt>::type>
64738fd1498Szrj 	std::pair<iterator, iterator>
64838fd1498Szrj 	equal_range(const _Kt& __x)
64938fd1498Szrj 	{
65038fd1498Szrj 	  auto __res = _Base::equal_range(__x);
65138fd1498Szrj 	  return { { __res.first, this }, { __res.second, this } };
65238fd1498Szrj 	}
65338fd1498Szrj #endif
65438fd1498Szrj 
65538fd1498Szrj       std::pair<const_iterator,const_iterator>
65638fd1498Szrj       equal_range(const key_type& __x) const
65738fd1498Szrj       {
65838fd1498Szrj 	std::pair<_Base_const_iterator, _Base_const_iterator> __res =
65938fd1498Szrj 	_Base::equal_range(__x);
66038fd1498Szrj 	return std::make_pair(const_iterator(__res.first, this),
66138fd1498Szrj 			      const_iterator(__res.second, this));
66238fd1498Szrj       }
66338fd1498Szrj 
66438fd1498Szrj #if __cplusplus > 201103L
66538fd1498Szrj       template<typename _Kt,
66638fd1498Szrj 	       typename _Req =
66738fd1498Szrj 		 typename __has_is_transparent<_Compare, _Kt>::type>
66838fd1498Szrj 	std::pair<const_iterator, const_iterator>
66938fd1498Szrj 	equal_range(const _Kt& __x) const
67038fd1498Szrj 	{
67138fd1498Szrj 	  auto __res = _Base::equal_range(__x);
67238fd1498Szrj 	  return { { __res.first, this }, { __res.second, this } };
67338fd1498Szrj 	}
67438fd1498Szrj #endif
67538fd1498Szrj 
67638fd1498Szrj       _Base&
67738fd1498Szrj       _M_base() _GLIBCXX_NOEXCEPT	{ return *this; }
67838fd1498Szrj 
67938fd1498Szrj       const _Base&
68038fd1498Szrj       _M_base() const _GLIBCXX_NOEXCEPT	{ return *this; }
68138fd1498Szrj     };
68238fd1498Szrj 
68338fd1498Szrj #if __cpp_deduction_guides >= 201606
68438fd1498Szrj 
68538fd1498Szrj  template<typename _InputIterator,
68638fd1498Szrj 	  typename _Compare = less<__iter_key_t<_InputIterator>>,
68738fd1498Szrj 	  typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
68838fd1498Szrj 	  typename = _RequireInputIter<_InputIterator>,
68938fd1498Szrj 	  typename = _RequireAllocator<_Allocator>>
69038fd1498Szrj   map(_InputIterator, _InputIterator,
69138fd1498Szrj       _Compare = _Compare(), _Allocator = _Allocator())
69238fd1498Szrj   -> map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
69338fd1498Szrj 	 _Compare, _Allocator>;
69438fd1498Szrj 
69538fd1498Szrj  template<typename _Key, typename _Tp, typename _Compare = less<_Key>,
69638fd1498Szrj 	  typename _Allocator = allocator<pair<const _Key, _Tp>>,
69738fd1498Szrj 	  typename = _RequireAllocator<_Allocator>>
69838fd1498Szrj    map(initializer_list<pair<_Key, _Tp>>,
69938fd1498Szrj        _Compare = _Compare(), _Allocator = _Allocator())
70038fd1498Szrj    -> map<_Key, _Tp, _Compare, _Allocator>;
70138fd1498Szrj 
70238fd1498Szrj  template <typename _InputIterator, typename _Allocator,
70338fd1498Szrj 	   typename = _RequireInputIter<_InputIterator>,
70438fd1498Szrj 	   typename = _RequireAllocator<_Allocator>>
70538fd1498Szrj    map(_InputIterator, _InputIterator, _Allocator)
70638fd1498Szrj    -> map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
70738fd1498Szrj 	  less<__iter_key_t<_InputIterator>>, _Allocator>;
70838fd1498Szrj 
70938fd1498Szrj  template<typename _Key, typename _Tp, typename _Allocator,
71038fd1498Szrj 	  typename = _RequireAllocator<_Allocator>>
71138fd1498Szrj    map(initializer_list<pair<_Key, _Tp>>, _Allocator)
71238fd1498Szrj    -> map<_Key, _Tp, less<_Key>, _Allocator>;
71338fd1498Szrj 
71438fd1498Szrj #endif
71538fd1498Szrj 
71638fd1498Szrj   template<typename _Key, typename _Tp,
71738fd1498Szrj 	   typename _Compare, typename _Allocator>
71838fd1498Szrj     inline bool
71938fd1498Szrj     operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
72038fd1498Szrj 	       const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
72138fd1498Szrj     { return __lhs._M_base() == __rhs._M_base(); }
72238fd1498Szrj 
72338fd1498Szrj   template<typename _Key, typename _Tp,
72438fd1498Szrj 	   typename _Compare, typename _Allocator>
72538fd1498Szrj     inline bool
72638fd1498Szrj     operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
72738fd1498Szrj 	       const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
72838fd1498Szrj     { return __lhs._M_base() != __rhs._M_base(); }
72938fd1498Szrj 
73038fd1498Szrj   template<typename _Key, typename _Tp,
73138fd1498Szrj 	   typename _Compare, typename _Allocator>
73238fd1498Szrj     inline bool
73338fd1498Szrj     operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
73438fd1498Szrj 	      const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
73538fd1498Szrj     { return __lhs._M_base() < __rhs._M_base(); }
73638fd1498Szrj 
73738fd1498Szrj   template<typename _Key, typename _Tp,
73838fd1498Szrj 	   typename _Compare, typename _Allocator>
73938fd1498Szrj     inline bool
74038fd1498Szrj     operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
74138fd1498Szrj 	       const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
74238fd1498Szrj     { return __lhs._M_base() <= __rhs._M_base(); }
74338fd1498Szrj 
74438fd1498Szrj   template<typename _Key, typename _Tp,
74538fd1498Szrj 	   typename _Compare, typename _Allocator>
74638fd1498Szrj     inline bool
74738fd1498Szrj     operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
74838fd1498Szrj 	       const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
74938fd1498Szrj     { return __lhs._M_base() >= __rhs._M_base(); }
75038fd1498Szrj 
75138fd1498Szrj   template<typename _Key, typename _Tp,
75238fd1498Szrj 	   typename _Compare, typename _Allocator>
75338fd1498Szrj     inline bool
75438fd1498Szrj     operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
75538fd1498Szrj 	      const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
75638fd1498Szrj     { return __lhs._M_base() > __rhs._M_base(); }
75738fd1498Szrj 
75838fd1498Szrj   template<typename _Key, typename _Tp,
75938fd1498Szrj 	   typename _Compare, typename _Allocator>
76038fd1498Szrj     inline void
76138fd1498Szrj     swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs,
76238fd1498Szrj 	 map<_Key, _Tp, _Compare, _Allocator>& __rhs)
76338fd1498Szrj     _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
76438fd1498Szrj     { __lhs.swap(__rhs); }
76538fd1498Szrj 
76638fd1498Szrj } // namespace __debug
76738fd1498Szrj } // namespace std
76838fd1498Szrj 
76938fd1498Szrj #endif
770