29#ifndef _GLIBCXX_DEBUG_MULTIMAP_H
30#define _GLIBCXX_DEBUG_MULTIMAP_H 1
37namespace 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;
55 typedef typename _Base::const_iterator _Base_const_iterator;
56 typedef typename _Base::iterator _Base_iterator;
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;
85 multimap> const_iterator;
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
97 multimap() : _Base() { }
99 multimap(
const multimap& __x)
104 multimap() =
default;
105 multimap(
const multimap&) =
default;
106 multimap(multimap&&) =
default;
108 multimap(initializer_list<value_type> __l,
109 const _Compare& __c = _Compare(),
110 const allocator_type& __a = allocator_type())
111 : _Base(__l, __c, __a) { }
114 multimap(
const allocator_type& __a)
117 multimap(
const multimap& __m,
118 const __type_identity_t<allocator_type>& __a)
119 : _Base(__m, __a) { }
121 multimap(multimap&& __m,
const __type_identity_t<allocator_type>& __a)
122 noexcept(
noexcept(_Base(
std::move(__m), __a)) )
126 multimap(initializer_list<value_type> __l,
const allocator_type& __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 ~multimap() =
default;
139 explicit multimap(
const _Compare& __comp,
140 const _Allocator& __a = _Allocator())
141 : _Base(__comp, __a) { }
143 template<
typename _InputIterator>
144 multimap(_InputIterator __first, _InputIterator __last,
145 const _Compare& __comp = _Compare(),
146 const _Allocator& __a = _Allocator())
148 __glibcxx_check_valid_constructor_range(__first, __last)),
152 multimap(_Base_ref __x)
153 : _Base(__x._M_ref) { }
155#if __cplusplus >= 201103L
157 operator=(
const multimap&) =
default;
160 operator=(multimap&&) =
default;
163 operator=(initializer_list<value_type> __l)
165 _Base::operator=(__l);
166 this->_M_invalidate_all();
171 using _Base::get_allocator;
175 begin() _GLIBCXX_NOEXCEPT
176 {
return iterator(_Base::begin(),
this); }
179 begin() const _GLIBCXX_NOEXCEPT
180 {
return const_iterator(_Base::begin(),
this); }
183 end() _GLIBCXX_NOEXCEPT
184 {
return iterator(_Base::end(),
this); }
187 end() const _GLIBCXX_NOEXCEPT
188 {
return const_iterator(_Base::end(),
this); }
191 rbegin() _GLIBCXX_NOEXCEPT
192 {
return reverse_iterator(end()); }
194 const_reverse_iterator
195 rbegin() const _GLIBCXX_NOEXCEPT
196 {
return const_reverse_iterator(end()); }
199 rend() _GLIBCXX_NOEXCEPT
200 {
return reverse_iterator(begin()); }
202 const_reverse_iterator
203 rend() const _GLIBCXX_NOEXCEPT
204 {
return const_reverse_iterator(begin()); }
206#if __cplusplus >= 201103L
208 cbegin() const noexcept
209 {
return const_iterator(_Base::begin(),
this); }
212 cend() const noexcept
213 {
return const_iterator(_Base::end(),
this); }
215 const_reverse_iterator
216 crbegin() const noexcept
217 {
return const_reverse_iterator(end()); }
219 const_reverse_iterator
220 crend() const noexcept
221 {
return const_reverse_iterator(begin()); }
227 using _Base::max_size;
230#if __cplusplus >= 201103L
231 template<
typename... _Args>
233 emplace(_Args&&... __args)
236 template<
typename... _Args>
238 emplace_hint(const_iterator __pos, _Args&&... __args)
250 insert(
const value_type& __x)
251 {
return iterator(_Base::insert(__x),
this); }
253#if __cplusplus >= 201103L
257 insert(value_type&& __x)
258 {
return { _Base::insert(
std::move(__x)),
this }; }
260 template<
typename _Pair,
typename =
typename
262 _Pair&&>::value>::type>
268#if __cplusplus >= 201103L
271 { _Base::insert(__list); }
275#if __cplusplus >= 201103L
276 insert(const_iterator __position,
const value_type& __x)
278 insert(iterator __position,
const value_type& __x)
282 return iterator(_Base::insert(__position.base(), __x),
this);
285#if __cplusplus >= 201103L
289 insert(const_iterator __position, value_type&& __x)
292 return { _Base::insert(__position.base(),
std::move(__x)),
this };
295 template<
typename _Pair,
typename =
typename
297 _Pair&&>::value>::type>
299 insert(const_iterator __position, _Pair&& __x)
310 template<
typename _InputIterator>
312 insert(_InputIterator __first, _InputIterator __last)
315 __glibcxx_check_valid_range2(__first, __last, __dist);
317 if (__dist.
second >= __gnu_debug::__dp_sign)
318 _Base::insert(__gnu_debug::__unsafe(__first),
319 __gnu_debug::__unsafe(__last));
321 _Base::insert(__first, __last);
324#if __cplusplus > 201402L
325 using node_type =
typename _Base::node_type;
328 extract(const_iterator __position)
332 return _Base::extract(__position.base());
336 extract(
const key_type& __key)
338 const auto __position = find(__key);
339 if (__position != end())
340 return extract(__position);
345 insert(node_type&& __nh)
346 {
return { _Base::insert(
std::move(__nh)),
this }; }
349 insert(const_iterator __hint, node_type&& __nh)
352 return { _Base::insert(__hint.base(),
std::move(__nh)),
this };
358#if __cplusplus >= 201103L
360 erase(const_iterator __position)
363 return { erase(__position.base()),
this };
367 erase(_Base_const_iterator __position)
369 __glibcxx_check_erase2(__position);
371 return _Base::erase(__position);
374 _GLIBCXX_ABI_TAG_CXX11
376 erase(iterator __position)
377 {
return erase(const_iterator(__position)); }
380 erase(iterator __position)
384 _Base::erase(__position.base());
389 erase(
const key_type& __x)
392 _Base::equal_range(__x);
393 size_type __count = 0;
394 _Base_iterator __victim = __victims.
first;
395 while (__victim != __victims.
second)
398 _Base::erase(__victim++);
404#if __cplusplus >= 201103L
406 erase(const_iterator __first, const_iterator __last)
411 for (_Base_const_iterator __victim = __first.base();
412 __victim != __last.base(); ++__victim)
414 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(),
415 _M_message(__gnu_debug::__msg_valid_range)
416 ._M_iterator(__first,
"first")
417 ._M_iterator(__last,
"last"));
421 return { _Base::erase(__first.base(), __last.base()),
this };
425 erase(iterator __first, iterator __last)
430 for (_Base_iterator __victim = __first.base();
431 __victim != __last.base(); ++__victim)
433 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
434 _M_message(__gnu_debug::__msg_valid_range)
435 ._M_iterator(__first,
"first")
436 ._M_iterator(__last,
"last"));
439 _Base::erase(__first.base(), __last.base());
452 clear() _GLIBCXX_NOEXCEPT
454 this->_M_invalidate_all();
459 using _Base::key_comp;
460 using _Base::value_comp;
464 find(
const key_type& __x)
465 {
return iterator(_Base::find(__x),
this); }
467#if __cplusplus > 201103L
468 template<
typename _Kt,
470 typename __has_is_transparent<_Compare, _Kt>::type>
473 {
return { _Base::find(__x),
this }; }
477 find(
const key_type& __x)
const
478 {
return const_iterator(_Base::find(__x),
this); }
480#if __cplusplus > 201103L
481 template<
typename _Kt,
483 typename __has_is_transparent<_Compare, _Kt>::type>
485 find(
const _Kt& __x)
const
486 {
return { _Base::find(__x),
this }; }
492 lower_bound(
const key_type& __x)
493 {
return iterator(_Base::lower_bound(__x),
this); }
495#if __cplusplus > 201103L
496 template<
typename _Kt,
498 typename __has_is_transparent<_Compare, _Kt>::type>
500 lower_bound(
const _Kt& __x)
501 {
return { _Base::lower_bound(__x),
this }; }
505 lower_bound(
const key_type& __x)
const
506 {
return const_iterator(_Base::lower_bound(__x),
this); }
508#if __cplusplus > 201103L
509 template<
typename _Kt,
511 typename __has_is_transparent<_Compare, _Kt>::type>
513 lower_bound(
const _Kt& __x)
const
514 {
return { _Base::lower_bound(__x),
this }; }
518 upper_bound(
const key_type& __x)
519 {
return iterator(_Base::upper_bound(__x),
this); }
521#if __cplusplus > 201103L
522 template<
typename _Kt,
524 typename __has_is_transparent<_Compare, _Kt>::type>
526 upper_bound(
const _Kt& __x)
527 {
return { _Base::upper_bound(__x),
this }; }
531 upper_bound(
const key_type& __x)
const
532 {
return const_iterator(_Base::upper_bound(__x),
this); }
534#if __cplusplus > 201103L
535 template<
typename _Kt,
537 typename __has_is_transparent<_Compare, _Kt>::type>
539 upper_bound(
const _Kt& __x)
const
540 {
return { _Base::upper_bound(__x),
this }; }
544 equal_range(
const key_type& __x)
547 _Base::equal_range(__x);
549 iterator(__res.
second,
this));
552#if __cplusplus > 201103L
553 template<
typename _Kt,
555 typename __has_is_transparent<_Compare, _Kt>::type>
557 equal_range(
const _Kt& __x)
559 auto __res = _Base::equal_range(__x);
560 return { { __res.
first,
this }, { __res.
second,
this } };
565 equal_range(
const key_type& __x)
const
568 _Base::equal_range(__x);
570 const_iterator(__res.
second,
this));
573#if __cplusplus > 201103L
574 template<
typename _Kt,
576 typename __has_is_transparent<_Compare, _Kt>::type>
578 equal_range(
const _Kt& __x)
const
580 auto __res = _Base::equal_range(__x);
581 return { { __res.
first,
this }, { __res.
second,
this } };
586 _M_base() _GLIBCXX_NOEXCEPT {
return *
this; }
589 _M_base() const _GLIBCXX_NOEXCEPT {
return *
this; }
592#if __cpp_deduction_guides >= 201606
594 template<
typename _InputIterator,
595 typename _Compare = less<__iter_key_t<_InputIterator>>,
596 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
597 typename = _RequireInputIter<_InputIterator>,
598 typename = _RequireNotAllocator<_Compare>,
599 typename = _RequireAllocator<_Allocator>>
600 multimap(_InputIterator, _InputIterator,
601 _Compare = _Compare(), _Allocator = _Allocator())
602 -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
603 _Compare, _Allocator>;
605 template<
typename _Key,
typename _Tp,
typename _Compare = less<_Key>,
606 typename _Allocator = allocator<pair<const _Key, _Tp>>,
607 typename = _RequireNotAllocator<_Compare>,
608 typename = _RequireAllocator<_Allocator>>
610 _Compare = _Compare(), _Allocator = _Allocator())
611 -> multimap<_Key, _Tp, _Compare, _Allocator>;
613 template<
typename _InputIterator,
typename _Allocator,
614 typename = _RequireInputIter<_InputIterator>,
615 typename = _RequireAllocator<_Allocator>>
616 multimap(_InputIterator, _InputIterator, _Allocator)
617 -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
618 less<__iter_key_t<_InputIterator>>, _Allocator>;
620 template<
typename _Key,
typename _Tp,
typename _Allocator,
621 typename = _RequireAllocator<_Allocator>>
623 -> multimap<_Key, _Tp, less<_Key>, _Allocator>;
627 template<
typename _Key,
typename _Tp,
628 typename _Compare,
typename _Allocator>
630 operator==(
const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
631 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
632 {
return __lhs._M_base() == __rhs._M_base(); }
634#if __cpp_lib_three_way_comparison
635 template<
typename _Key,
typename _Tp,
typename _Compare,
typename _Alloc>
636 inline __detail::__synth3way_t<pair<const _Key, _Tp>>
637 operator<=>(
const multimap<_Key, _Tp, _Compare, _Alloc>& __lhs,
638 const multimap<_Key, _Tp, _Compare, _Alloc>& __rhs)
639 {
return __lhs._M_base() <=> __rhs._M_base(); }
641 template<
typename _Key,
typename _Tp,
642 typename _Compare,
typename _Allocator>
644 operator!=(
const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
645 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
646 {
return __lhs._M_base() != __rhs._M_base(); }
648 template<
typename _Key,
typename _Tp,
649 typename _Compare,
typename _Allocator>
651 operator<(
const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
652 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
653 {
return __lhs._M_base() < __rhs._M_base(); }
655 template<
typename _Key,
typename _Tp,
656 typename _Compare,
typename _Allocator>
658 operator<=(
const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
659 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
660 {
return __lhs._M_base() <= __rhs._M_base(); }
662 template<
typename _Key,
typename _Tp,
663 typename _Compare,
typename _Allocator>
665 operator>=(
const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
666 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
667 {
return __lhs._M_base() >= __rhs._M_base(); }
669 template<
typename _Key,
typename _Tp,
670 typename _Compare,
typename _Allocator>
672 operator>(
const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
673 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
674 {
return __lhs._M_base() > __rhs._M_base(); }
677 template<
typename _Key,
typename _Tp,
678 typename _Compare,
typename _Allocator>
680 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
681 multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
682 _GLIBCXX_NOEXCEPT_IF(
noexcept(__lhs.swap(__rhs)))
683 { __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)
pair(_T1, _T2) -> pair< _T1, _T2 >
Two pairs of the same type are equal iff their members are equal.
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
auto declval() noexcept -> decltype(__declval< _Tp >(0))
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
ISO C++ entities toplevel namespace is std.
GNU debug classes for public use.
constexpr _Iterator __base(_Iterator __it)
Define a member typedef type only if a boolean constant is true.
Struct holding two objects of arbitrary type.
_T1 first
The first member.
_T2 second
The second member.
void _M_invalidate_if(_Predicate __pred)
Safe class dealing with some allocator dependent operations.
Like _Safe_sequence but with a special _M_invalidate_all implementation not invalidating past-the-end...