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