libstdc++
debug/multiset.h
Go to the documentation of this file.
1// Debugging multiset 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/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>
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> >
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;
53
55 typedef typename _Base::iterator _Base_iterator;
57
58 public:
59 // types:
60 typedef _Key key_type;
61 typedef _Key value_type;
62 typedef _Compare key_compare;
63 typedef _Compare value_compare;
64 typedef _Allocator allocator_type;
65 typedef typename _Base::reference reference;
66 typedef typename _Base::const_reference const_reference;
67
72
73 typedef typename _Base::size_type size_type;
74 typedef typename _Base::difference_type difference_type;
75 typedef typename _Base::pointer pointer;
76 typedef typename _Base::const_pointer const_pointer;
79
80 // 23.3.3.1 construct/copy/destroy:
81
82#if __cplusplus < 201103L
83 multiset() : _Base() { }
84
85 multiset(const multiset& __x)
86 : _Base(__x) { }
87
88 ~multiset() { }
89#else
90 multiset() = default;
91 multiset(const multiset&) = default;
92 multiset(multiset&&) = default;
93
95 const _Compare& __comp = _Compare(),
96 const allocator_type& __a = allocator_type())
97 : _Base(__l, __comp, __a) { }
98
99 explicit
100 multiset(const allocator_type& __a)
101 : _Base(__a) { }
102
103 multiset(const multiset& __m, const allocator_type& __a)
104 : _Base(__m, __a) { }
105
106 multiset(multiset&& __m, const allocator_type& __a)
107 noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) )
108 : _Safe(std::move(__m._M_safe()), __a),
109 _Base(std::move(__m._M_base()), __a) { }
110
111 multiset(initializer_list<value_type> __l, const allocator_type& __a)
112 : _Base(__l, __a)
113 { }
114
115 template<typename _InputIterator>
116 multiset(_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 ~multiset() = default;
123#endif
124
125 explicit multiset(const _Compare& __comp,
126 const _Allocator& __a = _Allocator())
127 : _Base(__comp, __a) { }
128
129 template<typename _InputIterator>
130 multiset(_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 multiset(const _Base& __x)
139 : _Base(__x) { }
140
141#if __cplusplus < 201103L
142 multiset&
143 operator=(const multiset& __x)
144 {
145 this->_M_safe() = __x;
146 _M_base() = __x;
147 return *this;
148 }
149#else
150 multiset&
151 operator=(const multiset&) = default;
152
153 multiset&
154 operator=(multiset&&) = default;
155
156 multiset&
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)...),
230 this);
231 }
232
233 template<typename... _Args>
235 emplace_hint(const_iterator __pos, _Args&&... __args)
236 {
238 return iterator(_Base::emplace_hint(__pos.base(),
239 std::forward<_Args>(__args)...),
240 this);
241 }
242#endif
243
245 insert(const value_type& __x)
246 { return iterator(_Base::insert(__x), this); }
247
248#if __cplusplus >= 201103L
250 insert(value_type&& __x)
251 { return iterator(_Base::insert(std::move(__x)), this); }
252#endif
253
255 insert(const_iterator __position, const value_type& __x)
256 {
257 __glibcxx_check_insert(__position);
258 return iterator(_Base::insert(__position.base(), __x), this);
259 }
260
261#if __cplusplus >= 201103L
263 insert(const_iterator __position, value_type&& __x)
264 {
265 __glibcxx_check_insert(__position);
266 return iterator(_Base::insert(__position.base(), std::move(__x)),
267 this);
268 }
269#endif
270
271 template<typename _InputIterator>
272 void
273 insert(_InputIterator __first, _InputIterator __last)
274 {
276 __glibcxx_check_valid_range2(__first, __last, __dist);
277
278 if (__dist.second >= __gnu_debug::__dp_sign)
279 _Base::insert(__gnu_debug::__unsafe(__first),
280 __gnu_debug::__unsafe(__last));
281 else
282 _Base::insert(__first, __last);
283 }
284
285#if __cplusplus >= 201103L
286 void
288 { _Base::insert(__l); }
289#endif
290
291#if __cplusplus > 201402L
292 using node_type = typename _Base::node_type;
293
294 node_type
295 extract(const_iterator __position)
296 {
297 __glibcxx_check_erase(__position);
298 this->_M_invalidate_if(_Equal(__position.base()));
299 return _Base::extract(__position.base());
300 }
301
302 node_type
303 extract(const key_type& __key)
304 {
305 const auto __position = find(__key);
306 if (__position != end())
307 return extract(__position);
308 return {};
309 }
310
312 insert(node_type&& __nh)
313 { return iterator(_Base::insert(std::move(__nh)), this); }
314
316 insert(const_iterator __hint, node_type&& __nh)
317 {
319 return iterator(_Base::insert(__hint.base(), std::move(__nh)), this);
320 }
321
322 using _Base::merge;
323#endif // C++17
324
325#if __cplusplus >= 201103L
327 erase(const_iterator __position)
328 {
329 __glibcxx_check_erase(__position);
330 this->_M_invalidate_if(_Equal(__position.base()));
331 return iterator(_Base::erase(__position.base()), this);
332 }
333#else
334 void
335 erase(iterator __position)
336 {
337 __glibcxx_check_erase(__position);
338 this->_M_invalidate_if(_Equal(__position.base()));
339 _Base::erase(__position.base());
340 }
341#endif
342
343 size_type
344 erase(const key_type& __x)
345 {
347 _Base::equal_range(__x);
348 size_type __count = 0;
349 _Base_iterator __victim = __victims.first;
350 while (__victim != __victims.second)
351 {
352 this->_M_invalidate_if(_Equal(__victim));
353 _Base::erase(__victim++);
354 ++__count;
355 }
356 return __count;
357 }
358
359#if __cplusplus >= 201103L
361 erase(const_iterator __first, const_iterator __last)
362 {
363 // _GLIBCXX_RESOLVE_LIB_DEFECTS
364 // 151. can't currently clear() empty container
365 __glibcxx_check_erase_range(__first, __last);
366 for (_Base_const_iterator __victim = __first.base();
367 __victim != __last.base(); ++__victim)
368 {
369 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
370 _M_message(__gnu_debug::__msg_valid_range)
371 ._M_iterator(__first, "first")
372 ._M_iterator(__last, "last"));
373 this->_M_invalidate_if(_Equal(__victim));
374 }
375 return iterator(_Base::erase(__first.base(), __last.base()), this);
376 }
377#else
378 void
379 erase(iterator __first, iterator __last)
380 {
381 // _GLIBCXX_RESOLVE_LIB_DEFECTS
382 // 151. can't currently clear() empty container
383 __glibcxx_check_erase_range(__first, __last);
384 for (_Base_iterator __victim = __first.base();
385 __victim != __last.base(); ++__victim)
386 {
387 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
388 _M_message(__gnu_debug::__msg_valid_range)
389 ._M_iterator(__first, "first")
390 ._M_iterator(__last, "last"));
391 this->_M_invalidate_if(_Equal(__victim));
392 }
393 _Base::erase(__first.base(), __last.base());
394 }
395#endif
396
397 void
398 swap(multiset& __x)
399 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
400 {
401 _Safe::_M_swap(__x);
402 _Base::swap(__x);
403 }
404
405 void
406 clear() _GLIBCXX_NOEXCEPT
407 {
408 this->_M_invalidate_all();
409 _Base::clear();
410 }
411
412 // observers:
413 using _Base::key_comp;
414 using _Base::value_comp;
415
416 // multiset operations:
418 find(const key_type& __x)
419 { return iterator(_Base::find(__x), this); }
420
421 // _GLIBCXX_RESOLVE_LIB_DEFECTS
422 // 214. set::find() missing const overload
424 find(const key_type& __x) const
425 { return const_iterator(_Base::find(__x), this); }
426
427#if __cplusplus > 201103L
428 template<typename _Kt,
429 typename _Req =
430 typename __has_is_transparent<_Compare, _Kt>::type>
432 find(const _Kt& __x)
433 { return { _Base::find(__x), this }; }
434
435 template<typename _Kt,
436 typename _Req =
437 typename __has_is_transparent<_Compare, _Kt>::type>
439 find(const _Kt& __x) const
440 { return { _Base::find(__x), this }; }
441#endif
442
443 using _Base::count;
444
446 lower_bound(const key_type& __x)
447 { return iterator(_Base::lower_bound(__x), this); }
448
449 // _GLIBCXX_RESOLVE_LIB_DEFECTS
450 // 214. set::find() missing const overload
452 lower_bound(const key_type& __x) const
453 { return const_iterator(_Base::lower_bound(__x), this); }
454
455#if __cplusplus > 201103L
456 template<typename _Kt,
457 typename _Req =
458 typename __has_is_transparent<_Compare, _Kt>::type>
460 lower_bound(const _Kt& __x)
461 { return { _Base::lower_bound(__x), this }; }
462
463 template<typename _Kt,
464 typename _Req =
465 typename __has_is_transparent<_Compare, _Kt>::type>
467 lower_bound(const _Kt& __x) const
468 { return { _Base::lower_bound(__x), this }; }
469#endif
470
472 upper_bound(const key_type& __x)
473 { return iterator(_Base::upper_bound(__x), this); }
474
475 // _GLIBCXX_RESOLVE_LIB_DEFECTS
476 // 214. set::find() missing const overload
478 upper_bound(const key_type& __x) const
479 { return const_iterator(_Base::upper_bound(__x), this); }
480
481#if __cplusplus > 201103L
482 template<typename _Kt,
483 typename _Req =
484 typename __has_is_transparent<_Compare, _Kt>::type>
486 upper_bound(const _Kt& __x)
487 { return { _Base::upper_bound(__x), this }; }
488
489 template<typename _Kt,
490 typename _Req =
491 typename __has_is_transparent<_Compare, _Kt>::type>
493 upper_bound(const _Kt& __x) const
494 { return { _Base::upper_bound(__x), this }; }
495#endif
496
498 equal_range(const key_type& __x)
499 {
501 _Base::equal_range(__x);
502 return std::make_pair(iterator(__res.first, this),
503 iterator(__res.second, this));
504 }
505
506 // _GLIBCXX_RESOLVE_LIB_DEFECTS
507 // 214. set::find() missing const overload
509 equal_range(const key_type& __x) const
510 {
512 _Base::equal_range(__x);
513 return std::make_pair(const_iterator(__res.first, this),
514 const_iterator(__res.second, this));
515 }
516
517#if __cplusplus > 201103L
518 template<typename _Kt,
519 typename _Req =
520 typename __has_is_transparent<_Compare, _Kt>::type>
522 equal_range(const _Kt& __x)
523 {
524 auto __res = _Base::equal_range(__x);
525 return { { __res.first, this }, { __res.second, this } };
526 }
527
528 template<typename _Kt,
529 typename _Req =
530 typename __has_is_transparent<_Compare, _Kt>::type>
532 equal_range(const _Kt& __x) const
533 {
534 auto __res = _Base::equal_range(__x);
535 return { { __res.first, this }, { __res.second, this } };
536 }
537#endif
538
539 _Base&
540 _M_base() _GLIBCXX_NOEXCEPT { return *this; }
541
542 const _Base&
543 _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
544 };
545
546#if __cpp_deduction_guides >= 201606
547
548 template<typename _InputIterator,
549 typename _Compare =
551 typename _Allocator =
553 typename = _RequireInputIter<_InputIterator>,
554 typename = _RequireAllocator<_Allocator>>
555 multiset(_InputIterator, _InputIterator,
556 _Compare = _Compare(), _Allocator = _Allocator())
558 _Compare, _Allocator>;
559
560 template<typename _Key,
561 typename _Compare = less<_Key>,
562 typename _Allocator = allocator<_Key>,
563 typename = _RequireAllocator<_Allocator>>
565 _Compare = _Compare(), _Allocator = _Allocator())
567
568 template<typename _InputIterator, typename _Allocator,
569 typename = _RequireInputIter<_InputIterator>,
570 typename = _RequireAllocator<_Allocator>>
571 multiset(_InputIterator, _InputIterator, _Allocator)
574 _Allocator>;
575
576 template<typename _Key, typename _Allocator,
577 typename = _RequireAllocator<_Allocator>>
579 -> multiset<_Key, less<_Key>, _Allocator>;
580
581#endif
582
583 template<typename _Key, typename _Compare, typename _Allocator>
584 inline bool
585 operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
587 { return __lhs._M_base() == __rhs._M_base(); }
588
589 template<typename _Key, typename _Compare, typename _Allocator>
590 inline bool
591 operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
593 { return __lhs._M_base() != __rhs._M_base(); }
594
595 template<typename _Key, typename _Compare, typename _Allocator>
596 inline bool
597 operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
598 const multiset<_Key, _Compare, _Allocator>& __rhs)
599 { return __lhs._M_base() < __rhs._M_base(); }
600
601 template<typename _Key, typename _Compare, typename _Allocator>
602 inline bool
603 operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
604 const multiset<_Key, _Compare, _Allocator>& __rhs)
605 { return __lhs._M_base() <= __rhs._M_base(); }
606
607 template<typename _Key, typename _Compare, typename _Allocator>
608 inline bool
609 operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
610 const multiset<_Key, _Compare, _Allocator>& __rhs)
611 { return __lhs._M_base() >= __rhs._M_base(); }
612
613 template<typename _Key, typename _Compare, typename _Allocator>
614 inline bool
615 operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
616 const multiset<_Key, _Compare, _Allocator>& __rhs)
617 { return __lhs._M_base() > __rhs._M_base(); }
618
619 template<typename _Key, typename _Compare, typename _Allocator>
620 void
621 swap(multiset<_Key, _Compare, _Allocator>& __x,
622 multiset<_Key, _Compare, _Allocator>& __y)
623 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
624 { return __x.swap(__y); }
625
626} // namespace __debug
627} // namespace std
628
629#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
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 elements, which can be retrieved in logarithmic time.
Definition: stl_multiset.h:97
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::multiset 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...