1 // Debugging multiset implementation -*- C++ -*-
2
3 // Copyright (C) 2003-2019 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
_GLIBCXX_VISIBILITY(default)37 namespace std _GLIBCXX_VISIBILITY(default)
38 {
39 namespace __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 public:
62 // types:
63 typedef _Key key_type;
64 typedef _Key value_type;
65 typedef _Compare key_compare;
66 typedef _Compare value_compare;
67 typedef _Allocator allocator_type;
68 typedef typename _Base::reference reference;
69 typedef typename _Base::const_reference const_reference;
70
71 typedef __gnu_debug::_Safe_iterator<_Base_iterator, multiset>
72 iterator;
73 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
74 multiset> const_iterator;
75
76 typedef typename _Base::size_type size_type;
77 typedef typename _Base::difference_type difference_type;
78 typedef typename _Base::pointer pointer;
79 typedef typename _Base::const_pointer const_pointer;
80 typedef std::reverse_iterator<iterator> reverse_iterator;
81 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
82
83 // 23.3.3.1 construct/copy/destroy:
84
85 #if __cplusplus < 201103L
86 multiset() : _Base() { }
87
88 multiset(const multiset& __x)
89 : _Base(__x) { }
90
91 ~multiset() { }
92 #else
93 multiset() = default;
94 multiset(const multiset&) = default;
95 multiset(multiset&&) = default;
96
97 multiset(initializer_list<value_type> __l,
98 const _Compare& __comp = _Compare(),
99 const allocator_type& __a = allocator_type())
100 : _Base(__l, __comp, __a) { }
101
102 explicit
103 multiset(const allocator_type& __a)
104 : _Base(__a) { }
105
106 multiset(const multiset& __m, const allocator_type& __a)
107 : _Base(__m, __a) { }
108
109 multiset(multiset&& __m, const allocator_type& __a)
110 noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) )
111 : _Safe(std::move(__m._M_safe()), __a),
112 _Base(std::move(__m._M_base()), __a) { }
113
114 multiset(initializer_list<value_type> __l, const allocator_type& __a)
115 : _Base(__l, __a)
116 { }
117
118 template<typename _InputIterator>
119 multiset(_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 ~multiset() = default;
126 #endif
127
128 explicit multiset(const _Compare& __comp,
129 const _Allocator& __a = _Allocator())
130 : _Base(__comp, __a) { }
131
132 template<typename _InputIterator>
133 multiset(_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 multiset(const _Base& __x)
142 : _Base(__x) { }
143
144 #if __cplusplus < 201103L
145 multiset&
146 operator=(const multiset& __x)
147 {
148 this->_M_safe() = __x;
149 _M_base() = __x;
150 return *this;
151 }
152 #else
153 multiset&
154 operator=(const multiset&) = default;
155
156 multiset&
157 operator=(multiset&&) = default;
158
159 multiset&
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 iterator
252 insert(value_type&& __x)
253 { return { _Base::insert(std::move(__x)), this }; }
254 #endif
255
256 iterator
257 insert(const_iterator __position, const value_type& __x)
258 {
259 __glibcxx_check_insert(__position);
260 return iterator(_Base::insert(__position.base(), __x), this);
261 }
262
263 #if __cplusplus >= 201103L
264 iterator
265 insert(const_iterator __position, value_type&& __x)
266 {
267 __glibcxx_check_insert(__position);
268 return { _Base::insert(__position.base(), std::move(__x)), this };
269 }
270 #endif
271
272 template<typename _InputIterator>
273 void
274 insert(_InputIterator __first, _InputIterator __last)
275 {
276 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
277 __glibcxx_check_valid_range2(__first, __last, __dist);
278
279 if (__dist.second >= __gnu_debug::__dp_sign)
280 _Base::insert(__gnu_debug::__unsafe(__first),
281 __gnu_debug::__unsafe(__last));
282 else
283 _Base::insert(__first, __last);
284 }
285
286 #if __cplusplus >= 201103L
287 void
288 insert(initializer_list<value_type> __l)
289 { _Base::insert(__l); }
290 #endif
291
292 #if __cplusplus > 201402L
293 using node_type = typename _Base::node_type;
294
295 node_type
296 extract(const_iterator __position)
297 {
298 __glibcxx_check_erase(__position);
299 this->_M_invalidate_if(_Equal(__position.base()));
300 return _Base::extract(__position.base());
301 }
302
303 node_type
304 extract(const key_type& __key)
305 {
306 const auto __position = find(__key);
307 if (__position != end())
308 return extract(__position);
309 return {};
310 }
311
312 iterator
313 insert(node_type&& __nh)
314 { return { _Base::insert(std::move(__nh)), this }; }
315
316 iterator
317 insert(const_iterator __hint, node_type&& __nh)
318 {
319 __glibcxx_check_insert(__hint);
320 return { _Base::insert(__hint.base(), std::move(__nh)), this };
321 }
322
323 using _Base::merge;
324 #endif // C++17
325
326 #if __cplusplus >= 201103L
327 _GLIBCXX_ABI_TAG_CXX11
328 iterator
329 erase(const_iterator __position)
330 {
331 __glibcxx_check_erase(__position);
332 this->_M_invalidate_if(_Equal(__position.base()));
333 return { _Base::erase(__position.base()), this };
334 }
335 #else
336 void
337 erase(iterator __position)
338 {
339 __glibcxx_check_erase(__position);
340 this->_M_invalidate_if(_Equal(__position.base()));
341 _Base::erase(__position.base());
342 }
343 #endif
344
345 size_type
346 erase(const key_type& __x)
347 {
348 std::pair<_Base_iterator, _Base_iterator> __victims =
349 _Base::equal_range(__x);
350 size_type __count = 0;
351 _Base_iterator __victim = __victims.first;
352 while (__victim != __victims.second)
353 {
354 this->_M_invalidate_if(_Equal(__victim));
355 _Base::erase(__victim++);
356 ++__count;
357 }
358 return __count;
359 }
360
361 #if __cplusplus >= 201103L
362 _GLIBCXX_ABI_TAG_CXX11
363 iterator
364 erase(const_iterator __first, const_iterator __last)
365 {
366 // _GLIBCXX_RESOLVE_LIB_DEFECTS
367 // 151. can't currently clear() empty container
368 __glibcxx_check_erase_range(__first, __last);
369 for (_Base_const_iterator __victim = __first.base();
370 __victim != __last.base(); ++__victim)
371 {
372 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(),
373 _M_message(__gnu_debug::__msg_valid_range)
374 ._M_iterator(__first, "first")
375 ._M_iterator(__last, "last"));
376 this->_M_invalidate_if(_Equal(__victim));
377 }
378
379 return { _Base::erase(__first.base(), __last.base()), this };
380 }
381 #else
382 void
383 erase(iterator __first, iterator __last)
384 {
385 // _GLIBCXX_RESOLVE_LIB_DEFECTS
386 // 151. can't currently clear() empty container
387 __glibcxx_check_erase_range(__first, __last);
388 for (_Base_iterator __victim = __first.base();
389 __victim != __last.base(); ++__victim)
390 {
391 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
392 _M_message(__gnu_debug::__msg_valid_range)
393 ._M_iterator(__first, "first")
394 ._M_iterator(__last, "last"));
395 this->_M_invalidate_if(_Equal(__victim));
396 }
397 _Base::erase(__first.base(), __last.base());
398 }
399 #endif
400
401 void
402 swap(multiset& __x)
403 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
404 {
405 _Safe::_M_swap(__x);
406 _Base::swap(__x);
407 }
408
409 void
410 clear() _GLIBCXX_NOEXCEPT
411 {
412 this->_M_invalidate_all();
413 _Base::clear();
414 }
415
416 // observers:
417 using _Base::key_comp;
418 using _Base::value_comp;
419
420 // multiset operations:
421 iterator
422 find(const key_type& __x)
423 { return iterator(_Base::find(__x), this); }
424
425 // _GLIBCXX_RESOLVE_LIB_DEFECTS
426 // 214. set::find() missing const overload
427 const_iterator
428 find(const key_type& __x) const
429 { return const_iterator(_Base::find(__x), this); }
430
431 #if __cplusplus > 201103L
432 template<typename _Kt,
433 typename _Req =
434 typename __has_is_transparent<_Compare, _Kt>::type>
435 iterator
436 find(const _Kt& __x)
437 { return { _Base::find(__x), this }; }
438
439 template<typename _Kt,
440 typename _Req =
441 typename __has_is_transparent<_Compare, _Kt>::type>
442 const_iterator
443 find(const _Kt& __x) const
444 { return { _Base::find(__x), this }; }
445 #endif
446
447 using _Base::count;
448
449 iterator
450 lower_bound(const key_type& __x)
451 { return iterator(_Base::lower_bound(__x), this); }
452
453 // _GLIBCXX_RESOLVE_LIB_DEFECTS
454 // 214. set::find() missing const overload
455 const_iterator
456 lower_bound(const key_type& __x) const
457 { return const_iterator(_Base::lower_bound(__x), this); }
458
459 #if __cplusplus > 201103L
460 template<typename _Kt,
461 typename _Req =
462 typename __has_is_transparent<_Compare, _Kt>::type>
463 iterator
464 lower_bound(const _Kt& __x)
465 { return { _Base::lower_bound(__x), this }; }
466
467 template<typename _Kt,
468 typename _Req =
469 typename __has_is_transparent<_Compare, _Kt>::type>
470 const_iterator
471 lower_bound(const _Kt& __x) const
472 { return { _Base::lower_bound(__x), this }; }
473 #endif
474
475 iterator
476 upper_bound(const key_type& __x)
477 { return iterator(_Base::upper_bound(__x), this); }
478
479 // _GLIBCXX_RESOLVE_LIB_DEFECTS
480 // 214. set::find() missing const overload
481 const_iterator
482 upper_bound(const key_type& __x) const
483 { return const_iterator(_Base::upper_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 upper_bound(const _Kt& __x)
491 { return { _Base::upper_bound(__x), this }; }
492
493 template<typename _Kt,
494 typename _Req =
495 typename __has_is_transparent<_Compare, _Kt>::type>
496 const_iterator
497 upper_bound(const _Kt& __x) const
498 { return { _Base::upper_bound(__x), this }; }
499 #endif
500
501 std::pair<iterator,iterator>
502 equal_range(const key_type& __x)
503 {
504 std::pair<_Base_iterator, _Base_iterator> __res =
505 _Base::equal_range(__x);
506 return std::make_pair(iterator(__res.first, this),
507 iterator(__res.second, this));
508 }
509
510 // _GLIBCXX_RESOLVE_LIB_DEFECTS
511 // 214. set::find() missing const overload
512 std::pair<const_iterator,const_iterator>
513 equal_range(const key_type& __x) const
514 {
515 std::pair<_Base_const_iterator, _Base_const_iterator> __res =
516 _Base::equal_range(__x);
517 return std::make_pair(const_iterator(__res.first, this),
518 const_iterator(__res.second, this));
519 }
520
521 #if __cplusplus > 201103L
522 template<typename _Kt,
523 typename _Req =
524 typename __has_is_transparent<_Compare, _Kt>::type>
525 std::pair<iterator, iterator>
526 equal_range(const _Kt& __x)
527 {
528 auto __res = _Base::equal_range(__x);
529 return { { __res.first, this }, { __res.second, this } };
530 }
531
532 template<typename _Kt,
533 typename _Req =
534 typename __has_is_transparent<_Compare, _Kt>::type>
535 std::pair<const_iterator, const_iterator>
536 equal_range(const _Kt& __x) const
537 {
538 auto __res = _Base::equal_range(__x);
539 return { { __res.first, this }, { __res.second, this } };
540 }
541 #endif
542
543 _Base&
544 _M_base() _GLIBCXX_NOEXCEPT { return *this; }
545
546 const _Base&
547 _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
548 };
549
550 #if __cpp_deduction_guides >= 201606
551
552 template<typename _InputIterator,
553 typename _Compare =
554 less<typename iterator_traits<_InputIterator>::value_type>,
555 typename _Allocator =
556 allocator<typename iterator_traits<_InputIterator>::value_type>,
557 typename = _RequireInputIter<_InputIterator>,
558 typename = _RequireNotAllocator<_Compare>,
559 typename = _RequireAllocator<_Allocator>>
560 multiset(_InputIterator, _InputIterator,
561 _Compare = _Compare(), _Allocator = _Allocator())
562 -> multiset<typename iterator_traits<_InputIterator>::value_type,
563 _Compare, _Allocator>;
564
565 template<typename _Key,
566 typename _Compare = less<_Key>,
567 typename _Allocator = allocator<_Key>,
568 typename = _RequireNotAllocator<_Compare>,
569 typename = _RequireAllocator<_Allocator>>
570 multiset(initializer_list<_Key>,
571 _Compare = _Compare(), _Allocator = _Allocator())
572 -> multiset<_Key, _Compare, _Allocator>;
573
574 template<typename _InputIterator, typename _Allocator,
575 typename = _RequireInputIter<_InputIterator>,
576 typename = _RequireAllocator<_Allocator>>
577 multiset(_InputIterator, _InputIterator, _Allocator)
578 -> multiset<typename iterator_traits<_InputIterator>::value_type,
579 less<typename iterator_traits<_InputIterator>::value_type>,
580 _Allocator>;
581
582 template<typename _Key, typename _Allocator,
583 typename = _RequireAllocator<_Allocator>>
584 multiset(initializer_list<_Key>, _Allocator)
585 -> multiset<_Key, less<_Key>, _Allocator>;
586
587 #endif
588
589 template<typename _Key, typename _Compare, typename _Allocator>
590 inline bool
591 operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
592 const multiset<_Key, _Compare, _Allocator>& __rhs)
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 inline bool
621 operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
622 const multiset<_Key, _Compare, _Allocator>& __rhs)
623 { return __lhs._M_base() > __rhs._M_base(); }
624
625 template<typename _Key, typename _Compare, typename _Allocator>
626 void
627 swap(multiset<_Key, _Compare, _Allocator>& __x,
628 multiset<_Key, _Compare, _Allocator>& __y)
629 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
630 { return __x.swap(__y); }
631
632 } // namespace __debug
633 } // namespace std
634
635 #endif
636