libstdc++
multiset.h
Go to the documentation of this file.
1// Debugging multiset implementation -*- C++ -*-
2
3// Copyright (C) 2003-2021 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/multiset.h
26 * This file is a GNU debug extension to the Standard C++ Library.
27 */
28
29#ifndef _GLIBCXX_DEBUG_MULTISET_H
30#define _GLIBCXX_DEBUG_MULTISET_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
37namespace std _GLIBCXX_VISIBILITY(default)
38{
39namespace __debug
40{
41 /// Class std::multiset with safety/checking/debug instrumentation.
42 template<typename _Key, typename _Compare = std::less<_Key>,
43 typename _Allocator = std::allocator<_Key> >
44 class multiset
45 : public __gnu_debug::_Safe_container<
46 multiset<_Key, _Compare, _Allocator>, _Allocator,
47 __gnu_debug::_Safe_node_sequence>,
48 public _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>
49 {
50 typedef _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator> _Base;
51 typedef __gnu_debug::_Safe_container<
52 multiset, _Allocator, __gnu_debug::_Safe_node_sequence> _Safe;
53
54 typedef typename _Base::const_iterator _Base_const_iterator;
55 typedef typename _Base::iterator _Base_iterator;
56 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
57
58 template<typename _ItT, typename _SeqT, typename _CatT>
59 friend class ::__gnu_debug::_Safe_iterator;
60
61 // Reference wrapper for base class. Disambiguates multiset(const _Base&)
62 // from copy constructor by requiring a user-defined conversion.
63 // See PR libstdc++/90102.
64 struct _Base_ref
65 {
66 _Base_ref(const _Base& __r) : _M_ref(__r) { }
67
68 const _Base& _M_ref;
69 };
70
71 public:
72 // types:
73 typedef _Key key_type;
74 typedef _Key value_type;
75 typedef _Compare key_compare;
76 typedef _Compare value_compare;
77 typedef _Allocator allocator_type;
78 typedef typename _Base::reference reference;
79 typedef typename _Base::const_reference const_reference;
80
81 typedef __gnu_debug::_Safe_iterator<_Base_iterator, multiset>
82 iterator;
83 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
84 multiset> const_iterator;
85
86 typedef typename _Base::size_type size_type;
87 typedef typename _Base::difference_type difference_type;
88 typedef typename _Base::pointer pointer;
89 typedef typename _Base::const_pointer const_pointer;
90 typedef std::reverse_iterator<iterator> reverse_iterator;
91 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
92
93 // 23.3.3.1 construct/copy/destroy:
94
95#if __cplusplus < 201103L
96 multiset() : _Base() { }
97
98 multiset(const multiset& __x)
99 : _Base(__x) { }
100
101 ~multiset() { }
102#else
103 multiset() = default;
104 multiset(const multiset&) = default;
105 multiset(multiset&&) = default;
106
107 multiset(initializer_list<value_type> __l,
108 const _Compare& __comp = _Compare(),
109 const allocator_type& __a = allocator_type())
110 : _Base(__l, __comp, __a) { }
111
112 explicit
113 multiset(const allocator_type& __a)
114 : _Base(__a) { }
115
116 multiset(const multiset& __m, const allocator_type& __a)
117 : _Base(__m, __a) { }
118
119 multiset(multiset&& __m, const allocator_type& __a)
120 noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) )
121 : _Safe(std::move(__m._M_safe()), __a),
122 _Base(std::move(__m._M_base()), __a) { }
123
124 multiset(initializer_list<value_type> __l, const allocator_type& __a)
125 : _Base(__l, __a)
126 { }
127
128 template<typename _InputIterator>
129 multiset(_InputIterator __first, _InputIterator __last,
130 const allocator_type& __a)
131 : _Base(__gnu_debug::__base(
132 __glibcxx_check_valid_constructor_range(__first, __last)),
133 __gnu_debug::__base(__last), __a) { }
134
135 ~multiset() = default;
136#endif
137
138 explicit multiset(const _Compare& __comp,
139 const _Allocator& __a = _Allocator())
140 : _Base(__comp, __a) { }
141
142 template<typename _InputIterator>
143 multiset(_InputIterator __first, _InputIterator __last,
144 const _Compare& __comp = _Compare(),
145 const _Allocator& __a = _Allocator())
146 : _Base(__gnu_debug::__base(
147 __glibcxx_check_valid_constructor_range(__first, __last)),
148 __gnu_debug::__base(__last),
149 __comp, __a) { }
150
151 multiset(_Base_ref __x)
152 : _Base(__x._M_ref) { }
153
154#if __cplusplus < 201103L
155 multiset&
156 operator=(const multiset& __x)
157 {
158 this->_M_safe() = __x;
159 _M_base() = __x;
160 return *this;
161 }
162#else
163 multiset&
164 operator=(const multiset&) = default;
165
166 multiset&
167 operator=(multiset&&) = default;
168
169 multiset&
170 operator=(initializer_list<value_type> __l)
171 {
172 _M_base() = __l;
173 this->_M_invalidate_all();
174 return *this;
175 }
176#endif
177
178 using _Base::get_allocator;
179
180 // iterators:
181 iterator
182 begin() _GLIBCXX_NOEXCEPT
183 { return iterator(_Base::begin(), this); }
184
185 const_iterator
186 begin() const _GLIBCXX_NOEXCEPT
187 { return const_iterator(_Base::begin(), this); }
188
189 iterator
190 end() _GLIBCXX_NOEXCEPT
191 { return iterator(_Base::end(), this); }
192
193 const_iterator
194 end() const _GLIBCXX_NOEXCEPT
195 { return const_iterator(_Base::end(), this); }
196
197 reverse_iterator
198 rbegin() _GLIBCXX_NOEXCEPT
199 { return reverse_iterator(end()); }
200
201 const_reverse_iterator
202 rbegin() const _GLIBCXX_NOEXCEPT
203 { return const_reverse_iterator(end()); }
204
205 reverse_iterator
206 rend() _GLIBCXX_NOEXCEPT
207 { return reverse_iterator(begin()); }
208
209 const_reverse_iterator
210 rend() const _GLIBCXX_NOEXCEPT
211 { return const_reverse_iterator(begin()); }
212
213#if __cplusplus >= 201103L
214 const_iterator
215 cbegin() const noexcept
216 { return const_iterator(_Base::begin(), this); }
217
218 const_iterator
219 cend() const noexcept
220 { return const_iterator(_Base::end(), this); }
221
222 const_reverse_iterator
223 crbegin() const noexcept
224 { return const_reverse_iterator(end()); }
225
226 const_reverse_iterator
227 crend() const noexcept
228 { return const_reverse_iterator(begin()); }
229#endif
230
231 // capacity:
232 using _Base::empty;
233 using _Base::size;
234 using _Base::max_size;
235
236 // modifiers:
237#if __cplusplus >= 201103L
238 template<typename... _Args>
239 iterator
240 emplace(_Args&&... __args)
241 { return { _Base::emplace(std::forward<_Args>(__args)...), this }; }
242
243 template<typename... _Args>
244 iterator
245 emplace_hint(const_iterator __pos, _Args&&... __args)
246 {
247 __glibcxx_check_insert(__pos);
248 return
249 {
250 _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...),
251 this
252 };
253 }
254#endif
255
256 iterator
257 insert(const value_type& __x)
258 { return iterator(_Base::insert(__x), this); }
259
260#if __cplusplus >= 201103L
261 iterator
262 insert(value_type&& __x)
263 { return { _Base::insert(std::move(__x)), this }; }
264#endif
265
266 iterator
267 insert(const_iterator __position, const value_type& __x)
268 {
269 __glibcxx_check_insert(__position);
270 return iterator(_Base::insert(__position.base(), __x), this);
271 }
272
273#if __cplusplus >= 201103L
274 iterator
275 insert(const_iterator __position, value_type&& __x)
276 {
277 __glibcxx_check_insert(__position);
278 return { _Base::insert(__position.base(), std::move(__x)), this };
279 }
280#endif
281
282 template<typename _InputIterator>
283 void
284 insert(_InputIterator __first, _InputIterator __last)
285 {
286 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
287 __glibcxx_check_valid_range2(__first, __last, __dist);
288
289 if (__dist.second >= __gnu_debug::__dp_sign)
290 _Base::insert(__gnu_debug::__unsafe(__first),
291 __gnu_debug::__unsafe(__last));
292 else
293 _Base::insert(__first, __last);
294 }
295
296#if __cplusplus >= 201103L
297 void
298 insert(initializer_list<value_type> __l)
299 { _Base::insert(__l); }
300#endif
301
302#if __cplusplus > 201402L
303 using node_type = typename _Base::node_type;
304
305 node_type
306 extract(const_iterator __position)
307 {
308 __glibcxx_check_erase(__position);
309 this->_M_invalidate_if(_Equal(__position.base()));
310 return _Base::extract(__position.base());
311 }
312
313 node_type
314 extract(const key_type& __key)
315 {
316 const auto __position = find(__key);
317 if (__position != end())
318 return extract(__position);
319 return {};
320 }
321
322 iterator
323 insert(node_type&& __nh)
324 { return { _Base::insert(std::move(__nh)), this }; }
325
326 iterator
327 insert(const_iterator __hint, node_type&& __nh)
328 {
329 __glibcxx_check_insert(__hint);
330 return { _Base::insert(__hint.base(), std::move(__nh)), this };
331 }
332
333 using _Base::merge;
334#endif // C++17
335
336#if __cplusplus >= 201103L
337 _GLIBCXX_ABI_TAG_CXX11
338 iterator
339 erase(const_iterator __position)
340 {
341 __glibcxx_check_erase(__position);
342 this->_M_invalidate_if(_Equal(__position.base()));
343 return { _Base::erase(__position.base()), this };
344 }
345#else
346 void
347 erase(iterator __position)
348 {
349 __glibcxx_check_erase(__position);
350 this->_M_invalidate_if(_Equal(__position.base()));
351 _Base::erase(__position.base());
352 }
353#endif
354
355 size_type
356 erase(const key_type& __x)
357 {
358 std::pair<_Base_iterator, _Base_iterator> __victims =
359 _Base::equal_range(__x);
360 size_type __count = 0;
361 _Base_iterator __victim = __victims.first;
362 while (__victim != __victims.second)
363 {
364 this->_M_invalidate_if(_Equal(__victim));
365 _Base::erase(__victim++);
366 ++__count;
367 }
368 return __count;
369 }
370
371#if __cplusplus >= 201103L
372 _GLIBCXX_ABI_TAG_CXX11
373 iterator
374 erase(const_iterator __first, const_iterator __last)
375 {
376 // _GLIBCXX_RESOLVE_LIB_DEFECTS
377 // 151. can't currently clear() empty container
378 __glibcxx_check_erase_range(__first, __last);
379 for (_Base_const_iterator __victim = __first.base();
380 __victim != __last.base(); ++__victim)
381 {
382 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(),
383 _M_message(__gnu_debug::__msg_valid_range)
384 ._M_iterator(__first, "first")
385 ._M_iterator(__last, "last"));
386 this->_M_invalidate_if(_Equal(__victim));
387 }
388
389 return { _Base::erase(__first.base(), __last.base()), this };
390 }
391#else
392 void
393 erase(iterator __first, iterator __last)
394 {
395 // _GLIBCXX_RESOLVE_LIB_DEFECTS
396 // 151. can't currently clear() empty container
397 __glibcxx_check_erase_range(__first, __last);
398 for (_Base_iterator __victim = __first.base();
399 __victim != __last.base(); ++__victim)
400 {
401 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
402 _M_message(__gnu_debug::__msg_valid_range)
403 ._M_iterator(__first, "first")
404 ._M_iterator(__last, "last"));
405 this->_M_invalidate_if(_Equal(__victim));
406 }
407 _Base::erase(__first.base(), __last.base());
408 }
409#endif
410
411 void
412 swap(multiset& __x)
413 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
414 {
415 _Safe::_M_swap(__x);
416 _Base::swap(__x);
417 }
418
419 void
420 clear() _GLIBCXX_NOEXCEPT
421 {
422 this->_M_invalidate_all();
423 _Base::clear();
424 }
425
426 // observers:
427 using _Base::key_comp;
428 using _Base::value_comp;
429
430 // multiset operations:
431 iterator
432 find(const key_type& __x)
433 { return iterator(_Base::find(__x), this); }
434
435 // _GLIBCXX_RESOLVE_LIB_DEFECTS
436 // 214. set::find() missing const overload
437 const_iterator
438 find(const key_type& __x) const
439 { return const_iterator(_Base::find(__x), this); }
440
441#if __cplusplus > 201103L
442 template<typename _Kt,
443 typename _Req =
444 typename __has_is_transparent<_Compare, _Kt>::type>
445 iterator
446 find(const _Kt& __x)
447 { return { _Base::find(__x), this }; }
448
449 template<typename _Kt,
450 typename _Req =
451 typename __has_is_transparent<_Compare, _Kt>::type>
452 const_iterator
453 find(const _Kt& __x) const
454 { return { _Base::find(__x), this }; }
455#endif
456
457 using _Base::count;
458
459 iterator
460 lower_bound(const key_type& __x)
461 { return iterator(_Base::lower_bound(__x), this); }
462
463 // _GLIBCXX_RESOLVE_LIB_DEFECTS
464 // 214. set::find() missing const overload
465 const_iterator
466 lower_bound(const key_type& __x) const
467 { return const_iterator(_Base::lower_bound(__x), this); }
468
469#if __cplusplus > 201103L
470 template<typename _Kt,
471 typename _Req =
472 typename __has_is_transparent<_Compare, _Kt>::type>
473 iterator
474 lower_bound(const _Kt& __x)
475 { return { _Base::lower_bound(__x), this }; }
476
477 template<typename _Kt,
478 typename _Req =
479 typename __has_is_transparent<_Compare, _Kt>::type>
480 const_iterator
481 lower_bound(const _Kt& __x) const
482 { return { _Base::lower_bound(__x), this }; }
483#endif
484
485 iterator
486 upper_bound(const key_type& __x)
487 { return iterator(_Base::upper_bound(__x), this); }
488
489 // _GLIBCXX_RESOLVE_LIB_DEFECTS
490 // 214. set::find() missing const overload
491 const_iterator
492 upper_bound(const key_type& __x) const
493 { return const_iterator(_Base::upper_bound(__x), this); }
494
495#if __cplusplus > 201103L
496 template<typename _Kt,
497 typename _Req =
498 typename __has_is_transparent<_Compare, _Kt>::type>
499 iterator
500 upper_bound(const _Kt& __x)
501 { return { _Base::upper_bound(__x), this }; }
502
503 template<typename _Kt,
504 typename _Req =
505 typename __has_is_transparent<_Compare, _Kt>::type>
506 const_iterator
507 upper_bound(const _Kt& __x) const
508 { return { _Base::upper_bound(__x), this }; }
509#endif
510
511 std::pair<iterator,iterator>
512 equal_range(const key_type& __x)
513 {
514 std::pair<_Base_iterator, _Base_iterator> __res =
515 _Base::equal_range(__x);
516 return std::make_pair(iterator(__res.first, this),
517 iterator(__res.second, this));
518 }
519
520 // _GLIBCXX_RESOLVE_LIB_DEFECTS
521 // 214. set::find() missing const overload
522 std::pair<const_iterator,const_iterator>
523 equal_range(const key_type& __x) const
524 {
525 std::pair<_Base_const_iterator, _Base_const_iterator> __res =
526 _Base::equal_range(__x);
527 return std::make_pair(const_iterator(__res.first, this),
528 const_iterator(__res.second, this));
529 }
530
531#if __cplusplus > 201103L
532 template<typename _Kt,
533 typename _Req =
534 typename __has_is_transparent<_Compare, _Kt>::type>
535 std::pair<iterator, iterator>
536 equal_range(const _Kt& __x)
537 {
538 auto __res = _Base::equal_range(__x);
539 return { { __res.first, this }, { __res.second, this } };
540 }
541
542 template<typename _Kt,
543 typename _Req =
544 typename __has_is_transparent<_Compare, _Kt>::type>
545 std::pair<const_iterator, const_iterator>
546 equal_range(const _Kt& __x) const
547 {
548 auto __res = _Base::equal_range(__x);
549 return { { __res.first, this }, { __res.second, this } };
550 }
551#endif
552
553 _Base&
554 _M_base() _GLIBCXX_NOEXCEPT { return *this; }
555
556 const _Base&
557 _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
558 };
559
560#if __cpp_deduction_guides >= 201606
561
562 template<typename _InputIterator,
563 typename _Compare =
564 less<typename iterator_traits<_InputIterator>::value_type>,
565 typename _Allocator =
566 allocator<typename iterator_traits<_InputIterator>::value_type>,
567 typename = _RequireInputIter<_InputIterator>,
568 typename = _RequireNotAllocator<_Compare>,
569 typename = _RequireAllocator<_Allocator>>
570 multiset(_InputIterator, _InputIterator,
571 _Compare = _Compare(), _Allocator = _Allocator())
572 -> multiset<typename iterator_traits<_InputIterator>::value_type,
573 _Compare, _Allocator>;
574
575 template<typename _Key,
576 typename _Compare = less<_Key>,
577 typename _Allocator = allocator<_Key>,
578 typename = _RequireNotAllocator<_Compare>,
579 typename = _RequireAllocator<_Allocator>>
580 multiset(initializer_list<_Key>,
581 _Compare = _Compare(), _Allocator = _Allocator())
582 -> multiset<_Key, _Compare, _Allocator>;
583
584 template<typename _InputIterator, typename _Allocator,
585 typename = _RequireInputIter<_InputIterator>,
586 typename = _RequireAllocator<_Allocator>>
587 multiset(_InputIterator, _InputIterator, _Allocator)
588 -> multiset<typename iterator_traits<_InputIterator>::value_type,
589 less<typename iterator_traits<_InputIterator>::value_type>,
590 _Allocator>;
591
592 template<typename _Key, typename _Allocator,
593 typename = _RequireAllocator<_Allocator>>
594 multiset(initializer_list<_Key>, _Allocator)
595 -> multiset<_Key, less<_Key>, _Allocator>;
596
597#endif // deduction guides
598
599 template<typename _Key, typename _Compare, typename _Allocator>
600 inline bool
601 operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
602 const multiset<_Key, _Compare, _Allocator>& __rhs)
603 { return __lhs._M_base() == __rhs._M_base(); }
604
605#if __cpp_lib_three_way_comparison
606 template<typename _Key, typename _Compare, typename _Alloc>
607 inline __detail::__synth3way_t<_Key>
608 operator<=>(const multiset<_Key, _Compare, _Alloc>& __lhs,
609 const multiset<_Key, _Compare, _Alloc>& __rhs)
610 { return __lhs._M_base() <=> __rhs._M_base(); }
611#else
612 template<typename _Key, typename _Compare, typename _Allocator>
613 inline bool
614 operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
615 const multiset<_Key, _Compare, _Allocator>& __rhs)
616 { return __lhs._M_base() != __rhs._M_base(); }
617
618 template<typename _Key, typename _Compare, typename _Allocator>
619 inline bool
620 operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
621 const multiset<_Key, _Compare, _Allocator>& __rhs)
622 { return __lhs._M_base() < __rhs._M_base(); }
623
624 template<typename _Key, typename _Compare, typename _Allocator>
625 inline bool
626 operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
627 const multiset<_Key, _Compare, _Allocator>& __rhs)
628 { return __lhs._M_base() <= __rhs._M_base(); }
629
630 template<typename _Key, typename _Compare, typename _Allocator>
631 inline bool
632 operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
633 const multiset<_Key, _Compare, _Allocator>& __rhs)
634 { return __lhs._M_base() >= __rhs._M_base(); }
635
636 template<typename _Key, typename _Compare, typename _Allocator>
637 inline bool
638 operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
639 const multiset<_Key, _Compare, _Allocator>& __rhs)
640 { return __lhs._M_base() > __rhs._M_base(); }
641#endif // three-way comparison
642
643 template<typename _Key, typename _Compare, typename _Allocator>
644 void
645 swap(multiset<_Key, _Compare, _Allocator>& __x,
646 multiset<_Key, _Compare, _Allocator>& __y)
647 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
648 { return __x.swap(__y); }
649
650} // namespace __debug
651} // namespace std
652
653#endif
__glibcxx_check_insert
#define __glibcxx_check_insert(_Position)
Definition: macros.h:146
__glibcxx_check_erase_range
#define __glibcxx_check_erase_range(_First, _Last)
Definition: macros.h:240
__glibcxx_check_erase
#define __glibcxx_check_erase(_Position)
Definition: macros.h:212
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:104
std::swap
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
Definition: any:428
std
ISO C++ entities toplevel namespace is std.
__gnu_debug::__base
constexpr _Iterator __base(_Iterator __it)
Definition: helper_functions.h:315
std::initializer_list
initializer_list
Definition: initializer_list:48
std::allocator
The standard allocator, as per C++03 [20.4.1].
Definition: allocator.h:125
std::less
One of the comparison functors.
Definition: stl_function.h:396
std::multiset
A standard container made up of elements, which can be retrieved in logarithmic time.
Definition: stl_multiset.h:97
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:213
std::pair::first
_T1 first
The first member.
Definition: stl_pair.h:217
std::pair::second
_T2 second
The second member.
Definition: stl_pair.h:218
__gnu_debug::_Safe_iterator
Safe iterator wrapper.
Definition: safe_iterator.h:117
__gnu_debug::_Safe_iterator::base
_Iterator & base() noexcept
Return the underlying iterator.
Definition: safe_iterator.h:363
std::__debug::multiset
Class std::multiset with safety/checking/debug instrumentation.
Definition: multiset.h:49
__gnu_debug::_Safe_container
Safe class dealing with some allocator dependent operations.
Definition: safe_container.h:43
__gnu_debug::_Safe_node_sequence
Like _Safe_sequence but with a special _M_invalidate_all implementation not invalidating past-the-end...
Definition: safe_sequence.h:133