libstdc++
set.h
Go to the documentation of this file.
1// Debugging set implementation -*- C++ -*-
2
3// Copyright (C) 2003-2020 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;
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
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&
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
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 {
269 return iterator(_Base::insert(__position.base(), __x), this);
270 }
271
272#if __cplusplus >= 201103L
274 insert(const_iterator __position, value_type&& __x)
275 {
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;
304
305 node_type
307 {
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
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
344 {
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 {
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 =
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,
591 _Allocator>;
592
593 template<typename _Key, typename _Allocator,
597
598#endif // deduction guides
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#if __cpp_lib_three_way_comparison
607 template<typename _Key, typename _Compare, typename _Alloc>
608 inline __detail::__synth3way_t<_Key>
611 { return __lhs._M_base() <=> __rhs._M_base(); }
612#else
613 template<typename _Key, typename _Compare, typename _Allocator>
614 inline bool
615 operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
616 const set<_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 set<_Key, _Compare, _Allocator>& __lhs,
622 const set<_Key, _Compare, _Allocator>& __rhs)
623 { return __lhs._M_base() < __rhs._M_base(); }
624
625 template<typename _Key, typename _Compare, typename _Allocator>
626 inline bool
627 operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
628 const set<_Key, _Compare, _Allocator>& __rhs)
629 { return __lhs._M_base() <= __rhs._M_base(); }
630
631 template<typename _Key, typename _Compare, typename _Allocator>
632 inline bool
633 operator>=(const set<_Key, _Compare, _Allocator>& __lhs,
634 const set<_Key, _Compare, _Allocator>& __rhs)
635 { return __lhs._M_base() >= __rhs._M_base(); }
636
637 template<typename _Key, typename _Compare, typename _Allocator>
638 inline bool
639 operator>(const set<_Key, _Compare, _Allocator>& __lhs,
640 const set<_Key, _Compare, _Allocator>& __rhs)
641 { return __lhs._M_base() > __rhs._M_base(); }
642#endif // three-way comparison
643
644 template<typename _Key, typename _Compare, typename _Allocator>
645 void
646 swap(set<_Key, _Compare, _Allocator>& __x,
647 set<_Key, _Compare, _Allocator>& __y)
648 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
649 { return __x.swap(__y); }
650
651} // namespace __debug
652} // namespace std
653
654#endif
#define __glibcxx_check_insert(_Position)
Definition macros.h:156
#define __glibcxx_check_erase_range(_First, _Last)
Definition macros.h:250
#define __glibcxx_check_erase(_Position)
Definition macros.h:222
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:101
ISO C++ entities toplevel namespace is std.
constexpr _Iterator __base(_Iterator __it)
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 set.h:49