1 // Debugging multimap 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/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>
33 #include <debug/safe_container.h>
34 #include <debug/safe_iterator.h>
35 #include <utility>
36
_GLIBCXX_VISIBILITY(default)37 namespace std _GLIBCXX_VISIBILITY(default)
38 {
39 namespace __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> > >
44 class multimap
45 : public __gnu_debug::_Safe_container<
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;
52 typedef __gnu_debug::_Safe_container<
53 multimap, _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, multimap>
73 iterator;
74 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
75 multimap> 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 multimap() : _Base() { }
88
89 multimap(const multimap& __x)
90 : _Base(__x) { }
91
92 ~multimap() { }
93 #else
94 multimap() = default;
95 multimap(const multimap&) = default;
96 multimap(multimap&&) = default;
97
98 multimap(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 multimap(const allocator_type& __a)
105 : _Base(__a) { }
106
107 multimap(const multimap& __m, const allocator_type& __a)
108 : _Base(__m, __a) { }
109
110 multimap(multimap&& __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 multimap(initializer_list<value_type> __l, const allocator_type& __a)
116 : _Base(__l, __a) { }
117
118 template<typename _InputIterator>
119 multimap(_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 ~multimap() = default;
126 #endif
127
128 explicit multimap(const _Compare& __comp,
129 const _Allocator& __a = _Allocator())
130 : _Base(__comp, __a) { }
131
132 template<typename _InputIterator>
133 multimap(_InputIterator __first, _InputIterator __last,
134 const _Compare& __comp = _Compare(),
135 const _Allocator& __a = _Allocator())
136 : _Base(__gnu_debug::__base(
137 __glibcxx_check_valid_constructor_range(__first, __last)),
138 __gnu_debug::__base(__last),
139 __comp, __a) { }
140
141 multimap(const _Base& __x)
142 : _Base(__x) { }
143
144 #if __cplusplus < 201103L
145 multimap&
146 operator=(const multimap& __x)
147 {
148 this->_M_safe() = __x;
149 _M_base() = __x;
150 return *this;
151 }
152 #else
153 multimap&
154 operator=(const multimap&) = default;
155
156 multimap&
157 operator=(multimap&&) = default;
158
159 multimap&
160 operator=(initializer_list<value_type> __l)
161 {
162 _M_base() = __l;
163 this->_M_invalidate_all();
164 return *this;
165 }
166 #endif
167
168 using _Base::get_allocator;
169
170 // iterators:
171 iterator
172 begin() _GLIBCXX_NOEXCEPT
173 { return iterator(_Base::begin(), this); }
174
175 const_iterator
176 begin() const _GLIBCXX_NOEXCEPT
177 { return const_iterator(_Base::begin(), this); }
178
179 iterator
180 end() _GLIBCXX_NOEXCEPT
181 { return iterator(_Base::end(), this); }
182
183 const_iterator
184 end() const _GLIBCXX_NOEXCEPT
185 { return const_iterator(_Base::end(), this); }
186
187 reverse_iterator
188 rbegin() _GLIBCXX_NOEXCEPT
189 { return reverse_iterator(end()); }
190
191 const_reverse_iterator
192 rbegin() const _GLIBCXX_NOEXCEPT
193 { return const_reverse_iterator(end()); }
194
195 reverse_iterator
196 rend() _GLIBCXX_NOEXCEPT
197 { return reverse_iterator(begin()); }
198
199 const_reverse_iterator
200 rend() const _GLIBCXX_NOEXCEPT
201 { return const_reverse_iterator(begin()); }
202
203 #if __cplusplus >= 201103L
204 const_iterator
205 cbegin() const noexcept
206 { return const_iterator(_Base::begin(), this); }
207
208 const_iterator
209 cend() const noexcept
210 { return const_iterator(_Base::end(), this); }
211
212 const_reverse_iterator
213 crbegin() const noexcept
214 { return const_reverse_iterator(end()); }
215
216 const_reverse_iterator
217 crend() const noexcept
218 { return const_reverse_iterator(begin()); }
219 #endif
220
221 // capacity:
222 using _Base::empty;
223 using _Base::size;
224 using _Base::max_size;
225
226 // modifiers:
227 #if __cplusplus >= 201103L
228 template<typename... _Args>
229 iterator
230 emplace(_Args&&... __args)
231 { return { _Base::emplace(std::forward<_Args>(__args)...), this }; }
232
233 template<typename... _Args>
234 iterator
235 emplace_hint(const_iterator __pos, _Args&&... __args)
236 {
237 __glibcxx_check_insert(__pos);
238 return
239 {
240 _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...),
241 this
242 };
243 }
244 #endif
245
246 iterator
247 insert(const value_type& __x)
248 { return iterator(_Base::insert(__x), this); }
249
250 #if __cplusplus >= 201103L
251 // _GLIBCXX_RESOLVE_LIB_DEFECTS
252 // 2354. Unnecessary copying when inserting into maps with braced-init
253 iterator
254 insert(value_type&& __x)
255 { return { _Base::insert(std::move(__x)), this }; }
256
257 template<typename _Pair, typename = typename
258 std::enable_if<std::is_constructible<value_type,
259 _Pair&&>::value>::type>
260 iterator
261 insert(_Pair&& __x)
262 { return { _Base::insert(std::forward<_Pair>(__x)), this }; }
263 #endif
264
265 #if __cplusplus >= 201103L
266 void
267 insert(std::initializer_list<value_type> __list)
268 { _Base::insert(__list); }
269 #endif
270
271 iterator
272 #if __cplusplus >= 201103L
273 insert(const_iterator __position, const value_type& __x)
274 #else
275 insert(iterator __position, const value_type& __x)
276 #endif
277 {
278 __glibcxx_check_insert(__position);
279 return iterator(_Base::insert(__position.base(), __x), this);
280 }
281
282 #if __cplusplus >= 201103L
283 // _GLIBCXX_RESOLVE_LIB_DEFECTS
284 // 2354. Unnecessary copying when inserting into maps with braced-init
285 iterator
286 insert(const_iterator __position, value_type&& __x)
287 {
288 __glibcxx_check_insert(__position);
289 return { _Base::insert(__position.base(), std::move(__x)), this };
290 }
291
292 template<typename _Pair, typename = typename
293 std::enable_if<std::is_constructible<value_type,
294 _Pair&&>::value>::type>
295 iterator
296 insert(const_iterator __position, _Pair&& __x)
297 {
298 __glibcxx_check_insert(__position);
299 return
300 {
301 _Base::insert(__position.base(), std::forward<_Pair>(__x)),
302 this
303 };
304 }
305 #endif
306
307 template<typename _InputIterator>
308 void
309 insert(_InputIterator __first, _InputIterator __last)
310 {
311 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
312 __glibcxx_check_valid_range2(__first, __last, __dist);
313
314 if (__dist.second >= __gnu_debug::__dp_sign)
315 _Base::insert(__gnu_debug::__unsafe(__first),
316 __gnu_debug::__unsafe(__last));
317 else
318 _Base::insert(__first, __last);
319 }
320
321 #if __cplusplus > 201402L
322 using node_type = typename _Base::node_type;
323
324 node_type
325 extract(const_iterator __position)
326 {
327 __glibcxx_check_erase(__position);
328 this->_M_invalidate_if(_Equal(__position.base()));
329 return _Base::extract(__position.base());
330 }
331
332 node_type
333 extract(const key_type& __key)
334 {
335 const auto __position = find(__key);
336 if (__position != end())
337 return extract(__position);
338 return {};
339 }
340
341 iterator
342 insert(node_type&& __nh)
343 { return { _Base::insert(std::move(__nh)), this }; }
344
345 iterator
346 insert(const_iterator __hint, node_type&& __nh)
347 {
348 __glibcxx_check_insert(__hint);
349 return { _Base::insert(__hint.base(), std::move(__nh)), this };
350 }
351
352 using _Base::merge;
353 #endif // C++17
354
355 #if __cplusplus >= 201103L
356 iterator
357 erase(const_iterator __position)
358 {
359 __glibcxx_check_erase(__position);
360 this->_M_invalidate_if(_Equal(__position.base()));
361 return { _Base::erase(__position.base()), this };
362 }
363
364 _GLIBCXX_ABI_TAG_CXX11
365 iterator
366 erase(iterator __position)
367 { return erase(const_iterator(__position)); }
368 #else
369 void
370 erase(iterator __position)
371 {
372 __glibcxx_check_erase(__position);
373 this->_M_invalidate_if(_Equal(__position.base()));
374 _Base::erase(__position.base());
375 }
376 #endif
377
378 size_type
379 erase(const key_type& __x)
380 {
381 std::pair<_Base_iterator, _Base_iterator> __victims =
382 _Base::equal_range(__x);
383 size_type __count = 0;
384 _Base_iterator __victim = __victims.first;
385 while (__victim != __victims.second)
386 {
387 this->_M_invalidate_if(_Equal(__victim));
388 _Base::erase(__victim++);
389 ++__count;
390 }
391 return __count;
392 }
393
394 #if __cplusplus >= 201103L
395 iterator
396 erase(const_iterator __first, const_iterator __last)
397 {
398 // _GLIBCXX_RESOLVE_LIB_DEFECTS
399 // 151. can't currently clear() empty container
400 __glibcxx_check_erase_range(__first, __last);
401 for (_Base_const_iterator __victim = __first.base();
402 __victim != __last.base(); ++__victim)
403 {
404 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(),
405 _M_message(__gnu_debug::__msg_valid_range)
406 ._M_iterator(__first, "first")
407 ._M_iterator(__last, "last"));
408 this->_M_invalidate_if(_Equal(__victim));
409 }
410
411 return { _Base::erase(__first.base(), __last.base()), this };
412 }
413 #else
414 void
415 erase(iterator __first, iterator __last)
416 {
417 // _GLIBCXX_RESOLVE_LIB_DEFECTS
418 // 151. can't currently clear() empty container
419 __glibcxx_check_erase_range(__first, __last);
420 for (_Base_iterator __victim = __first.base();
421 __victim != __last.base(); ++__victim)
422 {
423 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
424 _M_message(__gnu_debug::__msg_valid_range)
425 ._M_iterator(__first, "first")
426 ._M_iterator(__last, "last"));
427 this->_M_invalidate_if(_Equal(__victim));
428 }
429 _Base::erase(__first.base(), __last.base());
430 }
431 #endif
432
433 void
434 swap(multimap& __x)
435 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
436 {
437 _Safe::_M_swap(__x);
438 _Base::swap(__x);
439 }
440
441 void
442 clear() _GLIBCXX_NOEXCEPT
443 {
444 this->_M_invalidate_all();
445 _Base::clear();
446 }
447
448 // observers:
449 using _Base::key_comp;
450 using _Base::value_comp;
451
452 // 23.3.1.3 multimap operations:
453 iterator
454 find(const key_type& __x)
455 { return iterator(_Base::find(__x), this); }
456
457 #if __cplusplus > 201103L
458 template<typename _Kt,
459 typename _Req =
460 typename __has_is_transparent<_Compare, _Kt>::type>
461 iterator
462 find(const _Kt& __x)
463 { return { _Base::find(__x), this }; }
464 #endif
465
466 const_iterator
467 find(const key_type& __x) const
468 { return const_iterator(_Base::find(__x), this); }
469
470 #if __cplusplus > 201103L
471 template<typename _Kt,
472 typename _Req =
473 typename __has_is_transparent<_Compare, _Kt>::type>
474 const_iterator
475 find(const _Kt& __x) const
476 { return { _Base::find(__x), this }; }
477 #endif
478
479 using _Base::count;
480
481 iterator
482 lower_bound(const key_type& __x)
483 { return iterator(_Base::lower_bound(__x), this); }
484
485 #if __cplusplus > 201103L
486 template<typename _Kt,
487 typename _Req =
488 typename __has_is_transparent<_Compare, _Kt>::type>
489 iterator
490 lower_bound(const _Kt& __x)
491 { return { _Base::lower_bound(__x), this }; }
492 #endif
493
494 const_iterator
495 lower_bound(const key_type& __x) const
496 { return const_iterator(_Base::lower_bound(__x), this); }
497
498 #if __cplusplus > 201103L
499 template<typename _Kt,
500 typename _Req =
501 typename __has_is_transparent<_Compare, _Kt>::type>
502 const_iterator
503 lower_bound(const _Kt& __x) const
504 { return { _Base::lower_bound(__x), this }; }
505 #endif
506
507 iterator
508 upper_bound(const key_type& __x)
509 { return iterator(_Base::upper_bound(__x), this); }
510
511 #if __cplusplus > 201103L
512 template<typename _Kt,
513 typename _Req =
514 typename __has_is_transparent<_Compare, _Kt>::type>
515 iterator
516 upper_bound(const _Kt& __x)
517 { return { _Base::upper_bound(__x), this }; }
518 #endif
519
520 const_iterator
521 upper_bound(const key_type& __x) const
522 { return const_iterator(_Base::upper_bound(__x), this); }
523
524 #if __cplusplus > 201103L
525 template<typename _Kt,
526 typename _Req =
527 typename __has_is_transparent<_Compare, _Kt>::type>
528 const_iterator
529 upper_bound(const _Kt& __x) const
530 { return { _Base::upper_bound(__x), this }; }
531 #endif
532
533 std::pair<iterator,iterator>
534 equal_range(const key_type& __x)
535 {
536 std::pair<_Base_iterator, _Base_iterator> __res =
537 _Base::equal_range(__x);
538 return std::make_pair(iterator(__res.first, this),
539 iterator(__res.second, this));
540 }
541
542 #if __cplusplus > 201103L
543 template<typename _Kt,
544 typename _Req =
545 typename __has_is_transparent<_Compare, _Kt>::type>
546 std::pair<iterator, iterator>
547 equal_range(const _Kt& __x)
548 {
549 auto __res = _Base::equal_range(__x);
550 return { { __res.first, this }, { __res.second, this } };
551 }
552 #endif
553
554 std::pair<const_iterator,const_iterator>
555 equal_range(const key_type& __x) const
556 {
557 std::pair<_Base_const_iterator, _Base_const_iterator> __res =
558 _Base::equal_range(__x);
559 return std::make_pair(const_iterator(__res.first, this),
560 const_iterator(__res.second, this));
561 }
562
563 #if __cplusplus > 201103L
564 template<typename _Kt,
565 typename _Req =
566 typename __has_is_transparent<_Compare, _Kt>::type>
567 std::pair<const_iterator, const_iterator>
568 equal_range(const _Kt& __x) const
569 {
570 auto __res = _Base::equal_range(__x);
571 return { { __res.first, this }, { __res.second, this } };
572 }
573 #endif
574
575 _Base&
576 _M_base() _GLIBCXX_NOEXCEPT { return *this; }
577
578 const _Base&
579 _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
580 };
581
582 #if __cpp_deduction_guides >= 201606
583
584 template<typename _InputIterator,
585 typename _Compare = less<__iter_key_t<_InputIterator>>,
586 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
587 typename = _RequireInputIter<_InputIterator>,
588 typename = _RequireNotAllocator<_Compare>,
589 typename = _RequireAllocator<_Allocator>>
590 multimap(_InputIterator, _InputIterator,
591 _Compare = _Compare(), _Allocator = _Allocator())
592 -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
593 _Compare, _Allocator>;
594
595 template<typename _Key, typename _Tp, typename _Compare = less<_Key>,
596 typename _Allocator = allocator<pair<const _Key, _Tp>>,
597 typename = _RequireNotAllocator<_Compare>,
598 typename = _RequireAllocator<_Allocator>>
599 multimap(initializer_list<pair<_Key, _Tp>>,
600 _Compare = _Compare(), _Allocator = _Allocator())
601 -> multimap<_Key, _Tp, _Compare, _Allocator>;
602
603 template<typename _InputIterator, typename _Allocator,
604 typename = _RequireInputIter<_InputIterator>,
605 typename = _RequireAllocator<_Allocator>>
606 multimap(_InputIterator, _InputIterator, _Allocator)
607 -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
608 less<__iter_key_t<_InputIterator>>, _Allocator>;
609
610 template<typename _Key, typename _Tp, typename _Allocator,
611 typename = _RequireAllocator<_Allocator>>
612 multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
613 -> multimap<_Key, _Tp, less<_Key>, _Allocator>;
614
615 #endif
616
617 template<typename _Key, typename _Tp,
618 typename _Compare, typename _Allocator>
619 inline bool
620 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
621 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
622 { return __lhs._M_base() == __rhs._M_base(); }
623
624 #if __cpp_lib_three_way_comparison
625 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
626 inline __detail::__synth3way_t<pair<const _Key, _Tp>>
627 operator<=>(const multimap<_Key, _Tp, _Compare, _Alloc>& __lhs,
628 const multimap<_Key, _Tp, _Compare, _Alloc>& __rhs)
629 { return __lhs._M_base() <=> __rhs._M_base(); }
630 #else
631 template<typename _Key, typename _Tp,
632 typename _Compare, typename _Allocator>
633 inline bool
634 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
635 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
636 { return __lhs._M_base() != __rhs._M_base(); }
637
638 template<typename _Key, typename _Tp,
639 typename _Compare, typename _Allocator>
640 inline bool
641 operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
642 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
643 { return __lhs._M_base() < __rhs._M_base(); }
644
645 template<typename _Key, typename _Tp,
646 typename _Compare, typename _Allocator>
647 inline bool
648 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
649 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
650 { return __lhs._M_base() <= __rhs._M_base(); }
651
652 template<typename _Key, typename _Tp,
653 typename _Compare, typename _Allocator>
654 inline bool
655 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
656 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
657 { return __lhs._M_base() >= __rhs._M_base(); }
658
659 template<typename _Key, typename _Tp,
660 typename _Compare, typename _Allocator>
661 inline bool
662 operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
663 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
664 { return __lhs._M_base() > __rhs._M_base(); }
665 #endif // three-way comparison
666
667 template<typename _Key, typename _Tp,
668 typename _Compare, typename _Allocator>
669 inline void
670 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
671 multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
672 _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
673 { __lhs.swap(__rhs); }
674
675 } // namespace __debug
676 } // namespace std
677
678 #endif
679