libstdc++
debug/multiset.h
Go to the documentation of this file.
1// Debugging multiset implementation -*- C++ -*-
2
3// Copyright (C) 2003-2017 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 : _Safe(std::move(__m._M_safe()), __a),
108 _Base(std::move(__m._M_base()), __a) { }
109
110 multiset(initializer_list<value_type> __l, const allocator_type& __a)
111 : _Base(__l, __a)
112 { }
113
114 template<typename _InputIterator>
115 multiset(_InputIterator __first, _InputIterator __last,
116 const allocator_type& __a)
117 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
118 __last)),
119 __gnu_debug::__base(__last), __a) { }
120
121 ~multiset() = default;
122#endif
123
124 explicit multiset(const _Compare& __comp,
125 const _Allocator& __a = _Allocator())
126 : _Base(__comp, __a) { }
127
128 template<typename _InputIterator>
129 multiset(_InputIterator __first, _InputIterator __last,
130 const _Compare& __comp = _Compare(),
131 const _Allocator& __a = _Allocator())
132 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
133 __last)),
134 __gnu_debug::__base(__last),
135 __comp, __a) { }
136
137 multiset(const _Base& __x)
138 : _Base(__x) { }
139
140#if __cplusplus < 201103L
141 multiset&
142 operator=(const multiset& __x)
143 {
144 this->_M_safe() = __x;
145 _M_base() = __x;
146 return *this;
147 }
148#else
149 multiset&
150 operator=(const multiset&) = default;
151
152 multiset&
153 operator=(multiset&&) = default;
154
155 multiset&
156 operator=(initializer_list<value_type> __l)
157 {
158 _M_base() = __l;
159 this->_M_invalidate_all();
160 return *this;
161 }
162#endif
163
164 using _Base::get_allocator;
165
166 // iterators:
168 begin() _GLIBCXX_NOEXCEPT
169 { return iterator(_Base::begin(), this); }
170
172 begin() const _GLIBCXX_NOEXCEPT
173 { return const_iterator(_Base::begin(), this); }
174
176 end() _GLIBCXX_NOEXCEPT
177 { return iterator(_Base::end(), this); }
178
180 end() const _GLIBCXX_NOEXCEPT
181 { return const_iterator(_Base::end(), this); }
182
184 rbegin() _GLIBCXX_NOEXCEPT
185 { return reverse_iterator(end()); }
186
188 rbegin() const _GLIBCXX_NOEXCEPT
189 { return const_reverse_iterator(end()); }
190
192 rend() _GLIBCXX_NOEXCEPT
193 { return reverse_iterator(begin()); }
194
196 rend() const _GLIBCXX_NOEXCEPT
197 { return const_reverse_iterator(begin()); }
198
199#if __cplusplus >= 201103L
201 cbegin() const noexcept
202 { return const_iterator(_Base::begin(), this); }
203
205 cend() const noexcept
206 { return const_iterator(_Base::end(), this); }
207
209 crbegin() const noexcept
210 { return const_reverse_iterator(end()); }
211
213 crend() const noexcept
214 { return const_reverse_iterator(begin()); }
215#endif
216
217 // capacity:
218 using _Base::empty;
219 using _Base::size;
220 using _Base::max_size;
221
222 // modifiers:
223#if __cplusplus >= 201103L
224 template<typename... _Args>
226 emplace(_Args&&... __args)
227 {
228 return iterator(_Base::emplace(std::forward<_Args>(__args)...),
229 this);
230 }
231
232 template<typename... _Args>
234 emplace_hint(const_iterator __pos, _Args&&... __args)
235 {
237 return iterator(_Base::emplace_hint(__pos.base(),
238 std::forward<_Args>(__args)...),
239 this);
240 }
241#endif
242
244 insert(const value_type& __x)
245 { return iterator(_Base::insert(__x), this); }
246
247#if __cplusplus >= 201103L
249 insert(value_type&& __x)
250 { return iterator(_Base::insert(std::move(__x)), this); }
251#endif
252
254 insert(const_iterator __position, const value_type& __x)
255 {
256 __glibcxx_check_insert(__position);
257 return iterator(_Base::insert(__position.base(), __x), this);
258 }
259
260#if __cplusplus >= 201103L
262 insert(const_iterator __position, value_type&& __x)
263 {
264 __glibcxx_check_insert(__position);
265 return iterator(_Base::insert(__position.base(), std::move(__x)),
266 this);
267 }
268#endif
269
270 template<typename _InputIterator>
271 void
272 insert(_InputIterator __first, _InputIterator __last)
273 {
275 __glibcxx_check_valid_range2(__first, __last, __dist);
276
277 if (__dist.second >= __gnu_debug::__dp_sign)
278 _Base::insert(__gnu_debug::__unsafe(__first),
279 __gnu_debug::__unsafe(__last));
280 else
281 _Base::insert(__first, __last);
282 }
283
284#if __cplusplus >= 201103L
285 void
287 { _Base::insert(__l); }
288#endif
289
290#if __cplusplus > 201402L
291 using node_type = typename _Base::node_type;
292
293 node_type
294 extract(const_iterator __position)
295 {
296 __glibcxx_check_erase(__position);
297 this->_M_invalidate_if(_Equal(__position.base()));
298 return _Base::extract(__position.base());
299 }
300
301 node_type
302 extract(const key_type& __key)
303 {
304 const auto __position = find(__key);
305 if (__position != end())
306 return extract(__position);
307 return {};
308 }
309
311 insert(node_type&& __nh)
312 { return iterator(_Base::insert(std::move(__nh)), this); }
313
315 insert(const_iterator __hint, node_type&& __nh)
316 {
318 return iterator(_Base::insert(__hint.base(), std::move(__nh)), this);
319 }
320
321 using _Base::merge;
322#endif // C++17
323
324#if __cplusplus >= 201103L
326 erase(const_iterator __position)
327 {
328 __glibcxx_check_erase(__position);
329 this->_M_invalidate_if(_Equal(__position.base()));
330 return iterator(_Base::erase(__position.base()), this);
331 }
332#else
333 void
334 erase(iterator __position)
335 {
336 __glibcxx_check_erase(__position);
337 this->_M_invalidate_if(_Equal(__position.base()));
338 _Base::erase(__position.base());
339 }
340#endif
341
342 size_type
343 erase(const key_type& __x)
344 {
346 _Base::equal_range(__x);
347 size_type __count = 0;
348 _Base_iterator __victim = __victims.first;
349 while (__victim != __victims.second)
350 {
351 this->_M_invalidate_if(_Equal(__victim));
352 _Base::erase(__victim++);
353 ++__count;
354 }
355 return __count;
356 }
357
358#if __cplusplus >= 201103L
360 erase(const_iterator __first, const_iterator __last)
361 {
362 // _GLIBCXX_RESOLVE_LIB_DEFECTS
363 // 151. can't currently clear() empty container
364 __glibcxx_check_erase_range(__first, __last);
365 for (_Base_const_iterator __victim = __first.base();
366 __victim != __last.base(); ++__victim)
367 {
368 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
369 _M_message(__gnu_debug::__msg_valid_range)
370 ._M_iterator(__first, "first")
371 ._M_iterator(__last, "last"));
372 this->_M_invalidate_if(_Equal(__victim));
373 }
374 return iterator(_Base::erase(__first.base(), __last.base()), this);
375 }
376#else
377 void
378 erase(iterator __first, iterator __last)
379 {
380 // _GLIBCXX_RESOLVE_LIB_DEFECTS
381 // 151. can't currently clear() empty container
382 __glibcxx_check_erase_range(__first, __last);
383 for (_Base_iterator __victim = __first.base();
384 __victim != __last.base(); ++__victim)
385 {
386 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
387 _M_message(__gnu_debug::__msg_valid_range)
388 ._M_iterator(__first, "first")
389 ._M_iterator(__last, "last"));
390 this->_M_invalidate_if(_Equal(__victim));
391 }
392 _Base::erase(__first.base(), __last.base());
393 }
394#endif
395
396 void
397 swap(multiset& __x)
398 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
399 {
400 _Safe::_M_swap(__x);
401 _Base::swap(__x);
402 }
403
404 void
405 clear() _GLIBCXX_NOEXCEPT
406 {
407 this->_M_invalidate_all();
408 _Base::clear();
409 }
410
411 // observers:
412 using _Base::key_comp;
413 using _Base::value_comp;
414
415 // multiset operations:
417 find(const key_type& __x)
418 { return iterator(_Base::find(__x), this); }
419
420 // _GLIBCXX_RESOLVE_LIB_DEFECTS
421 // 214. set::find() missing const overload
423 find(const key_type& __x) const
424 { return const_iterator(_Base::find(__x), this); }
425
426#if __cplusplus > 201103L
427 template<typename _Kt,
428 typename _Req =
429 typename __has_is_transparent<_Compare, _Kt>::type>
431 find(const _Kt& __x)
432 { return { _Base::find(__x), this }; }
433
434 template<typename _Kt,
435 typename _Req =
436 typename __has_is_transparent<_Compare, _Kt>::type>
438 find(const _Kt& __x) const
439 { return { _Base::find(__x), this }; }
440#endif
441
442 using _Base::count;
443
445 lower_bound(const key_type& __x)
446 { return iterator(_Base::lower_bound(__x), this); }
447
448 // _GLIBCXX_RESOLVE_LIB_DEFECTS
449 // 214. set::find() missing const overload
451 lower_bound(const key_type& __x) const
452 { return const_iterator(_Base::lower_bound(__x), this); }
453
454#if __cplusplus > 201103L
455 template<typename _Kt,
456 typename _Req =
457 typename __has_is_transparent<_Compare, _Kt>::type>
459 lower_bound(const _Kt& __x)
460 { return { _Base::lower_bound(__x), this }; }
461
462 template<typename _Kt,
463 typename _Req =
464 typename __has_is_transparent<_Compare, _Kt>::type>
466 lower_bound(const _Kt& __x) const
467 { return { _Base::lower_bound(__x), this }; }
468#endif
469
471 upper_bound(const key_type& __x)
472 { return iterator(_Base::upper_bound(__x), this); }
473
474 // _GLIBCXX_RESOLVE_LIB_DEFECTS
475 // 214. set::find() missing const overload
477 upper_bound(const key_type& __x) const
478 { return const_iterator(_Base::upper_bound(__x), this); }
479
480#if __cplusplus > 201103L
481 template<typename _Kt,
482 typename _Req =
483 typename __has_is_transparent<_Compare, _Kt>::type>
485 upper_bound(const _Kt& __x)
486 { return { _Base::upper_bound(__x), this }; }
487
488 template<typename _Kt,
489 typename _Req =
490 typename __has_is_transparent<_Compare, _Kt>::type>
492 upper_bound(const _Kt& __x) const
493 { return { _Base::upper_bound(__x), this }; }
494#endif
495
497 equal_range(const key_type& __x)
498 {
500 _Base::equal_range(__x);
501 return std::make_pair(iterator(__res.first, this),
502 iterator(__res.second, this));
503 }
504
505 // _GLIBCXX_RESOLVE_LIB_DEFECTS
506 // 214. set::find() missing const overload
508 equal_range(const key_type& __x) const
509 {
511 _Base::equal_range(__x);
512 return std::make_pair(const_iterator(__res.first, this),
513 const_iterator(__res.second, this));
514 }
515
516#if __cplusplus > 201103L
517 template<typename _Kt,
518 typename _Req =
519 typename __has_is_transparent<_Compare, _Kt>::type>
521 equal_range(const _Kt& __x)
522 {
523 auto __res = _Base::equal_range(__x);
524 return { { __res.first, this }, { __res.second, this } };
525 }
526
527 template<typename _Kt,
528 typename _Req =
529 typename __has_is_transparent<_Compare, _Kt>::type>
531 equal_range(const _Kt& __x) const
532 {
533 auto __res = _Base::equal_range(__x);
534 return { { __res.first, this }, { __res.second, this } };
535 }
536#endif
537
538 _Base&
539 _M_base() _GLIBCXX_NOEXCEPT { return *this; }
540
541 const _Base&
542 _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
543 };
544
545 template<typename _Key, typename _Compare, typename _Allocator>
546 inline bool
547 operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
549 { return __lhs._M_base() == __rhs._M_base(); }
550
551 template<typename _Key, typename _Compare, typename _Allocator>
552 inline bool
553 operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
555 { return __lhs._M_base() != __rhs._M_base(); }
556
557 template<typename _Key, typename _Compare, typename _Allocator>
558 inline bool
559 operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
560 const multiset<_Key, _Compare, _Allocator>& __rhs)
561 { return __lhs._M_base() < __rhs._M_base(); }
562
563 template<typename _Key, typename _Compare, typename _Allocator>
564 inline bool
565 operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
566 const multiset<_Key, _Compare, _Allocator>& __rhs)
567 { return __lhs._M_base() <= __rhs._M_base(); }
568
569 template<typename _Key, typename _Compare, typename _Allocator>
570 inline bool
571 operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
572 const multiset<_Key, _Compare, _Allocator>& __rhs)
573 { return __lhs._M_base() >= __rhs._M_base(); }
574
575 template<typename _Key, typename _Compare, typename _Allocator>
576 inline bool
577 operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
578 const multiset<_Key, _Compare, _Allocator>& __rhs)
579 { return __lhs._M_base() > __rhs._M_base(); }
580
581 template<typename _Key, typename _Compare, typename _Allocator>
582 void
583 swap(multiset<_Key, _Compare, _Allocator>& __x,
584 multiset<_Key, _Compare, _Allocator>& __y)
585 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
586 { return __x.swap(__y); }
587
588} // namespace __debug
589} // namespace std
590
591#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:519
ISO C++ entities toplevel namespace is std.
initializer_list
A standard container made up of elements, which can be retrieved in logarithmic time.
Definition: stl_multiset.h:96
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:199
_T1 first
second_type is the second bound type
Definition: stl_pair.h:203
_T2 second
first is a copy of the first object
Definition: stl_pair.h:204
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...