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>
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 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
68 typedef __gnu_debug::_Safe_iterator<_Base_iterator, multiset>
69 iterator;
70 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
71 multiset> const_iterator;
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;
77 typedef std::reverse_iterator<iterator> reverse_iterator;
78 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
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
94 multiset(initializer_list<value_type> __l,
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:
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)...),
230 this);
231 }
232
233 template<typename... _Args>
234 iterator
235 emplace_hint(const_iterator __pos, _Args&&... __args)
236 {
237 __glibcxx_check_insert(__pos);
238 return iterator(_Base::emplace_hint(__pos.base(),
239 std::forward<_Args>(__args)...),
240 this);
241 }
242 #endif
243
244 iterator
245 insert(const value_type& __x)
246 { return iterator(_Base::insert(__x), this); }
247
248 #if __cplusplus >= 201103L
249 iterator
250 insert(value_type&& __x)
251 { return iterator(_Base::insert(std::move(__x)), this); }
252 #endif
253
254 iterator
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
262 iterator
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 {
275 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
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
287 insert(initializer_list<value_type> __l)
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
311 iterator
312 insert(node_type&& __nh)
313 { return iterator(_Base::insert(std::move(__nh)), this); }
314
315 iterator
316 insert(const_iterator __hint, node_type&& __nh)
317 {
318 __glibcxx_check_insert(__hint);
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
326 iterator
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 {
346 std::pair<_Base_iterator, _Base_iterator> __victims =
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
360 iterator
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:
417 iterator
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
423 const_iterator
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>
431 iterator
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>
438 const_iterator
439 find(const _Kt& __x) const
440 { return { _Base::find(__x), this }; }
441 #endif
442
443 using _Base::count;
444
445 iterator
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
451 const_iterator
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>
459 iterator
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>
466 const_iterator
467 lower_bound(const _Kt& __x) const
468 { return { _Base::lower_bound(__x), this }; }
469 #endif
470
471 iterator
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
477 const_iterator
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>
485 iterator
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>
492 const_iterator
493 upper_bound(const _Kt& __x) const
494 { return { _Base::upper_bound(__x), this }; }
495 #endif
496
497 std::pair<iterator,iterator>
498 equal_range(const key_type& __x)
499 {
500 std::pair<_Base_iterator, _Base_iterator> __res =
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
508 std::pair<const_iterator,const_iterator>
509 equal_range(const key_type& __x) const
510 {
511 std::pair<_Base_const_iterator, _Base_const_iterator> __res =
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>
521 std::pair<iterator, iterator>
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>
531 std::pair<const_iterator, const_iterator>
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 =
550 less<typename iterator_traits<_InputIterator>::value_type>,
551 typename _Allocator =
552 allocator<typename iterator_traits<_InputIterator>::value_type>,
553 typename = _RequireInputIter<_InputIterator>,
554 typename = _RequireAllocator<_Allocator>>
555 multiset(_InputIterator, _InputIterator,
556 _Compare = _Compare(), _Allocator = _Allocator())
557 -> multiset<typename iterator_traits<_InputIterator>::value_type,
558 _Compare, _Allocator>;
559
560 template<typename _Key,
561 typename _Compare = less<_Key>,
562 typename _Allocator = allocator<_Key>,
563 typename = _RequireAllocator<_Allocator>>
564 multiset(initializer_list<_Key>,
565 _Compare = _Compare(), _Allocator = _Allocator())
566 -> multiset<_Key, _Compare, _Allocator>;
567
568 template<typename _InputIterator, typename _Allocator,
569 typename = _RequireInputIter<_InputIterator>,
570 typename = _RequireAllocator<_Allocator>>
571 multiset(_InputIterator, _InputIterator, _Allocator)
572 -> multiset<typename iterator_traits<_InputIterator>::value_type,
573 less<typename iterator_traits<_InputIterator>::value_type>,
574 _Allocator>;
575
576 template<typename _Key, typename _Allocator,
577 typename = _RequireAllocator<_Allocator>>
578 multiset(initializer_list<_Key>, _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,
586 const multiset<_Key, _Compare, _Allocator>& __rhs)
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,
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 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
630