1 // Debugging set implementation -*- C++ -*-
2
3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
4 // Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
10 // any later version.
11
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
16
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
25
26 /** @file debug/set.h
27 * This file is a GNU debug extension to the Standard C++ Library.
28 */
29
30 #ifndef _GLIBCXX_DEBUG_SET_H
31 #define _GLIBCXX_DEBUG_SET_H 1
32
33 #include <debug/safe_sequence.h>
34 #include <debug/safe_iterator.h>
35 #include <utility>
36
_GLIBCXX_VISIBILITY(default)37 namespace std _GLIBCXX_VISIBILITY(default)
38 {
39 namespace __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 _GLIBCXX_STD_C::set<_Key,_Compare,_Allocator>,
46 public __gnu_debug::_Safe_sequence<set<_Key, _Compare, _Allocator> >
47 {
48 typedef _GLIBCXX_STD_C::set<_Key, _Compare, _Allocator> _Base;
49
50 typedef typename _Base::const_iterator _Base_const_iterator;
51 typedef typename _Base::iterator _Base_iterator;
52 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
53 public:
54 // types:
55 typedef _Key key_type;
56 typedef _Key value_type;
57 typedef _Compare key_compare;
58 typedef _Compare value_compare;
59 typedef _Allocator allocator_type;
60 typedef typename _Base::reference reference;
61 typedef typename _Base::const_reference const_reference;
62
63 typedef __gnu_debug::_Safe_iterator<_Base_iterator, set>
64 iterator;
65 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, set>
66 const_iterator;
67
68 typedef typename _Base::size_type size_type;
69 typedef typename _Base::difference_type difference_type;
70 typedef typename _Base::pointer pointer;
71 typedef typename _Base::const_pointer const_pointer;
72 typedef std::reverse_iterator<iterator> reverse_iterator;
73 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
74
75 // 23.3.3.1 construct/copy/destroy:
76 explicit set(const _Compare& __comp = _Compare(),
77 const _Allocator& __a = _Allocator())
78 : _Base(__comp, __a) { }
79
80 template<typename _InputIterator>
81 set(_InputIterator __first, _InputIterator __last,
82 const _Compare& __comp = _Compare(),
83 const _Allocator& __a = _Allocator())
84 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
85 __last)),
86 __gnu_debug::__base(__last),
87 __comp, __a) { }
88
89 set(const set& __x)
90 : _Base(__x) { }
91
92 set(const _Base& __x)
93 : _Base(__x) { }
94
95 #ifdef __GXX_EXPERIMENTAL_CXX0X__
96 set(set&& __x)
97 noexcept(is_nothrow_copy_constructible<_Compare>::value)
98 : _Base(std::move(__x))
99 { this->_M_swap(__x); }
100
101 set(initializer_list<value_type> __l,
102 const _Compare& __comp = _Compare(),
103 const allocator_type& __a = allocator_type())
104 : _Base(__l, __comp, __a) { }
105 #endif
106
107 ~set() _GLIBCXX_NOEXCEPT { }
108
109 set&
110 operator=(const set& __x)
111 {
112 *static_cast<_Base*>(this) = __x;
113 this->_M_invalidate_all();
114 return *this;
115 }
116
117 #ifdef __GXX_EXPERIMENTAL_CXX0X__
118 set&
119 operator=(set&& __x)
120 {
121 // NB: DR 1204.
122 // NB: DR 675.
123 clear();
124 swap(__x);
125 return *this;
126 }
127
128 set&
129 operator=(initializer_list<value_type> __l)
130 {
131 this->clear();
132 this->insert(__l);
133 return *this;
134 }
135 #endif
136
137 using _Base::get_allocator;
138
139 // iterators:
140 iterator
141 begin() _GLIBCXX_NOEXCEPT
142 { return iterator(_Base::begin(), this); }
143
144 const_iterator
145 begin() const _GLIBCXX_NOEXCEPT
146 { return const_iterator(_Base::begin(), this); }
147
148 iterator
149 end() _GLIBCXX_NOEXCEPT
150 { return iterator(_Base::end(), this); }
151
152 const_iterator
153 end() const _GLIBCXX_NOEXCEPT
154 { return const_iterator(_Base::end(), this); }
155
156 reverse_iterator
157 rbegin() _GLIBCXX_NOEXCEPT
158 { return reverse_iterator(end()); }
159
160 const_reverse_iterator
161 rbegin() const _GLIBCXX_NOEXCEPT
162 { return const_reverse_iterator(end()); }
163
164 reverse_iterator
165 rend() _GLIBCXX_NOEXCEPT
166 { return reverse_iterator(begin()); }
167
168 const_reverse_iterator
169 rend() const _GLIBCXX_NOEXCEPT
170 { return const_reverse_iterator(begin()); }
171
172 #ifdef __GXX_EXPERIMENTAL_CXX0X__
173 const_iterator
174 cbegin() const noexcept
175 { return const_iterator(_Base::begin(), this); }
176
177 const_iterator
178 cend() const noexcept
179 { return const_iterator(_Base::end(), this); }
180
181 const_reverse_iterator
182 crbegin() const noexcept
183 { return const_reverse_iterator(end()); }
184
185 const_reverse_iterator
186 crend() const noexcept
187 { return const_reverse_iterator(begin()); }
188 #endif
189
190 // capacity:
191 using _Base::empty;
192 using _Base::size;
193 using _Base::max_size;
194
195 // modifiers:
196 std::pair<iterator, bool>
197 insert(const value_type& __x)
198 {
199 std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
200 return std::pair<iterator, bool>(iterator(__res.first, this),
201 __res.second);
202 }
203
204 #ifdef __GXX_EXPERIMENTAL_CXX0X__
205 std::pair<iterator, bool>
206 insert(value_type&& __x)
207 {
208 std::pair<_Base_iterator, bool> __res
209 = _Base::insert(std::move(__x));
210 return std::pair<iterator, bool>(iterator(__res.first, this),
211 __res.second);
212 }
213 #endif
214
215 iterator
216 insert(const_iterator __position, const value_type& __x)
217 {
218 __glibcxx_check_insert(__position);
219 return iterator(_Base::insert(__position.base(), __x), this);
220 }
221
222 #ifdef __GXX_EXPERIMENTAL_CXX0X__
223 iterator
224 insert(const_iterator __position, value_type&& __x)
225 {
226 __glibcxx_check_insert(__position);
227 return iterator(_Base::insert(__position.base(), std::move(__x)),
228 this);
229 }
230 #endif
231
232 template <typename _InputIterator>
233 void
234 insert(_InputIterator __first, _InputIterator __last)
235 {
236 __glibcxx_check_valid_range(__first, __last);
237 _Base::insert(__gnu_debug::__base(__first),
238 __gnu_debug::__base(__last));
239 }
240
241 #ifdef __GXX_EXPERIMENTAL_CXX0X__
242 void
243 insert(initializer_list<value_type> __l)
244 { _Base::insert(__l); }
245 #endif
246
247 #ifdef __GXX_EXPERIMENTAL_CXX0X__
248 iterator
249 erase(const_iterator __position)
250 {
251 __glibcxx_check_erase(__position);
252 this->_M_invalidate_if(_Equal(__position.base()));
253 return iterator(_Base::erase(__position.base()), this);
254 }
255 #else
256 void
257 erase(iterator __position)
258 {
259 __glibcxx_check_erase(__position);
260 this->_M_invalidate_if(_Equal(__position.base()));
261 _Base::erase(__position.base());
262 }
263 #endif
264
265 size_type
266 erase(const key_type& __x)
267 {
268 _Base_iterator __victim = _Base::find(__x);
269 if (__victim == _Base::end())
270 return 0;
271 else
272 {
273 this->_M_invalidate_if(_Equal(__victim));
274 _Base::erase(__victim);
275 return 1;
276 }
277 }
278
279 #ifdef __GXX_EXPERIMENTAL_CXX0X__
280 iterator
281 erase(const_iterator __first, const_iterator __last)
282 {
283 // _GLIBCXX_RESOLVE_LIB_DEFECTS
284 // 151. can't currently clear() empty container
285 __glibcxx_check_erase_range(__first, __last);
286 for (_Base_const_iterator __victim = __first.base();
287 __victim != __last.base(); ++__victim)
288 {
289 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
290 _M_message(__gnu_debug::__msg_valid_range)
291 ._M_iterator(__first, "first")
292 ._M_iterator(__last, "last"));
293 this->_M_invalidate_if(_Equal(__victim));
294 }
295 return iterator(_Base::erase(__first.base(), __last.base()), this);
296 }
297 #else
298 void
299 erase(iterator __first, iterator __last)
300 {
301 // _GLIBCXX_RESOLVE_LIB_DEFECTS
302 // 151. can't currently clear() empty container
303 __glibcxx_check_erase_range(__first, __last);
304 for (_Base_iterator __victim = __first.base();
305 __victim != __last.base(); ++__victim)
306 {
307 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
308 _M_message(__gnu_debug::__msg_valid_range)
309 ._M_iterator(__first, "first")
310 ._M_iterator(__last, "last"));
311 this->_M_invalidate_if(_Equal(__victim));
312 }
313 _Base::erase(__first.base(), __last.base());
314 }
315 #endif
316
317 void
318 swap(set& __x)
319 {
320 _Base::swap(__x);
321 this->_M_swap(__x);
322 }
323
324 void
325 clear() _GLIBCXX_NOEXCEPT
326 {
327 this->_M_invalidate_all();
328 _Base::clear();
329 }
330
331 // observers:
332 using _Base::key_comp;
333 using _Base::value_comp;
334
335 // set operations:
336 iterator
337 find(const key_type& __x)
338 { return iterator(_Base::find(__x), this); }
339
340 // _GLIBCXX_RESOLVE_LIB_DEFECTS
341 // 214. set::find() missing const overload
342 const_iterator
343 find(const key_type& __x) const
344 { return const_iterator(_Base::find(__x), this); }
345
346 using _Base::count;
347
348 iterator
349 lower_bound(const key_type& __x)
350 { return iterator(_Base::lower_bound(__x), this); }
351
352 // _GLIBCXX_RESOLVE_LIB_DEFECTS
353 // 214. set::find() missing const overload
354 const_iterator
355 lower_bound(const key_type& __x) const
356 { return const_iterator(_Base::lower_bound(__x), this); }
357
358 iterator
359 upper_bound(const key_type& __x)
360 { return iterator(_Base::upper_bound(__x), this); }
361
362 // _GLIBCXX_RESOLVE_LIB_DEFECTS
363 // 214. set::find() missing const overload
364 const_iterator
365 upper_bound(const key_type& __x) const
366 { return const_iterator(_Base::upper_bound(__x), this); }
367
368 std::pair<iterator,iterator>
369 equal_range(const key_type& __x)
370 {
371 std::pair<_Base_iterator, _Base_iterator> __res =
372 _Base::equal_range(__x);
373 return std::make_pair(iterator(__res.first, this),
374 iterator(__res.second, this));
375 }
376
377 // _GLIBCXX_RESOLVE_LIB_DEFECTS
378 // 214. set::find() missing const overload
379 std::pair<const_iterator,const_iterator>
380 equal_range(const key_type& __x) const
381 {
382 std::pair<_Base_iterator, _Base_iterator> __res =
383 _Base::equal_range(__x);
384 return std::make_pair(const_iterator(__res.first, this),
385 const_iterator(__res.second, this));
386 }
387
388 _Base&
389 _M_base() _GLIBCXX_NOEXCEPT { return *this; }
390
391 const _Base&
392 _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
393
394 private:
395 void
396 _M_invalidate_all()
397 {
398 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
399 this->_M_invalidate_if(_Not_equal(_M_base().end()));
400 }
401 };
402
403 template<typename _Key, typename _Compare, typename _Allocator>
404 inline bool
405 operator==(const set<_Key, _Compare, _Allocator>& __lhs,
406 const set<_Key, _Compare, _Allocator>& __rhs)
407 { return __lhs._M_base() == __rhs._M_base(); }
408
409 template<typename _Key, typename _Compare, typename _Allocator>
410 inline bool
411 operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
412 const set<_Key, _Compare, _Allocator>& __rhs)
413 { return __lhs._M_base() != __rhs._M_base(); }
414
415 template<typename _Key, typename _Compare, typename _Allocator>
416 inline bool
417 operator<(const set<_Key, _Compare, _Allocator>& __lhs,
418 const set<_Key, _Compare, _Allocator>& __rhs)
419 { return __lhs._M_base() < __rhs._M_base(); }
420
421 template<typename _Key, typename _Compare, typename _Allocator>
422 inline bool
423 operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
424 const set<_Key, _Compare, _Allocator>& __rhs)
425 { return __lhs._M_base() <= __rhs._M_base(); }
426
427 template<typename _Key, typename _Compare, typename _Allocator>
428 inline bool
429 operator>=(const set<_Key, _Compare, _Allocator>& __lhs,
430 const set<_Key, _Compare, _Allocator>& __rhs)
431 { return __lhs._M_base() >= __rhs._M_base(); }
432
433 template<typename _Key, typename _Compare, typename _Allocator>
434 inline bool
435 operator>(const set<_Key, _Compare, _Allocator>& __lhs,
436 const set<_Key, _Compare, _Allocator>& __rhs)
437 { return __lhs._M_base() > __rhs._M_base(); }
438
439 template<typename _Key, typename _Compare, typename _Allocator>
440 void
441 swap(set<_Key, _Compare, _Allocator>& __x,
442 set<_Key, _Compare, _Allocator>& __y)
443 { return __x.swap(__y); }
444
445 } // namespace __debug
446 } // namespace std
447
448 #endif
449