deque revision 1.1.1.1.8.2
1 // Debugging deque implementation -*- C++ -*- 2 3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 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/deque 27 * This file is a GNU debug extension to the Standard C++ Library. 28 */ 29 30 #ifndef _GLIBCXX_DEBUG_DEQUE 31 #define _GLIBCXX_DEBUG_DEQUE 1 32 33 #include <deque> 34 #include <debug/safe_sequence.h> 35 #include <debug/safe_iterator.h> 36 37 namespace std 38 { 39 namespace __debug 40 { 41 /// Class std::deque with safety/checking/debug instrumentation. 42 template<typename _Tp, typename _Allocator = std::allocator<_Tp> > 43 class deque 44 : public _GLIBCXX_STD_D::deque<_Tp, _Allocator>, 45 public __gnu_debug::_Safe_sequence<deque<_Tp, _Allocator> > 46 { 47 typedef _GLIBCXX_STD_D::deque<_Tp, _Allocator> _Base; 48 typedef __gnu_debug::_Safe_sequence<deque> _Safe_base; 49 50 public: 51 typedef typename _Base::reference reference; 52 typedef typename _Base::const_reference const_reference; 53 54 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,deque> 55 iterator; 56 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,deque> 57 const_iterator; 58 59 typedef typename _Base::size_type size_type; 60 typedef typename _Base::difference_type difference_type; 61 62 typedef _Tp value_type; 63 typedef _Allocator allocator_type; 64 typedef typename _Base::pointer pointer; 65 typedef typename _Base::const_pointer const_pointer; 66 typedef std::reverse_iterator<iterator> reverse_iterator; 67 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 68 69 // 23.2.1.1 construct/copy/destroy: 70 explicit deque(const _Allocator& __a = _Allocator()) 71 : _Base(__a) { } 72 73 explicit deque(size_type __n, const _Tp& __value = _Tp(), 74 const _Allocator& __a = _Allocator()) 75 : _Base(__n, __value, __a) { } 76 77 template<class _InputIterator> 78 deque(_InputIterator __first, _InputIterator __last, 79 const _Allocator& __a = _Allocator()) 80 : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, __a) 81 { } 82 83 deque(const deque& __x) 84 : _Base(__x), _Safe_base() { } 85 86 deque(const _Base& __x) 87 : _Base(__x), _Safe_base() { } 88 89 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 90 deque(deque&& __x) 91 : _Base(std::forward<deque>(__x)), _Safe_base() 92 { this->_M_swap(__x); } 93 94 deque(initializer_list<value_type> __l, 95 const allocator_type& __a = allocator_type()) 96 : _Base(__l, __a), _Safe_base() { } 97 #endif 98 99 ~deque() { } 100 101 deque& 102 operator=(const deque& __x) 103 { 104 *static_cast<_Base*>(this) = __x; 105 this->_M_invalidate_all(); 106 return *this; 107 } 108 109 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 110 deque& 111 operator=(deque&& __x) 112 { 113 // NB: DR 1204. 114 // NB: DR 675. 115 clear(); 116 swap(__x); 117 return *this; 118 } 119 120 deque& 121 operator=(initializer_list<value_type> __l) 122 { 123 *static_cast<_Base*>(this) = __l; 124 this->_M_invalidate_all(); 125 return *this; 126 } 127 #endif 128 129 template<class _InputIterator> 130 void 131 assign(_InputIterator __first, _InputIterator __last) 132 { 133 __glibcxx_check_valid_range(__first, __last); 134 _Base::assign(__first, __last); 135 this->_M_invalidate_all(); 136 } 137 138 void 139 assign(size_type __n, const _Tp& __t) 140 { 141 _Base::assign(__n, __t); 142 this->_M_invalidate_all(); 143 } 144 145 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 146 void 147 assign(initializer_list<value_type> __l) 148 { 149 _Base::assign(__l); 150 this->_M_invalidate_all(); 151 } 152 #endif 153 154 using _Base::get_allocator; 155 156 // iterators: 157 iterator 158 begin() 159 { return iterator(_Base::begin(), this); } 160 161 const_iterator 162 begin() const 163 { return const_iterator(_Base::begin(), this); } 164 165 iterator 166 end() 167 { return iterator(_Base::end(), this); } 168 169 const_iterator 170 end() const 171 { return const_iterator(_Base::end(), this); } 172 173 reverse_iterator 174 rbegin() 175 { return reverse_iterator(end()); } 176 177 const_reverse_iterator 178 rbegin() const 179 { return const_reverse_iterator(end()); } 180 181 reverse_iterator 182 rend() 183 { return reverse_iterator(begin()); } 184 185 const_reverse_iterator 186 rend() const 187 { return const_reverse_iterator(begin()); } 188 189 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 190 const_iterator 191 cbegin() const 192 { return const_iterator(_Base::begin(), this); } 193 194 const_iterator 195 cend() const 196 { return const_iterator(_Base::end(), this); } 197 198 const_reverse_iterator 199 crbegin() const 200 { return const_reverse_iterator(end()); } 201 202 const_reverse_iterator 203 crend() const 204 { return const_reverse_iterator(begin()); } 205 #endif 206 207 // 23.2.1.2 capacity: 208 using _Base::size; 209 using _Base::max_size; 210 211 void 212 resize(size_type __sz, _Tp __c = _Tp()) 213 { 214 typedef typename _Base::const_iterator _Base_const_iterator; 215 typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth; 216 217 bool __invalidate_all = __sz > this->size(); 218 if (__sz < this->size()) 219 this->_M_invalidate_if(_After_nth(__sz, _M_base().begin())); 220 221 _Base::resize(__sz, __c); 222 223 if (__invalidate_all) 224 this->_M_invalidate_all(); 225 } 226 227 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 228 using _Base::shrink_to_fit; 229 #endif 230 231 using _Base::empty; 232 233 // element access: 234 reference 235 operator[](size_type __n) 236 { 237 __glibcxx_check_subscript(__n); 238 return _M_base()[__n]; 239 } 240 241 const_reference 242 operator[](size_type __n) const 243 { 244 __glibcxx_check_subscript(__n); 245 return _M_base()[__n]; 246 } 247 248 using _Base::at; 249 250 reference 251 front() 252 { 253 __glibcxx_check_nonempty(); 254 return _Base::front(); 255 } 256 257 const_reference 258 front() const 259 { 260 __glibcxx_check_nonempty(); 261 return _Base::front(); 262 } 263 264 reference 265 back() 266 { 267 __glibcxx_check_nonempty(); 268 return _Base::back(); 269 } 270 271 const_reference 272 back() const 273 { 274 __glibcxx_check_nonempty(); 275 return _Base::back(); 276 } 277 278 // 23.2.1.3 modifiers: 279 void 280 push_front(const _Tp& __x) 281 { 282 _Base::push_front(__x); 283 this->_M_invalidate_all(); 284 } 285 286 void 287 push_back(const _Tp& __x) 288 { 289 _Base::push_back(__x); 290 this->_M_invalidate_all(); 291 } 292 293 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 294 void 295 push_front(_Tp&& __x) 296 { emplace_front(std::move(__x)); } 297 298 void 299 push_back(_Tp&& __x) 300 { emplace_back(std::move(__x)); } 301 302 template<typename... _Args> 303 void 304 emplace_front(_Args&&... __args) 305 { 306 _Base::emplace_front(std::forward<_Args>(__args)...); 307 this->_M_invalidate_all(); 308 } 309 310 template<typename... _Args> 311 void 312 emplace_back(_Args&&... __args) 313 { 314 _Base::emplace_back(std::forward<_Args>(__args)...); 315 this->_M_invalidate_all(); 316 } 317 318 template<typename... _Args> 319 iterator 320 emplace(iterator __position, _Args&&... __args) 321 { 322 __glibcxx_check_insert(__position); 323 typename _Base::iterator __res = _Base::emplace(__position.base(), 324 std::forward<_Args>(__args)...); 325 this->_M_invalidate_all(); 326 return iterator(__res, this); 327 } 328 #endif 329 330 iterator 331 insert(iterator __position, const _Tp& __x) 332 { 333 __glibcxx_check_insert(__position); 334 typename _Base::iterator __res = _Base::insert(__position.base(), __x); 335 this->_M_invalidate_all(); 336 return iterator(__res, this); 337 } 338 339 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 340 iterator 341 insert(iterator __position, _Tp&& __x) 342 { return emplace(__position, std::move(__x)); } 343 344 void 345 insert(iterator __p, initializer_list<value_type> __l) 346 { 347 _Base::insert(__p, __l); 348 this->_M_invalidate_all(); 349 } 350 #endif 351 352 void 353 insert(iterator __position, size_type __n, const _Tp& __x) 354 { 355 __glibcxx_check_insert(__position); 356 _Base::insert(__position.base(), __n, __x); 357 this->_M_invalidate_all(); 358 } 359 360 template<class _InputIterator> 361 void 362 insert(iterator __position, 363 _InputIterator __first, _InputIterator __last) 364 { 365 __glibcxx_check_insert_range(__position, __first, __last); 366 _Base::insert(__position.base(), __first, __last); 367 this->_M_invalidate_all(); 368 } 369 370 void 371 pop_front() 372 { 373 __glibcxx_check_nonempty(); 374 iterator __victim = begin(); 375 __victim._M_invalidate(); 376 _Base::pop_front(); 377 } 378 379 void 380 pop_back() 381 { 382 __glibcxx_check_nonempty(); 383 iterator __victim = end(); 384 --__victim; 385 __victim._M_invalidate(); 386 _Base::pop_back(); 387 } 388 389 iterator 390 erase(iterator __position) 391 { 392 __glibcxx_check_erase(__position); 393 if (__position == begin() || __position == end()-1) 394 { 395 __position._M_invalidate(); 396 return iterator(_Base::erase(__position.base()), this); 397 } 398 else 399 { 400 typename _Base::iterator __res = _Base::erase(__position.base()); 401 this->_M_invalidate_all(); 402 return iterator(__res, this); 403 } 404 } 405 406 iterator 407 erase(iterator __first, iterator __last) 408 { 409 // _GLIBCXX_RESOLVE_LIB_DEFECTS 410 // 151. can't currently clear() empty container 411 __glibcxx_check_erase_range(__first, __last); 412 if (__first == begin() || __last == end()) 413 { 414 this->_M_detach_singular(); 415 for (iterator __position = __first; __position != __last; ) 416 { 417 iterator __victim = __position++; 418 __victim._M_invalidate(); 419 } 420 __try 421 { 422 return iterator(_Base::erase(__first.base(), __last.base()), 423 this); 424 } 425 __catch(...) 426 { 427 this->_M_revalidate_singular(); 428 __throw_exception_again; 429 } 430 } 431 else 432 { 433 typename _Base::iterator __res = _Base::erase(__first.base(), 434 __last.base()); 435 this->_M_invalidate_all(); 436 return iterator(__res, this); 437 } 438 } 439 440 void 441 swap(deque& __x) 442 { 443 _Base::swap(__x); 444 this->_M_swap(__x); 445 } 446 447 void 448 clear() 449 { 450 _Base::clear(); 451 this->_M_invalidate_all(); 452 } 453 454 _Base& 455 _M_base() { return *this; } 456 457 const _Base& 458 _M_base() const { return *this; } 459 }; 460 461 template<typename _Tp, typename _Alloc> 462 inline bool 463 operator==(const deque<_Tp, _Alloc>& __lhs, 464 const deque<_Tp, _Alloc>& __rhs) 465 { return __lhs._M_base() == __rhs._M_base(); } 466 467 template<typename _Tp, typename _Alloc> 468 inline bool 469 operator!=(const deque<_Tp, _Alloc>& __lhs, 470 const deque<_Tp, _Alloc>& __rhs) 471 { return __lhs._M_base() != __rhs._M_base(); } 472 473 template<typename _Tp, typename _Alloc> 474 inline bool 475 operator<(const deque<_Tp, _Alloc>& __lhs, 476 const deque<_Tp, _Alloc>& __rhs) 477 { return __lhs._M_base() < __rhs._M_base(); } 478 479 template<typename _Tp, typename _Alloc> 480 inline bool 481 operator<=(const deque<_Tp, _Alloc>& __lhs, 482 const deque<_Tp, _Alloc>& __rhs) 483 { return __lhs._M_base() <= __rhs._M_base(); } 484 485 template<typename _Tp, typename _Alloc> 486 inline bool 487 operator>=(const deque<_Tp, _Alloc>& __lhs, 488 const deque<_Tp, _Alloc>& __rhs) 489 { return __lhs._M_base() >= __rhs._M_base(); } 490 491 template<typename _Tp, typename _Alloc> 492 inline bool 493 operator>(const deque<_Tp, _Alloc>& __lhs, 494 const deque<_Tp, _Alloc>& __rhs) 495 { return __lhs._M_base() > __rhs._M_base(); } 496 497 template<typename _Tp, typename _Alloc> 498 inline void 499 swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs) 500 { __lhs.swap(__rhs); } 501 502 } // namespace __debug 503 } // namespace std 504 505 #endif 506
Indexes created Mon Mar 02 05:31:46 UTC 2026