libstdc++
set.h
Go to the documentation of this file.
1// Debugging set implementation -*- C++ -*-
2
3// Copyright (C) 2003-2021 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>
33#include <debug/safe_container.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
45 : public __gnu_debug::_Safe_container<
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;
51 typedef __gnu_debug::_Safe_container<
52 set, _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 // Reference wrapper for base class. Disambiguates set(const _Base&)
62 // from copy constructor by requiring a user-defined conversion.
63 // See PR libstdc++/90102.
64 struct _Base_ref
65 {
66 _Base_ref(const _Base& __r) : _M_ref(__r) { }
67
68 const _Base& _M_ref;
69 };
70
71 public:
72 // types:
73 typedef _Key key_type;
74 typedef _Key value_type;
75 typedef _Compare key_compare;
76 typedef _Compare value_compare;
77 typedef _Allocator allocator_type;
78 typedef typename _Base::reference reference;
79 typedef typename _Base::const_reference const_reference;
80
81 typedef __gnu_debug::_Safe_iterator<_Base_iterator, set>
82 iterator;
83 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, set>
84 const_iterator;
85
86 typedef typename _Base::size_type size_type;
87 typedef typename _Base::difference_type difference_type;
88 typedef typename _Base::pointer pointer;
89 typedef typename _Base::const_pointer const_pointer;
90 typedef std::reverse_iterator<iterator> reverse_iterator;
91 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
92
93 // 23.3.3.1 construct/copy/destroy:
94
95#if __cplusplus < 201103L
96 set() : _Base() { }
97
98 set(const set& __x)
99 : _Base(__x) { }
100
101 ~set() { }
102#else
103 set() = default;
104 set(const set&) = default;
105 set(set&&) = default;
106
107 set(initializer_list<value_type> __l,
108 const _Compare& __comp = _Compare(),
109 const allocator_type& __a = allocator_type())
110 : _Base(__l, __comp, __a) { }
111
112 explicit
113 set(const allocator_type& __a)
114 : _Base(__a) { }
115
116 set(const set& __x, const allocator_type& __a)
117 : _Base(__x, __a) { }
118
119 set(set&& __x, const allocator_type& __a)
120 noexcept( noexcept(_Base(std::move(__x._M_base()), __a)) )
121 : _Safe(std::move(__x._M_safe()), __a),
122 _Base(std::move(__x._M_base()), __a) { }
123
124 set(initializer_list<value_type> __l, const allocator_type& __a)
125 : _Base(__l, __a) { }
126
127 template<typename _InputIterator>
128 set(_InputIterator __first, _InputIterator __last,
129 const allocator_type& __a)
130 : _Base(__gnu_debug::__base(
131 __glibcxx_check_valid_constructor_range(__first, __last)),
132 __gnu_debug::__base(__last), __a) { }
133
134 ~set() = default;
135#endif
136
137 explicit set(const _Compare& __comp,
138 const _Allocator& __a = _Allocator())
139 : _Base(__comp, __a) { }
140
141 template<typename _InputIterator>
142 set(_InputIterator __first, _InputIterator __last,
143 const _Compare& __comp = _Compare(),
144 const _Allocator& __a = _Allocator())
145 : _Base(__gnu_debug::__base(
146 __glibcxx_check_valid_constructor_range(__first, __last)),
147 __gnu_debug::__base(__last),
148 __comp, __a) { }
149
150 set(_Base_ref __x)
151 : _Base(__x._M_ref) { }
152
153#if __cplusplus < 201103L
154 set&
155 operator=(const set& __x)
156 {
157 this->_M_safe() = __x;
158 _M_base() = __x;
159 return *this;
160 }
161#else
162 set&
163 operator=(const set&) = default;
164
165 set&
166 operator=(set&&) = default;
167
168 set&
169 operator=(initializer_list<value_type> __l)
170 {
171 _M_base() = __l;
172 this->_M_invalidate_all();
173 return *this;
174 }
175#endif
176
177 using _Base::get_allocator;
178
179 // iterators:
180 iterator
181 begin() _GLIBCXX_NOEXCEPT
182 { return iterator(_Base::begin(), this); }
183
184 const_iterator
185 begin() const _GLIBCXX_NOEXCEPT
186 { return const_iterator(_Base::begin(), this); }
187
188 iterator
189 end() _GLIBCXX_NOEXCEPT
190 { return iterator(_Base::end(), this); }
191
192 const_iterator
193 end() const _GLIBCXX_NOEXCEPT
194 { return const_iterator(_Base::end(), this); }
195
196 reverse_iterator
197 rbegin() _GLIBCXX_NOEXCEPT
198 { return reverse_iterator(end()); }
199
200 const_reverse_iterator
201 rbegin() const _GLIBCXX_NOEXCEPT
202 { return const_reverse_iterator(end()); }
203
204 reverse_iterator
205 rend() _GLIBCXX_NOEXCEPT
206 { return reverse_iterator(begin()); }
207
208 const_reverse_iterator
209 rend() const _GLIBCXX_NOEXCEPT
210 { return const_reverse_iterator(begin()); }
211
212#if __cplusplus >= 201103L
213 const_iterator
214 cbegin() const noexcept
215 { return const_iterator(_Base::begin(), this); }
216
217 const_iterator
218 cend() const noexcept
219 { return const_iterator(_Base::end(), this); }
220
221 const_reverse_iterator
222 crbegin() const noexcept
223 { return const_reverse_iterator(end()); }
224
225 const_reverse_iterator
226 crend() const noexcept
227 { return const_reverse_iterator(begin()); }
228#endif
229
230 // capacity:
231 using _Base::empty;
232 using _Base::size;
233 using _Base::max_size;
234
235 // modifiers:
236#if __cplusplus >= 201103L
237 template<typename... _Args>
238 std::pair<iterator, bool>
239 emplace(_Args&&... __args)
240 {
241 auto __res = _Base::emplace(std::forward<_Args>(__args)...);
242 return { { __res.first, this }, __res.second };
243 }
244
245 template<typename... _Args>
246 iterator
247 emplace_hint(const_iterator __pos, _Args&&... __args)
248 {
249 __glibcxx_check_insert(__pos);
250 return
251 {
252 _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...),
253 this
254 };
255 }
256#endif
257
258 std::pair<iterator, bool>
259 insert(const value_type& __x)
260 {
261 std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
262 return std::pair<iterator, bool>(iterator(__res.first, this),
263 __res.second);
264 }
265
266#if __cplusplus >= 201103L
267 std::pair<iterator, bool>
268 insert(value_type&& __x)
269 {
270 auto __res = _Base::insert(std::move(__x));
271 return { { __res.first, this }, __res.second };
272 }
273#endif
274
275 iterator
276 insert(const_iterator __position, const value_type& __x)
277 {
278 __glibcxx_check_insert(__position);
279 return iterator(_Base::insert(__position.base(), __x), this);
280 }
281
282#if __cplusplus >= 201103L
283 iterator
284 insert(const_iterator __position, value_type&& __x)
285 {
286 __glibcxx_check_insert(__position);
287 return { _Base::insert(__position.base(), std::move(__x)), this };
288 }
289#endif
290
291 template <typename _InputIterator>
292 void
293 insert(_InputIterator __first, _InputIterator __last)
294 {
295 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
296 __glibcxx_check_valid_range2(__first, __last, __dist);
297
298 if (__dist.second >= __gnu_debug::__dp_sign)
299 _Base::insert(__gnu_debug::__unsafe(__first),
300 __gnu_debug::__unsafe(__last));
301 else
302 _Base::insert(__first, __last);
303 }
304
305#if __cplusplus >= 201103L
306 void
307 insert(initializer_list<value_type> __l)
308 { _Base::insert(__l); }
309#endif
310
311#if __cplusplus > 201402L
312 using node_type = typename _Base::node_type;
313 using insert_return_type = _Node_insert_return<iterator, node_type>;
314
315 node_type
316 extract(const_iterator __position)
317 {
318 __glibcxx_check_erase(__position);
319 this->_M_invalidate_if(_Equal(__position.base()));
320 return _Base::extract(__position.base());
321 }
322
323 node_type
324 extract(const key_type& __key)
325 {
326 const auto __position = find(__key);
327 if (__position != end())
328 return extract(__position);
329 return {};
330 }
331
332 insert_return_type
333 insert(node_type&& __nh)
334 {
335 auto __ret = _Base::insert(std::move(__nh));
336 iterator __pos = iterator(__ret.position, this);
337 return { __pos, __ret.inserted, std::move(__ret.node) };
338 }
339
340 iterator
341 insert(const_iterator __hint, node_type&& __nh)
342 {
343 __glibcxx_check_insert(__hint);
344 return { _Base::insert(__hint.base(), std::move(__nh)), this };
345 }
346
347 using _Base::merge;
348#endif // C++17
349
350#if __cplusplus >= 201103L
351 _GLIBCXX_ABI_TAG_CXX11
352 iterator
353 erase(const_iterator __position)
354 {
355 __glibcxx_check_erase(__position);
356 this->_M_invalidate_if(_Equal(__position.base()));
357 return { _Base::erase(__position.base()), this };
358 }
359#else
360 void
361 erase(iterator __position)
362 {
363 __glibcxx_check_erase(__position);
364 this->_M_invalidate_if(_Equal(__position.base()));
365 _Base::erase(__position.base());
366 }
367#endif
368
369 size_type
370 erase(const key_type& __x)
371 {
372 _Base_iterator __victim = _Base::find(__x);
373 if (__victim == _Base::end())
374 return 0;
375 else
376 {
377 this->_M_invalidate_if(_Equal(__victim));
378 _Base::erase(__victim);
379 return 1;
380 }
381 }
382
383#if __cplusplus >= 201103L
384 _GLIBCXX_ABI_TAG_CXX11
385 iterator
386 erase(const_iterator __first, const_iterator __last)
387 {
388 // _GLIBCXX_RESOLVE_LIB_DEFECTS
389 // 151. can't currently clear() empty container
390 __glibcxx_check_erase_range(__first, __last);
391 for (_Base_const_iterator __victim = __first.base();
392 __victim != __last.base(); ++__victim)
393 {
394 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(),
395 _M_message(__gnu_debug::__msg_valid_range)
396 ._M_iterator(__first, "first")
397 ._M_iterator(__last, "last"));
398 this->_M_invalidate_if(_Equal(__victim));
399 }
400
401 return { _Base::erase(__first.base(), __last.base()), this };
402 }
403#else
404 void
405 erase(iterator __first, iterator __last)
406 {
407 // _GLIBCXX_RESOLVE_LIB_DEFECTS
408 // 151. can't currently clear() empty container
409 __glibcxx_check_erase_range(__first, __last);
410 for (_Base_iterator __victim = __first.base();
411 __victim != __last.base(); ++__victim)
412 {
413 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
414 _M_message(__gnu_debug::__msg_valid_range)
415 ._M_iterator(__first, "first")
416 ._M_iterator(__last, "last"));
417 this->_M_invalidate_if(_Equal(__victim));
418 }
419 _Base::erase(__first.base(), __last.base());
420 }
421#endif
422
423 void
424 swap(set& __x)
425 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
426 {
427 _Safe::_M_swap(__x);
428 _Base::swap(__x);
429 }
430
431 void
432 clear() _GLIBCXX_NOEXCEPT
433 {
434 this->_M_invalidate_all();
435 _Base::clear();
436 }
437
438 // observers:
439 using _Base::key_comp;
440 using _Base::value_comp;
441
442 // set operations:
443 iterator
444 find(const key_type& __x)
445 { return iterator(_Base::find(__x), this); }
446
447 // _GLIBCXX_RESOLVE_LIB_DEFECTS
448 // 214. set::find() missing const overload
449 const_iterator
450 find(const key_type& __x) const
451 { return const_iterator(_Base::find(__x), this); }
452
453#if __cplusplus > 201103L
454 template<typename _Kt,
455 typename _Req =
456 typename __has_is_transparent<_Compare, _Kt>::type>
457 iterator
458 find(const _Kt& __x)
459 { return { _Base::find(__x), this }; }
460
461 template<typename _Kt,
462 typename _Req =
463 typename __has_is_transparent<_Compare, _Kt>::type>
464 const_iterator
465 find(const _Kt& __x) const
466 { return { _Base::find(__x), this }; }
467#endif
468
469 using _Base::count;
470
471 iterator
472 lower_bound(const key_type& __x)
473 { return iterator(_Base::lower_bound(__x), this); }
474
475 // _GLIBCXX_RESOLVE_LIB_DEFECTS
476 // 214. set::find() missing const overload
477 const_iterator
478 lower_bound(const key_type& __x) const
479 { return const_iterator(_Base::lower_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 lower_bound(const _Kt& __x)
487 { return { _Base::lower_bound(__x), this }; }
488
489 template<typename _Kt,
490 typename _Req =
491 typename __has_is_transparent<_Compare, _Kt>::type>
492 const_iterator
493 lower_bound(const _Kt& __x) const
494 { return { _Base::lower_bound(__x), this }; }
495#endif
496
497 iterator
498 upper_bound(const key_type& __x)
499 { return iterator(_Base::upper_bound(__x), this); }
500
501 // _GLIBCXX_RESOLVE_LIB_DEFECTS
502 // 214. set::find() missing const overload
503 const_iterator
504 upper_bound(const key_type& __x) const
505 { return const_iterator(_Base::upper_bound(__x), this); }
506
507#if __cplusplus > 201103L
508 template<typename _Kt,
509 typename _Req =
510 typename __has_is_transparent<_Compare, _Kt>::type>
511 iterator
512 upper_bound(const _Kt& __x)
513 { return { _Base::upper_bound(__x), this }; }
514
515 template<typename _Kt,
516 typename _Req =
517 typename __has_is_transparent<_Compare, _Kt>::type>
518 const_iterator
519 upper_bound(const _Kt& __x) const
520 { return { _Base::upper_bound(__x), this }; }
521#endif
522
523 std::pair<iterator, iterator>
524 equal_range(const key_type& __x)
525 {
526 std::pair<_Base_iterator, _Base_iterator> __res =
527 _Base::equal_range(__x);
528 return std::make_pair(iterator(__res.first, this),
529 iterator(__res.second, this));
530 }
531
532 // _GLIBCXX_RESOLVE_LIB_DEFECTS
533 // 214. set::find() missing const overload
534 std::pair<const_iterator, const_iterator>
535 equal_range(const key_type& __x) const
536 {
537 std::pair<_Base_const_iterator, _Base_const_iterator> __res =
538 _Base::equal_range(__x);
539 return std::make_pair(const_iterator(__res.first, this),
540 const_iterator(__res.second, this));
541 }
542
543#if __cplusplus > 201103L
544 template<typename _Kt,
545 typename _Req =
546 typename __has_is_transparent<_Compare, _Kt>::type>
547 std::pair<iterator, iterator>
548 equal_range(const _Kt& __x)
549 {
550 auto __res = _Base::equal_range(__x);
551 return { { __res.first, this }, { __res.second, this } };
552 }
553
554 template<typename _Kt,
555 typename _Req =
556 typename __has_is_transparent<_Compare, _Kt>::type>
557 std::pair<const_iterator, const_iterator>
558 equal_range(const _Kt& __x) const
559 {
560 auto __res = _Base::equal_range(__x);
561 return { { __res.first, this }, { __res.second, this } };
562 }
563#endif
564
565 _Base&
566 _M_base() _GLIBCXX_NOEXCEPT { return *this; }
567
568 const _Base&
569 _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
570 };
571
572#if __cpp_deduction_guides >= 201606
573
574 template<typename _InputIterator,
575 typename _Compare =
576 less<typename iterator_traits<_InputIterator>::value_type>,
577 typename _Allocator =
578 allocator<typename iterator_traits<_InputIterator>::value_type>,
579 typename = _RequireInputIter<_InputIterator>,
580 typename = _RequireNotAllocator<_Compare>,
581 typename = _RequireAllocator<_Allocator>>
582 set(_InputIterator, _InputIterator,
583 _Compare = _Compare(), _Allocator = _Allocator())
584 -> set<typename iterator_traits<_InputIterator>::value_type,
585 _Compare, _Allocator>;
586
587 template<typename _Key, typename _Compare = less<_Key>,
588 typename _Allocator = allocator<_Key>,
589 typename = _RequireNotAllocator<_Compare>,
590 typename = _RequireAllocator<_Allocator>>
591 set(initializer_list<_Key>,
592 _Compare = _Compare(), _Allocator = _Allocator())
593 -> set<_Key, _Compare, _Allocator>;
594
595 template<typename _InputIterator, typename _Allocator,
596 typename = _RequireInputIter<_InputIterator>,
597 typename = _RequireAllocator<_Allocator>>
598 set(_InputIterator, _InputIterator, _Allocator)
599 -> set<typename iterator_traits<_InputIterator>::value_type,
600 less<typename iterator_traits<_InputIterator>::value_type>,
601 _Allocator>;
602
603 template<typename _Key, typename _Allocator,
604 typename = _RequireAllocator<_Allocator>>
605 set(initializer_list<_Key>, _Allocator)
606 -> set<_Key, less<_Key>, _Allocator>;
607
608#endif // deduction guides
609
610 template<typename _Key, typename _Compare, typename _Allocator>
611 inline bool
612 operator==(const set<_Key, _Compare, _Allocator>& __lhs,
613 const set<_Key, _Compare, _Allocator>& __rhs)
614 { return __lhs._M_base() == __rhs._M_base(); }
615
616#if __cpp_lib_three_way_comparison
617 template<typename _Key, typename _Compare, typename _Alloc>
618 inline __detail::__synth3way_t<_Key>
619 operator<=>(const set<_Key, _Compare, _Alloc>& __lhs,
620 const set<_Key, _Compare, _Alloc>& __rhs)
621 { return __lhs._M_base() <=> __rhs._M_base(); }
622#else
623 template<typename _Key, typename _Compare, typename _Allocator>
624 inline bool
625 operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
626 const set<_Key, _Compare, _Allocator>& __rhs)
627 { return __lhs._M_base() != __rhs._M_base(); }
628
629 template<typename _Key, typename _Compare, typename _Allocator>
630 inline bool
631 operator<(const set<_Key, _Compare, _Allocator>& __lhs,
632 const set<_Key, _Compare, _Allocator>& __rhs)
633 { return __lhs._M_base() < __rhs._M_base(); }
634
635 template<typename _Key, typename _Compare, typename _Allocator>
636 inline bool
637 operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
638 const set<_Key, _Compare, _Allocator>& __rhs)
639 { return __lhs._M_base() <= __rhs._M_base(); }
640
641 template<typename _Key, typename _Compare, typename _Allocator>
642 inline bool
643 operator>=(const set<_Key, _Compare, _Allocator>& __lhs,
644 const set<_Key, _Compare, _Allocator>& __rhs)
645 { return __lhs._M_base() >= __rhs._M_base(); }
646
647 template<typename _Key, typename _Compare, typename _Allocator>
648 inline bool
649 operator>(const set<_Key, _Compare, _Allocator>& __lhs,
650 const set<_Key, _Compare, _Allocator>& __rhs)
651 { return __lhs._M_base() > __rhs._M_base(); }
652#endif // three-way comparison
653
654 template<typename _Key, typename _Compare, typename _Allocator>
655 void
656 swap(set<_Key, _Compare, _Allocator>& __x,
657 set<_Key, _Compare, _Allocator>& __y)
658 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
659 { return __x.swap(__y); }
660
661} // namespace __debug
662} // namespace std
663
664#endif
__glibcxx_check_insert
#define __glibcxx_check_insert(_Position)
Definition: macros.h:146
__glibcxx_check_erase_range
#define __glibcxx_check_erase_range(_First, _Last)
Definition: macros.h:240
__glibcxx_check_erase
#define __glibcxx_check_erase(_Position)
Definition: macros.h:212
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:104
std::swap
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
Definition: any:428
std
ISO C++ entities toplevel namespace is std.
__gnu_debug::__base
constexpr _Iterator __base(_Iterator __it)
Definition: helper_functions.h:315
std::initializer_list
initializer_list
Definition: initializer_list:48
std::allocator
The standard allocator, as per C++03 [20.4.1].
Definition: allocator.h:125
std::_Node_insert_return
Return type of insert(node_handle&&) on unique maps/sets.
Definition: node_handle.h:382
std::less
One of the comparison functors.
Definition: stl_function.h:396
std::set
A standard container made up of unique keys, which can be retrieved in logarithmic time.
Definition: stl_set.h:95
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:213
std::pair::first
_T1 first
The first member.
Definition: stl_pair.h:217
std::pair::second
_T2 second
The second member.
Definition: stl_pair.h:218
__gnu_debug::_Safe_iterator
Safe iterator wrapper.
Definition: safe_iterator.h:117
__gnu_debug::_Safe_iterator::base
_Iterator & base() noexcept
Return the underlying iterator.
Definition: safe_iterator.h:363
__gnu_debug::_Safe_container
Safe class dealing with some allocator dependent operations.
Definition: safe_container.h:43
__gnu_debug::_Safe_node_sequence
Like _Safe_sequence but with a special _M_invalidate_all implementation not invalidating past-the-end...
Definition: safe_sequence.h:133
std::__debug::set
Class std::set with safety/checking/debug instrumentation.
Definition: set.h:49