libstdc++
|
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(const_iterator __first, const_iterator __last) 00273 { 00274 __glibcxx_check_erase_range(__first, __last); 00275 for (_Base_const_iterator __tmp = __first.base(); 00276 __tmp != __last.base(); ++__tmp) 00277 { 00278 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 00279 _M_message(__gnu_debug::__msg_valid_range) 00280 ._M_iterator(__first, "first") 00281 ._M_iterator(__last, "last")); 00282 this->_M_invalidate_if(_Equal(__tmp)); 00283 } 00284 return iterator(_Base::erase(__first.base(), 00285 __last.base()), this); 00286 } 00287 00288 _Base& 00289 _M_base() { return *this; } 00290 00291 const _Base& 00292 _M_base() const { return *this; } 00293 00294 private: 00295 void 00296 _M_invalidate_all() 00297 { 00298 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 00299 this->_M_invalidate_if(_Not_equal(_Base::end())); 00300 } 00301 }; 00302 00303 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00304 inline void 00305 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 00306 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 00307 { __x.swap(__y); } 00308 00309 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00310 inline bool 00311 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 00312 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 00313 { return __x._M_equal(__y); } 00314 00315 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00316 inline bool 00317 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 00318 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 00319 { return !(__x == __y); } 00320 00321 00322 /// Class std::unordered_multiset with safety/checking/debug instrumentation. 00323 template<typename _Value, 00324 typename _Hash = std::hash<_Value>, 00325 typename _Pred = std::equal_to<_Value>, 00326 typename _Alloc = std::allocator<_Value> > 00327 class unordered_multiset 00328 : public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>, 00329 public __gnu_debug::_Safe_sequence<unordered_multiset<_Value, _Hash, 00330 _Pred, _Alloc> > 00331 { 00332 typedef _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, 00333 _Pred, _Alloc> _Base; 00334 typedef __gnu_debug::_Safe_sequence<unordered_multiset> _Safe_base; 00335 typedef typename _Base::const_iterator _Base_const_iterator; 00336 typedef typename _Base::iterator _Base_iterator; 00337 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 00338 00339 public: 00340 typedef typename _Base::size_type size_type; 00341 typedef typename _Base::hasher hasher; 00342 typedef typename _Base::key_equal key_equal; 00343 typedef typename _Base::allocator_type allocator_type; 00344 00345 typedef typename _Base::key_type key_type; 00346 typedef typename _Base::value_type value_type; 00347 00348 typedef __gnu_debug::_Safe_iterator<_Base_iterator, 00349 unordered_multiset> iterator; 00350 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, 00351 unordered_multiset> const_iterator; 00352 00353 explicit 00354 unordered_multiset(size_type __n = 10, 00355 const hasher& __hf = hasher(), 00356 const key_equal& __eql = key_equal(), 00357 const allocator_type& __a = allocator_type()) 00358 : _Base(__n, __hf, __eql, __a) { } 00359 00360 template<typename _InputIterator> 00361 unordered_multiset(_InputIterator __first, _InputIterator __last, 00362 size_type __n = 0, 00363 const hasher& __hf = hasher(), 00364 const key_equal& __eql = key_equal(), 00365 const allocator_type& __a = allocator_type()) 00366 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 00367 __last)), 00368 __gnu_debug::__base(__last), __n, 00369 __hf, __eql, __a), _Safe_base() { } 00370 00371 unordered_multiset(const unordered_multiset& __x) 00372 : _Base(__x), _Safe_base() { } 00373 00374 unordered_multiset(const _Base& __x) 00375 : _Base(__x), _Safe_base() { } 00376 00377 unordered_multiset(unordered_multiset&& __x) 00378 : _Base(std::move(__x)), _Safe_base() { } 00379 00380 unordered_multiset(initializer_list<value_type> __l, 00381 size_type __n = 0, 00382 const hasher& __hf = hasher(), 00383 const key_equal& __eql = key_equal(), 00384 const allocator_type& __a = allocator_type()) 00385 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { } 00386 00387 unordered_multiset& 00388 operator=(const unordered_multiset& __x) 00389 { 00390 *static_cast<_Base*>(this) = __x; 00391 this->_M_invalidate_all(); 00392 return *this; 00393 } 00394 00395 unordered_multiset& 00396 operator=(unordered_multiset&& __x) 00397 { 00398 // NB: DR 1204. 00399 // NB: DR 675. 00400 clear(); 00401 swap(__x); 00402 return *this; 00403 } 00404 00405 unordered_multiset& 00406 operator=(initializer_list<value_type> __l) 00407 { 00408 this->clear(); 00409 this->insert(__l); 00410 return *this; 00411 } 00412 00413 void 00414 swap(unordered_multiset& __x) 00415 { 00416 _Base::swap(__x); 00417 _Safe_base::_M_swap(__x); 00418 } 00419 00420 void 00421 clear() 00422 { 00423 _Base::clear(); 00424 this->_M_invalidate_all(); 00425 } 00426 00427 iterator 00428 begin() 00429 { return iterator(_Base::begin(), this); } 00430 00431 const_iterator 00432 begin() const 00433 { return const_iterator(_Base::begin(), this); } 00434 00435 iterator 00436 end() 00437 { return iterator(_Base::end(), this); } 00438 00439 const_iterator 00440 end() const 00441 { return const_iterator(_Base::end(), this); } 00442 00443 const_iterator 00444 cbegin() const 00445 { return const_iterator(_Base::begin(), this); } 00446 00447 const_iterator 00448 cend() const 00449 { return const_iterator(_Base::end(), this); } 00450 00451 // local versions 00452 using _Base::begin; 00453 using _Base::end; 00454 using _Base::cbegin; 00455 using _Base::cend; 00456 00457 iterator 00458 insert(const value_type& __obj) 00459 { return iterator(_Base::insert(__obj), this); } 00460 00461 iterator 00462 insert(const_iterator __hint, const value_type& __obj) 00463 { 00464 __glibcxx_check_insert(__hint); 00465 return iterator(_Base::insert(__hint.base(), __obj), this); 00466 } 00467 00468 iterator 00469 insert(value_type&& __obj) 00470 { return iterator(_Base::insert(std::move(__obj)), this); } 00471 00472 iterator 00473 insert(const_iterator __hint, value_type&& __obj) 00474 { 00475 __glibcxx_check_insert(__hint); 00476 return iterator(_Base::insert(__hint.base(), std::move(__obj)), this); 00477 } 00478 00479 void 00480 insert(std::initializer_list<value_type> __l) 00481 { _Base::insert(__l); } 00482 00483 template<typename _InputIterator> 00484 void 00485 insert(_InputIterator __first, _InputIterator __last) 00486 { 00487 __glibcxx_check_valid_range(__first, __last); 00488 _Base::insert(__gnu_debug::__base(__first), 00489 __gnu_debug::__base(__last)); 00490 } 00491 00492 iterator 00493 find(const key_type& __key) 00494 { return iterator(_Base::find(__key), this); } 00495 00496 const_iterator 00497 find(const key_type& __key) const 00498 { return const_iterator(_Base::find(__key), this); } 00499 00500 std::pair<iterator, iterator> 00501 equal_range(const key_type& __key) 00502 { 00503 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; 00504 __pair_type __res = _Base::equal_range(__key); 00505 return std::make_pair(iterator(__res.first, this), 00506 iterator(__res.second, this)); 00507 } 00508 00509 std::pair<const_iterator, const_iterator> 00510 equal_range(const key_type& __key) const 00511 { 00512 std::pair<_Base_const_iterator, _Base_const_iterator> 00513 __res = _Base::equal_range(__key); 00514 return std::make_pair(const_iterator(__res.first, this), 00515 const_iterator(__res.second, this)); 00516 } 00517 00518 size_type 00519 erase(const key_type& __key) 00520 { 00521 size_type __ret(0); 00522 std::pair<_Base_iterator, _Base_iterator> __pair = 00523 _Base::equal_range(__key); 00524 for (_Base_iterator __victim = __pair.first; __victim != __pair.second;) 00525 { 00526 this->_M_invalidate_if(_Equal(__victim)); 00527 _Base::erase(__victim++); 00528 ++__ret; 00529 } 00530 return __ret; 00531 } 00532 00533 iterator 00534 erase(const_iterator __it) 00535 { 00536 __glibcxx_check_erase(__it); 00537 this->_M_invalidate_if(_Equal(__it.base())); 00538 return iterator(_Base::erase(__it.base()), this); 00539 } 00540 00541 iterator 00542 erase(const_iterator __first, const_iterator __last) 00543 { 00544 __glibcxx_check_erase_range(__first, __last); 00545 for (_Base_const_iterator __tmp = __first.base(); 00546 __tmp != __last.base(); ++__tmp) 00547 { 00548 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 00549 _M_message(__gnu_debug::__msg_valid_range) 00550 ._M_iterator(__first, "first") 00551 ._M_iterator(__last, "last")); 00552 this->_M_invalidate_if(_Equal(__tmp)); 00553 } 00554 return iterator(_Base::erase(__first.base(), 00555 __last.base()), this); 00556 } 00557 00558 _Base& 00559 _M_base() { return *this; } 00560 00561 const _Base& 00562 _M_base() const { return *this; } 00563 00564 private: 00565 void 00566 _M_invalidate_all() 00567 { 00568 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 00569 this->_M_invalidate_if(_Not_equal(_Base::end())); 00570 } 00571 }; 00572 00573 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00574 inline void 00575 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 00576 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 00577 { __x.swap(__y); } 00578 00579 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00580 inline bool 00581 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 00582 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 00583 { return __x._M_equal(__y); } 00584 00585 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00586 inline bool 00587 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 00588 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 00589 { return !(__x == __y); } 00590 00591 } // namespace __debug 00592 } // namespace std 00593 00594 #endif // __GXX_EXPERIMENTAL_CXX0X__ 00595 00596 #endif