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(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