libstdc++
|
00001 // Debugging set implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003-2014 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** @file debug/set.h 00026 * This file is a GNU debug extension to the Standard C++ Library. 00027 */ 00028 00029 #ifndef _GLIBCXX_DEBUG_SET_H 00030 #define _GLIBCXX_DEBUG_SET_H 1 00031 00032 #include <debug/safe_sequence.h> 00033 #include <debug/safe_iterator.h> 00034 #include <utility> 00035 00036 namespace std _GLIBCXX_VISIBILITY(default) 00037 { 00038 namespace __debug 00039 { 00040 /// Class std::set with safety/checking/debug instrumentation. 00041 template<typename _Key, typename _Compare = std::less<_Key>, 00042 typename _Allocator = std::allocator<_Key> > 00043 class set 00044 : public _GLIBCXX_STD_C::set<_Key,_Compare,_Allocator>, 00045 public __gnu_debug::_Safe_sequence<set<_Key, _Compare, _Allocator> > 00046 { 00047 typedef _GLIBCXX_STD_C::set<_Key, _Compare, _Allocator> _Base; 00048 00049 typedef typename _Base::const_iterator _Base_const_iterator; 00050 typedef typename _Base::iterator _Base_iterator; 00051 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 00052 #if __cplusplus >= 201103L 00053 typedef __gnu_cxx::__alloc_traits<typename 00054 _Base::allocator_type> _Alloc_traits; 00055 #endif 00056 public: 00057 // types: 00058 typedef _Key key_type; 00059 typedef _Key value_type; 00060 typedef _Compare key_compare; 00061 typedef _Compare value_compare; 00062 typedef _Allocator allocator_type; 00063 typedef typename _Base::reference reference; 00064 typedef typename _Base::const_reference const_reference; 00065 00066 typedef __gnu_debug::_Safe_iterator<_Base_iterator, set> 00067 iterator; 00068 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, set> 00069 const_iterator; 00070 00071 typedef typename _Base::size_type size_type; 00072 typedef typename _Base::difference_type difference_type; 00073 typedef typename _Base::pointer pointer; 00074 typedef typename _Base::const_pointer const_pointer; 00075 typedef std::reverse_iterator<iterator> reverse_iterator; 00076 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00077 00078 // 23.3.3.1 construct/copy/destroy: 00079 00080 set() : _Base() { } 00081 00082 explicit set(const _Compare& __comp, 00083 const _Allocator& __a = _Allocator()) 00084 : _Base(__comp, __a) { } 00085 00086 template<typename _InputIterator> 00087 set(_InputIterator __first, _InputIterator __last, 00088 const _Compare& __comp = _Compare(), 00089 const _Allocator& __a = _Allocator()) 00090 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 00091 __last)), 00092 __gnu_debug::__base(__last), 00093 __comp, __a) { } 00094 00095 set(const set& __x) 00096 : _Base(__x) { } 00097 00098 set(const _Base& __x) 00099 : _Base(__x) { } 00100 00101 #if __cplusplus >= 201103L 00102 set(set&& __x) 00103 noexcept(is_nothrow_copy_constructible<_Compare>::value) 00104 : _Base(std::move(__x)) 00105 { this->_M_swap(__x); } 00106 00107 set(initializer_list<value_type> __l, 00108 const _Compare& __comp = _Compare(), 00109 const allocator_type& __a = allocator_type()) 00110 : _Base(__l, __comp, __a) { } 00111 00112 explicit 00113 set(const allocator_type& __a) 00114 : _Base(__a) { } 00115 00116 set(const set& __x, const allocator_type& __a) 00117 : _Base(__x, __a) { } 00118 00119 set(set&& __x, const allocator_type& __a) 00120 : _Base(std::move(__x._M_base()), __a) { } 00121 00122 set(initializer_list<value_type> __l, const allocator_type& __a) 00123 : _Base(__l, __a) 00124 { } 00125 00126 template<typename _InputIterator> 00127 set(_InputIterator __first, _InputIterator __last, 00128 const allocator_type& __a) 00129 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 00130 __last)), 00131 __gnu_debug::__base(__last), __a) 00132 { } 00133 #endif 00134 00135 ~set() _GLIBCXX_NOEXCEPT { } 00136 00137 set& 00138 operator=(const set& __x) 00139 { 00140 _M_base() = __x; 00141 this->_M_invalidate_all(); 00142 return *this; 00143 } 00144 00145 #if __cplusplus >= 201103L 00146 set& 00147 operator=(set&& __x) 00148 noexcept(_Alloc_traits::_S_nothrow_move()) 00149 { 00150 __glibcxx_check_self_move_assign(__x); 00151 bool __xfer_memory = _Alloc_traits::_S_propagate_on_move_assign() 00152 || __x.get_allocator() == this->get_allocator(); 00153 _M_base() = std::move(__x._M_base()); 00154 if (__xfer_memory) 00155 this->_M_swap(__x); 00156 else 00157 this->_M_invalidate_all(); 00158 __x._M_invalidate_all(); 00159 return *this; 00160 } 00161 00162 set& 00163 operator=(initializer_list<value_type> __l) 00164 { 00165 _M_base() = __l; 00166 this->_M_invalidate_all(); 00167 return *this; 00168 } 00169 #endif 00170 00171 using _Base::get_allocator; 00172 00173 // iterators: 00174 iterator 00175 begin() _GLIBCXX_NOEXCEPT 00176 { return iterator(_Base::begin(), this); } 00177 00178 const_iterator 00179 begin() const _GLIBCXX_NOEXCEPT 00180 { return const_iterator(_Base::begin(), this); } 00181 00182 iterator 00183 end() _GLIBCXX_NOEXCEPT 00184 { return iterator(_Base::end(), this); } 00185 00186 const_iterator 00187 end() const _GLIBCXX_NOEXCEPT 00188 { return const_iterator(_Base::end(), this); } 00189 00190 reverse_iterator 00191 rbegin() _GLIBCXX_NOEXCEPT 00192 { return reverse_iterator(end()); } 00193 00194 const_reverse_iterator 00195 rbegin() const _GLIBCXX_NOEXCEPT 00196 { return const_reverse_iterator(end()); } 00197 00198 reverse_iterator 00199 rend() _GLIBCXX_NOEXCEPT 00200 { return reverse_iterator(begin()); } 00201 00202 const_reverse_iterator 00203 rend() const _GLIBCXX_NOEXCEPT 00204 { return const_reverse_iterator(begin()); } 00205 00206 #if __cplusplus >= 201103L 00207 const_iterator 00208 cbegin() const noexcept 00209 { return const_iterator(_Base::begin(), this); } 00210 00211 const_iterator 00212 cend() const noexcept 00213 { return const_iterator(_Base::end(), this); } 00214 00215 const_reverse_iterator 00216 crbegin() const noexcept 00217 { return const_reverse_iterator(end()); } 00218 00219 const_reverse_iterator 00220 crend() const noexcept 00221 { return const_reverse_iterator(begin()); } 00222 #endif 00223 00224 // capacity: 00225 using _Base::empty; 00226 using _Base::size; 00227 using _Base::max_size; 00228 00229 // modifiers: 00230 #if __cplusplus >= 201103L 00231 template<typename... _Args> 00232 std::pair<iterator, bool> 00233 emplace(_Args&&... __args) 00234 { 00235 auto __res = _Base::emplace(std::forward<_Args>(__args)...); 00236 return std::pair<iterator, bool>(iterator(__res.first, this), 00237 __res.second); 00238 } 00239 00240 template<typename... _Args> 00241 iterator 00242 emplace_hint(const_iterator __pos, _Args&&... __args) 00243 { 00244 __glibcxx_check_insert(__pos); 00245 return iterator(_Base::emplace_hint(__pos.base(), 00246 std::forward<_Args>(__args)...), 00247 this); 00248 } 00249 #endif 00250 00251 std::pair<iterator, bool> 00252 insert(const value_type& __x) 00253 { 00254 std::pair<_Base_iterator, bool> __res = _Base::insert(__x); 00255 return std::pair<iterator, bool>(iterator(__res.first, this), 00256 __res.second); 00257 } 00258 00259 #if __cplusplus >= 201103L 00260 std::pair<iterator, bool> 00261 insert(value_type&& __x) 00262 { 00263 std::pair<_Base_iterator, bool> __res 00264 = _Base::insert(std::move(__x)); 00265 return std::pair<iterator, bool>(iterator(__res.first, this), 00266 __res.second); 00267 } 00268 #endif 00269 00270 iterator 00271 insert(const_iterator __position, const value_type& __x) 00272 { 00273 __glibcxx_check_insert(__position); 00274 return iterator(_Base::insert(__position.base(), __x), this); 00275 } 00276 00277 #if __cplusplus >= 201103L 00278 iterator 00279 insert(const_iterator __position, value_type&& __x) 00280 { 00281 __glibcxx_check_insert(__position); 00282 return iterator(_Base::insert(__position.base(), std::move(__x)), 00283 this); 00284 } 00285 #endif 00286 00287 template <typename _InputIterator> 00288 void 00289 insert(_InputIterator __first, _InputIterator __last) 00290 { 00291 __glibcxx_check_valid_range(__first, __last); 00292 _Base::insert(__gnu_debug::__base(__first), 00293 __gnu_debug::__base(__last)); 00294 } 00295 00296 #if __cplusplus >= 201103L 00297 void 00298 insert(initializer_list<value_type> __l) 00299 { _Base::insert(__l); } 00300 #endif 00301 00302 #if __cplusplus >= 201103L 00303 iterator 00304 erase(const_iterator __position) 00305 { 00306 __glibcxx_check_erase(__position); 00307 this->_M_invalidate_if(_Equal(__position.base())); 00308 return iterator(_Base::erase(__position.base()), this); 00309 } 00310 #else 00311 void 00312 erase(iterator __position) 00313 { 00314 __glibcxx_check_erase(__position); 00315 this->_M_invalidate_if(_Equal(__position.base())); 00316 _Base::erase(__position.base()); 00317 } 00318 #endif 00319 00320 size_type 00321 erase(const key_type& __x) 00322 { 00323 _Base_iterator __victim = _Base::find(__x); 00324 if (__victim == _Base::end()) 00325 return 0; 00326 else 00327 { 00328 this->_M_invalidate_if(_Equal(__victim)); 00329 _Base::erase(__victim); 00330 return 1; 00331 } 00332 } 00333 00334 #if __cplusplus >= 201103L 00335 iterator 00336 erase(const_iterator __first, const_iterator __last) 00337 { 00338 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00339 // 151. can't currently clear() empty container 00340 __glibcxx_check_erase_range(__first, __last); 00341 for (_Base_const_iterator __victim = __first.base(); 00342 __victim != __last.base(); ++__victim) 00343 { 00344 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 00345 _M_message(__gnu_debug::__msg_valid_range) 00346 ._M_iterator(__first, "first") 00347 ._M_iterator(__last, "last")); 00348 this->_M_invalidate_if(_Equal(__victim)); 00349 } 00350 return iterator(_Base::erase(__first.base(), __last.base()), this); 00351 } 00352 #else 00353 void 00354 erase(iterator __first, iterator __last) 00355 { 00356 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00357 // 151. can't currently clear() empty container 00358 __glibcxx_check_erase_range(__first, __last); 00359 for (_Base_iterator __victim = __first.base(); 00360 __victim != __last.base(); ++__victim) 00361 { 00362 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 00363 _M_message(__gnu_debug::__msg_valid_range) 00364 ._M_iterator(__first, "first") 00365 ._M_iterator(__last, "last")); 00366 this->_M_invalidate_if(_Equal(__victim)); 00367 } 00368 _Base::erase(__first.base(), __last.base()); 00369 } 00370 #endif 00371 00372 void 00373 swap(set& __x) 00374 #if __cplusplus >= 201103L 00375 noexcept(_Alloc_traits::_S_nothrow_swap()) 00376 #endif 00377 { 00378 #if __cplusplus >= 201103L 00379 if (!_Alloc_traits::_S_propagate_on_swap()) 00380 __glibcxx_check_equal_allocs(__x); 00381 #endif 00382 _Base::swap(__x); 00383 this->_M_swap(__x); 00384 } 00385 00386 void 00387 clear() _GLIBCXX_NOEXCEPT 00388 { 00389 this->_M_invalidate_all(); 00390 _Base::clear(); 00391 } 00392 00393 // observers: 00394 using _Base::key_comp; 00395 using _Base::value_comp; 00396 00397 // set operations: 00398 iterator 00399 find(const key_type& __x) 00400 { return iterator(_Base::find(__x), this); } 00401 00402 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00403 // 214. set::find() missing const overload 00404 const_iterator 00405 find(const key_type& __x) const 00406 { return const_iterator(_Base::find(__x), this); } 00407 00408 using _Base::count; 00409 00410 iterator 00411 lower_bound(const key_type& __x) 00412 { return iterator(_Base::lower_bound(__x), this); } 00413 00414 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00415 // 214. set::find() missing const overload 00416 const_iterator 00417 lower_bound(const key_type& __x) const 00418 { return const_iterator(_Base::lower_bound(__x), this); } 00419 00420 iterator 00421 upper_bound(const key_type& __x) 00422 { return iterator(_Base::upper_bound(__x), this); } 00423 00424 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00425 // 214. set::find() missing const overload 00426 const_iterator 00427 upper_bound(const key_type& __x) const 00428 { return const_iterator(_Base::upper_bound(__x), this); } 00429 00430 std::pair<iterator,iterator> 00431 equal_range(const key_type& __x) 00432 { 00433 std::pair<_Base_iterator, _Base_iterator> __res = 00434 _Base::equal_range(__x); 00435 return std::make_pair(iterator(__res.first, this), 00436 iterator(__res.second, this)); 00437 } 00438 00439 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00440 // 214. set::find() missing const overload 00441 std::pair<const_iterator,const_iterator> 00442 equal_range(const key_type& __x) const 00443 { 00444 std::pair<_Base_iterator, _Base_iterator> __res = 00445 _Base::equal_range(__x); 00446 return std::make_pair(const_iterator(__res.first, this), 00447 const_iterator(__res.second, this)); 00448 } 00449 00450 _Base& 00451 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 00452 00453 const _Base& 00454 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 00455 00456 private: 00457 void 00458 _M_invalidate_all() 00459 { 00460 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 00461 this->_M_invalidate_if(_Not_equal(_M_base().end())); 00462 } 00463 }; 00464 00465 template<typename _Key, typename _Compare, typename _Allocator> 00466 inline bool 00467 operator==(const set<_Key, _Compare, _Allocator>& __lhs, 00468 const set<_Key, _Compare, _Allocator>& __rhs) 00469 { return __lhs._M_base() == __rhs._M_base(); } 00470 00471 template<typename _Key, typename _Compare, typename _Allocator> 00472 inline bool 00473 operator!=(const set<_Key, _Compare, _Allocator>& __lhs, 00474 const set<_Key, _Compare, _Allocator>& __rhs) 00475 { return __lhs._M_base() != __rhs._M_base(); } 00476 00477 template<typename _Key, typename _Compare, typename _Allocator> 00478 inline bool 00479 operator<(const set<_Key, _Compare, _Allocator>& __lhs, 00480 const set<_Key, _Compare, _Allocator>& __rhs) 00481 { return __lhs._M_base() < __rhs._M_base(); } 00482 00483 template<typename _Key, typename _Compare, typename _Allocator> 00484 inline bool 00485 operator<=(const set<_Key, _Compare, _Allocator>& __lhs, 00486 const set<_Key, _Compare, _Allocator>& __rhs) 00487 { return __lhs._M_base() <= __rhs._M_base(); } 00488 00489 template<typename _Key, typename _Compare, typename _Allocator> 00490 inline bool 00491 operator>=(const set<_Key, _Compare, _Allocator>& __lhs, 00492 const set<_Key, _Compare, _Allocator>& __rhs) 00493 { return __lhs._M_base() >= __rhs._M_base(); } 00494 00495 template<typename _Key, typename _Compare, typename _Allocator> 00496 inline bool 00497 operator>(const set<_Key, _Compare, _Allocator>& __lhs, 00498 const set<_Key, _Compare, _Allocator>& __rhs) 00499 { return __lhs._M_base() > __rhs._M_base(); } 00500 00501 template<typename _Key, typename _Compare, typename _Allocator> 00502 void 00503 swap(set<_Key, _Compare, _Allocator>& __x, 00504 set<_Key, _Compare, _Allocator>& __y) 00505 { return __x.swap(__y); } 00506 00507 } // namespace __debug 00508 } // namespace std 00509 00510 #endif