libstdc++
debug/set.h
Go to the documentation of this file.
1// Debugging set implementation -*- C++ -*-
2
3// Copyright (C) 2003-2016 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 public:
59 // types:
60 typedef _Key key_type;
61 typedef _Key value_type;
62 typedef _Compare key_compare;
63 typedef _Compare value_compare;
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 set() : _Base() { }
84
85 set(const set& __x)
86 : _Base(__x) { }
87
88 ~set() { }
89#else
90 set() = default;
91 set(const set&) = default;
92 set(set&&) = default;
93
95 const _Compare& __comp = _Compare(),
96 const allocator_type& __a = allocator_type())
97 : _Base(__l, __comp, __a) { }
98
99 explicit
100 set(const allocator_type& __a)
101 : _Base(__a) { }
102
103 set(const set& __x, const allocator_type& __a)
104 : _Base(__x, __a) { }
105
106 set(set&& __x, const allocator_type& __a)
107 : _Safe(std::move(__x._M_safe()), __a),
108 _Base(std::move(__x._M_base()), __a) { }
109
111 : _Base(__l, __a) { }
112
113 template<typename _InputIterator>
114 set(_InputIterator __first, _InputIterator __last,
115 const allocator_type& __a)
116 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
117 __last)),
118 __gnu_debug::__base(__last), __a) { }
119
120 ~set() = default;
121#endif
122
123 explicit set(const _Compare& __comp,
124 const _Allocator& __a = _Allocator())
125 : _Base(__comp, __a) { }
126
127 template<typename _InputIterator>
128 set(_InputIterator __first, _InputIterator __last,
129 const _Compare& __comp = _Compare(),
130 const _Allocator& __a = _Allocator())
131 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
132 __last)),
133 __gnu_debug::__base(__last),
134 __comp, __a) { }
135
136 set(const _Base& __x)
137 : _Base(__x) { }
138
139#if __cplusplus < 201103L
140 set&
141 operator=(const set& __x)
142 {
143 this->_M_safe() = __x;
144 _M_base() = __x;
145 return *this;
146 }
147#else
148 set&
149 operator=(const set&) = default;
150
151 set&
152 operator=(set&&) = default;
153
154 set&
156 {
157 _M_base() = __l;
158 this->_M_invalidate_all();
159 return *this;
160 }
161#endif
162
163 using _Base::get_allocator;
164
165 // iterators:
167 begin() _GLIBCXX_NOEXCEPT
168 { return iterator(_Base::begin(), this); }
169
171 begin() const _GLIBCXX_NOEXCEPT
172 { return const_iterator(_Base::begin(), this); }
173
176 { return iterator(_Base::end(), this); }
177
179 end() const _GLIBCXX_NOEXCEPT
180 { return const_iterator(_Base::end(), this); }
181
183 rbegin() _GLIBCXX_NOEXCEPT
184 { return reverse_iterator(end()); }
185
187 rbegin() const _GLIBCXX_NOEXCEPT
188 { return const_reverse_iterator(end()); }
189
191 rend() _GLIBCXX_NOEXCEPT
192 { return reverse_iterator(begin()); }
193
195 rend() const _GLIBCXX_NOEXCEPT
196 { return const_reverse_iterator(begin()); }
197
198#if __cplusplus >= 201103L
200 cbegin() const noexcept
201 { return const_iterator(_Base::begin(), this); }
202
204 cend() const noexcept
205 { return const_iterator(_Base::end(), this); }
206
208 crbegin() const noexcept
209 { return const_reverse_iterator(end()); }
210
212 crend() const noexcept
213 { return const_reverse_iterator(begin()); }
214#endif
215
216 // capacity:
217 using _Base::empty;
218 using _Base::size;
219 using _Base::max_size;
220
221 // modifiers:
222#if __cplusplus >= 201103L
223 template<typename... _Args>
225 emplace(_Args&&... __args)
226 {
227 auto __res = _Base::emplace(std::forward<_Args>(__args)...);
228 return std::pair<iterator, bool>(iterator(__res.first, this),
229 __res.second);
230 }
231
232 template<typename... _Args>
234 emplace_hint(const_iterator __pos, _Args&&... __args)
235 {
237 return iterator(_Base::emplace_hint(__pos.base(),
239 this);
240 }
241#endif
242
244 insert(const value_type& __x)
245 {
246 std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
247 return std::pair<iterator, bool>(iterator(__res.first, this),
248 __res.second);
249 }
250
251#if __cplusplus >= 201103L
253 insert(value_type&& __x)
254 {
256 = _Base::insert(std::move(__x));
257 return std::pair<iterator, bool>(iterator(__res.first, this),
258 __res.second);
259 }
260#endif
261
263 insert(const_iterator __position, const value_type& __x)
264 {
266 return iterator(_Base::insert(__position.base(), __x), this);
267 }
268
269#if __cplusplus >= 201103L
271 insert(const_iterator __position, value_type&& __x)
272 {
274 return iterator(_Base::insert(__position.base(), std::move(__x)),
275 this);
276 }
277#endif
278
279 template <typename _InputIterator>
280 void
281 insert(_InputIterator __first, _InputIterator __last)
282 {
284 __glibcxx_check_valid_range2(__first, __last, __dist);
285
286 if (__dist.second >= __gnu_debug::__dp_sign)
287 _Base::insert(__gnu_debug::__unsafe(__first),
288 __gnu_debug::__unsafe(__last));
289 else
290 _Base::insert(__first, __last);
291 }
292
293#if __cplusplus >= 201103L
294 void
296 { _Base::insert(__l); }
297#endif
298
299#if __cplusplus >= 201103L
302 {
304 this->_M_invalidate_if(_Equal(__position.base()));
305 return iterator(_Base::erase(__position.base()), this);
306 }
307#else
308 void
309 erase(iterator __position)
310 {
312 this->_M_invalidate_if(_Equal(__position.base()));
313 _Base::erase(__position.base());
314 }
315#endif
316
317 size_type
318 erase(const key_type& __x)
319 {
320 _Base_iterator __victim = _Base::find(__x);
321 if (__victim == _Base::end())
322 return 0;
323 else
324 {
325 this->_M_invalidate_if(_Equal(__victim));
326 _Base::erase(__victim);
327 return 1;
328 }
329 }
330
331#if __cplusplus >= 201103L
333 erase(const_iterator __first, const_iterator __last)
334 {
335 // _GLIBCXX_RESOLVE_LIB_DEFECTS
336 // 151. can't currently clear() empty container
337 __glibcxx_check_erase_range(__first, __last);
338 for (_Base_const_iterator __victim = __first.base();
339 __victim != __last.base(); ++__victim)
340 {
341 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
342 _M_message(__gnu_debug::__msg_valid_range)
343 ._M_iterator(__first, "first")
344 ._M_iterator(__last, "last"));
345 this->_M_invalidate_if(_Equal(__victim));
346 }
347 return iterator(_Base::erase(__first.base(), __last.base()), this);
348 }
349#else
350 void
351 erase(iterator __first, iterator __last)
352 {
353 // _GLIBCXX_RESOLVE_LIB_DEFECTS
354 // 151. can't currently clear() empty container
355 __glibcxx_check_erase_range(__first, __last);
356 for (_Base_iterator __victim = __first.base();
357 __victim != __last.base(); ++__victim)
358 {
359 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
360 _M_message(__gnu_debug::__msg_valid_range)
361 ._M_iterator(__first, "first")
362 ._M_iterator(__last, "last"));
363 this->_M_invalidate_if(_Equal(__victim));
364 }
365 _Base::erase(__first.base(), __last.base());
366 }
367#endif
368
369 void
370 swap(set& __x)
371 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
372 {
373 _Safe::_M_swap(__x);
374 _Base::swap(__x);
375 }
376
377 void
378 clear() _GLIBCXX_NOEXCEPT
379 {
380 this->_M_invalidate_all();
381 _Base::clear();
382 }
383
384 // observers:
385 using _Base::key_comp;
386 using _Base::value_comp;
387
388 // set operations:
390 find(const key_type& __x)
391 { return iterator(_Base::find(__x), this); }
392
393 // _GLIBCXX_RESOLVE_LIB_DEFECTS
394 // 214. set::find() missing const overload
396 find(const key_type& __x) const
397 { return const_iterator(_Base::find(__x), this); }
398
399#if __cplusplus > 201103L
400 template<typename _Kt,
401 typename _Req =
402 typename __has_is_transparent<_Compare, _Kt>::type>
404 find(const _Kt& __x)
405 { return { _Base::find(__x), this }; }
406
407 template<typename _Kt,
408 typename _Req =
409 typename __has_is_transparent<_Compare, _Kt>::type>
411 find(const _Kt& __x) const
412 { return { _Base::find(__x), this }; }
413#endif
414
415 using _Base::count;
416
418 lower_bound(const key_type& __x)
419 { return iterator(_Base::lower_bound(__x), this); }
420
421 // _GLIBCXX_RESOLVE_LIB_DEFECTS
422 // 214. set::find() missing const overload
424 lower_bound(const key_type& __x) const
425 { return const_iterator(_Base::lower_bound(__x), this); }
426
427#if __cplusplus > 201103L
428 template<typename _Kt,
429 typename _Req =
430 typename __has_is_transparent<_Compare, _Kt>::type>
432 lower_bound(const _Kt& __x)
433 { return { _Base::lower_bound(__x), this }; }
434
435 template<typename _Kt,
436 typename _Req =
437 typename __has_is_transparent<_Compare, _Kt>::type>
439 lower_bound(const _Kt& __x) const
440 { return { _Base::lower_bound(__x), this }; }
441#endif
442
444 upper_bound(const key_type& __x)
445 { return iterator(_Base::upper_bound(__x), this); }
446
447 // _GLIBCXX_RESOLVE_LIB_DEFECTS
448 // 214. set::find() missing const overload
450 upper_bound(const key_type& __x) const
451 { return const_iterator(_Base::upper_bound(__x), this); }
452
453#if __cplusplus > 201103L
454 template<typename _Kt,
455 typename _Req =
456 typename __has_is_transparent<_Compare, _Kt>::type>
458 upper_bound(const _Kt& __x)
459 { return { _Base::upper_bound(__x), this }; }
460
461 template<typename _Kt,
462 typename _Req =
463 typename __has_is_transparent<_Compare, _Kt>::type>
465 upper_bound(const _Kt& __x) const
466 { return { _Base::upper_bound(__x), this }; }
467#endif
468
470 equal_range(const key_type& __x)
471 {
473 _Base::equal_range(__x);
474 return std::make_pair(iterator(__res.first, this),
475 iterator(__res.second, this));
476 }
477
478 // _GLIBCXX_RESOLVE_LIB_DEFECTS
479 // 214. set::find() missing const overload
481 equal_range(const key_type& __x) const
482 {
484 _Base::equal_range(__x);
485 return std::make_pair(const_iterator(__res.first, this),
486 const_iterator(__res.second, this));
487 }
488
489#if __cplusplus > 201103L
490 template<typename _Kt,
491 typename _Req =
492 typename __has_is_transparent<_Compare, _Kt>::type>
494 equal_range(const _Kt& __x)
495 {
496 auto __res = _Base::equal_range(__x);
497 return { { __res.first, this }, { __res.second, this } };
498 }
499
500 template<typename _Kt,
501 typename _Req =
502 typename __has_is_transparent<_Compare, _Kt>::type>
504 equal_range(const _Kt& __x) const
505 {
506 auto __res = _Base::equal_range(__x);
507 return { { __res.first, this }, { __res.second, this } };
508 }
509#endif
510
511 _Base&
512 _M_base() _GLIBCXX_NOEXCEPT { return *this; }
513
514 const _Base&
515 _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
516 };
517
518 template<typename _Key, typename _Compare, typename _Allocator>
519 inline bool
520 operator==(const set<_Key, _Compare, _Allocator>& __lhs,
522 { return __lhs._M_base() == __rhs._M_base(); }
523
524 template<typename _Key, typename _Compare, typename _Allocator>
525 inline bool
526 operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
528 { return __lhs._M_base() != __rhs._M_base(); }
529
530 template<typename _Key, typename _Compare, typename _Allocator>
531 inline bool
532 operator<(const set<_Key, _Compare, _Allocator>& __lhs,
533 const set<_Key, _Compare, _Allocator>& __rhs)
534 { return __lhs._M_base() < __rhs._M_base(); }
535
536 template<typename _Key, typename _Compare, typename _Allocator>
537 inline bool
538 operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
539 const set<_Key, _Compare, _Allocator>& __rhs)
540 { return __lhs._M_base() <= __rhs._M_base(); }
541
542 template<typename _Key, typename _Compare, typename _Allocator>
543 inline bool
544 operator>=(const set<_Key, _Compare, _Allocator>& __lhs,
545 const set<_Key, _Compare, _Allocator>& __rhs)
546 { return __lhs._M_base() >= __rhs._M_base(); }
547
548 template<typename _Key, typename _Compare, typename _Allocator>
549 inline bool
550 operator>(const set<_Key, _Compare, _Allocator>& __lhs,
551 const set<_Key, _Compare, _Allocator>& __rhs)
552 { return __lhs._M_base() > __rhs._M_base(); }
553
554 template<typename _Key, typename _Compare, typename _Allocator>
555 void
556 swap(set<_Key, _Compare, _Allocator>& __x,
557 set<_Key, _Compare, _Allocator>& __y)
558 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
559 { return __x.swap(__y); }
560
561} // namespace __debug
562} // namespace std
563
564#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:502
ISO C++ entities toplevel namespace is std.
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