libstdc++
|
00001 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 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 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00034 # include <unordered_set> 00035 #else 00036 # include <c++0x_warning.h> 00037 #endif 00038 00039 #include <debug/safe_sequence.h> 00040 #include <debug/safe_iterator.h> 00041 #include <initializer_list> 00042 00043 namespace std 00044 { 00045 namespace __debug 00046 { 00047 template<typename _Value, 00048 typename _Hash = std::hash<_Value>, 00049 typename _Pred = std::equal_to<_Value>, 00050 typename _Alloc = std::allocator<_Value> > 00051 class unordered_set 00052 : public _GLIBCXX_STD_D::unordered_set<_Value, _Hash, _Pred, _Alloc>, 00053 public __gnu_debug::_Safe_sequence<unordered_set<_Value, _Hash, 00054 _Pred, _Alloc> > 00055 { 00056 typedef _GLIBCXX_STD_D::unordered_set<_Value, _Hash, 00057 _Pred, _Alloc> _Base; 00058 typedef __gnu_debug::_Safe_sequence<unordered_set> _Safe_base; 00059 00060 public: 00061 typedef typename _Base::size_type size_type; 00062 typedef typename _Base::hasher hasher; 00063 typedef typename _Base::key_equal key_equal; 00064 typedef typename _Base::allocator_type allocator_type; 00065 00066 typedef typename _Base::key_type key_type; 00067 typedef typename _Base::value_type value_type; 00068 00069 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, 00070 unordered_set> iterator; 00071 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, 00072 unordered_set> const_iterator; 00073 00074 explicit 00075 unordered_set(size_type __n = 10, 00076 const hasher& __hf = hasher(), 00077 const key_equal& __eql = key_equal(), 00078 const allocator_type& __a = allocator_type()) 00079 : _Base(__n, __hf, __eql, __a) { } 00080 00081 template<typename _InputIterator> 00082 unordered_set(_InputIterator __f, _InputIterator __l, 00083 size_type __n = 10, 00084 const hasher& __hf = hasher(), 00085 const key_equal& __eql = key_equal(), 00086 const allocator_type& __a = allocator_type()) 00087 : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, 00088 __hf, __eql, __a), _Safe_base() { } 00089 00090 unordered_set(const unordered_set& __x) 00091 : _Base(__x), _Safe_base() { } 00092 00093 unordered_set(const _Base& __x) 00094 : _Base(__x), _Safe_base() { } 00095 00096 unordered_set(unordered_set&& __x) 00097 : _Base(std::forward<unordered_set>(__x)), _Safe_base() { } 00098 00099 unordered_set(initializer_list<value_type> __l, 00100 size_type __n = 10, 00101 const hasher& __hf = hasher(), 00102 const key_equal& __eql = key_equal(), 00103 const allocator_type& __a = allocator_type()) 00104 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { } 00105 00106 unordered_set& 00107 operator=(const unordered_set& __x) 00108 { 00109 *static_cast<_Base*>(this) = __x; 00110 this->_M_invalidate_all(); 00111 return *this; 00112 } 00113 00114 unordered_set& 00115 operator=(unordered_set&& __x) 00116 { 00117 // NB: DR 675. 00118 clear(); 00119 swap(__x); 00120 return *this; 00121 } 00122 00123 unordered_set& 00124 operator=(initializer_list<value_type> __l) 00125 { 00126 this->clear(); 00127 this->insert(__l); 00128 return *this; 00129 } 00130 00131 void 00132 swap(unordered_set&& __x) 00133 { 00134 _Base::swap(__x); 00135 _Safe_base::_M_swap(__x); 00136 } 00137 00138 void 00139 clear() 00140 { 00141 _Base::clear(); 00142 this->_M_invalidate_all(); 00143 } 00144 00145 iterator 00146 begin() 00147 { return iterator(_Base::begin(), this); } 00148 00149 const_iterator 00150 begin() const 00151 { return const_iterator(_Base::begin(), this); } 00152 00153 iterator 00154 end() 00155 { return iterator(_Base::end(), this); } 00156 00157 const_iterator 00158 end() const 00159 { return const_iterator(_Base::end(), this); } 00160 00161 const_iterator 00162 cbegin() const 00163 { return const_iterator(_Base::begin(), this); } 00164 00165 const_iterator 00166 cend() const 00167 { return const_iterator(_Base::end(), this); } 00168 00169 // local versions 00170 using _Base::begin; 00171 using _Base::end; 00172 using _Base::cbegin; 00173 using _Base::cend; 00174 00175 std::pair<iterator, bool> 00176 insert(const value_type& __obj) 00177 { 00178 typedef std::pair<typename _Base::iterator, bool> __pair_type; 00179 __pair_type __res = _Base::insert(__obj); 00180 return std::make_pair(iterator(__res.first, this), __res.second); 00181 } 00182 00183 iterator 00184 insert(iterator, const value_type& __obj) 00185 { 00186 typedef std::pair<typename _Base::iterator, bool> __pair_type; 00187 __pair_type __res = _Base::insert(__obj); 00188 return iterator(__res.first, this); 00189 } 00190 00191 const_iterator 00192 insert(const_iterator, const value_type& __obj) 00193 { 00194 typedef std::pair<typename _Base::iterator, bool> __pair_type; 00195 __pair_type __res = _Base::insert(__obj); 00196 return const_iterator(__res.first, this); 00197 } 00198 00199 void 00200 insert(std::initializer_list<value_type> __l) 00201 { _Base::insert(__l); } 00202 00203 template<typename _InputIterator> 00204 void 00205 insert(_InputIterator __first, _InputIterator __last) 00206 { 00207 __glibcxx_check_valid_range(__first, __last); 00208 _Base::insert(__first, __last); 00209 } 00210 00211 iterator 00212 find(const key_type& __key) 00213 { return iterator(_Base::find(__key), this); } 00214 00215 const_iterator 00216 find(const key_type& __key) const 00217 { return const_iterator(_Base::find(__key), this); } 00218 00219 std::pair<iterator, iterator> 00220 equal_range(const key_type& __key) 00221 { 00222 typedef typename _Base::iterator _Base_iterator; 00223 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; 00224 __pair_type __res = _Base::equal_range(__key); 00225 return std::make_pair(iterator(__res.first, this), 00226 iterator(__res.second, this)); 00227 } 00228 00229 std::pair<const_iterator, const_iterator> 00230 equal_range(const key_type& __key) const 00231 { 00232 typedef typename _Base::const_iterator _Base_iterator; 00233 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; 00234 __pair_type __res = _Base::equal_range(__key); 00235 return std::make_pair(const_iterator(__res.first, this), 00236 const_iterator(__res.second, this)); 00237 } 00238 00239 size_type 00240 erase(const key_type& __key) 00241 { 00242 size_type __ret(0); 00243 iterator __victim(_Base::find(__key), this); 00244 if (__victim != end()) 00245 { 00246 this->erase(__victim); 00247 __ret = 1; 00248 } 00249 return __ret; 00250 } 00251 00252 iterator 00253 erase(iterator __it) 00254 { 00255 __glibcxx_check_erase(__it); 00256 __it._M_invalidate(); 00257 return iterator(_Base::erase(__it.base()), this); 00258 } 00259 00260 const_iterator 00261 erase(const_iterator __it) 00262 { 00263 __glibcxx_check_erase(__it); 00264 __it._M_invalidate(); 00265 return const_iterator(_Base::erase(__it.base()), this); 00266 } 00267 00268 iterator 00269 erase(iterator __first, iterator __last) 00270 { 00271 __glibcxx_check_erase_range(__first, __last); 00272 for (iterator __tmp = __first; __tmp != __last;) 00273 { 00274 iterator __victim = __tmp++; 00275 __victim._M_invalidate(); 00276 } 00277 return iterator(_Base::erase(__first.base(), 00278 __last.base()), this); 00279 } 00280 00281 const_iterator 00282 erase(const_iterator __first, const_iterator __last) 00283 { 00284 __glibcxx_check_erase_range(__first, __last); 00285 for (const_iterator __tmp = __first; __tmp != __last;) 00286 { 00287 const_iterator __victim = __tmp++; 00288 __victim._M_invalidate(); 00289 } 00290 return const_iterator(_Base::erase(__first.base(), 00291 __last.base()), this); 00292 } 00293 00294 _Base& 00295 _M_base() { return *this; } 00296 00297 const _Base& 00298 _M_base() const { return *this; } 00299 00300 private: 00301 void 00302 _M_invalidate_all() 00303 { 00304 typedef typename _Base::const_iterator _Base_const_iterator; 00305 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 00306 this->_M_invalidate_if(_Not_equal(_M_base().end())); 00307 } 00308 }; 00309 00310 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00311 inline void 00312 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 00313 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 00314 { __x.swap(__y); } 00315 00316 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00317 inline void 00318 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>&& __x, 00319 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 00320 { __x.swap(__y); } 00321 00322 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00323 inline void 00324 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 00325 unordered_set<_Value, _Hash, _Pred, _Alloc>&& __y) 00326 { __x.swap(__y); } 00327 00328 00329 template<typename _Value, 00330 typename _Hash = std::hash<_Value>, 00331 typename _Pred = std::equal_to<_Value>, 00332 typename _Alloc = std::allocator<_Value> > 00333 class unordered_multiset 00334 : public _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash, _Pred, _Alloc>, 00335 public __gnu_debug::_Safe_sequence<unordered_multiset<_Value, _Hash, 00336 _Pred, _Alloc> > 00337 { 00338 typedef _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash, 00339 _Pred, _Alloc> _Base; 00340 typedef __gnu_debug::_Safe_sequence<unordered_multiset> _Safe_base; 00341 00342 public: 00343 typedef typename _Base::size_type size_type; 00344 typedef typename _Base::hasher hasher; 00345 typedef typename _Base::key_equal key_equal; 00346 typedef typename _Base::allocator_type allocator_type; 00347 00348 typedef typename _Base::key_type key_type; 00349 typedef typename _Base::value_type value_type; 00350 00351 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, 00352 unordered_multiset> iterator; 00353 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, 00354 unordered_multiset> const_iterator; 00355 00356 explicit 00357 unordered_multiset(size_type __n = 10, 00358 const hasher& __hf = hasher(), 00359 const key_equal& __eql = key_equal(), 00360 const allocator_type& __a = allocator_type()) 00361 : _Base(__n, __hf, __eql, __a) { } 00362 00363 template<typename _InputIterator> 00364 unordered_multiset(_InputIterator __f, _InputIterator __l, 00365 size_type __n = 10, 00366 const hasher& __hf = hasher(), 00367 const key_equal& __eql = key_equal(), 00368 const allocator_type& __a = allocator_type()) 00369 : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, 00370 __hf, __eql, __a), _Safe_base() { } 00371 00372 unordered_multiset(const unordered_multiset& __x) 00373 : _Base(__x), _Safe_base() { } 00374 00375 unordered_multiset(const _Base& __x) 00376 : _Base(__x), _Safe_base() { } 00377 00378 unordered_multiset(unordered_multiset&& __x) 00379 : _Base(std::forward<unordered_multiset>(__x)), _Safe_base() { } 00380 00381 unordered_multiset(initializer_list<value_type> __l, 00382 size_type __n = 10, 00383 const hasher& __hf = hasher(), 00384 const key_equal& __eql = key_equal(), 00385 const allocator_type& __a = allocator_type()) 00386 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { } 00387 00388 unordered_multiset& 00389 operator=(const unordered_multiset& __x) 00390 { 00391 *static_cast<_Base*>(this) = __x; 00392 this->_M_invalidate_all(); 00393 return *this; 00394 } 00395 00396 unordered_multiset& 00397 operator=(unordered_multiset&& __x) 00398 { 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(iterator, const value_type& __obj) 00463 { return iterator(_Base::insert(__obj), this); } 00464 00465 const_iterator 00466 insert(const_iterator, const value_type& __obj) 00467 { return const_iterator(_Base::insert(__obj), this); } 00468 00469 void 00470 insert(std::initializer_list<value_type> __l) 00471 { _Base::insert(__l); } 00472 00473 template<typename _InputIterator> 00474 void 00475 insert(_InputIterator __first, _InputIterator __last) 00476 { 00477 __glibcxx_check_valid_range(__first, __last); 00478 _Base::insert(__first, __last); 00479 } 00480 00481 iterator 00482 find(const key_type& __key) 00483 { return iterator(_Base::find(__key), this); } 00484 00485 const_iterator 00486 find(const key_type& __key) const 00487 { return const_iterator(_Base::find(__key), this); } 00488 00489 std::pair<iterator, iterator> 00490 equal_range(const key_type& __key) 00491 { 00492 typedef typename _Base::iterator _Base_iterator; 00493 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; 00494 __pair_type __res = _Base::equal_range(__key); 00495 return std::make_pair(iterator(__res.first, this), 00496 iterator(__res.second, this)); 00497 } 00498 00499 std::pair<const_iterator, const_iterator> 00500 equal_range(const key_type& __key) const 00501 { 00502 typedef typename _Base::const_iterator _Base_iterator; 00503 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; 00504 __pair_type __res = _Base::equal_range(__key); 00505 return std::make_pair(const_iterator(__res.first, this), 00506 const_iterator(__res.second, this)); 00507 } 00508 00509 size_type 00510 erase(const key_type& __key) 00511 { 00512 size_type __ret(0); 00513 iterator __victim(_Base::find(__key), this); 00514 if (__victim != end()) 00515 { 00516 this->erase(__victim); 00517 __ret = 1; 00518 } 00519 return __ret; 00520 } 00521 00522 iterator 00523 erase(iterator __it) 00524 { 00525 __glibcxx_check_erase(__it); 00526 __it._M_invalidate(); 00527 return iterator(_Base::erase(__it.base()), this); 00528 } 00529 00530 const_iterator 00531 erase(const_iterator __it) 00532 { 00533 __glibcxx_check_erase(__it); 00534 __it._M_invalidate(); 00535 return const_iterator(_Base::erase(__it.base()), this); 00536 } 00537 00538 iterator 00539 erase(iterator __first, iterator __last) 00540 { 00541 __glibcxx_check_erase_range(__first, __last); 00542 for (iterator __tmp = __first; __tmp != __last;) 00543 { 00544 iterator __victim = __tmp++; 00545 __victim._M_invalidate(); 00546 } 00547 return iterator(_Base::erase(__first.base(), 00548 __last.base()), this); 00549 } 00550 00551 const_iterator 00552 erase(const_iterator __first, const_iterator __last) 00553 { 00554 __glibcxx_check_erase_range(__first, __last); 00555 for (const_iterator __tmp = __first; __tmp != __last;) 00556 { 00557 const_iterator __victim = __tmp++; 00558 __victim._M_invalidate(); 00559 } 00560 return const_iterator(_Base::erase(__first.base(), 00561 __last.base()), this); 00562 } 00563 00564 _Base& 00565 _M_base() { return *this; } 00566 00567 const _Base& 00568 _M_base() const { return *this; } 00569 00570 private: 00571 void 00572 _M_invalidate_all() 00573 { 00574 typedef typename _Base::const_iterator _Base_const_iterator; 00575 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 00576 this->_M_invalidate_if(_Not_equal(_M_base().end())); 00577 } 00578 }; 00579 00580 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00581 inline void 00582 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 00583 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 00584 { __x.swap(__y); } 00585 00586 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00587 inline void 00588 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>&& __x, 00589 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 00590 { __x.swap(__y); } 00591 00592 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00593 inline void 00594 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 00595 unordered_multiset<_Value, _Hash, _Pred, _Alloc>&& __y) 00596 { __x.swap(__y); } 00597 00598 } // namespace __debug 00599 } // namespace std 00600 00601 #endif