libstdc++
debug/multimap.h
Go to the documentation of this file.
1// Debugging multimap implementation -*- C++ -*-
2
3// Copyright (C) 2003-2018 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/multimap.h
26 * This file is a GNU debug extension to the Standard C++ Library.
27 */
28
29#ifndef _GLIBCXX_DEBUG_MULTIMAP_H
30#define _GLIBCXX_DEBUG_MULTIMAP_H 1
31
32#include <debug/safe_sequence.h>
34#include <debug/safe_iterator.h>
35#include <utility>
36
37namespace std _GLIBCXX_VISIBILITY(default)
38{
39namespace __debug
40{
41 /// Class std::multimap 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> > >
46 multimap<_Key, _Tp, _Compare, _Allocator>, _Allocator,
47 __gnu_debug::_Safe_node_sequence>,
48 public _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator>
49 {
50 typedef _GLIBCXX_STD_C::multimap<
51 _Key, _Tp, _Compare, _Allocator> _Base;
54
56 typedef typename _Base::iterator _Base_iterator;
58
59 public:
60 // types:
61 typedef _Key key_type;
62 typedef _Tp mapped_type;
64 typedef _Compare key_compare;
65 typedef _Allocator allocator_type;
66 typedef typename _Base::reference reference;
67 typedef typename _Base::const_reference const_reference;
68
73
74 typedef typename _Base::size_type size_type;
75 typedef typename _Base::difference_type difference_type;
76 typedef typename _Base::pointer pointer;
77 typedef typename _Base::const_pointer const_pointer;
80
81 // 23.3.1.1 construct/copy/destroy:
82
83#if __cplusplus < 201103L
84 multimap() : _Base() { }
85
86 multimap(const multimap& __x)
87 : _Base(__x) { }
88
89 ~multimap() { }
90#else
91 multimap() = default;
92 multimap(const multimap&) = default;
93 multimap(multimap&&) = default;
94
96 const _Compare& __c = _Compare(),
97 const allocator_type& __a = allocator_type())
98 : _Base(__l, __c, __a) { }
99
100 explicit
101 multimap(const allocator_type& __a)
102 : _Base(__a) { }
103
104 multimap(const multimap& __m, const allocator_type& __a)
105 : _Base(__m, __a) { }
106
107 multimap(multimap&& __m, const allocator_type& __a)
108 noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) )
109 : _Safe(std::move(__m._M_safe()), __a),
110 _Base(std::move(__m._M_base()), __a) { }
111
112 multimap(initializer_list<value_type> __l, const allocator_type& __a)
113 : _Base(__l, __a) { }
114
115 template<typename _InputIterator>
116 multimap(_InputIterator __first, _InputIterator __last,
117 const allocator_type& __a)
118 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
119 __last)),
120 __gnu_debug::__base(__last), __a) { }
121
122 ~multimap() = default;
123#endif
124
125 explicit multimap(const _Compare& __comp,
126 const _Allocator& __a = _Allocator())
127 : _Base(__comp, __a) { }
128
129 template<typename _InputIterator>
130 multimap(_InputIterator __first, _InputIterator __last,
131 const _Compare& __comp = _Compare(),
132 const _Allocator& __a = _Allocator())
133 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
134 __last)),
135 __gnu_debug::__base(__last),
136 __comp, __a) { }
137
138 multimap(const _Base& __x)
139 : _Base(__x) { }
140
141#if __cplusplus < 201103L
142 multimap&
143 operator=(const multimap& __x)
144 {
145 this->_M_safe() = __x;
146 _M_base() = __x;
147 return *this;
148 }
149#else
150 multimap&
151 operator=(const multimap&) = default;
152
153 multimap&
154 operator=(multimap&&) = default;
155
156 multimap&
157 operator=(initializer_list<value_type> __l)
158 {
159 _M_base() = __l;
160 this->_M_invalidate_all();
161 return *this;
162 }
163#endif
164
165 using _Base::get_allocator;
166
167 // iterators:
169 begin() _GLIBCXX_NOEXCEPT
170 { return iterator(_Base::begin(), this); }
171
173 begin() const _GLIBCXX_NOEXCEPT
174 { return const_iterator(_Base::begin(), this); }
175
177 end() _GLIBCXX_NOEXCEPT
178 { return iterator(_Base::end(), this); }
179
181 end() const _GLIBCXX_NOEXCEPT
182 { return const_iterator(_Base::end(), this); }
183
185 rbegin() _GLIBCXX_NOEXCEPT
186 { return reverse_iterator(end()); }
187
189 rbegin() const _GLIBCXX_NOEXCEPT
190 { return const_reverse_iterator(end()); }
191
193 rend() _GLIBCXX_NOEXCEPT
194 { return reverse_iterator(begin()); }
195
197 rend() const _GLIBCXX_NOEXCEPT
198 { return const_reverse_iterator(begin()); }
199
200#if __cplusplus >= 201103L
202 cbegin() const noexcept
203 { return const_iterator(_Base::begin(), this); }
204
206 cend() const noexcept
207 { return const_iterator(_Base::end(), this); }
208
210 crbegin() const noexcept
211 { return const_reverse_iterator(end()); }
212
214 crend() const noexcept
215 { return const_reverse_iterator(begin()); }
216#endif
217
218 // capacity:
219 using _Base::empty;
220 using _Base::size;
221 using _Base::max_size;
222
223 // modifiers:
224#if __cplusplus >= 201103L
225 template<typename... _Args>
227 emplace(_Args&&... __args)
228 {
229 return iterator(_Base::emplace(std::forward<_Args>(__args)...), this);
230 }
231
232 template<typename... _Args>
234 emplace_hint(const_iterator __pos, _Args&&... __args)
235 {
237 return iterator(_Base::emplace_hint(__pos.base(),
238 std::forward<_Args>(__args)...),
239 this);
240 }
241#endif
242
244 insert(const value_type& __x)
245 { return iterator(_Base::insert(__x), this); }
246
247#if __cplusplus >= 201103L
248 // _GLIBCXX_RESOLVE_LIB_DEFECTS
249 // 2354. Unnecessary copying when inserting into maps with braced-init
251 insert(value_type&& __x)
252 { return { _Base::insert(std::move(__x)), this }; }
253
254 template<typename _Pair, typename = typename
256 _Pair&&>::value>::type>
258 insert(_Pair&& __x)
259 { return iterator(_Base::insert(std::forward<_Pair>(__x)), this); }
260#endif
261
262#if __cplusplus >= 201103L
263 void
265 { _Base::insert(__list); }
266#endif
267
269#if __cplusplus >= 201103L
270 insert(const_iterator __position, const value_type& __x)
271#else
272 insert(iterator __position, const value_type& __x)
273#endif
274 {
275 __glibcxx_check_insert(__position);
276 return iterator(_Base::insert(__position.base(), __x), this);
277 }
278
279#if __cplusplus >= 201103L
280 // _GLIBCXX_RESOLVE_LIB_DEFECTS
281 // 2354. Unnecessary copying when inserting into maps with braced-init
283 insert(const_iterator __position, value_type&& __x)
284 {
285 __glibcxx_check_insert(__position);
286 return { _Base::insert(__position.base(), std::move(__x)), this };
287 }
288
289 template<typename _Pair, typename = typename
291 _Pair&&>::value>::type>
293 insert(const_iterator __position, _Pair&& __x)
294 {
295 __glibcxx_check_insert(__position);
296 return iterator(_Base::insert(__position.base(),
297 std::forward<_Pair>(__x)), this);
298 }
299#endif
300
301 template<typename _InputIterator>
302 void
303 insert(_InputIterator __first, _InputIterator __last)
304 {
306 __glibcxx_check_valid_range2(__first, __last, __dist);
307
308 if (__dist.second >= __gnu_debug::__dp_sign)
309 _Base::insert(__gnu_debug::__unsafe(__first),
310 __gnu_debug::__unsafe(__last));
311 else
312 _Base::insert(__first, __last);
313 }
314
315#if __cplusplus > 201402L
316 using node_type = typename _Base::node_type;
317
318 node_type
319 extract(const_iterator __position)
320 {
321 __glibcxx_check_erase(__position);
322 this->_M_invalidate_if(_Equal(__position.base()));
323 return _Base::extract(__position.base());
324 }
325
326 node_type
327 extract(const key_type& __key)
328 {
329 const auto __position = find(__key);
330 if (__position != end())
331 return extract(__position);
332 return {};
333 }
334
336 insert(node_type&& __nh)
337 { return iterator(_Base::insert(std::move(__nh)), this); }
338
340 insert(const_iterator __hint, node_type&& __nh)
341 {
343 return iterator(_Base::insert(__hint.base(), std::move(__nh)), this);
344 }
345
346 using _Base::merge;
347#endif // C++17
348
349#if __cplusplus >= 201103L
351 erase(const_iterator __position)
352 {
353 __glibcxx_check_erase(__position);
354 this->_M_invalidate_if(_Equal(__position.base()));
355 return iterator(_Base::erase(__position.base()), this);
356 }
357
359 erase(iterator __position)
360 { return erase(const_iterator(__position)); }
361#else
362 void
363 erase(iterator __position)
364 {
365 __glibcxx_check_erase(__position);
366 this->_M_invalidate_if(_Equal(__position.base()));
367 _Base::erase(__position.base());
368 }
369#endif
370
371 size_type
372 erase(const key_type& __x)
373 {
375 _Base::equal_range(__x);
376 size_type __count = 0;
377 _Base_iterator __victim = __victims.first;
378 while (__victim != __victims.second)
379 {
380 this->_M_invalidate_if(_Equal(__victim));
381 _Base::erase(__victim++);
382 ++__count;
383 }
384 return __count;
385 }
386
387#if __cplusplus >= 201103L
389 erase(const_iterator __first, const_iterator __last)
390 {
391 // _GLIBCXX_RESOLVE_LIB_DEFECTS
392 // 151. can't currently clear() empty container
393 __glibcxx_check_erase_range(__first, __last);
394 for (_Base_const_iterator __victim = __first.base();
395 __victim != __last.base(); ++__victim)
396 {
397 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
398 _M_message(__gnu_debug::__msg_valid_range)
399 ._M_iterator(__first, "first")
400 ._M_iterator(__last, "last"));
401 this->_M_invalidate_if(_Equal(__victim));
402 }
403 return iterator(_Base::erase(__first.base(), __last.base()), this);
404 }
405#else
406 void
407 erase(iterator __first, iterator __last)
408 {
409 // _GLIBCXX_RESOLVE_LIB_DEFECTS
410 // 151. can't currently clear() empty container
411 __glibcxx_check_erase_range(__first, __last);
412 for (_Base_iterator __victim = __first.base();
413 __victim != __last.base(); ++__victim)
414 {
415 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
416 _M_message(__gnu_debug::__msg_valid_range)
417 ._M_iterator(__first, "first")
418 ._M_iterator(__last, "last"));
419 this->_M_invalidate_if(_Equal(__victim));
420 }
421 _Base::erase(__first.base(), __last.base());
422 }
423#endif
424
425 void
426 swap(multimap& __x)
427 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
428 {
429 _Safe::_M_swap(__x);
430 _Base::swap(__x);
431 }
432
433 void
434 clear() _GLIBCXX_NOEXCEPT
435 {
436 this->_M_invalidate_all();
437 _Base::clear();
438 }
439
440 // observers:
441 using _Base::key_comp;
442 using _Base::value_comp;
443
444 // 23.3.1.3 multimap operations:
446 find(const key_type& __x)
447 { return iterator(_Base::find(__x), this); }
448
449#if __cplusplus > 201103L
450 template<typename _Kt,
451 typename _Req =
452 typename __has_is_transparent<_Compare, _Kt>::type>
454 find(const _Kt& __x)
455 { return { _Base::find(__x), this }; }
456#endif
457
459 find(const key_type& __x) const
460 { return const_iterator(_Base::find(__x), this); }
461
462#if __cplusplus > 201103L
463 template<typename _Kt,
464 typename _Req =
465 typename __has_is_transparent<_Compare, _Kt>::type>
467 find(const _Kt& __x) const
468 { return { _Base::find(__x), this }; }
469#endif
470
471 using _Base::count;
472
474 lower_bound(const key_type& __x)
475 { return iterator(_Base::lower_bound(__x), this); }
476
477#if __cplusplus > 201103L
478 template<typename _Kt,
479 typename _Req =
480 typename __has_is_transparent<_Compare, _Kt>::type>
482 lower_bound(const _Kt& __x)
483 { return { _Base::lower_bound(__x), this }; }
484#endif
485
487 lower_bound(const key_type& __x) const
488 { return const_iterator(_Base::lower_bound(__x), this); }
489
490#if __cplusplus > 201103L
491 template<typename _Kt,
492 typename _Req =
493 typename __has_is_transparent<_Compare, _Kt>::type>
495 lower_bound(const _Kt& __x) const
496 { return { _Base::lower_bound(__x), this }; }
497#endif
498
500 upper_bound(const key_type& __x)
501 { return iterator(_Base::upper_bound(__x), this); }
502
503#if __cplusplus > 201103L
504 template<typename _Kt,
505 typename _Req =
506 typename __has_is_transparent<_Compare, _Kt>::type>
508 upper_bound(const _Kt& __x)
509 { return { _Base::upper_bound(__x), this }; }
510#endif
511
513 upper_bound(const key_type& __x) const
514 { return const_iterator(_Base::upper_bound(__x), this); }
515
516#if __cplusplus > 201103L
517 template<typename _Kt,
518 typename _Req =
519 typename __has_is_transparent<_Compare, _Kt>::type>
521 upper_bound(const _Kt& __x) const
522 { return { _Base::upper_bound(__x), this }; }
523#endif
524
526 equal_range(const key_type& __x)
527 {
529 _Base::equal_range(__x);
530 return std::make_pair(iterator(__res.first, this),
531 iterator(__res.second, this));
532 }
533
534#if __cplusplus > 201103L
535 template<typename _Kt,
536 typename _Req =
537 typename __has_is_transparent<_Compare, _Kt>::type>
539 equal_range(const _Kt& __x)
540 {
541 auto __res = _Base::equal_range(__x);
542 return { { __res.first, this }, { __res.second, this } };
543 }
544#endif
545
547 equal_range(const key_type& __x) const
548 {
550 _Base::equal_range(__x);
551 return std::make_pair(const_iterator(__res.first, this),
552 const_iterator(__res.second, this));
553 }
554
555#if __cplusplus > 201103L
556 template<typename _Kt,
557 typename _Req =
558 typename __has_is_transparent<_Compare, _Kt>::type>
560 equal_range(const _Kt& __x) const
561 {
562 auto __res = _Base::equal_range(__x);
563 return { { __res.first, this }, { __res.second, this } };
564 }
565#endif
566
567 _Base&
568 _M_base() _GLIBCXX_NOEXCEPT { return *this; }
569
570 const _Base&
571 _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
572 };
573
574#if __cpp_deduction_guides >= 201606
575
576 template<typename _InputIterator,
577 typename _Compare = less<__iter_key_t<_InputIterator>>,
578 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
579 typename = _RequireInputIter<_InputIterator>,
580 typename = _RequireAllocator<_Allocator>>
581 multimap(_InputIterator, _InputIterator,
582 _Compare = _Compare(), _Allocator = _Allocator())
583 -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
584 _Compare, _Allocator>;
585
586 template<typename _Key, typename _Tp, typename _Compare = less<_Key>,
587 typename _Allocator = allocator<pair<const _Key, _Tp>>,
588 typename = _RequireAllocator<_Allocator>>
590 _Compare = _Compare(), _Allocator = _Allocator())
592
593 template<typename _InputIterator, typename _Allocator,
594 typename = _RequireInputIter<_InputIterator>,
595 typename = _RequireAllocator<_Allocator>>
596 multimap(_InputIterator, _InputIterator, _Allocator)
597 -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
599
600 template<typename _Key, typename _Tp, typename _Allocator,
601 typename = _RequireAllocator<_Allocator>>
603 -> multimap<_Key, _Tp, less<_Key>, _Allocator>;
604
605#endif
606
607 template<typename _Key, typename _Tp,
608 typename _Compare, typename _Allocator>
609 inline bool
610 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
612 { return __lhs._M_base() == __rhs._M_base(); }
613
614 template<typename _Key, typename _Tp,
615 typename _Compare, typename _Allocator>
616 inline bool
617 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
619 { return __lhs._M_base() != __rhs._M_base(); }
620
621 template<typename _Key, typename _Tp,
622 typename _Compare, typename _Allocator>
623 inline bool
624 operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
625 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
626 { return __lhs._M_base() < __rhs._M_base(); }
627
628 template<typename _Key, typename _Tp,
629 typename _Compare, typename _Allocator>
630 inline bool
631 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
632 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
633 { return __lhs._M_base() <= __rhs._M_base(); }
634
635 template<typename _Key, typename _Tp,
636 typename _Compare, typename _Allocator>
637 inline bool
638 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
639 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
640 { return __lhs._M_base() >= __rhs._M_base(); }
641
642 template<typename _Key, typename _Tp,
643 typename _Compare, typename _Allocator>
644 inline bool
645 operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
646 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
647 { return __lhs._M_base() > __rhs._M_base(); }
648
649 template<typename _Key, typename _Tp,
650 typename _Compare, typename _Allocator>
651 inline void
652 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
653 multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
654 _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
655 { __lhs.swap(__rhs); }
656
657} // namespace __debug
658} // namespace std
659
660#endif
#define __glibcxx_check_insert(_Position)
Definition: macros.h:79
#define __glibcxx_check_erase_range(_First, _Last)
Definition: macros.h:173
#define __glibcxx_check_erase(_Position)
Definition: macros.h:145
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.
Definition: stl_pair.h:524
ISO C++ entities toplevel namespace is std.
initializer_list
is_constructible
Definition: type_traits:874
Define a member typedef type only if a boolean constant is true.
Definition: type_traits:1907
The standard allocator, as per [20.4].
Definition: allocator.h:109
One of the comparison functors.
Definition: stl_function.h:382
A standard container made up of (key,value) pairs, which can be retrieved based on a key,...
Definition: stl_multimap.h:100
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:210
_T1 first
second_type is the second bound type
Definition: stl_pair.h:214
_T2 second
first is a copy of the first object
Definition: stl_pair.h:215
Safe iterator wrapper.
Definition: safe_iterator.h:89
_Iterator & base() noexcept
Return the underlying iterator.
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...