visus
/
toolchain-gcc-arm-embedded
Watch 1
Star 0
Fork 0
Code Issues 0 Pull Requests 0 Releases 0 Wiki Activity
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
2 Commits
1 Branch
Branch: main
Branches Tags
${ item.name }
Create branch ${ searchTerm }
from 'main'
${ noResults }
toolchain-gcc-arm-embedded/arm-none-eabi/include/c++/10.2.1/debug/map.h

798 lines
22KB
Raw Permalink Blame History 

  1. // Debugging map implementation -*- C++ -*-

  2. 

  3. // Copyright (C) 2003-2020 Free Software Foundation, Inc.

  4. //

  5. // This file is part of the GNU ISO C++ Library.  This library is free

  6. // software; you can redistribute it and/or modify it under the

  7. // terms of the GNU General Public License as published by the

  8. // Free Software Foundation; either version 3, or (at your option)

  9. // any later version.

  10. 

  11. // This library is distributed in the hope that it will be useful,

  12. // but WITHOUT ANY WARRANTY; without even the implied warranty of

  13. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

  14. // GNU General Public License for more details.

  15. 

  16. // Under Section 7 of GPL version 3, you are granted additional

  17. // permissions described in the GCC Runtime Library Exception, version

  18. // 3.1, as published by the Free Software Foundation.

  19. 

  20. // You should have received a copy of the GNU General Public License and

  21. // a copy of the GCC Runtime Library Exception along with this program;

  22. // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see

  23. // <http://www.gnu.org/licenses/>.

  24. 

  25. /** @file debug/map.h

  26.  *  This file is a GNU debug extension to the Standard C++ Library.

  27.  */

  28. 

  29. #ifndef _GLIBCXX_DEBUG_MAP_H

  30. #define _GLIBCXX_DEBUG_MAP_H 1

  31. 

  32. #include <debug/safe_sequence.h>

  33. #include <debug/safe_container.h>

  34. #include <debug/safe_iterator.h>

  35. #include <utility>

  36. 

  37. namespace std _GLIBCXX_VISIBILITY(default)

  38. {

  39. namespace __debug

  40. {

  41.   /// Class std::map with safety/checking/debug instrumentation.

  42.   template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,

  43. 	   typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >

  44.     class map

  45.     : public __gnu_debug::_Safe_container<

  46. 	map<_Key, _Tp, _Compare, _Allocator>, _Allocator,

  47. 	__gnu_debug::_Safe_node_sequence>,

  48.       public _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator>

  49.     {

  50.       typedef _GLIBCXX_STD_C::map<

  51. 	_Key, _Tp, _Compare, _Allocator>			_Base;

  52.       typedef __gnu_debug::_Safe_container<

  53. 	map, _Allocator, __gnu_debug::_Safe_node_sequence>	_Safe;

  54. 

  55.       typedef typename _Base::const_iterator	_Base_const_iterator;

  56.       typedef typename _Base::iterator		_Base_iterator;

  57.       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;

  58. 

  59.       template<typename _ItT, typename _SeqT, typename _CatT>

  60. 	friend class ::__gnu_debug::_Safe_iterator;

  61. 

  62.     public:

  63.       // types:

  64.       typedef _Key					key_type;

  65.       typedef _Tp					mapped_type;

  66.       typedef std::pair<const _Key, _Tp>		value_type;

  67.       typedef _Compare					key_compare;

  68.       typedef _Allocator				allocator_type;

  69.       typedef typename _Base::reference			reference;

  70.       typedef typename _Base::const_reference		const_reference;

  71. 

  72.       typedef __gnu_debug::_Safe_iterator<_Base_iterator, map>

  73. 							iterator;

  74.       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, map>

  75. 							const_iterator;

  76. 

  77.       typedef typename _Base::size_type			size_type;

  78.       typedef typename _Base::difference_type		difference_type;

  79.       typedef typename _Base::pointer			pointer;

  80.       typedef typename _Base::const_pointer		const_pointer;

  81.       typedef std::reverse_iterator<iterator>		reverse_iterator;

  82.       typedef std::reverse_iterator<const_iterator>	const_reverse_iterator;

  83. 

  84.       // 23.3.1.1 construct/copy/destroy:

  85. 

  86. #if __cplusplus < 201103L

  87.       map() : _Base() { }

  88. 

  89.       map(const map& __x)

  90.       : _Base(__x) { }

  91. 

  92.       ~map() { }

  93. #else

  94.       map() = default;

  95.       map(const map&) = default;

  96.       map(map&&) = default;

  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. 

  103.       explicit

  104.       map(const allocator_type& __a)

  105.       : _Base(__a) { }

  106. 

  107.       map(const map& __m, const allocator_type& __a)

  108.       : _Base(__m, __a) { }

  109. 

  110.       map(map&& __m, const allocator_type& __a)

  111.       noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) )

  112.       : _Safe(std::move(__m._M_safe()), __a),

  113. 	_Base(std::move(__m._M_base()), __a) { }

  114. 

  115.       map(initializer_list<value_type> __l, const allocator_type& __a)

  116.       : _Base(__l, __a) { }

  117. 

  118.       template<typename _InputIterator>

  119. 	map(_InputIterator __first, _InputIterator __last,

  120. 	    const allocator_type& __a)

  121. 	: _Base(__gnu_debug::__base(

  122. 		  __glibcxx_check_valid_constructor_range(__first, __last)),

  123. 		__gnu_debug::__base(__last), __a)

  124. 	{ }

  125. 

  126.       ~map() = default;

  127. #endif

  128. 

  129.       map(const _Base& __x)

  130.       : _Base(__x) { }

  131. 

  132.       explicit map(const _Compare& __comp,

  133. 		   const _Allocator& __a = _Allocator())

  134.       : _Base(__comp, __a) { }

  135. 

  136.       template<typename _InputIterator>

  137. 	map(_InputIterator __first, _InputIterator __last,

  138. 	    const _Compare& __comp = _Compare(),

  139. 	    const _Allocator& __a = _Allocator())

  140. 	: _Base(__gnu_debug::__base(

  141. 		  __glibcxx_check_valid_constructor_range(__first, __last)),

  142. 		__gnu_debug::__base(__last),

  143. 		__comp, __a) { }

  144. 

  145. #if __cplusplus < 201103L

  146.       map&

  147.       operator=(const map& __x)

  148.       {

  149. 	this->_M_safe() = __x;

  150. 	_M_base() = __x;

  151. 	return *this;

  152.       }

  153. #else

  154.       map&

  155.       operator=(const map&) = default;

  156. 

  157.       map&

  158.       operator=(map&&) = default;

  159. 

  160.       map&

  161.       operator=(initializer_list<value_type> __l)

  162.       {

  163. 	_M_base() = __l;

  164. 	this->_M_invalidate_all();

  165. 	return *this;

  166.       }

  167. #endif

  168. 

  169.       // _GLIBCXX_RESOLVE_LIB_DEFECTS

  170.       // 133. map missing get_allocator()

  171.       using _Base::get_allocator;

  172. 

  173.       // iterators:

  174.       iterator

  175.       begin() _GLIBCXX_NOEXCEPT

  176.       { return iterator(_Base::begin(), this); }

  177. 

  178.       const_iterator

  179.       begin() const _GLIBCXX_NOEXCEPT

  180.       { return const_iterator(_Base::begin(), this); }

  181. 

  182.       iterator

  183.       end() _GLIBCXX_NOEXCEPT

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

  185. 

  186.       const_iterator

  187.       end() const _GLIBCXX_NOEXCEPT

  188.       { return const_iterator(_Base::end(), this); }

  189. 

  190.       reverse_iterator

  191.       rbegin() _GLIBCXX_NOEXCEPT

  192.       { return reverse_iterator(end()); }

  193. 

  194.       const_reverse_iterator

  195.       rbegin() const _GLIBCXX_NOEXCEPT

  196.       { return const_reverse_iterator(end()); }

  197. 

  198.       reverse_iterator

  199.       rend() _GLIBCXX_NOEXCEPT

  200.       { return reverse_iterator(begin()); }

  201. 

  202.       const_reverse_iterator

  203.       rend() const _GLIBCXX_NOEXCEPT

  204.       { return const_reverse_iterator(begin()); }

  205. 

  206. #if __cplusplus >= 201103L

  207.       const_iterator

  208.       cbegin() const noexcept

  209.       { return const_iterator(_Base::begin(), this); }

  210. 

  211.       const_iterator

  212.       cend() const noexcept

  213.       { return const_iterator(_Base::end(), this); }

  214. 

  215.       const_reverse_iterator

  216.       crbegin() const noexcept

  217.       { return const_reverse_iterator(end()); }

  218. 

  219.       const_reverse_iterator

  220.       crend() const noexcept

  221.       { return const_reverse_iterator(begin()); }

  222. #endif

  223. 

  224.       // capacity:

  225.       using _Base::empty;

  226.       using _Base::size;

  227.       using _Base::max_size;

  228. 

  229.       // 23.3.1.2 element access:

  230.       using _Base::operator[];

  231. 

  232.       // _GLIBCXX_RESOLVE_LIB_DEFECTS

  233.       // DR 464. Suggestion for new member functions in standard containers.

  234.       using _Base::at;

  235. 

  236.       // modifiers:

  237. #if __cplusplus >= 201103L

  238.       template<typename... _Args>

  239. 	std::pair<iterator, bool>

  240. 	emplace(_Args&&... __args)

  241. 	{

  242. 	  auto __res = _Base::emplace(std::forward<_Args>(__args)...);

  243. 	  return { { __res.first, this }, __res.second };

  244. 	}

  245. 

  246.       template<typename... _Args>

  247. 	iterator

  248. 	emplace_hint(const_iterator __pos, _Args&&... __args)

  249. 	{

  250. 	  __glibcxx_check_insert(__pos);

  251. 	  return

  252. 	    {

  253. 	      _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...),

  254. 	      this

  255. 	    };

  256. 	}

  257. #endif

  258. 

  259.       std::pair<iterator, bool>

  260.       insert(const value_type& __x)

  261.       {

  262. 	std::pair<_Base_iterator, bool> __res = _Base::insert(__x);

  263. 	return std::pair<iterator, bool>(iterator(__res.first, this),

  264. 					 __res.second);

  265.       }

  266. 

  267. #if __cplusplus >= 201103L

  268.       // _GLIBCXX_RESOLVE_LIB_DEFECTS

  269.       // 2354. Unnecessary copying when inserting into maps with braced-init

  270.       std::pair<iterator, bool>

  271.       insert(value_type&& __x)

  272.       {

  273. 	auto __res = _Base::insert(std::move(__x));

  274. 	return { { __res.first, this }, __res.second };

  275.       }

  276. 

  277.       template<typename _Pair, typename = typename

  278. 	       std::enable_if<std::is_constructible<value_type,

  279. 						    _Pair&&>::value>::type>

  280. 	std::pair<iterator, bool>

  281. 	insert(_Pair&& __x)

  282. 	{

  283. 	  auto __res = _Base::insert(std::forward<_Pair>(__x));

  284. 	  return { { __res.first, this }, __res.second };

  285. 	}

  286. #endif

  287. 

  288. #if __cplusplus >= 201103L

  289.       void

  290.       insert(std::initializer_list<value_type> __list)

  291.       { _Base::insert(__list); }

  292. #endif

  293. 

  294.       iterator

  295. #if __cplusplus >= 201103L

  296.       insert(const_iterator __position, const value_type& __x)

  297. #else

  298.       insert(iterator __position, const value_type& __x)

  299. #endif

  300.       {

  301. 	__glibcxx_check_insert(__position);

  302. 	return iterator(_Base::insert(__position.base(), __x), this);

  303.       }

  304. 

  305. #if __cplusplus >= 201103L

  306.       // _GLIBCXX_RESOLVE_LIB_DEFECTS

  307.       // 2354. Unnecessary copying when inserting into maps with braced-init

  308.       iterator

  309.       insert(const_iterator __position, value_type&& __x)

  310.       {

  311. 	__glibcxx_check_insert(__position);

  312. 	return { _Base::insert(__position.base(), std::move(__x)), this };

  313.       }

  314. 

  315.       template<typename _Pair, typename = typename

  316. 	       std::enable_if<std::is_constructible<value_type,

  317. 						    _Pair&&>::value>::type>

  318. 	iterator

  319. 	insert(const_iterator __position, _Pair&& __x)

  320. 	{

  321. 	  __glibcxx_check_insert(__position);

  322. 	  return

  323. 	    {

  324. 	      _Base::insert(__position.base(), std::forward<_Pair>(__x)),

  325. 	      this

  326. 	    };

  327. 	}

  328. #endif

  329. 

  330.       template<typename _InputIterator>

  331. 	void

  332. 	insert(_InputIterator __first, _InputIterator __last)

  333. 	{

  334. 	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;

  335. 	  __glibcxx_check_valid_range2(__first, __last, __dist);

  336. 

  337. 	  if (__dist.second >= __gnu_debug::__dp_sign)

  338. 	    _Base::insert(__gnu_debug::__unsafe(__first),

  339. 			  __gnu_debug::__unsafe(__last));

  340. 	  else

  341. 	    _Base::insert(__first, __last);

  342. 	}

  343. 

  344. 

  345. #if __cplusplus > 201402L

  346.       template <typename... _Args>

  347.         pair<iterator, bool>

  348.         try_emplace(const key_type& __k, _Args&&... __args)

  349.         {

  350. 	  auto __res = _Base::try_emplace(__k,

  351. 					  std::forward<_Args>(__args)...);

  352. 	  return { { __res.first, this }, __res.second };

  353. 	}

  354. 

  355.       template <typename... _Args>

  356.         pair<iterator, bool>

  357.         try_emplace(key_type&& __k, _Args&&... __args)

  358.         {

  359. 	  auto __res = _Base::try_emplace(std::move(__k),

  360. 					  std::forward<_Args>(__args)...);

  361. 	  return { { __res.first, this }, __res.second };

  362. 	}

  363. 

  364.       template <typename... _Args>

  365.         iterator

  366.         try_emplace(const_iterator __hint, const key_type& __k,

  367.                     _Args&&... __args)

  368.         {

  369. 	  __glibcxx_check_insert(__hint);

  370. 	  return

  371. 	    {

  372. 	      _Base::try_emplace(__hint.base(), __k,

  373. 				 std::forward<_Args>(__args)...),

  374. 	      this

  375. 	    };

  376. 	}

  377. 

  378.       template <typename... _Args>

  379.         iterator

  380.         try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)

  381.         {

  382. 	  __glibcxx_check_insert(__hint);

  383. 	  return

  384. 	    {

  385. 	      _Base::try_emplace(__hint.base(), std::move(__k),

  386. 				 std::forward<_Args>(__args)...),

  387. 	      this

  388. 	    };

  389. 	}

  390. 

  391.       template <typename _Obj>

  392.         std::pair<iterator, bool>

  393.         insert_or_assign(const key_type& __k, _Obj&& __obj)

  394. 	{

  395. 	  auto __res = _Base::insert_or_assign(__k,

  396. 					       std::forward<_Obj>(__obj));

  397. 	  return { { __res.first, this }, __res.second };

  398. 	}

  399. 

  400.       template <typename _Obj>

  401.         std::pair<iterator, bool>

  402.         insert_or_assign(key_type&& __k, _Obj&& __obj)

  403. 	{

  404. 	  auto __res = _Base::insert_or_assign(std::move(__k),

  405. 					       std::forward<_Obj>(__obj));

  406. 	  return { { __res.first, this }, __res.second };

  407. 	}

  408. 

  409.       template <typename _Obj>

  410.         iterator

  411.         insert_or_assign(const_iterator __hint,

  412.                          const key_type& __k, _Obj&& __obj)

  413. 	{

  414. 	  __glibcxx_check_insert(__hint);

  415. 	  return

  416. 	    {

  417. 	      _Base::insert_or_assign(__hint.base(), __k,

  418. 				      std::forward<_Obj>(__obj)),

  419. 	      this

  420. 	    };

  421. 	}

  422. 

  423.       template <typename _Obj>

  424.         iterator

  425.         insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)

  426.         {

  427. 	  __glibcxx_check_insert(__hint);

  428. 	  return

  429. 	    {

  430. 	      _Base::insert_or_assign(__hint.base(), std::move(__k),

  431. 				      std::forward<_Obj>(__obj)),

  432. 	      this

  433. 	    };

  434. 	}

  435. #endif // C++17

  436. 

  437. #if __cplusplus > 201402L

  438.       using node_type = typename _Base::node_type;

  439.       using insert_return_type = _Node_insert_return<iterator, node_type>;

  440. 

  441.       node_type

  442.       extract(const_iterator __position)

  443.       {

  444. 	__glibcxx_check_erase(__position);

  445. 	this->_M_invalidate_if(_Equal(__position.base()));

  446. 	return _Base::extract(__position.base());

  447.       }

  448. 

  449.       node_type

  450.       extract(const key_type& __key)

  451.       {

  452. 	const auto __position = find(__key);

  453. 	if (__position != end())

  454. 	  return extract(__position);

  455. 	return {};

  456.       }

  457. 

  458.       insert_return_type

  459.       insert(node_type&& __nh)

  460.       {

  461. 	auto __ret = _Base::insert(std::move(__nh));

  462. 	return

  463. 	  { { __ret.position, this }, __ret.inserted, std::move(__ret.node) };

  464.       }

  465. 

  466.       iterator

  467.       insert(const_iterator __hint, node_type&& __nh)

  468.       {

  469. 	__glibcxx_check_insert(__hint);

  470. 	return { _Base::insert(__hint.base(), std::move(__nh)), this };

  471.       }

  472. 

  473.       using _Base::merge;

  474. #endif // C++17

  475. 

  476. #if __cplusplus >= 201103L

  477.       iterator

  478.       erase(const_iterator __position)

  479.       {

  480. 	__glibcxx_check_erase(__position);

  481. 	this->_M_invalidate_if(_Equal(__position.base()));

  482. 	return { _Base::erase(__position.base()), this };

  483.       }

  484. 

  485.       _GLIBCXX_ABI_TAG_CXX11

  486.       iterator

  487.       erase(iterator __position)

  488.       { return erase(const_iterator(__position)); }

  489. #else

  490.       void

  491.       erase(iterator __position)

  492.       {

  493. 	__glibcxx_check_erase(__position);

  494. 	this->_M_invalidate_if(_Equal(__position.base()));

  495. 	_Base::erase(__position.base());

  496.       }

  497. #endif

  498. 

  499.       size_type

  500.       erase(const key_type& __x)

  501.       {

  502. 	_Base_iterator __victim = _Base::find(__x);

  503. 	if (__victim == _Base::end())

  504. 	  return 0;

  505. 	else

  506. 	  {

  507. 	    this->_M_invalidate_if(_Equal(__victim));

  508. 	    _Base::erase(__victim);

  509. 	    return 1;

  510. 	  }

  511.       }

  512. 

  513. #if __cplusplus >= 201103L

  514.       iterator

  515.       erase(const_iterator __first, const_iterator __last)

  516.       {

  517. 	// _GLIBCXX_RESOLVE_LIB_DEFECTS

  518. 	// 151. can't currently clear() empty container

  519. 	__glibcxx_check_erase_range(__first, __last);

  520. 	for (_Base_const_iterator __victim = __first.base();

  521. 	     __victim != __last.base(); ++__victim)

  522. 	  {

  523. 	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(),

  524. 				  _M_message(__gnu_debug::__msg_valid_range)

  525. 				  ._M_iterator(__first, "first")

  526. 				  ._M_iterator(__last, "last"));

  527. 	    this->_M_invalidate_if(_Equal(__victim));

  528. 	  }

  529. 

  530. 	return { _Base::erase(__first.base(), __last.base()), this };

  531.       }

  532. #else

  533.       void

  534.       erase(iterator __first, iterator __last)

  535.       {

  536. 	// _GLIBCXX_RESOLVE_LIB_DEFECTS

  537. 	// 151. can't currently clear() empty container

  538. 	__glibcxx_check_erase_range(__first, __last);

  539. 	for (_Base_iterator __victim = __first.base();

  540. 	     __victim != __last.base(); ++__victim)

  541. 	  {

  542. 	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),

  543. 				  _M_message(__gnu_debug::__msg_valid_range)

  544. 				  ._M_iterator(__first, "first")

  545. 				  ._M_iterator(__last, "last"));

  546. 	    this->_M_invalidate_if(_Equal(__victim));

  547. 	  }

  548. 	_Base::erase(__first.base(), __last.base());

  549.       }

  550. #endif

  551. 

  552.       void

  553.       swap(map& __x)

  554.       _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )

  555.       {

  556. 	_Safe::_M_swap(__x);

  557. 	_Base::swap(__x);

  558.       }

  559. 

  560.       void

  561.       clear() _GLIBCXX_NOEXCEPT

  562.       {

  563. 	this->_M_invalidate_all();

  564. 	_Base::clear();

  565.       }

  566. 

  567.       // observers:

  568.       using _Base::key_comp;

  569.       using _Base::value_comp;

  570. 

  571.       // 23.3.1.3 map operations:

  572.       iterator

  573.       find(const key_type& __x)

  574.       { return iterator(_Base::find(__x), this); }

  575. 

  576. #if __cplusplus > 201103L

  577.       template<typename _Kt,

  578. 	       typename _Req =

  579. 		 typename __has_is_transparent<_Compare, _Kt>::type>

  580. 	iterator

  581. 	find(const _Kt& __x)

  582. 	{ return { _Base::find(__x), this }; }

  583. #endif

  584. 

  585.       const_iterator

  586.       find(const key_type& __x) const

  587.       { return const_iterator(_Base::find(__x), this); }

  588. 

  589. #if __cplusplus > 201103L

  590.       template<typename _Kt,

  591. 	       typename _Req =

  592. 		 typename __has_is_transparent<_Compare, _Kt>::type>

  593. 	const_iterator

  594. 	find(const _Kt& __x) const

  595. 	{ return { _Base::find(__x), this }; }

  596. #endif

  597. 

  598.       using _Base::count;

  599. 

  600.       iterator

  601.       lower_bound(const key_type& __x)

  602.       { return iterator(_Base::lower_bound(__x), this); }

  603. 

  604. #if __cplusplus > 201103L

  605.       template<typename _Kt,

  606. 	       typename _Req =

  607. 		 typename __has_is_transparent<_Compare, _Kt>::type>

  608. 	iterator

  609. 	lower_bound(const _Kt& __x)

  610. 	{ return { _Base::lower_bound(__x), this }; }

  611. #endif

  612. 

  613.       const_iterator

  614.       lower_bound(const key_type& __x) const

  615.       { return const_iterator(_Base::lower_bound(__x), this); }

  616. 

  617. #if __cplusplus > 201103L

  618.       template<typename _Kt,

  619. 	       typename _Req =

  620. 		 typename __has_is_transparent<_Compare, _Kt>::type>

  621. 	const_iterator

  622. 	lower_bound(const _Kt& __x) const

  623. 	{ return { _Base::lower_bound(__x), this }; }

  624. #endif

  625. 

  626.       iterator

  627.       upper_bound(const key_type& __x)

  628.       { return iterator(_Base::upper_bound(__x), this); }

  629. 

  630. #if __cplusplus > 201103L

  631.       template<typename _Kt,

  632. 	       typename _Req =

  633. 		 typename __has_is_transparent<_Compare, _Kt>::type>

  634. 	iterator

  635. 	upper_bound(const _Kt& __x)

  636. 	{ return { _Base::upper_bound(__x), this }; }

  637. #endif

  638. 

  639.       const_iterator

  640.       upper_bound(const key_type& __x) const

  641.       { return const_iterator(_Base::upper_bound(__x), this); }

  642. 

  643. #if __cplusplus > 201103L

  644.       template<typename _Kt,

  645. 	       typename _Req =

  646. 		 typename __has_is_transparent<_Compare, _Kt>::type>

  647. 	const_iterator

  648. 	upper_bound(const _Kt& __x) const

  649. 	{ return { _Base::upper_bound(__x), this }; }

  650. #endif

  651. 

  652.       std::pair<iterator,iterator>

  653.       equal_range(const key_type& __x)

  654.       {

  655. 	std::pair<_Base_iterator, _Base_iterator> __res =

  656. 	_Base::equal_range(__x);

  657. 	return std::make_pair(iterator(__res.first, this),

  658. 			      iterator(__res.second, this));

  659.       }

  660. 

  661. #if __cplusplus > 201103L

  662.       template<typename _Kt,

  663. 	       typename _Req =

  664. 		 typename __has_is_transparent<_Compare, _Kt>::type>

  665. 	std::pair<iterator, iterator>

  666. 	equal_range(const _Kt& __x)

  667. 	{

  668. 	  auto __res = _Base::equal_range(__x);

  669. 	  return { { __res.first, this }, { __res.second, this } };

  670. 	}

  671. #endif

  672. 

  673.       std::pair<const_iterator,const_iterator>

  674.       equal_range(const key_type& __x) const

  675.       {

  676. 	std::pair<_Base_const_iterator, _Base_const_iterator> __res =

  677. 	_Base::equal_range(__x);

  678. 	return std::make_pair(const_iterator(__res.first, this),

  679. 			      const_iterator(__res.second, this));

  680.       }

  681. 

  682. #if __cplusplus > 201103L

  683.       template<typename _Kt,

  684. 	       typename _Req =

  685. 		 typename __has_is_transparent<_Compare, _Kt>::type>

  686. 	std::pair<const_iterator, const_iterator>

  687. 	equal_range(const _Kt& __x) const

  688. 	{

  689. 	  auto __res = _Base::equal_range(__x);

  690. 	  return { { __res.first, this }, { __res.second, this } };

  691. 	}

  692. #endif

  693. 

  694.       _Base&

  695.       _M_base() _GLIBCXX_NOEXCEPT	{ return *this; }

  696. 

  697.       const _Base&

  698.       _M_base() const _GLIBCXX_NOEXCEPT	{ return *this; }

  699.     };

  700. 

  701. #if __cpp_deduction_guides >= 201606

  702. 

  703.   template<typename _InputIterator,

  704. 	   typename _Compare = less<__iter_key_t<_InputIterator>>,

  705. 	   typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,

  706. 	   typename = _RequireInputIter<_InputIterator>,

  707. 	   typename = _RequireNotAllocator<_Compare>,

  708. 	   typename = _RequireAllocator<_Allocator>>

  709.     map(_InputIterator, _InputIterator,

  710. 	_Compare = _Compare(), _Allocator = _Allocator())

  711.     -> map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,

  712. 	   _Compare, _Allocator>;

  713. 

  714.   template<typename _Key, typename _Tp, typename _Compare = less<_Key>,

  715. 	   typename _Allocator = allocator<pair<const _Key, _Tp>>,

  716. 	   typename = _RequireNotAllocator<_Compare>,

  717. 	   typename = _RequireAllocator<_Allocator>>

  718.     map(initializer_list<pair<_Key, _Tp>>,

  719. 	_Compare = _Compare(), _Allocator = _Allocator())

  720.     -> map<_Key, _Tp, _Compare, _Allocator>;

  721. 

  722.   template <typename _InputIterator, typename _Allocator,

  723. 	    typename = _RequireInputIter<_InputIterator>,

  724. 	    typename = _RequireAllocator<_Allocator>>

  725.     map(_InputIterator, _InputIterator, _Allocator)

  726.     -> map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,

  727. 	   less<__iter_key_t<_InputIterator>>, _Allocator>;

  728. 

  729.   template<typename _Key, typename _Tp, typename _Allocator,

  730. 	   typename = _RequireAllocator<_Allocator>>

  731.     map(initializer_list<pair<_Key, _Tp>>, _Allocator)

  732.     -> map<_Key, _Tp, less<_Key>, _Allocator>;

  733. 

  734. #endif // deduction guides

  735. 

  736.   template<typename _Key, typename _Tp,

  737. 	   typename _Compare, typename _Allocator>

  738.     inline bool

  739.     operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,

  740. 	       const map<_Key, _Tp, _Compare, _Allocator>& __rhs)

  741.     { return __lhs._M_base() == __rhs._M_base(); }

  742. 

  743. #if __cpp_lib_three_way_comparison

  744.   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>

  745.     inline __detail::__synth3way_t<pair<const _Key, _Tp>>

  746.     operator<=>(const map<_Key, _Tp, _Compare, _Alloc>& __lhs,

  747. 		const map<_Key, _Tp, _Compare, _Alloc>& __rhs)

  748.     { return __lhs._M_base() <=> __rhs._M_base(); }

  749. #else

  750.   template<typename _Key, typename _Tp,

  751. 	   typename _Compare, typename _Allocator>

  752.     inline bool

  753.     operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,

  754. 	       const map<_Key, _Tp, _Compare, _Allocator>& __rhs)

  755.     { return __lhs._M_base() != __rhs._M_base(); }

  756. 

  757.   template<typename _Key, typename _Tp,

  758. 	   typename _Compare, typename _Allocator>

  759.     inline bool

  760.     operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,

  761. 	      const map<_Key, _Tp, _Compare, _Allocator>& __rhs)

  762.     { return __lhs._M_base() < __rhs._M_base(); }

  763. 

  764.   template<typename _Key, typename _Tp,

  765. 	   typename _Compare, typename _Allocator>

  766.     inline bool

  767.     operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,

  768. 	       const map<_Key, _Tp, _Compare, _Allocator>& __rhs)

  769.     { return __lhs._M_base() <= __rhs._M_base(); }

  770. 

  771.   template<typename _Key, typename _Tp,

  772. 	   typename _Compare, typename _Allocator>

  773.     inline bool

  774.     operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,

  775. 	       const map<_Key, _Tp, _Compare, _Allocator>& __rhs)

  776.     { return __lhs._M_base() >= __rhs._M_base(); }

  777. 

  778.   template<typename _Key, typename _Tp,

  779. 	   typename _Compare, typename _Allocator>

  780.     inline bool

  781.     operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,

  782. 	      const map<_Key, _Tp, _Compare, _Allocator>& __rhs)

  783.     { return __lhs._M_base() > __rhs._M_base(); }

  784. #endif // three-way comparison

  785. 

  786.   template<typename _Key, typename _Tp,

  787. 	   typename _Compare, typename _Allocator>

  788.     inline void

  789.     swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs,

  790. 	 map<_Key, _Tp, _Compare, _Allocator>& __rhs)

  791.     _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))

  792.     { __lhs.swap(__rhs); }

  793. 

  794. } // namespace __debug

  795. } // namespace std

  796. 

  797. #endif