OSDN Git Service

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