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>
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 public:
60 // types:
61 typedef _Key key_type;
62 typedef _Tp mapped_type;
63 typedef std::pair<const _Key, _Tp> value_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
69 typedef __gnu_debug::_Safe_iterator<_Base_iterator, multimap>
70 iterator;
71 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
72 multimap> const_iterator;
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;
78 typedef std::reverse_iterator<iterator> reverse_iterator;
79 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
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
95 multimap(initializer_list<value_type> __l,
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:
168 iterator
169 begin() _GLIBCXX_NOEXCEPT
170 { return iterator(_Base::begin(), this); }
171
172 const_iterator
173 begin() const _GLIBCXX_NOEXCEPT
174 { return const_iterator(_Base::begin(), this); }
175
176 iterator
177 end() _GLIBCXX_NOEXCEPT
178 { return iterator(_Base::end(), this); }
179
180 const_iterator
181 end() const _GLIBCXX_NOEXCEPT
182 { return const_iterator(_Base::end(), this); }
183
184 reverse_iterator
185 rbegin() _GLIBCXX_NOEXCEPT
186 { return reverse_iterator(end()); }
187
188 const_reverse_iterator
189 rbegin() const _GLIBCXX_NOEXCEPT
190 { return const_reverse_iterator(end()); }
191
192 reverse_iterator
193 rend() _GLIBCXX_NOEXCEPT
194 { return reverse_iterator(begin()); }
195
196 const_reverse_iterator
197 rend() const _GLIBCXX_NOEXCEPT
198 { return const_reverse_iterator(begin()); }
199
200 #if __cplusplus >= 201103L
201 const_iterator
202 cbegin() const noexcept
203 { return const_iterator(_Base::begin(), this); }
204
205 const_iterator
206 cend() const noexcept
207 { return const_iterator(_Base::end(), this); }
208
209 const_reverse_iterator
210 crbegin() const noexcept
211 { return const_reverse_iterator(end()); }
212
213 const_reverse_iterator
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>
226 iterator
227 emplace(_Args&&... __args)
228 {
229 return iterator(_Base::emplace(std::forward<_Args>(__args)...), this);
230 }
231
232 template<typename... _Args>
233 iterator
234 emplace_hint(const_iterator __pos, _Args&&... __args)
235 {
236 __glibcxx_check_insert(__pos);
237 return iterator(_Base::emplace_hint(__pos.base(),
238 std::forward<_Args>(__args)...),
239 this);
240 }
241 #endif
242
243 iterator
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
250 iterator
251 insert(value_type&& __x)
252 { return { _Base::insert(std::move(__x)), this }; }
253
254 template<typename _Pair, typename = typename
255 std::enable_if<std::is_constructible<value_type,
256 _Pair&&>::value>::type>
257 iterator
258 insert(_Pair&& __x)
259 { return iterator(_Base::insert(std::forward<_Pair>(__x)), this); }
260 #endif
261
262 #if __cplusplus >= 201103L
263 void
264 insert(std::initializer_list<value_type> __list)
265 { _Base::insert(__list); }
266 #endif
267
268 iterator
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
282 iterator
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
290 std::enable_if<std::is_constructible<value_type,
291 _Pair&&>::value>::type>
292 iterator
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 {
305 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
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
335 iterator
336 insert(node_type&& __nh)
337 { return iterator(_Base::insert(std::move(__nh)), this); }
338
339 iterator
340 insert(const_iterator __hint, node_type&& __nh)
341 {
342 __glibcxx_check_insert(__hint);
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
350 iterator
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
358 iterator
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 {
374 std::pair<_Base_iterator, _Base_iterator> __victims =
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
388 iterator
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:
445 iterator
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>
453 iterator
454 find(const _Kt& __x)
455 { return { _Base::find(__x), this }; }
456 #endif
457
458 const_iterator
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>
466 const_iterator
467 find(const _Kt& __x) const
468 { return { _Base::find(__x), this }; }
469 #endif
470
471 using _Base::count;
472
473 iterator
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>
481 iterator
482 lower_bound(const _Kt& __x)
483 { return { _Base::lower_bound(__x), this }; }
484 #endif
485
486 const_iterator
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>
494 const_iterator
495 lower_bound(const _Kt& __x) const
496 { return { _Base::lower_bound(__x), this }; }
497 #endif
498
499 iterator
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>
507 iterator
508 upper_bound(const _Kt& __x)
509 { return { _Base::upper_bound(__x), this }; }
510 #endif
511
512 const_iterator
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>
520 const_iterator
521 upper_bound(const _Kt& __x) const
522 { return { _Base::upper_bound(__x), this }; }
523 #endif
524
525 std::pair<iterator,iterator>
526 equal_range(const key_type& __x)
527 {
528 std::pair<_Base_iterator, _Base_iterator> __res =
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>
538 std::pair<iterator, iterator>
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
546 std::pair<const_iterator,const_iterator>
547 equal_range(const key_type& __x) const
548 {
549 std::pair<_Base_const_iterator, _Base_const_iterator> __res =
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>
559 std::pair<const_iterator, const_iterator>
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>>
589 multimap(initializer_list<pair<_Key, _Tp>>,
590 _Compare = _Compare(), _Allocator = _Allocator())
591 -> multimap<_Key, _Tp, _Compare, _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>,
598 less<__iter_key_t<_InputIterator>>, _Allocator>;
599
600 template<typename _Key, typename _Tp, typename _Allocator,
601 typename = _RequireAllocator<_Allocator>>
602 multimap(initializer_list<pair<_Key, _Tp>>, _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,
611 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
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,
618 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
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
661