29 #ifndef _GLIBCXX_DEBUG_MULTIMAP_H
30 #define _GLIBCXX_DEBUG_MULTIMAP_H 1
37 namespace std _GLIBCXX_VISIBILITY(default)
42 template<
typename _Key,
typename _Tp,
typename _Compare = std::less<_Key>,
43 typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
46 multimap<_Key, _Tp, _Compare, _Allocator>, _Allocator,
47 __gnu_debug::_Safe_node_sequence>,
48 public _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator>
50 typedef _GLIBCXX_STD_C::multimap<
51 _Key, _Tp, _Compare, _Allocator>
_Base;
59 template<
typename _ItT,
typename _SeqT,
typename _CatT>
60 friend class ::__gnu_debug::_Safe_iterator;
67 _Base_ref(
const _Base& __r) : _M_ref(__r) { }
74 typedef _Key key_type;
75 typedef _Tp mapped_type;
77 typedef _Compare key_compare;
78 typedef _Allocator allocator_type;
79 typedef typename _Base::reference reference;
80 typedef typename _Base::const_reference const_reference;
87 typedef typename _Base::size_type size_type;
88 typedef typename _Base::difference_type difference_type;
89 typedef typename _Base::pointer pointer;
90 typedef typename _Base::const_pointer const_pointer;
96 #if __cplusplus < 201103L
109 const _Compare& __c = _Compare(),
110 const allocator_type& __a = allocator_type())
111 :
_Base(__l, __c, __a) { }
118 const __type_identity_t<allocator_type>& __a)
119 :
_Base(__m, __a) { }
127 :
_Base(__l, __a) { }
129 template<
typename _InputIterator>
130 multimap(_InputIterator __first, _InputIterator __last,
131 const allocator_type& __a)
133 __glibcxx_check_valid_constructor_range(__first, __last)),
136 #if __glibcxx_containers_ranges
141 template<std::__detail::__container_compatible_range<value_type> _Rg>
142 multimap(std::from_range_t __t, _Rg&& __rg,
144 const allocator_type& __a = allocator_type())
145 :
_Base(__t, std::forward<_Rg>(__rg), __c, __a)
148 template<std::__detail::__container_compatible_range<value_type> _Rg>
149 multimap(std::from_range_t __t, _Rg&& __rg,
150 const allocator_type& __a = allocator_type())
151 :
_Base(__t, std::forward<_Rg>(__rg), __a)
158 explicit multimap(
const _Compare& __comp,
159 const _Allocator& __a = _Allocator())
160 :
_Base(__comp, __a) { }
162 template<
typename _InputIterator>
163 multimap(_InputIterator __first, _InputIterator __last,
164 const _Compare& __comp = _Compare(),
165 const _Allocator& __a = _Allocator())
167 __glibcxx_check_valid_constructor_range(__first, __last)),
172 :
_Base(__x._M_ref) { }
174 #if __cplusplus >= 201103L
176 operator=(
const multimap&) =
default;
184 _Base::operator=(__l);
185 this->_M_invalidate_all();
190 using _Base::get_allocator;
194 begin() _GLIBCXX_NOEXCEPT
195 {
return iterator(_Base::begin(),
this); }
198 begin()
const _GLIBCXX_NOEXCEPT
202 end() _GLIBCXX_NOEXCEPT
203 {
return iterator(_Base::end(),
this); }
206 end()
const _GLIBCXX_NOEXCEPT
210 rbegin() _GLIBCXX_NOEXCEPT
214 rbegin()
const _GLIBCXX_NOEXCEPT
218 rend() _GLIBCXX_NOEXCEPT
222 rend()
const _GLIBCXX_NOEXCEPT
225 #if __cplusplus >= 201103L
227 cbegin()
const noexcept
231 cend()
const noexcept
235 crbegin()
const noexcept
239 crend()
const noexcept
246 using _Base::max_size;
249 #if __cplusplus >= 201103L
250 template<
typename... _Args>
252 emplace(_Args&&... __args)
253 {
return { _Base::emplace(std::forward<_Args>(__args)...),
this }; }
255 template<
typename... _Args>
262 _Base::emplace_hint(__pos.
base(), std::forward<_Args>(__args)...),
270 {
return iterator(_Base::insert(__x),
this); }
272 #if __cplusplus >= 201103L
277 {
return { _Base::insert(
std::move(__x)),
this }; }
279 template<
typename _Pair,
typename =
typename
281 _Pair&&>::value>::type>
284 {
return { _Base::insert(std::forward<_Pair>(__x)),
this }; }
287 #if __cplusplus >= 201103L
290 { _Base::insert(__list); }
294 #if __cplusplus >= 201103L
301 return iterator(_Base::insert(__position.
base(), __x),
this);
304 #if __cplusplus >= 201103L
311 return { _Base::insert(__position.
base(),
std::move(__x)),
this };
314 template<
typename _Pair,
typename =
typename
316 _Pair&&>::value>::type>
323 _Base::insert(__position.
base(), std::forward<_Pair>(__x)),
329 template<
typename _InputIterator>
331 insert(_InputIterator __first, _InputIterator __last)
334 __glibcxx_check_valid_range2(__first, __last, __dist);
336 if (__dist.
second >= __gnu_debug::__dp_sign)
337 _Base::insert(__gnu_debug::__unsafe(__first),
338 __gnu_debug::__unsafe(__last));
340 _Base::insert(__first, __last);
343 #if __cplusplus > 201402L
344 using node_type =
typename _Base::node_type;
351 return _Base::extract(__position.
base());
355 extract(
const key_type& __key)
357 const auto __position = find(__key);
358 if (__position != end())
359 return extract(__position);
364 insert(node_type&& __nh)
365 {
return { _Base::insert(
std::move(__nh)),
this }; }
371 return { _Base::insert(__hint.
base(),
std::move(__nh)),
this };
377 #if __cplusplus >= 201103L
382 return { erase(__position.
base()),
this };
388 __glibcxx_check_erase2(__position);
390 return _Base::erase(__position);
393 _GLIBCXX_ABI_TAG_CXX11
403 _Base::erase(__position.
base());
408 erase(
const key_type& __x)
411 _Base::equal_range(__x);
412 size_type __count = 0;
414 while (__victim != __victims.
second)
417 _Base::erase(__victim++);
423 #if __cplusplus >= 201103L
431 __victim != __last.
base(); ++__victim)
433 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(),
434 _M_message(__gnu_debug::__msg_valid_range)
435 ._M_iterator(__first,
"first")
436 ._M_iterator(__last,
"last"));
440 return { _Base::erase(__first.base(), __last.
base()),
this };
450 __victim != __last.
base(); ++__victim)
452 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
453 _M_message(__gnu_debug::__msg_valid_range)
454 ._M_iterator(__first,
"first")
455 ._M_iterator(__last,
"last"));
458 _Base::erase(__first.base(), __last.
base());
464 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
471 clear() _GLIBCXX_NOEXCEPT
473 this->_M_invalidate_all();
478 using _Base::key_comp;
479 using _Base::value_comp;
483 find(
const key_type& __x)
484 {
return iterator(_Base::find(__x),
this); }
486 #if __cplusplus > 201103L
487 template<
typename _Kt,
489 typename __has_is_transparent<_Compare, _Kt>::type>
492 {
return { _Base::find(__x),
this }; }
496 find(
const key_type& __x)
const
499 #if __cplusplus > 201103L
500 template<
typename _Kt,
502 typename __has_is_transparent<_Compare, _Kt>::type>
504 find(
const _Kt& __x)
const
505 {
return { _Base::find(__x),
this }; }
511 lower_bound(
const key_type& __x)
512 {
return iterator(_Base::lower_bound(__x),
this); }
514 #if __cplusplus > 201103L
515 template<
typename _Kt,
517 typename __has_is_transparent<_Compare, _Kt>::type>
519 lower_bound(
const _Kt& __x)
520 {
return { _Base::lower_bound(__x),
this }; }
524 lower_bound(
const key_type& __x)
const
527 #if __cplusplus > 201103L
528 template<
typename _Kt,
530 typename __has_is_transparent<_Compare, _Kt>::type>
532 lower_bound(
const _Kt& __x)
const
533 {
return { _Base::lower_bound(__x),
this }; }
537 upper_bound(
const key_type& __x)
538 {
return iterator(_Base::upper_bound(__x),
this); }
540 #if __cplusplus > 201103L
541 template<
typename _Kt,
543 typename __has_is_transparent<_Compare, _Kt>::type>
545 upper_bound(
const _Kt& __x)
546 {
return { _Base::upper_bound(__x),
this }; }
550 upper_bound(
const key_type& __x)
const
553 #if __cplusplus > 201103L
554 template<
typename _Kt,
556 typename __has_is_transparent<_Compare, _Kt>::type>
558 upper_bound(
const _Kt& __x)
const
559 {
return { _Base::upper_bound(__x),
this }; }
563 equal_range(
const key_type& __x)
566 _Base::equal_range(__x);
571 #if __cplusplus > 201103L
572 template<
typename _Kt,
574 typename __has_is_transparent<_Compare, _Kt>::type>
576 equal_range(
const _Kt& __x)
578 auto __res = _Base::equal_range(__x);
579 return { { __res.first,
this }, { __res.second,
this } };
584 equal_range(
const key_type& __x)
const
587 _Base::equal_range(__x);
592 #if __cplusplus > 201103L
593 template<
typename _Kt,
595 typename __has_is_transparent<_Compare, _Kt>::type>
597 equal_range(
const _Kt& __x)
const
599 auto __res = _Base::equal_range(__x);
600 return { { __res.first,
this }, { __res.second,
this } };
605 _M_base() _GLIBCXX_NOEXCEPT {
return *
this; }
608 _M_base()
const _GLIBCXX_NOEXCEPT {
return *
this; }
611 #if __cpp_deduction_guides >= 201606
613 template<
typename _InputIterator,
616 typename = _RequireInputIter<_InputIterator>,
617 typename = _RequireNotAllocator<_Compare>,
618 typename = _RequireAllocator<_Allocator>>
619 multimap(_InputIterator, _InputIterator,
620 _Compare = _Compare(), _Allocator = _Allocator())
622 _Compare, _Allocator>;
624 template<
typename _Key,
typename _Tp,
typename _Compare = less<_Key>,
625 typename _Allocator = allocator<pair<const _Key, _Tp>>,
626 typename = _RequireNotAllocator<_Compare>,
627 typename = _RequireAllocator<_Allocator>>
629 _Compare = _Compare(), _Allocator = _Allocator())
632 template<
typename _InputIterator,
typename _Allocator,
633 typename = _RequireInputIter<_InputIterator>,
634 typename = _RequireAllocator<_Allocator>>
635 multimap(_InputIterator, _InputIterator, _Allocator)
639 template<
typename _Key,
typename _Tp,
typename _Allocator,
640 typename = _RequireAllocator<_Allocator>>
644 #if __glibcxx_containers_ranges
645 template<ranges::input_range _Rg,
647 __allocator_like _Alloc =
649 multimap(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc())
651 __detail::__range_mapped_type<_Rg>,
654 template<ranges::input_range _Rg, __allocator_like _Alloc>
655 multimap(from_range_t, _Rg&&, _Alloc)
657 __detail::__range_mapped_type<_Rg>,
663 template<
typename _Key,
typename _Tp,
664 typename _Compare,
typename _Allocator>
668 {
return __lhs._M_base() == __rhs._M_base(); }
670 #if __cpp_lib_three_way_comparison
671 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
672 inline __detail::__synth3way_t<pair<const _Key, _Tp>>
675 {
return __lhs._M_base() <=> __rhs._M_base(); }
677 template<
typename _Key,
typename _Tp,
678 typename _Compare,
typename _Allocator>
680 operator!=(
const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
681 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
682 {
return __lhs._M_base() != __rhs._M_base(); }
684 template<
typename _Key,
typename _Tp,
685 typename _Compare,
typename _Allocator>
687 operator<(
const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
688 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
689 {
return __lhs._M_base() < __rhs._M_base(); }
691 template<
typename _Key,
typename _Tp,
692 typename _Compare,
typename _Allocator>
694 operator<=(
const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
695 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
696 {
return __lhs._M_base() <= __rhs._M_base(); }
698 template<
typename _Key,
typename _Tp,
699 typename _Compare,
typename _Allocator>
701 operator>=(
const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
702 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
703 {
return __lhs._M_base() >= __rhs._M_base(); }
705 template<
typename _Key,
typename _Tp,
706 typename _Compare,
typename _Allocator>
708 operator>(
const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
709 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
710 {
return __lhs._M_base() > __rhs._M_base(); }
713 template<
typename _Key,
typename _Tp,
714 typename _Compare,
typename _Allocator>
716 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
717 multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
718 _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
719 { __lhs.swap(__rhs); }
#define __glibcxx_check_insert(_Position)
#define __glibcxx_check_erase_range(_First, _Last)
#define __glibcxx_check_erase(_Position)
constexpr bool operator<=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
constexpr bool operator>=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
constexpr bool operator<(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
constexpr bool operator>(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
ISO C++ entities toplevel namespace is std.
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
constexpr _Iterator __base(_Iterator __it)
Define a member typedef type only if a boolean constant is true.
The standard allocator, as per C++03 [20.4.1].
constexpr _Iterator & base() noexcept
Return the underlying iterator.
One of the comparison functors.
Struct holding two objects of arbitrary type.
_T1 first
The first member.
_T2 second
The second member.
A standard container made up of (key,value) pairs, which can be retrieved based on a key,...
void _M_invalidate_if(_Predicate __pred)
Class std::multimap with safety/checking/debug instrumentation.
Safe class dealing with some allocator dependent operations.
Like _Safe_sequence but with a special _M_invalidate_all implementation not invalidating past-the-end...