]> git.ipfire.org Git - thirdparty/gcc.git/blame - libstdc++-v3/include/debug/unordered_set
projects / thirdparty / gcc.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
hashtable.h: Fold in include/tr1_impl/hashtable.h contents.
[thirdparty/gcc.git] / libstdc++-v3 / include / debug / unordered_set
CommitLineData
e63637ea
BK		 1// Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
2
6b592ab3 3// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
e63637ea
BK		 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
748086b7 9// Free Software Foundation; either version 3, or (at your option)
e63637ea
BK		 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
748086b7
JJ		 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/>.
e63637ea
BK		 25
26/** @file debug/unordered_set
27 * This file is a GNU debug extension to the Standard C++ Library.
28 */
29
30#ifndef _GLIBCXX_DEBUG_UNORDERED_SET
31#define _GLIBCXX_DEBUG_UNORDERED_SET 1
32
33#ifdef __GXX_EXPERIMENTAL_CXX0X__
34# include <unordered_set>
35#else
ab65a4c7 36# include <bits/c++0x_warning.h>
e63637ea
BK		 37#endif
38
ced3cb9f 39#include <debug/safe_sequence.h>
e63637ea 40#include <debug/safe_iterator.h>
ced3cb9f 41#include <initializer_list>
e63637ea
BK		 42
43namespace std
44{
45namespace __debug
46{
1ceb9e06 47 /// Class std::unordered_set with safety/checking/debug instrumentation.
e63637ea 48 template<typename _Value,
ced3cb9f 49 typename _Hash = std::hash<_Value>,
e63637ea 50 typename _Pred = std::equal_to<_Value>,
ced3cb9f 51 typename _Alloc = std::allocator<_Value> >
e63637ea 52 class unordered_set
ced3cb9f
PC		 53 : public _GLIBCXX_STD_D::unordered_set<_Value, _Hash, _Pred, _Alloc>,
54 public __gnu_debug::_Safe_sequence<unordered_set<_Value, _Hash,
55 _Pred, _Alloc> >
e63637ea 56 {
ced3cb9f
PC		 57 typedef _GLIBCXX_STD_D::unordered_set<_Value, _Hash,
58 _Pred, _Alloc> _Base;
e63637ea
BK		 59 typedef __gnu_debug::_Safe_sequence<unordered_set> _Safe_base;
60
61 public:
ced3cb9f
PC		 62 typedef typename _Base::size_type size_type;
63 typedef typename _Base::hasher hasher;
64 typedef typename _Base::key_equal key_equal;
65 typedef typename _Base::allocator_type allocator_type;
66
67 typedef typename _Base::key_type key_type;
68 typedef typename _Base::value_type value_type;
69
70 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
71 unordered_set> iterator;
72 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
73 unordered_set> const_iterator;
e63637ea
BK		 74
75 explicit
76 unordered_set(size_type __n = 10,
77 const hasher& __hf = hasher(),
78 const key_equal& __eql = key_equal(),
79 const allocator_type& __a = allocator_type())
ced3cb9f 80 : _Base(__n, __hf, __eql, __a) { }
e63637ea
BK		 81
82 template<typename _InputIterator>
83 unordered_set(_InputIterator __f, _InputIterator __l,
84 size_type __n = 10,
85 const hasher& __hf = hasher(),
86 const key_equal& __eql = key_equal(),
87 const allocator_type& __a = allocator_type())
ced3cb9f
PC		 88 : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n,
89 __hf, __eql, __a), _Safe_base() { }
90
91 unordered_set(const unordered_set& __x)
92 : _Base(__x), _Safe_base() { }
93
94 unordered_set(const _Base& __x)
95 : _Base(__x), _Safe_base() { }
96
97 unordered_set(unordered_set&& __x)
98 : _Base(std::forward<unordered_set>(__x)), _Safe_base() { }
e63637ea 99
988499f4
JM		 100 unordered_set(initializer_list<value_type> __l,
101 size_type __n = 10,
102 const hasher& __hf = hasher(),
103 const key_equal& __eql = key_equal(),
104 const allocator_type& __a = allocator_type())
ced3cb9f 105 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
e63637ea 106
ced3cb9f
PC		 107 unordered_set&
108 operator=(const unordered_set& __x)
109 {
110 *static_cast<_Base*>(this) = __x;
111 this->_M_invalidate_all();
112 return *this;
113 }
69b3331e
PC		 114
115 unordered_set&
116 operator=(unordered_set&& __x)
117 {
0462fd5e
PC		 118 // NB: DR 1204.
119 // NB: DR 675.
120 clear();
121 swap(__x);
69b3331e
PC		 122 return *this;
123 }
124
988499f4
JM		 125 unordered_set&
126 operator=(initializer_list<value_type> __l)
127 {
128 this->clear();
129 this->insert(__l);
130 return *this;
131 }
132
e63637ea 133 void
ff74fd13 134 swap(unordered_set& __x)
e63637ea 135 {
ced3cb9f 136 _Base::swap(__x);
e63637ea
BK		 137 _Safe_base::_M_swap(__x);
138 }
69b3331e
PC		 139
140 void
141 clear()
142 {
143 _Base::clear();
144 this->_M_invalidate_all();
145 }
146
ced3cb9f
PC		 147 iterator
148 begin()
149 { return iterator(_Base::begin(), this); }
150
151 const_iterator
152 begin() const
153 { return const_iterator(_Base::begin(), this); }
154
155 iterator
156 end()
157 { return iterator(_Base::end(), this); }
158
159 const_iterator
160 end() const
161 { return const_iterator(_Base::end(), this); }
162
163 const_iterator
164 cbegin() const
165 { return const_iterator(_Base::begin(), this); }
166
167 const_iterator
168 cend() const
169 { return const_iterator(_Base::end(), this); }
170
171 // local versions
172 using _Base::begin;
173 using _Base::end;
174 using _Base::cbegin;
175 using _Base::cend;
176
177 std::pair<iterator, bool>
178 insert(const value_type& __obj)
179 {
180 typedef std::pair<typename _Base::iterator, bool> __pair_type;
181 __pair_type __res = _Base::insert(__obj);
182 return std::make_pair(iterator(__res.first, this), __res.second);
183 }
184
185 iterator
ced3cb9f
PC		 186 insert(const_iterator, const value_type& __obj)
187 {
188 typedef std::pair<typename _Base::iterator, bool> __pair_type;
189 __pair_type __res = _Base::insert(__obj);
3b2524b1 190 return iterator(__res.first, this);
ced3cb9f
PC		 191 }
192
193 void
194 insert(std::initializer_list<value_type> __l)
195 { _Base::insert(__l); }
196
197 template<typename _InputIterator>
198 void
199 insert(_InputIterator __first, _InputIterator __last)
200 {
201 __glibcxx_check_valid_range(__first, __last);
202 _Base::insert(__first, __last);
203 }
204
205 iterator
206 find(const key_type& __key)
207 { return iterator(_Base::find(__key), this); }
208
209 const_iterator
210 find(const key_type& __key) const
211 { return const_iterator(_Base::find(__key), this); }
212
213 std::pair<iterator, iterator>
214 equal_range(const key_type& __key)
215 {
216 typedef typename _Base::iterator _Base_iterator;
217 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
218 __pair_type __res = _Base::equal_range(__key);
219 return std::make_pair(iterator(__res.first, this),
220 iterator(__res.second, this));
221 }
222
223 std::pair<const_iterator, const_iterator>
224 equal_range(const key_type& __key) const
225 {
226 typedef typename _Base::const_iterator _Base_iterator;
227 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
228 __pair_type __res = _Base::equal_range(__key);
229 return std::make_pair(const_iterator(__res.first, this),
230 const_iterator(__res.second, this));
231 }
232
233 size_type
234 erase(const key_type& __key)
235 {
236 size_type __ret(0);
237 iterator __victim(_Base::find(__key), this);
238 if (__victim != end())
239 {
240 this->erase(__victim);
241 __ret = 1;
242 }
243 return __ret;
244 }
245
246 iterator
ced3cb9f
PC		 247 erase(const_iterator __it)
248 {
249 __glibcxx_check_erase(__it);
250 __it._M_invalidate();
3b2524b1 251 return iterator(_Base::erase(__it.base()), this);
ced3cb9f
PC		 252 }
253
254 iterator
ced3cb9f
PC		 255 erase(const_iterator __first, const_iterator __last)
256 {
257 __glibcxx_check_erase_range(__first, __last);
258 for (const_iterator __tmp = __first; __tmp != __last;)
259 {
260 const_iterator __victim = __tmp++;
261 __victim._M_invalidate();
262 }
3b2524b1
PC		 263 return iterator(_Base::erase(__first.base(),
264 __last.base()), this);
ced3cb9f
PC		 265 }
266
267 _Base&
268 _M_base() { return *this; }
269
270 const _Base&
271 _M_base() const { return *this; }
272
69b3331e
PC		 273 private:
274 void
275 _M_invalidate_all()
276 {
277 typedef typename _Base::const_iterator _Base_const_iterator;
278 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
ced3cb9f 279 this->_M_invalidate_if(_Not_equal(_M_base().end()));
69b3331e 280 }
e63637ea
BK		 281 };
282
283 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
69b3331e
PC		 284 inline void
285 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
286 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
287 { __x.swap(__y); }
e63637ea 288
e63637ea 289
1ceb9e06 290 /// Class std::unordered_multiset with safety/checking/debug instrumentation.
e63637ea 291 template<typename _Value,
ced3cb9f 292 typename _Hash = std::hash<_Value>,
e63637ea 293 typename _Pred = std::equal_to<_Value>,
ced3cb9f 294 typename _Alloc = std::allocator<_Value> >
e63637ea 295 class unordered_multiset
ced3cb9f
PC		 296 : public _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash, _Pred, _Alloc>,
297 public __gnu_debug::_Safe_sequence<unordered_multiset<_Value, _Hash,
298 _Pred, _Alloc> >
e63637ea 299 {
ced3cb9f
PC		 300 typedef _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash,
301 _Pred, _Alloc> _Base;
e63637ea
BK		 302 typedef __gnu_debug::_Safe_sequence<unordered_multiset> _Safe_base;
303
304 public:
ced3cb9f
PC		 305 typedef typename _Base::size_type size_type;
306 typedef typename _Base::hasher hasher;
307 typedef typename _Base::key_equal key_equal;
308 typedef typename _Base::allocator_type allocator_type;
309
310 typedef typename _Base::key_type key_type;
311 typedef typename _Base::value_type value_type;
312
313 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
314 unordered_multiset> iterator;
315 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
316 unordered_multiset> const_iterator;
e63637ea
BK		 317
318 explicit
319 unordered_multiset(size_type __n = 10,
ced3cb9f
PC		 320 const hasher& __hf = hasher(),
321 const key_equal& __eql = key_equal(),
322 const allocator_type& __a = allocator_type())
323 : _Base(__n, __hf, __eql, __a) { }
e63637ea
BK		 324
325 template<typename _InputIterator>
326 unordered_multiset(_InputIterator __f, _InputIterator __l,
ced3cb9f
PC		 327 size_type __n = 10,
328 const hasher& __hf = hasher(),
329 const key_equal& __eql = key_equal(),
330 const allocator_type& __a = allocator_type())
331 : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n,
332 __hf, __eql, __a), _Safe_base() { }
333
334 unordered_multiset(const unordered_multiset& __x)
335 : _Base(__x), _Safe_base() { }
336
337 unordered_multiset(const _Base& __x)
338 : _Base(__x), _Safe_base() { }
339
340 unordered_multiset(unordered_multiset&& __x)
341 : _Base(std::forward<unordered_multiset>(__x)), _Safe_base() { }
e63637ea 342
988499f4
JM		 343 unordered_multiset(initializer_list<value_type> __l,
344 size_type __n = 10,
345 const hasher& __hf = hasher(),
346 const key_equal& __eql = key_equal(),
347 const allocator_type& __a = allocator_type())
ced3cb9f 348 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
e63637ea 349
ced3cb9f
PC		 350 unordered_multiset&
351 operator=(const unordered_multiset& __x)
352 {
353 *static_cast<_Base*>(this) = __x;
354 this->_M_invalidate_all();
355 return *this;
356 }
69b3331e
PC		 357
358 unordered_multiset&
359 operator=(unordered_multiset&& __x)
360 {
0462fd5e 361 // NB: DR 1204.
69b3331e
PC		 362 // NB: DR 675.
363 clear();
364 swap(__x);
365 return *this;
366 }
367
988499f4
JM		 368 unordered_multiset&
369 operator=(initializer_list<value_type> __l)
370 {
371 this->clear();
372 this->insert(__l);
373 return *this;
374 }
375
e63637ea 376 void
ff74fd13 377 swap(unordered_multiset& __x)
e63637ea 378 {
ced3cb9f 379 _Base::swap(__x);
e63637ea
BK		 380 _Safe_base::_M_swap(__x);
381 }
69b3331e 382
ced3cb9f 383 void
69b3331e
PC		 384 clear()
385 {
386 _Base::clear();
387 this->_M_invalidate_all();
388 }
389
ced3cb9f
PC		 390 iterator
391 begin()
392 { return iterator(_Base::begin(), this); }
393
394 const_iterator
395 begin() const
396 { return const_iterator(_Base::begin(), this); }
397
398 iterator
399 end()
400 { return iterator(_Base::end(), this); }
401
402 const_iterator
403 end() const
404 { return const_iterator(_Base::end(), this); }
405
406 const_iterator
407 cbegin() const
408 { return const_iterator(_Base::begin(), this); }
409
410 const_iterator
411 cend() const
412 { return const_iterator(_Base::end(), this); }
413
414 // local versions
415 using _Base::begin;
416 using _Base::end;
417 using _Base::cbegin;
418 using _Base::cend;
419
420 iterator
421 insert(const value_type& __obj)
422 { return iterator(_Base::insert(__obj), this); }
423
424 iterator
ced3cb9f 425 insert(const_iterator, const value_type& __obj)
3b2524b1 426 { return iterator(_Base::insert(__obj), this); }
ced3cb9f
PC		 427
428 void
429 insert(std::initializer_list<value_type> __l)
430 { _Base::insert(__l); }
431
432 template<typename _InputIterator>
433 void
434 insert(_InputIterator __first, _InputIterator __last)
435 {
436 __glibcxx_check_valid_range(__first, __last);
437 _Base::insert(__first, __last);
438 }
439
440 iterator
441 find(const key_type& __key)
442 { return iterator(_Base::find(__key), this); }
443
444 const_iterator
445 find(const key_type& __key) const
446 { return const_iterator(_Base::find(__key), this); }
447
448 std::pair<iterator, iterator>
449 equal_range(const key_type& __key)
450 {
451 typedef typename _Base::iterator _Base_iterator;
452 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
453 __pair_type __res = _Base::equal_range(__key);
454 return std::make_pair(iterator(__res.first, this),
455 iterator(__res.second, this));
456 }
457
458 std::pair<const_iterator, const_iterator>
459 equal_range(const key_type& __key) const
460 {
461 typedef typename _Base::const_iterator _Base_iterator;
462 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
463 __pair_type __res = _Base::equal_range(__key);
464 return std::make_pair(const_iterator(__res.first, this),
465 const_iterator(__res.second, this));
466 }
467
468 size_type
469 erase(const key_type& __key)
470 {
471 size_type __ret(0);
472 iterator __victim(_Base::find(__key), this);
473 if (__victim != end())
474 {
475 this->erase(__victim);
476 __ret = 1;
477 }
478 return __ret;
479 }
480
481 iterator
ced3cb9f
PC		 482 erase(const_iterator __it)
483 {
484 __glibcxx_check_erase(__it);
485 __it._M_invalidate();
3b2524b1 486 return iterator(_Base::erase(__it.base()), this);
ced3cb9f
PC		 487 }
488
489 iterator
ced3cb9f
PC		 490 erase(const_iterator __first, const_iterator __last)
491 {
492 __glibcxx_check_erase_range(__first, __last);
493 for (const_iterator __tmp = __first; __tmp != __last;)
494 {
495 const_iterator __victim = __tmp++;
496 __victim._M_invalidate();
497 }
3b2524b1
PC		 498 return iterator(_Base::erase(__first.base(),
499 __last.base()), this);
ced3cb9f
PC		 500 }
501
502 _Base&
503 _M_base() { return *this; }
504
505 const _Base&
506 _M_base() const { return *this; }
507
69b3331e
PC		 508 private:
509 void
510 _M_invalidate_all()
511 {
512 typedef typename _Base::const_iterator _Base_const_iterator;
513 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
ced3cb9f 514 this->_M_invalidate_if(_Not_equal(_M_base().end()));
69b3331e 515 }
e63637ea
BK		 516 };
517
518 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
69b3331e
PC		 519 inline void
520 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
521 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
522 { __x.swap(__y); }
e63637ea 523
e63637ea
BK		 524} // namespace __debug
525} // namespace std
526
e63637ea 527#endif
Mirror of https://gcc.gnu.org/git/gcc.git