1 // Debugging set implementation -*- C++ -*- 2 3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 4 // Free Software Foundation, Inc. 5 // 6 // This file is part of the GNU ISO C++ Library. This library is free 7 // software; you can redistribute it and/or modify it under the 8 // terms of the GNU General Public License as published by the 9 // Free Software Foundation; either version 3, or (at your option) 10 // any later version. 11 12 // This library is distributed in the hope that it will be useful, 13 // but WITHOUT ANY WARRANTY; without even the implied warranty of 14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 // GNU General Public License for more details. 16 17 // Under Section 7 of GPL version 3, you are granted additional 18 // permissions described in the GCC Runtime Library Exception, version 19 // 3.1, as published by the Free Software Foundation. 20 21 // You should have received a copy of the GNU General Public License and 22 // a copy of the GCC Runtime Library Exception along with this program; 23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24 // <http://www.gnu.org/licenses/>. 25 26 /** @file debug/set.h 27 * This file is a GNU debug extension to the Standard C++ Library. 28 */ 29 30 #ifndef _GLIBCXX_DEBUG_SET_H 31 #define _GLIBCXX_DEBUG_SET_H 1 32 33 #include <debug/safe_sequence.h> 34 #include <debug/safe_iterator.h> 35 #include <utility> 36 37 namespace std _GLIBCXX_VISIBILITY(default) 38 { 39 namespace __debug 40 { 41 /// Class std::set with safety/checking/debug instrumentation. 42 template<typename _Key, typename _Compare = std::less<_Key>, 43 typename _Allocator = std::allocator<_Key> > 44 class set 45 : public _GLIBCXX_STD_C::set<_Key,_Compare,_Allocator>, 46 public __gnu_debug::_Safe_sequence<set<_Key, _Compare, _Allocator> > 47 { 48 typedef _GLIBCXX_STD_C::set<_Key, _Compare, _Allocator> _Base; 49 50 typedef typename _Base::const_iterator _Base_const_iterator; 51 typedef typename _Base::iterator _Base_iterator; 52 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 53 public: 54 // types: 55 typedef _Key key_type; 56 typedef _Key value_type; 57 typedef _Compare key_compare; 58 typedef _Compare value_compare; 59 typedef _Allocator allocator_type; 60 typedef typename _Base::reference reference; 61 typedef typename _Base::const_reference const_reference; 62 63 typedef __gnu_debug::_Safe_iterator<_Base_iterator, set> 64 iterator; 65 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, set> 66 const_iterator; 67 68 typedef typename _Base::size_type size_type; 69 typedef typename _Base::difference_type difference_type; 70 typedef typename _Base::pointer pointer; 71 typedef typename _Base::const_pointer const_pointer; 72 typedef std::reverse_iterator<iterator> reverse_iterator; 73 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 74 75 // 23.3.3.1 construct/copy/destroy: 76 explicit set(const _Compare& __comp = _Compare(), 77 const _Allocator& __a = _Allocator()) 78 : _Base(__comp, __a) { } 79 80 template<typename _InputIterator> 81 set(_InputIterator __first, _InputIterator __last, 82 const _Compare& __comp = _Compare(), 83 const _Allocator& __a = _Allocator()) 84 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 85 __last)), 86 __gnu_debug::__base(__last), 87 __comp, __a) { } 88 89 set(const set& __x) 90 : _Base(__x) { } 91 92 set(const _Base& __x) 93 : _Base(__x) { } 94 95 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 96 set(set&& __x) 97 noexcept(is_nothrow_copy_constructible<_Compare>::value) 98 : _Base(std::move(__x)) 99 { this->_M_swap(__x); } 100 101 set(initializer_list<value_type> __l, 102 const _Compare& __comp = _Compare(), 103 const allocator_type& __a = allocator_type()) 104 : _Base(__l, __comp, __a) { } 105 #endif 106 107 ~set() _GLIBCXX_NOEXCEPT { } 108 109 set& 110 operator=(const set& __x) 111 { 112 *static_cast<_Base*>(this) = __x; 113 this->_M_invalidate_all(); 114 return *this; 115 } 116 117 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 118 set& 119 operator=(set&& __x) 120 { 121 // NB: DR 1204. 122 // NB: DR 675. 123 clear(); 124 swap(__x); 125 return *this; 126 } 127 128 set& 129 operator=(initializer_list<value_type> __l) 130 { 131 this->clear(); 132 this->insert(__l); 133 return *this; 134 } 135 #endif 136 137 using _Base::get_allocator; 138 139 // iterators: 140 iterator 141 begin() _GLIBCXX_NOEXCEPT 142 { return iterator(_Base::begin(), this); } 143 144 const_iterator 145 begin() const _GLIBCXX_NOEXCEPT 146 { return const_iterator(_Base::begin(), this); } 147 148 iterator 149 end() _GLIBCXX_NOEXCEPT 150 { return iterator(_Base::end(), this); } 151 152 const_iterator 153 end() const _GLIBCXX_NOEXCEPT 154 { return const_iterator(_Base::end(), this); } 155 156 reverse_iterator 157 rbegin() _GLIBCXX_NOEXCEPT 158 { return reverse_iterator(end()); } 159 160 const_reverse_iterator 161 rbegin() const _GLIBCXX_NOEXCEPT 162 { return const_reverse_iterator(end()); } 163 164 reverse_iterator 165 rend() _GLIBCXX_NOEXCEPT 166 { return reverse_iterator(begin()); } 167 168 const_reverse_iterator 169 rend() const _GLIBCXX_NOEXCEPT 170 { return const_reverse_iterator(begin()); } 171 172 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 173 const_iterator 174 cbegin() const noexcept 175 { return const_iterator(_Base::begin(), this); } 176 177 const_iterator 178 cend() const noexcept 179 { return const_iterator(_Base::end(), this); } 180 181 const_reverse_iterator 182 crbegin() const noexcept 183 { return const_reverse_iterator(end()); } 184 185 const_reverse_iterator 186 crend() const noexcept 187 { return const_reverse_iterator(begin()); } 188 #endif 189 190 // capacity: 191 using _Base::empty; 192 using _Base::size; 193 using _Base::max_size; 194 195 // modifiers: 196 std::pair<iterator, bool> 197 insert(const value_type& __x) 198 { 199 std::pair<_Base_iterator, bool> __res = _Base::insert(__x); 200 return std::pair<iterator, bool>(iterator(__res.first, this), 201 __res.second); 202 } 203 204 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 205 std::pair<iterator, bool> 206 insert(value_type&& __x) 207 { 208 std::pair<_Base_iterator, bool> __res 209 = _Base::insert(std::move(__x)); 210 return std::pair<iterator, bool>(iterator(__res.first, this), 211 __res.second); 212 } 213 #endif 214 215 iterator 216 insert(const_iterator __position, const value_type& __x) 217 { 218 __glibcxx_check_insert(__position); 219 return iterator(_Base::insert(__position.base(), __x), this); 220 } 221 222 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 223 iterator 224 insert(const_iterator __position, value_type&& __x) 225 { 226 __glibcxx_check_insert(__position); 227 return iterator(_Base::insert(__position.base(), std::move(__x)), 228 this); 229 } 230 #endif 231 232 template <typename _InputIterator> 233 void 234 insert(_InputIterator __first, _InputIterator __last) 235 { 236 __glibcxx_check_valid_range(__first, __last); 237 _Base::insert(__gnu_debug::__base(__first), 238 __gnu_debug::__base(__last)); 239 } 240 241 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 242 void 243 insert(initializer_list<value_type> __l) 244 { _Base::insert(__l); } 245 #endif 246 247 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 248 iterator 249 erase(const_iterator __position) 250 { 251 __glibcxx_check_erase(__position); 252 this->_M_invalidate_if(_Equal(__position.base())); 253 return iterator(_Base::erase(__position.base()), this); 254 } 255 #else 256 void 257 erase(iterator __position) 258 { 259 __glibcxx_check_erase(__position); 260 this->_M_invalidate_if(_Equal(__position.base())); 261 _Base::erase(__position.base()); 262 } 263 #endif 264 265 size_type 266 erase(const key_type& __x) 267 { 268 _Base_iterator __victim = _Base::find(__x); 269 if (__victim == _Base::end()) 270 return 0; 271 else 272 { 273 this->_M_invalidate_if(_Equal(__victim)); 274 _Base::erase(__victim); 275 return 1; 276 } 277 } 278 279 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 280 iterator 281 erase(const_iterator __first, const_iterator __last) 282 { 283 // _GLIBCXX_RESOLVE_LIB_DEFECTS 284 // 151. can't currently clear() empty container 285 __glibcxx_check_erase_range(__first, __last); 286 for (_Base_const_iterator __victim = __first.base(); 287 __victim != __last.base(); ++__victim) 288 { 289 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 290 _M_message(__gnu_debug::__msg_valid_range) 291 ._M_iterator(__first, "first") 292 ._M_iterator(__last, "last")); 293 this->_M_invalidate_if(_Equal(__victim)); 294 } 295 return iterator(_Base::erase(__first.base(), __last.base()), this); 296 } 297 #else 298 void 299 erase(iterator __first, iterator __last) 300 { 301 // _GLIBCXX_RESOLVE_LIB_DEFECTS 302 // 151. can't currently clear() empty container 303 __glibcxx_check_erase_range(__first, __last); 304 for (_Base_iterator __victim = __first.base(); 305 __victim != __last.base(); ++__victim) 306 { 307 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 308 _M_message(__gnu_debug::__msg_valid_range) 309 ._M_iterator(__first, "first") 310 ._M_iterator(__last, "last")); 311 this->_M_invalidate_if(_Equal(__victim)); 312 } 313 _Base::erase(__first.base(), __last.base()); 314 } 315 #endif 316 317 void 318 swap(set& __x) 319 { 320 _Base::swap(__x); 321 this->_M_swap(__x); 322 } 323 324 void 325 clear() _GLIBCXX_NOEXCEPT 326 { 327 this->_M_invalidate_all(); 328 _Base::clear(); 329 } 330 331 // observers: 332 using _Base::key_comp; 333 using _Base::value_comp; 334 335 // set operations: 336 iterator 337 find(const key_type& __x) 338 { return iterator(_Base::find(__x), this); } 339 340 // _GLIBCXX_RESOLVE_LIB_DEFECTS 341 // 214. set::find() missing const overload 342 const_iterator 343 find(const key_type& __x) const 344 { return const_iterator(_Base::find(__x), this); } 345 346 using _Base::count; 347 348 iterator 349 lower_bound(const key_type& __x) 350 { return iterator(_Base::lower_bound(__x), this); } 351 352 // _GLIBCXX_RESOLVE_LIB_DEFECTS 353 // 214. set::find() missing const overload 354 const_iterator 355 lower_bound(const key_type& __x) const 356 { return const_iterator(_Base::lower_bound(__x), this); } 357 358 iterator 359 upper_bound(const key_type& __x) 360 { return iterator(_Base::upper_bound(__x), this); } 361 362 // _GLIBCXX_RESOLVE_LIB_DEFECTS 363 // 214. set::find() missing const overload 364 const_iterator 365 upper_bound(const key_type& __x) const 366 { return const_iterator(_Base::upper_bound(__x), this); } 367 368 std::pair<iterator,iterator> 369 equal_range(const key_type& __x) 370 { 371 std::pair<_Base_iterator, _Base_iterator> __res = 372 _Base::equal_range(__x); 373 return std::make_pair(iterator(__res.first, this), 374 iterator(__res.second, this)); 375 } 376 377 // _GLIBCXX_RESOLVE_LIB_DEFECTS 378 // 214. set::find() missing const overload 379 std::pair<const_iterator,const_iterator> 380 equal_range(const key_type& __x) const 381 { 382 std::pair<_Base_iterator, _Base_iterator> __res = 383 _Base::equal_range(__x); 384 return std::make_pair(const_iterator(__res.first, this), 385 const_iterator(__res.second, this)); 386 } 387 388 _Base& 389 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 390 391 const _Base& 392 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 393 394 private: 395 void 396 _M_invalidate_all() 397 { 398 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 399 this->_M_invalidate_if(_Not_equal(_M_base().end())); 400 } 401 }; 402 403 template<typename _Key, typename _Compare, typename _Allocator> 404 inline bool 405 operator==(const set<_Key, _Compare, _Allocator>& __lhs, 406 const set<_Key, _Compare, _Allocator>& __rhs) 407 { return __lhs._M_base() == __rhs._M_base(); } 408 409 template<typename _Key, typename _Compare, typename _Allocator> 410 inline bool 411 operator!=(const set<_Key, _Compare, _Allocator>& __lhs, 412 const set<_Key, _Compare, _Allocator>& __rhs) 413 { return __lhs._M_base() != __rhs._M_base(); } 414 415 template<typename _Key, typename _Compare, typename _Allocator> 416 inline bool 417 operator<(const set<_Key, _Compare, _Allocator>& __lhs, 418 const set<_Key, _Compare, _Allocator>& __rhs) 419 { return __lhs._M_base() < __rhs._M_base(); } 420 421 template<typename _Key, typename _Compare, typename _Allocator> 422 inline bool 423 operator<=(const set<_Key, _Compare, _Allocator>& __lhs, 424 const set<_Key, _Compare, _Allocator>& __rhs) 425 { return __lhs._M_base() <= __rhs._M_base(); } 426 427 template<typename _Key, typename _Compare, typename _Allocator> 428 inline bool 429 operator>=(const set<_Key, _Compare, _Allocator>& __lhs, 430 const set<_Key, _Compare, _Allocator>& __rhs) 431 { return __lhs._M_base() >= __rhs._M_base(); } 432 433 template<typename _Key, typename _Compare, typename _Allocator> 434 inline bool 435 operator>(const set<_Key, _Compare, _Allocator>& __lhs, 436 const set<_Key, _Compare, _Allocator>& __rhs) 437 { return __lhs._M_base() > __rhs._M_base(); } 438 439 template<typename _Key, typename _Compare, typename _Allocator> 440 void 441 swap(set<_Key, _Compare, _Allocator>& __x, 442 set<_Key, _Compare, _Allocator>& __y) 443 { return __x.swap(__y); } 444 445 } // namespace __debug 446 } // namespace std 447 448 #endif 449
