libstdc++
debug/set.h
Go to the documentation of this file.
1// Debugging set 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/set.h
26 * This file is a GNU debug extension to the Standard C++ Library.
27 */
28
29#ifndef _GLIBCXX_DEBUG_SET_H
30#define _GLIBCXX_DEBUG_SET_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::set with safety/checking/debug instrumentation.
42 template<typename _Key, typename _Compare = std::less<_Key>,
43 typename _Allocator = std::allocator<_Key> >
44 class set
46 set<_Key, _Compare, _Allocator>, _Allocator,
47 __gnu_debug::_Safe_node_sequence>,
48 public _GLIBCXX_STD_C::set<_Key,_Compare,_Allocator>
49 {
50 typedef _GLIBCXX_STD_C::set<_Key, _Compare, _Allocator> _Base;
53
55 typedef typename _Base::iterator _Base_iterator;
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
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;
82
83 // 23.3.3.1 construct/copy/destroy:
84
85#if __cplusplus < 201103L
86 set() : _Base() { }
87
88 set(const set& __x)
89 : _Base(__x) { }
90
91 ~set() { }
92#else
93 set() = default;
94 set(const set&) = default;
95 set(set&&) = default;
96
98 const _Compare& __comp = _Compare(),
99 const allocator_type& __a = allocator_type())
100 : _Base(__l, __comp, __a) { }
101
102 explicit
103 set(const allocator_type& __a)
104 : _Base(__a) { }
105
106 set(const set& __x, const allocator_type& __a)
107 : _Base(__x, __a) { }
108
109 set(set&& __x, const allocator_type& __a)
110 noexcept( noexcept(_Base(std::move(__x._M_base()), __a)) )
111 : _Safe(std::move(__x._M_safe()), __a),
112 _Base(std::move(__x._M_base()), __a) { }
113
114 set(initializer_list<value_type> __l, const allocator_type& __a)
115 : _Base(__l, __a) { }
116
117 template<typename _InputIterator>
118 set(_InputIterator __first, _InputIterator __last,
119 const allocator_type& __a)
121 __glibcxx_check_valid_constructor_range(__first, __last)),
122 __gnu_debug::__base(__last), __a) { }
123
124 ~set() = default;
125#endif
126
127 explicit set(const _Compare& __comp,
128 const _Allocator& __a = _Allocator())
129 : _Base(__comp, __a) { }
130
131 template<typename _InputIterator>
132 set(_InputIterator __first, _InputIterator __last,
133 const _Compare& __comp = _Compare(),
134 const _Allocator& __a = _Allocator())
136 __glibcxx_check_valid_constructor_range(__first, __last)),
137 __gnu_debug::__base(__last),
138 __comp, __a) { }
139
140 set(const _Base& __x)
141 : _Base(__x) { }
142
143#if __cplusplus < 201103L
144 set&
145 operator=(const set& __x)
146 {
147 this->_M_safe() = __x;
148 _M_base() = __x;
149 return *this;
150 }
151#else
152 set&
153 operator=(const set&) = default;
154
155 set&
156 operator=(set&&) = default;
157
158 set&
159 operator=(initializer_list<value_type> __l)
160 {
161 _M_base() = __l;
162 this->_M_invalidate_all();
163 return *this;
164 }
165#endif
166
167 using _Base::get_allocator;
168
169 // iterators:
171 begin() _GLIBCXX_NOEXCEPT
172 { return iterator(_Base::begin(), this); }
173
175 begin() const _GLIBCXX_NOEXCEPT
176 { return const_iterator(_Base::begin(), this); }
177
179 end() _GLIBCXX_NOEXCEPT
180 { return iterator(_Base::end(), this); }
181
183 end() const _GLIBCXX_NOEXCEPT
184 { return const_iterator(_Base::end(), this); }
185
187 rbegin() _GLIBCXX_NOEXCEPT
188 { return reverse_iterator(end()); }
189
191 rbegin() const _GLIBCXX_NOEXCEPT
192 { return const_reverse_iterator(end()); }
193
195 rend() _GLIBCXX_NOEXCEPT
196 { return reverse_iterator(begin()); }
197
199 rend() const _GLIBCXX_NOEXCEPT
200 { return const_reverse_iterator(begin()); }
201
202#if __cplusplus >= 201103L
204 cbegin() const noexcept
205 { return const_iterator(_Base::begin(), this); }
206
208 cend() const noexcept
209 { return const_iterator(_Base::end(), this); }
210
212 crbegin() const noexcept
213 { return const_reverse_iterator(end()); }
214
216 crend() const noexcept
217 { return const_reverse_iterator(begin()); }
218#endif
219
220 // capacity:
221 using _Base::empty;
222 using _Base::size;
223 using _Base::max_size;
224
225 // modifiers:
226#if __cplusplus >= 201103L
227 template<typename... _Args>
229 emplace(_Args&&... __args)
230 {
231 auto __res = _Base::emplace(std::forward<_Args>(__args)...);
232 return { { __res.first, this }, __res.second };
233 }
234
235 template<typename... _Args>
237 emplace_hint(const_iterator __pos, _Args&&... __args)
238 {
240 return
241 {
242 _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...),
243 this
244 };
245 }
246#endif
247
249 insert(const value_type& __x)
250 {
251 std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
252 return std::pair<iterator, bool>(iterator(__res.first, this),
253 __res.second);
254 }
255
256#if __cplusplus >= 201103L
258 insert(value_type&& __x)
259 {
260 auto __res = _Base::insert(std::move(__x));
261 return { { __res.first, this }, __res.second };
262 }
263#endif
264
266 insert(const_iterator __position, const value_type& __x)
267 {
268 __glibcxx_check_insert(__position);
269 return iterator(_Base::insert(__position.base(), __x), this);
270 }
271
272#if __cplusplus >= 201103L
274 insert(const_iterator __position, value_type&& __x)
275 {
276 __glibcxx_check_insert(__position);
277 return { _Base::insert(__position.base(), std::move(__x)), this };
278 }
279#endif
280
281 template <typename _InputIterator>
282 void
283 insert(_InputIterator __first, _InputIterator __last)
284 {
286 __glibcxx_check_valid_range2(__first, __last, __dist);
287
288 if (__dist.second >= __gnu_debug::__dp_sign)
289 _Base::insert(__gnu_debug::__unsafe(__first),
290 __gnu_debug::__unsafe(__last));
291 else
292 _Base::insert(__first, __last);
293 }
294
295#if __cplusplus >= 201103L
296 void
298 { _Base::insert(__l); }
299#endif
300
301#if __cplusplus > 201402L
302 using node_type = typename _Base::node_type;
303 using insert_return_type = _Node_insert_return<iterator, 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 insert_return_type
323 insert(node_type&& __nh)
324 {
325 auto __ret = _Base::insert(std::move(__nh));
326 iterator __pos = iterator(__ret.position, this);
327 return { __pos, __ret.inserted, std::move(__ret.node) };
328 }
329
331 insert(const_iterator __hint, node_type&& __nh)
332 {
334 return { _Base::insert(__hint.base(), std::move(__nh)), this };
335 }
336
337 using _Base::merge;
338#endif // C++17
339
340#if __cplusplus >= 201103L
341 _GLIBCXX_ABI_TAG_CXX11
343 erase(const_iterator __position)
344 {
345 __glibcxx_check_erase(__position);
346 this->_M_invalidate_if(_Equal(__position.base()));
347 return { _Base::erase(__position.base()), this };
348 }
349#else
350 void
351 erase(iterator __position)
352 {
353 __glibcxx_check_erase(__position);
354 this->_M_invalidate_if(_Equal(__position.base()));
355 _Base::erase(__position.base());
356 }
357#endif
358
359 size_type
360 erase(const key_type& __x)
361 {
362 _Base_iterator __victim = _Base::find(__x);
363 if (__victim == _Base::end())
364 return 0;
365 else
366 {
367 this->_M_invalidate_if(_Equal(__victim));
368 _Base::erase(__victim);
369 return 1;
370 }
371 }
372
373#if __cplusplus >= 201103L
374 _GLIBCXX_ABI_TAG_CXX11
376 erase(const_iterator __first, const_iterator __last)
377 {
378 // _GLIBCXX_RESOLVE_LIB_DEFECTS
379 // 151. can't currently clear() empty container
380 __glibcxx_check_erase_range(__first, __last);
381 for (_Base_const_iterator __victim = __first.base();
382 __victim != __last.base(); ++__victim)
383 {
384 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(),
385 _M_message(__gnu_debug::__msg_valid_range)
386 ._M_iterator(__first, "first")
387 ._M_iterator(__last, "last"));
388 this->_M_invalidate_if(_Equal(__victim));
389 }
390
391 return { _Base::erase(__first.base(), __last.base()), this };
392 }
393#else
394 void
395 erase(iterator __first, iterator __last)
396 {
397 // _GLIBCXX_RESOLVE_LIB_DEFECTS
398 // 151. can't currently clear() empty container
399 __glibcxx_check_erase_range(__first, __last);
400 for (_Base_iterator __victim = __first.base();
401 __victim != __last.base(); ++__victim)
402 {
403 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
404 _M_message(__gnu_debug::__msg_valid_range)
405 ._M_iterator(__first, "first")
406 ._M_iterator(__last, "last"));
407 this->_M_invalidate_if(_Equal(__victim));
408 }
409 _Base::erase(__first.base(), __last.base());
410 }
411#endif
412
413 void
414 swap(set& __x)
415 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
416 {
417 _Safe::_M_swap(__x);
418 _Base::swap(__x);
419 }
420
421 void
422 clear() _GLIBCXX_NOEXCEPT
423 {
424 this->_M_invalidate_all();
425 _Base::clear();
426 }
427
428 // observers:
429 using _Base::key_comp;
430 using _Base::value_comp;
431
432 // set operations:
434 find(const key_type& __x)
435 { return iterator(_Base::find(__x), this); }
436
437 // _GLIBCXX_RESOLVE_LIB_DEFECTS
438 // 214. set::find() missing const overload
440 find(const key_type& __x) const
441 { return const_iterator(_Base::find(__x), this); }
442
443#if __cplusplus > 201103L
444 template<typename _Kt,
445 typename _Req =
446 typename __has_is_transparent<_Compare, _Kt>::type>
448 find(const _Kt& __x)
449 { return { _Base::find(__x), this }; }
450
451 template<typename _Kt,
452 typename _Req =
453 typename __has_is_transparent<_Compare, _Kt>::type>
455 find(const _Kt& __x) const
456 { return { _Base::find(__x), this }; }
457#endif
458
459 using _Base::count;
460
462 lower_bound(const key_type& __x)
463 { return iterator(_Base::lower_bound(__x), this); }
464
465 // _GLIBCXX_RESOLVE_LIB_DEFECTS
466 // 214. set::find() missing const overload
468 lower_bound(const key_type& __x) const
469 { return const_iterator(_Base::lower_bound(__x), this); }
470
471#if __cplusplus > 201103L
472 template<typename _Kt,
473 typename _Req =
474 typename __has_is_transparent<_Compare, _Kt>::type>
476 lower_bound(const _Kt& __x)
477 { return { _Base::lower_bound(__x), this }; }
478
479 template<typename _Kt,
480 typename _Req =
481 typename __has_is_transparent<_Compare, _Kt>::type>
483 lower_bound(const _Kt& __x) const
484 { return { _Base::lower_bound(__x), this }; }
485#endif
486
488 upper_bound(const key_type& __x)
489 { return iterator(_Base::upper_bound(__x), this); }
490
491 // _GLIBCXX_RESOLVE_LIB_DEFECTS
492 // 214. set::find() missing const overload
494 upper_bound(const key_type& __x) const
495 { return const_iterator(_Base::upper_bound(__x), this); }
496
497#if __cplusplus > 201103L
498 template<typename _Kt,
499 typename _Req =
500 typename __has_is_transparent<_Compare, _Kt>::type>
502 upper_bound(const _Kt& __x)
503 { return { _Base::upper_bound(__x), this }; }
504
505 template<typename _Kt,
506 typename _Req =
507 typename __has_is_transparent<_Compare, _Kt>::type>
509 upper_bound(const _Kt& __x) const
510 { return { _Base::upper_bound(__x), this }; }
511#endif
512
514 equal_range(const key_type& __x)
515 {
517 _Base::equal_range(__x);
518 return std::make_pair(iterator(__res.first, this),
519 iterator(__res.second, this));
520 }
521
522 // _GLIBCXX_RESOLVE_LIB_DEFECTS
523 // 214. set::find() missing const overload
525 equal_range(const key_type& __x) const
526 {
528 _Base::equal_range(__x);
529 return std::make_pair(const_iterator(__res.first, this),
530 const_iterator(__res.second, this));
531 }
532
533#if __cplusplus > 201103L
534 template<typename _Kt,
535 typename _Req =
536 typename __has_is_transparent<_Compare, _Kt>::type>
538 equal_range(const _Kt& __x)
539 {
540 auto __res = _Base::equal_range(__x);
541 return { { __res.first, this }, { __res.second, this } };
542 }
543
544 template<typename _Kt,
545 typename _Req =
546 typename __has_is_transparent<_Compare, _Kt>::type>
548 equal_range(const _Kt& __x) const
549 {
550 auto __res = _Base::equal_range(__x);
551 return { { __res.first, this }, { __res.second, this } };
552 }
553#endif
554
555 _Base&
556 _M_base() _GLIBCXX_NOEXCEPT { return *this; }
557
558 const _Base&
559 _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
560 };
561
562#if __cpp_deduction_guides >= 201606
563
564 template<typename _InputIterator,
565 typename _Compare =
567 typename _Allocator =
569 typename = _RequireInputIter<_InputIterator>,
570 typename = _RequireNotAllocator<_Compare>,
571 typename = _RequireAllocator<_Allocator>>
572 set(_InputIterator, _InputIterator,
573 _Compare = _Compare(), _Allocator = _Allocator())
575 _Compare, _Allocator>;
576
577 template<typename _Key, typename _Compare = less<_Key>,
578 typename _Allocator = allocator<_Key>,
579 typename = _RequireNotAllocator<_Compare>,
580 typename = _RequireAllocator<_Allocator>>
582 _Compare = _Compare(), _Allocator = _Allocator())
584
585 template<typename _InputIterator, typename _Allocator,
586 typename = _RequireInputIter<_InputIterator>,
587 typename = _RequireAllocator<_Allocator>>
588 set(_InputIterator, _InputIterator, _Allocator)
591 _Allocator>;
592
593 template<typename _Key, typename _Allocator,
594 typename = _RequireAllocator<_Allocator>>
595 set(initializer_list<_Key>, _Allocator)
596 -> set<_Key, less<_Key>, _Allocator>;
597
598#endif
599
600 template<typename _Key, typename _Compare, typename _Allocator>
601 inline bool
602 operator==(const set<_Key, _Compare, _Allocator>& __lhs,
604 { return __lhs._M_base() == __rhs._M_base(); }
605
606 template<typename _Key, typename _Compare, typename _Allocator>
607 inline bool
608 operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
610 { return __lhs._M_base() != __rhs._M_base(); }
611
612 template<typename _Key, typename _Compare, typename _Allocator>
613 inline bool
614 operator<(const set<_Key, _Compare, _Allocator>& __lhs,
615 const set<_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 set<_Key, _Compare, _Allocator>& __lhs,
621 const set<_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 set<_Key, _Compare, _Allocator>& __lhs,
627 const set<_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 set<_Key, _Compare, _Allocator>& __lhs,
633 const set<_Key, _Compare, _Allocator>& __rhs)
634 { return __lhs._M_base() > __rhs._M_base(); }
635
636 template<typename _Key, typename _Compare, typename _Allocator>
637 void
638 swap(set<_Key, _Compare, _Allocator>& __x,
639 set<_Key, _Compare, _Allocator>& __y)
640 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
641 { return __x.swap(__y); }
642
643} // namespace __debug
644} // namespace std
645
646#endif
#define __glibcxx_check_insert(_Position)
Definition: macros.h:140
#define __glibcxx_check_erase_range(_First, _Last)
Definition: macros.h:234
#define __glibcxx_check_erase(_Position)
Definition: macros.h:206
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.
_Iterator __base(_Iterator __it)
initializer_list
The standard allocator, as per [20.4].
Definition: allocator.h:112
One of the comparison functors.
Definition: stl_function.h:382
A standard container made up of unique keys, which can be retrieved in logarithmic time.
Definition: stl_set.h:95
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.
_Iterator & base() noexcept
Return the underlying iterator.
Safe class dealing with some allocator dependent operations.
Like _Safe_sequence but with a special _M_invalidate_all implementation not invalidating past-the-end...
Class std::set with safety/checking/debug instrumentation.
Definition: debug/set.h:49