libstdc++
debug/unordered_set
Go to the documentation of this file.
00001 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
00004 // Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the
00008 // terms of the GNU General Public License as published by the
00009 // Free Software Foundation; either version 3, or (at your option)
00010 // any later version.
00011 
00012 // This library is distributed in the hope that it will be useful,
00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 // GNU General Public License for more details.
00016 
00017 // Under Section 7 of GPL version 3, you are granted additional
00018 // permissions described in the GCC Runtime Library Exception, version
00019 // 3.1, as published by the Free Software Foundation.
00020 
00021 // You should have received a copy of the GNU General Public License and
00022 // a copy of the GCC Runtime Library Exception along with this program;
00023 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00024 // <http://www.gnu.org/licenses/>.
00025 
00026 /** @file debug/unordered_set
00027  *  This file is a GNU debug extension to the Standard C++ Library.
00028  */
00029 
00030 #ifndef _GLIBCXX_DEBUG_UNORDERED_SET
00031 #define _GLIBCXX_DEBUG_UNORDERED_SET 1
00032 
00033 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00034 # include <bits/c++0x_warning.h>
00035 #else
00036 # include <unordered_set>
00037 
00038 #include <debug/safe_sequence.h>
00039 #include <debug/safe_iterator.h>
00040 
00041 namespace std _GLIBCXX_VISIBILITY(default)
00042 {
00043 namespace __debug
00044 {
00045   /// Class std::unordered_set with safety/checking/debug instrumentation.
00046   template<typename _Value,
00047        typename _Hash = std::hash<_Value>,
00048        typename _Pred = std::equal_to<_Value>,
00049        typename _Alloc = std::allocator<_Value> >
00050     class unordered_set
00051     : public _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc>,
00052       public __gnu_debug::_Safe_sequence<unordered_set<_Value, _Hash,
00053                                _Pred, _Alloc> >
00054     {
00055       typedef _GLIBCXX_STD_C::unordered_set<_Value, _Hash,
00056                         _Pred, _Alloc> _Base;
00057       typedef __gnu_debug::_Safe_sequence<unordered_set> _Safe_base;
00058       typedef typename _Base::const_iterator _Base_const_iterator;
00059       typedef typename _Base::iterator _Base_iterator;
00060       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
00061 
00062     public:
00063       typedef typename _Base::size_type       size_type;
00064       typedef typename _Base::hasher          hasher;
00065       typedef typename _Base::key_equal       key_equal;
00066       typedef typename _Base::allocator_type  allocator_type;
00067 
00068       typedef typename _Base::key_type        key_type;
00069       typedef typename _Base::value_type      value_type;
00070 
00071       typedef __gnu_debug::_Safe_iterator<_Base_iterator,
00072                       unordered_set> iterator;
00073       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
00074                       unordered_set> const_iterator;
00075 
00076       explicit
00077       unordered_set(size_type __n = 10,
00078             const hasher& __hf = hasher(),
00079             const key_equal& __eql = key_equal(),
00080             const allocator_type& __a = allocator_type())
00081       : _Base(__n, __hf, __eql, __a) { }
00082 
00083       template<typename _InputIterator>
00084         unordered_set(_InputIterator __first, _InputIterator __last, 
00085               size_type __n = 0,
00086               const hasher& __hf = hasher(), 
00087               const key_equal& __eql = key_equal(), 
00088               const allocator_type& __a = allocator_type())
00089     : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
00090                                      __last)),
00091         __gnu_debug::__base(__last), __n,
00092         __hf, __eql, __a), _Safe_base() { }
00093 
00094       unordered_set(const unordered_set& __x) 
00095       : _Base(__x), _Safe_base() { }
00096 
00097       unordered_set(const _Base& __x) 
00098       : _Base(__x), _Safe_base() { }
00099 
00100       unordered_set(unordered_set&& __x) 
00101       : _Base(std::move(__x)), _Safe_base() { }
00102 
00103       unordered_set(initializer_list<value_type> __l,
00104             size_type __n = 0,
00105             const hasher& __hf = hasher(),
00106             const key_equal& __eql = key_equal(),
00107             const allocator_type& __a = allocator_type())
00108       : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
00109 
00110       unordered_set&
00111       operator=(const unordered_set& __x)
00112       {
00113     *static_cast<_Base*>(this) = __x;
00114     this->_M_invalidate_all();
00115     return *this;
00116       }
00117 
00118       unordered_set&
00119       operator=(unordered_set&& __x)
00120       {
00121     // NB: DR 1204.
00122     // NB: DR 675.
00123     clear();
00124     swap(__x);
00125     return *this;
00126       }
00127 
00128       unordered_set&
00129       operator=(initializer_list<value_type> __l)
00130       {
00131     this->clear();
00132     this->insert(__l);
00133     return *this;
00134       }
00135 
00136       void
00137       swap(unordered_set& __x)
00138       {
00139     _Base::swap(__x);
00140     _Safe_base::_M_swap(__x);
00141       }
00142 
00143       void
00144       clear()
00145       {
00146     _Base::clear();
00147     this->_M_invalidate_all();
00148       }
00149 
00150       iterator 
00151       begin()
00152       { return iterator(_Base::begin(), this); }
00153 
00154       const_iterator
00155       begin() const
00156       { return const_iterator(_Base::begin(), this); }
00157 
00158       iterator
00159       end()
00160       { return iterator(_Base::end(), this); }
00161 
00162       const_iterator
00163       end() const
00164       { return const_iterator(_Base::end(), this); }
00165 
00166       const_iterator
00167       cbegin() const
00168       { return const_iterator(_Base::begin(), this); }
00169 
00170       const_iterator
00171       cend() const
00172       { return const_iterator(_Base::end(), this); }
00173 
00174       // local versions
00175       using _Base::begin;
00176       using _Base::end;
00177       using _Base::cbegin;
00178       using _Base::cend;
00179 
00180       std::pair<iterator, bool>
00181       insert(const value_type& __obj)
00182       {
00183     typedef std::pair<_Base_iterator, bool> __pair_type;
00184     __pair_type __res = _Base::insert(__obj);
00185     return std::make_pair(iterator(__res.first, this), __res.second);
00186       }
00187 
00188       iterator
00189       insert(const_iterator __hint, const value_type& __obj)
00190       {
00191     __glibcxx_check_insert(__hint);
00192     return iterator(_Base::insert(__hint.base(), __obj), this);
00193       }
00194 
00195       std::pair<iterator, bool>
00196       insert(value_type&& __obj)
00197       {
00198     typedef std::pair<typename _Base::iterator, bool> __pair_type;
00199     __pair_type __res = _Base::insert(std::move(__obj));
00200     return std::make_pair(iterator(__res.first, this), __res.second);
00201       }
00202 
00203       iterator
00204       insert(const_iterator __hint, value_type&& __obj)
00205       {
00206     __glibcxx_check_insert(__hint);
00207     return iterator(_Base::insert(__hint.base(), std::move(__obj)), this);
00208       }
00209 
00210       void
00211       insert(std::initializer_list<value_type> __l)
00212       { _Base::insert(__l); }
00213 
00214       template<typename _InputIterator>
00215         void
00216         insert(_InputIterator __first, _InputIterator __last)
00217         {
00218       __glibcxx_check_valid_range(__first, __last);
00219       _Base::insert(__gnu_debug::__base(__first),
00220             __gnu_debug::__base(__last));
00221     }
00222 
00223       iterator
00224       find(const key_type& __key)
00225       { return iterator(_Base::find(__key), this); }
00226 
00227       const_iterator
00228       find(const key_type& __key) const
00229       { return const_iterator(_Base::find(__key), this); }
00230 
00231       std::pair<iterator, iterator>
00232       equal_range(const key_type& __key)
00233       {
00234     typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
00235     __pair_type __res = _Base::equal_range(__key);
00236     return std::make_pair(iterator(__res.first, this),
00237                   iterator(__res.second, this));
00238       }
00239 
00240       std::pair<const_iterator, const_iterator>
00241       equal_range(const key_type& __key) const
00242       {
00243     std::pair<_Base_const_iterator, _Base_const_iterator>
00244       __res = _Base::equal_range(__key);
00245     return std::make_pair(const_iterator(__res.first, this),
00246                   const_iterator(__res.second, this));
00247       }
00248 
00249       size_type
00250       erase(const key_type& __key)
00251       {
00252     size_type __ret(0);
00253     _Base_iterator __victim(_Base::find(__key));
00254     if (__victim != _Base::end())
00255       {
00256         this->_M_invalidate_if(_Equal(__victim));
00257         _Base::erase(__victim);
00258         __ret = 1;
00259       }
00260     return __ret;
00261       }
00262 
00263       iterator
00264       erase(const_iterator __it)
00265       {
00266     __glibcxx_check_erase(__it);
00267     this->_M_invalidate_if(_Equal(__it.base()));
00268     return iterator(_Base::erase(__it.base()), this);
00269       }
00270 
00271       iterator
00272       erase(iterator __it)
00273       { return erase(const_iterator(__it)); }
00274 
00275       iterator
00276       erase(const_iterator __first, const_iterator __last)
00277       {
00278     __glibcxx_check_erase_range(__first, __last);
00279     for (_Base_const_iterator __tmp = __first.base();
00280          __tmp != __last.base(); ++__tmp)
00281       {
00282         _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
00283                   _M_message(__gnu_debug::__msg_valid_range)
00284                   ._M_iterator(__first, "first")
00285                   ._M_iterator(__last, "last"));
00286         this->_M_invalidate_if(_Equal(__tmp));
00287       }
00288     return iterator(_Base::erase(__first.base(),
00289                      __last.base()), this);
00290       }
00291 
00292       _Base&
00293       _M_base() { return *this; }
00294 
00295       const _Base&
00296       _M_base() const { return *this; }
00297 
00298     private:
00299       void
00300       _M_invalidate_all()
00301       {
00302     typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00303     this->_M_invalidate_if(_Not_equal(_Base::end()));
00304       }
00305     };
00306 
00307   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00308     inline void
00309     swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00310      unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00311     { __x.swap(__y); }
00312 
00313   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00314     inline bool
00315     operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00316            const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00317     { return __x._M_equal(__y); }
00318 
00319   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00320     inline bool
00321     operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00322            const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00323     { return !(__x == __y); }
00324 
00325 
00326   /// Class std::unordered_multiset with safety/checking/debug instrumentation.
00327   template<typename _Value,
00328        typename _Hash = std::hash<_Value>,
00329        typename _Pred = std::equal_to<_Value>,
00330        typename _Alloc = std::allocator<_Value> >
00331     class unordered_multiset
00332     : public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>,
00333       public __gnu_debug::_Safe_sequence<unordered_multiset<_Value, _Hash,
00334                                 _Pred, _Alloc> >
00335     {
00336       typedef _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash,
00337                          _Pred, _Alloc> _Base;
00338       typedef __gnu_debug::_Safe_sequence<unordered_multiset> _Safe_base;
00339       typedef typename _Base::const_iterator _Base_const_iterator;
00340       typedef typename _Base::iterator _Base_iterator;
00341       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
00342 
00343     public:
00344       typedef typename _Base::size_type       size_type;
00345       typedef typename _Base::hasher          hasher;
00346       typedef typename _Base::key_equal       key_equal;
00347       typedef typename _Base::allocator_type  allocator_type;
00348 
00349       typedef typename _Base::key_type        key_type;
00350       typedef typename _Base::value_type      value_type;
00351 
00352       typedef __gnu_debug::_Safe_iterator<_Base_iterator,
00353                       unordered_multiset> iterator;
00354       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
00355                       unordered_multiset> const_iterator;
00356 
00357       explicit
00358       unordered_multiset(size_type __n = 10,
00359              const hasher& __hf = hasher(),
00360              const key_equal& __eql = key_equal(),
00361              const allocator_type& __a = allocator_type())
00362       : _Base(__n, __hf, __eql, __a) { }
00363 
00364       template<typename _InputIterator>
00365         unordered_multiset(_InputIterator __first, _InputIterator __last, 
00366                size_type __n = 0,
00367                const hasher& __hf = hasher(), 
00368                const key_equal& __eql = key_equal(), 
00369                const allocator_type& __a = allocator_type())
00370     : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
00371                                      __last)),
00372         __gnu_debug::__base(__last), __n,
00373         __hf, __eql, __a), _Safe_base() { }
00374 
00375       unordered_multiset(const unordered_multiset& __x) 
00376       : _Base(__x), _Safe_base() { }
00377 
00378       unordered_multiset(const _Base& __x) 
00379       : _Base(__x), _Safe_base() { }
00380 
00381       unordered_multiset(unordered_multiset&& __x) 
00382       : _Base(std::move(__x)), _Safe_base() { }
00383 
00384       unordered_multiset(initializer_list<value_type> __l,
00385              size_type __n = 0,
00386              const hasher& __hf = hasher(),
00387              const key_equal& __eql = key_equal(),
00388              const allocator_type& __a = allocator_type())
00389       : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
00390 
00391       unordered_multiset&
00392       operator=(const unordered_multiset& __x)
00393       {
00394     *static_cast<_Base*>(this) = __x;
00395     this->_M_invalidate_all();
00396     return *this;
00397       }
00398 
00399       unordered_multiset&
00400       operator=(unordered_multiset&& __x)
00401       {
00402     // NB: DR 1204.
00403         // NB: DR 675.
00404     clear();
00405     swap(__x);
00406     return *this;
00407       }
00408 
00409       unordered_multiset&
00410       operator=(initializer_list<value_type> __l)
00411       {
00412     this->clear();
00413     this->insert(__l);
00414     return *this;
00415       }
00416 
00417       void
00418       swap(unordered_multiset& __x)
00419       {
00420     _Base::swap(__x);
00421     _Safe_base::_M_swap(__x);
00422       }
00423 
00424       void
00425       clear()
00426       {
00427     _Base::clear();
00428     this->_M_invalidate_all();
00429       }
00430 
00431       iterator
00432       begin()
00433       { return iterator(_Base::begin(), this); }
00434 
00435       const_iterator
00436       begin() const
00437       { return const_iterator(_Base::begin(), this); }
00438 
00439       iterator
00440       end()
00441       { return iterator(_Base::end(), this); }
00442 
00443       const_iterator
00444       end() const
00445       { return const_iterator(_Base::end(), this); }
00446 
00447       const_iterator
00448       cbegin() const
00449       { return const_iterator(_Base::begin(), this); }
00450 
00451       const_iterator
00452       cend() const
00453       { return const_iterator(_Base::end(), this); }
00454 
00455       // local versions
00456       using _Base::begin;
00457       using _Base::end;
00458       using _Base::cbegin;
00459       using _Base::cend;
00460 
00461       iterator
00462       insert(const value_type& __obj)
00463       { return iterator(_Base::insert(__obj), this); }
00464 
00465       iterator
00466       insert(const_iterator __hint, const value_type& __obj)
00467       {
00468     __glibcxx_check_insert(__hint);
00469     return iterator(_Base::insert(__hint.base(), __obj), this);
00470       }
00471 
00472       iterator
00473       insert(value_type&& __obj)
00474       { return iterator(_Base::insert(std::move(__obj)), this); }
00475 
00476       iterator
00477       insert(const_iterator __hint, value_type&& __obj)
00478       {
00479     __glibcxx_check_insert(__hint);
00480     return iterator(_Base::insert(__hint.base(), std::move(__obj)), this);
00481       }
00482 
00483       void
00484       insert(std::initializer_list<value_type> __l)
00485       { _Base::insert(__l); }
00486 
00487       template<typename _InputIterator>
00488         void
00489         insert(_InputIterator __first, _InputIterator __last)
00490         {
00491       __glibcxx_check_valid_range(__first, __last);
00492       _Base::insert(__gnu_debug::__base(__first),
00493             __gnu_debug::__base(__last));
00494     }
00495 
00496       iterator
00497       find(const key_type& __key)
00498       { return iterator(_Base::find(__key), this); }
00499 
00500       const_iterator
00501       find(const key_type& __key) const
00502       { return const_iterator(_Base::find(__key), this); }
00503 
00504       std::pair<iterator, iterator>
00505       equal_range(const key_type& __key)
00506       {
00507     typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
00508     __pair_type __res = _Base::equal_range(__key);
00509     return std::make_pair(iterator(__res.first, this),
00510                   iterator(__res.second, this));
00511       }
00512 
00513       std::pair<const_iterator, const_iterator>
00514       equal_range(const key_type& __key) const
00515       {
00516     std::pair<_Base_const_iterator, _Base_const_iterator>
00517       __res = _Base::equal_range(__key);
00518     return std::make_pair(const_iterator(__res.first, this),
00519                   const_iterator(__res.second, this));
00520       }
00521 
00522       size_type
00523       erase(const key_type& __key)
00524       {
00525     size_type __ret(0);
00526     std::pair<_Base_iterator, _Base_iterator> __pair =
00527       _Base::equal_range(__key);
00528     for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
00529       {
00530         this->_M_invalidate_if(_Equal(__victim));
00531         _Base::erase(__victim++);
00532         ++__ret;
00533       }
00534     return __ret;
00535       }
00536 
00537       iterator
00538       erase(const_iterator __it)
00539       {
00540     __glibcxx_check_erase(__it);
00541     this->_M_invalidate_if(_Equal(__it.base()));
00542     return iterator(_Base::erase(__it.base()), this);
00543       }
00544 
00545       iterator
00546       erase(iterator __it)
00547       { return erase(const_iterator(__it)); }
00548 
00549       iterator
00550       erase(const_iterator __first, const_iterator __last)
00551       {
00552     __glibcxx_check_erase_range(__first, __last);
00553     for (_Base_const_iterator __tmp = __first.base();
00554          __tmp != __last.base(); ++__tmp)
00555       {
00556         _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
00557                   _M_message(__gnu_debug::__msg_valid_range)
00558                   ._M_iterator(__first, "first")
00559                   ._M_iterator(__last, "last"));
00560         this->_M_invalidate_if(_Equal(__tmp));
00561       }
00562     return iterator(_Base::erase(__first.base(),
00563                      __last.base()), this);
00564       }
00565 
00566       _Base&
00567       _M_base() { return *this; }
00568 
00569       const _Base&
00570       _M_base() const { return *this; }
00571 
00572     private:
00573       void
00574       _M_invalidate_all()
00575       {
00576     typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00577     this->_M_invalidate_if(_Not_equal(_Base::end()));
00578       }
00579     };
00580 
00581   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00582     inline void
00583     swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00584      unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00585     { __x.swap(__y); }
00586 
00587   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00588     inline bool
00589     operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00590            const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00591     { return __x._M_equal(__y); }
00592 
00593   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00594     inline bool
00595     operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00596            const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00597     { return !(__x == __y); }
00598 
00599 } // namespace __debug
00600 } // namespace std
00601 
00602 #endif // __GXX_EXPERIMENTAL_CXX0X__
00603 
00604 #endif