libstdc++
|
00001 // Debugging set implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003-2013 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 public: 00053 // types: 00054 typedef _Key key_type; 00055 typedef _Key value_type; 00056 typedef _Compare key_compare; 00057 typedef _Compare value_compare; 00058 typedef _Allocator allocator_type; 00059 typedef typename _Base::reference reference; 00060 typedef typename _Base::const_reference const_reference; 00061 00062 typedef __gnu_debug::_Safe_iterator<_Base_iterator, set> 00063 iterator; 00064 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, set> 00065 const_iterator; 00066 00067 typedef typename _Base::size_type size_type; 00068 typedef typename _Base::difference_type difference_type; 00069 typedef typename _Base::pointer pointer; 00070 typedef typename _Base::const_pointer const_pointer; 00071 typedef std::reverse_iterator<iterator> reverse_iterator; 00072 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00073 00074 // 23.3.3.1 construct/copy/destroy: 00075 explicit set(const _Compare& __comp = _Compare(), 00076 const _Allocator& __a = _Allocator()) 00077 : _Base(__comp, __a) { } 00078 00079 template<typename _InputIterator> 00080 set(_InputIterator __first, _InputIterator __last, 00081 const _Compare& __comp = _Compare(), 00082 const _Allocator& __a = _Allocator()) 00083 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 00084 __last)), 00085 __gnu_debug::__base(__last), 00086 __comp, __a) { } 00087 00088 set(const set& __x) 00089 : _Base(__x) { } 00090 00091 set(const _Base& __x) 00092 : _Base(__x) { } 00093 00094 #if __cplusplus >= 201103L 00095 set(set&& __x) 00096 noexcept(is_nothrow_copy_constructible<_Compare>::value) 00097 : _Base(std::move(__x)) 00098 { this->_M_swap(__x); } 00099 00100 set(initializer_list<value_type> __l, 00101 const _Compare& __comp = _Compare(), 00102 const allocator_type& __a = allocator_type()) 00103 : _Base(__l, __comp, __a) { } 00104 #endif 00105 00106 ~set() _GLIBCXX_NOEXCEPT { } 00107 00108 set& 00109 operator=(const set& __x) 00110 { 00111 *static_cast<_Base*>(this) = __x; 00112 this->_M_invalidate_all(); 00113 return *this; 00114 } 00115 00116 #if __cplusplus >= 201103L 00117 set& 00118 operator=(set&& __x) 00119 { 00120 // NB: DR 1204. 00121 // NB: DR 675. 00122 __glibcxx_check_self_move_assign(__x); 00123 clear(); 00124 swap(__x); 00125 return *this; 00126 } 00127 00128 set& 00129 operator=(initializer_list<value_type> __l) 00130 { 00131 this->clear(); 00132 this->insert(__l); 00133 return *this; 00134 } 00135 #endif 00136 00137 using _Base::get_allocator; 00138 00139 // iterators: 00140 iterator 00141 begin() _GLIBCXX_NOEXCEPT 00142 { return iterator(_Base::begin(), this); } 00143 00144 const_iterator 00145 begin() const _GLIBCXX_NOEXCEPT 00146 { return const_iterator(_Base::begin(), this); } 00147 00148 iterator 00149 end() _GLIBCXX_NOEXCEPT 00150 { return iterator(_Base::end(), this); } 00151 00152 const_iterator 00153 end() const _GLIBCXX_NOEXCEPT 00154 { return const_iterator(_Base::end(), this); } 00155 00156 reverse_iterator 00157 rbegin() _GLIBCXX_NOEXCEPT 00158 { return reverse_iterator(end()); } 00159 00160 const_reverse_iterator 00161 rbegin() const _GLIBCXX_NOEXCEPT 00162 { return const_reverse_iterator(end()); } 00163 00164 reverse_iterator 00165 rend() _GLIBCXX_NOEXCEPT 00166 { return reverse_iterator(begin()); } 00167 00168 const_reverse_iterator 00169 rend() const _GLIBCXX_NOEXCEPT 00170 { return const_reverse_iterator(begin()); } 00171 00172 #if __cplusplus >= 201103L 00173 const_iterator 00174 cbegin() const noexcept 00175 { return const_iterator(_Base::begin(), this); } 00176 00177 const_iterator 00178 cend() const noexcept 00179 { return const_iterator(_Base::end(), this); } 00180 00181 const_reverse_iterator 00182 crbegin() const noexcept 00183 { return const_reverse_iterator(end()); } 00184 00185 const_reverse_iterator 00186 crend() const noexcept 00187 { return const_reverse_iterator(begin()); } 00188 #endif 00189 00190 // capacity: 00191 using _Base::empty; 00192 using _Base::size; 00193 using _Base::max_size; 00194 00195 // modifiers: 00196 #if __cplusplus >= 201103L 00197 template<typename... _Args> 00198 std::pair<iterator, bool> 00199 emplace(_Args&&... __args) 00200 { 00201 auto __res = _Base::emplace(std::forward<_Args>(__args)...); 00202 return std::pair<iterator, bool>(iterator(__res.first, this), 00203 __res.second); 00204 } 00205 00206 template<typename... _Args> 00207 iterator 00208 emplace_hint(const_iterator __pos, _Args&&... __args) 00209 { 00210 __glibcxx_check_insert(__pos); 00211 return iterator(_Base::emplace_hint(__pos.base(), 00212 std::forward<_Args>(__args)...), 00213 this); 00214 } 00215 #endif 00216 00217 std::pair<iterator, bool> 00218 insert(const value_type& __x) 00219 { 00220 std::pair<_Base_iterator, bool> __res = _Base::insert(__x); 00221 return std::pair<iterator, bool>(iterator(__res.first, this), 00222 __res.second); 00223 } 00224 00225 #if __cplusplus >= 201103L 00226 std::pair<iterator, bool> 00227 insert(value_type&& __x) 00228 { 00229 std::pair<_Base_iterator, bool> __res 00230 = _Base::insert(std::move(__x)); 00231 return std::pair<iterator, bool>(iterator(__res.first, this), 00232 __res.second); 00233 } 00234 #endif 00235 00236 iterator 00237 insert(const_iterator __position, const value_type& __x) 00238 { 00239 __glibcxx_check_insert(__position); 00240 return iterator(_Base::insert(__position.base(), __x), this); 00241 } 00242 00243 #if __cplusplus >= 201103L 00244 iterator 00245 insert(const_iterator __position, value_type&& __x) 00246 { 00247 __glibcxx_check_insert(__position); 00248 return iterator(_Base::insert(__position.base(), std::move(__x)), 00249 this); 00250 } 00251 #endif 00252 00253 template <typename _InputIterator> 00254 void 00255 insert(_InputIterator __first, _InputIterator __last) 00256 { 00257 __glibcxx_check_valid_range(__first, __last); 00258 _Base::insert(__gnu_debug::__base(__first), 00259 __gnu_debug::__base(__last)); 00260 } 00261 00262 #if __cplusplus >= 201103L 00263 void 00264 insert(initializer_list<value_type> __l) 00265 { _Base::insert(__l); } 00266 #endif 00267 00268 #if __cplusplus >= 201103L 00269 iterator 00270 erase(const_iterator __position) 00271 { 00272 __glibcxx_check_erase(__position); 00273 this->_M_invalidate_if(_Equal(__position.base())); 00274 return iterator(_Base::erase(__position.base()), this); 00275 } 00276 #else 00277 void 00278 erase(iterator __position) 00279 { 00280 __glibcxx_check_erase(__position); 00281 this->_M_invalidate_if(_Equal(__position.base())); 00282 _Base::erase(__position.base()); 00283 } 00284 #endif 00285 00286 size_type 00287 erase(const key_type& __x) 00288 { 00289 _Base_iterator __victim = _Base::find(__x); 00290 if (__victim == _Base::end()) 00291 return 0; 00292 else 00293 { 00294 this->_M_invalidate_if(_Equal(__victim)); 00295 _Base::erase(__victim); 00296 return 1; 00297 } 00298 } 00299 00300 #if __cplusplus >= 201103L 00301 iterator 00302 erase(const_iterator __first, const_iterator __last) 00303 { 00304 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00305 // 151. can't currently clear() empty container 00306 __glibcxx_check_erase_range(__first, __last); 00307 for (_Base_const_iterator __victim = __first.base(); 00308 __victim != __last.base(); ++__victim) 00309 { 00310 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 00311 _M_message(__gnu_debug::__msg_valid_range) 00312 ._M_iterator(__first, "first") 00313 ._M_iterator(__last, "last")); 00314 this->_M_invalidate_if(_Equal(__victim)); 00315 } 00316 return iterator(_Base::erase(__first.base(), __last.base()), this); 00317 } 00318 #else 00319 void 00320 erase(iterator __first, iterator __last) 00321 { 00322 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00323 // 151. can't currently clear() empty container 00324 __glibcxx_check_erase_range(__first, __last); 00325 for (_Base_iterator __victim = __first.base(); 00326 __victim != __last.base(); ++__victim) 00327 { 00328 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 00329 _M_message(__gnu_debug::__msg_valid_range) 00330 ._M_iterator(__first, "first") 00331 ._M_iterator(__last, "last")); 00332 this->_M_invalidate_if(_Equal(__victim)); 00333 } 00334 _Base::erase(__first.base(), __last.base()); 00335 } 00336 #endif 00337 00338 void 00339 swap(set& __x) 00340 { 00341 _Base::swap(__x); 00342 this->_M_swap(__x); 00343 } 00344 00345 void 00346 clear() _GLIBCXX_NOEXCEPT 00347 { 00348 this->_M_invalidate_all(); 00349 _Base::clear(); 00350 } 00351 00352 // observers: 00353 using _Base::key_comp; 00354 using _Base::value_comp; 00355 00356 // set operations: 00357 iterator 00358 find(const key_type& __x) 00359 { return iterator(_Base::find(__x), this); } 00360 00361 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00362 // 214. set::find() missing const overload 00363 const_iterator 00364 find(const key_type& __x) const 00365 { return const_iterator(_Base::find(__x), this); } 00366 00367 using _Base::count; 00368 00369 iterator 00370 lower_bound(const key_type& __x) 00371 { return iterator(_Base::lower_bound(__x), this); } 00372 00373 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00374 // 214. set::find() missing const overload 00375 const_iterator 00376 lower_bound(const key_type& __x) const 00377 { return const_iterator(_Base::lower_bound(__x), this); } 00378 00379 iterator 00380 upper_bound(const key_type& __x) 00381 { return iterator(_Base::upper_bound(__x), this); } 00382 00383 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00384 // 214. set::find() missing const overload 00385 const_iterator 00386 upper_bound(const key_type& __x) const 00387 { return const_iterator(_Base::upper_bound(__x), this); } 00388 00389 std::pair<iterator,iterator> 00390 equal_range(const key_type& __x) 00391 { 00392 std::pair<_Base_iterator, _Base_iterator> __res = 00393 _Base::equal_range(__x); 00394 return std::make_pair(iterator(__res.first, this), 00395 iterator(__res.second, this)); 00396 } 00397 00398 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00399 // 214. set::find() missing const overload 00400 std::pair<const_iterator,const_iterator> 00401 equal_range(const key_type& __x) const 00402 { 00403 std::pair<_Base_iterator, _Base_iterator> __res = 00404 _Base::equal_range(__x); 00405 return std::make_pair(const_iterator(__res.first, this), 00406 const_iterator(__res.second, this)); 00407 } 00408 00409 _Base& 00410 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 00411 00412 const _Base& 00413 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 00414 00415 private: 00416 void 00417 _M_invalidate_all() 00418 { 00419 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 00420 this->_M_invalidate_if(_Not_equal(_M_base().end())); 00421 } 00422 }; 00423 00424 template<typename _Key, typename _Compare, typename _Allocator> 00425 inline bool 00426 operator==(const set<_Key, _Compare, _Allocator>& __lhs, 00427 const set<_Key, _Compare, _Allocator>& __rhs) 00428 { return __lhs._M_base() == __rhs._M_base(); } 00429 00430 template<typename _Key, typename _Compare, typename _Allocator> 00431 inline bool 00432 operator!=(const set<_Key, _Compare, _Allocator>& __lhs, 00433 const set<_Key, _Compare, _Allocator>& __rhs) 00434 { return __lhs._M_base() != __rhs._M_base(); } 00435 00436 template<typename _Key, typename _Compare, typename _Allocator> 00437 inline bool 00438 operator<(const set<_Key, _Compare, _Allocator>& __lhs, 00439 const set<_Key, _Compare, _Allocator>& __rhs) 00440 { return __lhs._M_base() < __rhs._M_base(); } 00441 00442 template<typename _Key, typename _Compare, typename _Allocator> 00443 inline bool 00444 operator<=(const set<_Key, _Compare, _Allocator>& __lhs, 00445 const set<_Key, _Compare, _Allocator>& __rhs) 00446 { return __lhs._M_base() <= __rhs._M_base(); } 00447 00448 template<typename _Key, typename _Compare, typename _Allocator> 00449 inline bool 00450 operator>=(const set<_Key, _Compare, _Allocator>& __lhs, 00451 const set<_Key, _Compare, _Allocator>& __rhs) 00452 { return __lhs._M_base() >= __rhs._M_base(); } 00453 00454 template<typename _Key, typename _Compare, typename _Allocator> 00455 inline bool 00456 operator>(const set<_Key, _Compare, _Allocator>& __lhs, 00457 const set<_Key, _Compare, _Allocator>& __rhs) 00458 { return __lhs._M_base() > __rhs._M_base(); } 00459 00460 template<typename _Key, typename _Compare, typename _Allocator> 00461 void 00462 swap(set<_Key, _Compare, _Allocator>& __x, 00463 set<_Key, _Compare, _Allocator>& __y) 00464 { return __x.swap(__y); } 00465 00466 } // namespace __debug 00467 } // namespace std 00468 00469 #endif