stl_deque.h

Go to the documentation of this file.
00001 // deque implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002 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 2, 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 // You should have received a copy of the GNU General Public License along 00017 // with this library; see the file COPYING. If not, write to the Free 00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 00019 // USA. 00020 00021 // As a special exception, you may use this file as part of a free software 00022 // library without restriction. Specifically, if other files instantiate 00023 // templates or use macros or inline functions from this file, or you compile 00024 // this file and link it with other files to produce an executable, this 00025 // file does not by itself cause the resulting executable to be covered by 00026 // the GNU General Public License. This exception does not however 00027 // invalidate any other reasons why the executable file might be covered by 00028 // the GNU General Public License. 00029 00030 /* 00031 * 00032 * Copyright (c) 1994 00033 * Hewlett-Packard Company 00034 * 00035 * Permission to use, copy, modify, distribute and sell this software 00036 * and its documentation for any purpose is hereby granted without fee, 00037 * provided that the above copyright notice appear in all copies and 00038 * that both that copyright notice and this permission notice appear 00039 * in supporting documentation. Hewlett-Packard Company makes no 00040 * representations about the suitability of this software for any 00041 * purpose. It is provided "as is" without express or implied warranty. 00042 * 00043 * 00044 * Copyright (c) 1997 00045 * Silicon Graphics Computer Systems, Inc. 00046 * 00047 * Permission to use, copy, modify, distribute and sell this software 00048 * and its documentation for any purpose is hereby granted without fee, 00049 * provided that the above copyright notice appear in all copies and 00050 * that both that copyright notice and this permission notice appear 00051 * in supporting documentation. Silicon Graphics makes no 00052 * representations about the suitability of this software for any 00053 * purpose. It is provided "as is" without express or implied warranty. 00054 */ 00055 00061 #include <bits/concept_check.h> 00062 #include <bits/stl_iterator_base_types.h> 00063 #include <bits/stl_iterator_base_funcs.h> 00064 00065 #ifndef __GLIBCPP_INTERNAL_DEQUE_H 00066 #define __GLIBCPP_INTERNAL_DEQUE_H 00067 00068 00069 // Since this entire file is within namespace std, there's no reason to 00070 // waste two spaces along the left column. Thus the leading indentation is 00071 // slightly violated from here on. 00072 namespace std 00073 { 00074 00085 inline size_t 00086 __deque_buf_size(size_t __size) 00087 { return __size < 512 ? size_t(512 / __size) : size_t(1); } 00088 00089 00091 00101 template <class _Tp, class _Ref, class _Ptr> 00102 struct _Deque_iterator 00103 { 00104 typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator; 00105 typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; 00106 static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); } 00107 00108 typedef random_access_iterator_tag iterator_category; 00109 typedef _Tp value_type; 00110 typedef _Ptr pointer; 00111 typedef _Ref reference; 00112 typedef size_t size_type; 00113 typedef ptrdiff_t difference_type; 00114 typedef _Tp** _Map_pointer; 00115 typedef _Deque_iterator _Self; 00116 00117 _Tp* _M_cur; 00118 _Tp* _M_first; 00119 _Tp* _M_last; 00120 _Map_pointer _M_node; 00121 00122 _Deque_iterator(_Tp* __x, _Map_pointer __y) 00123 : _M_cur(__x), _M_first(*__y), 00124 _M_last(*__y + _S_buffer_size()), _M_node(__y) {} 00125 _Deque_iterator() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {} 00126 _Deque_iterator(const iterator& __x) 00127 : _M_cur(__x._M_cur), _M_first(__x._M_first), 00128 _M_last(__x._M_last), _M_node(__x._M_node) {} 00129 00130 reference operator*() const { return *_M_cur; } 00131 pointer operator->() const { return _M_cur; } 00132 00133 _Self& operator++() { 00134 ++_M_cur; 00135 if (_M_cur == _M_last) { 00136 _M_set_node(_M_node + 1); 00137 _M_cur = _M_first; 00138 } 00139 return *this; 00140 } 00141 _Self operator++(int) { 00142 _Self __tmp = *this; 00143 ++*this; 00144 return __tmp; 00145 } 00146 00147 _Self& operator--() { 00148 if (_M_cur == _M_first) { 00149 _M_set_node(_M_node - 1); 00150 _M_cur = _M_last; 00151 } 00152 --_M_cur; 00153 return *this; 00154 } 00155 _Self operator--(int) { 00156 _Self __tmp = *this; 00157 --*this; 00158 return __tmp; 00159 } 00160 00161 _Self& operator+=(difference_type __n) 00162 { 00163 difference_type __offset = __n + (_M_cur - _M_first); 00164 if (__offset >= 0 && __offset < difference_type(_S_buffer_size())) 00165 _M_cur += __n; 00166 else { 00167 difference_type __node_offset = 00168 __offset > 0 ? __offset / difference_type(_S_buffer_size()) 00169 : -difference_type((-__offset - 1) / _S_buffer_size()) - 1; 00170 _M_set_node(_M_node + __node_offset); 00171 _M_cur = _M_first + 00172 (__offset - __node_offset * difference_type(_S_buffer_size())); 00173 } 00174 return *this; 00175 } 00176 00177 _Self operator+(difference_type __n) const 00178 { 00179 _Self __tmp = *this; 00180 return __tmp += __n; 00181 } 00182 00183 _Self& operator-=(difference_type __n) { return *this += -__n; } 00184 00185 _Self operator-(difference_type __n) const { 00186 _Self __tmp = *this; 00187 return __tmp -= __n; 00188 } 00189 00190 reference operator[](difference_type __n) const { return *(*this + __n); } 00191 00198 void _M_set_node(_Map_pointer __new_node) { 00199 _M_node = __new_node; 00200 _M_first = *__new_node; 00201 _M_last = _M_first + difference_type(_S_buffer_size()); 00202 } 00203 }; 00204 00205 // Note: we also provide overloads whose operands are of the same type in 00206 // order to avoid ambiguos overload resolution when std::rel_ops operators 00207 // are in scope (for additional details, see libstdc++/3628) 00208 template <class _Tp, class _Ref, class _Ptr> 00209 inline bool 00210 operator==(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, 00211 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) 00212 { 00213 return __x._M_cur == __y._M_cur; 00214 } 00215 00216 template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR> 00217 inline bool 00218 operator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, 00219 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) 00220 { 00221 return __x._M_cur == __y._M_cur; 00222 } 00223 00224 template <class _Tp, class _Ref, class _Ptr> 00225 inline bool 00226 operator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, 00227 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) 00228 { 00229 return !(__x == __y); 00230 } 00231 00232 template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR> 00233 inline bool 00234 operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, 00235 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) 00236 { 00237 return !(__x == __y); 00238 } 00239 00240 template <class _Tp, class _Ref, class _Ptr> 00241 inline bool 00242 operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, 00243 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) 00244 { 00245 return (__x._M_node == __y._M_node) ? 00246 (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node); 00247 } 00248 00249 template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR> 00250 inline bool 00251 operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, 00252 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) 00253 { 00254 return (__x._M_node == __y._M_node) ? 00255 (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node); 00256 } 00257 00258 template <class _Tp, class _Ref, class _Ptr> 00259 inline bool 00260 operator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, 00261 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) 00262 { 00263 return __y < __x; 00264 } 00265 00266 template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR> 00267 inline bool 00268 operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, 00269 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) 00270 { 00271 return __y < __x; 00272 } 00273 00274 template <class _Tp, class _Ref, class _Ptr> 00275 inline bool 00276 operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, 00277 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) 00278 { 00279 return !(__y < __x); 00280 } 00281 00282 template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR> 00283 inline bool 00284 operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, 00285 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) 00286 { 00287 return !(__y < __x); 00288 } 00289 00290 template <class _Tp, class _Ref, class _Ptr> 00291 inline bool 00292 operator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, 00293 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) 00294 { 00295 return !(__x < __y); 00296 } 00297 00298 template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR> 00299 inline bool 00300 operator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, 00301 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) 00302 { 00303 return !(__x < __y); 00304 } 00305 00306 // _GLIBCPP_RESOLVE_LIB_DEFECTS 00307 // According to the resolution of DR179 not only the various comparison 00308 // operators but also operator- must accept mixed iterator/const_iterator 00309 // parameters. 00310 template <typename _Tp, typename _RefL, typename _PtrL, 00311 typename _RefR, typename _PtrR> 00312 inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type 00313 operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, 00314 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) 00315 { 00316 return _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type 00317 (_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size()) * 00318 (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first) + 00319 (__y._M_last - __y._M_cur); 00320 } 00321 00322 template <class _Tp, class _Ref, class _Ptr> 00323 inline _Deque_iterator<_Tp, _Ref, _Ptr> 00324 operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x) 00325 { 00326 return __x + __n; 00327 } 00328 00329 00331 00341 template <class _Tp, class _Alloc, bool __is_static> 00342 class _Deque_alloc_base 00343 { 00344 public: 00345 typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type; 00346 allocator_type get_allocator() const { return _M_node_allocator; } 00347 00348 _Deque_alloc_base(const allocator_type& __a) 00349 : _M_node_allocator(__a), _M_map_allocator(__a), 00350 _M_map(0), _M_map_size(0) 00351 {} 00352 00353 protected: 00354 typedef typename _Alloc_traits<_Tp*, _Alloc>::allocator_type 00355 _Map_allocator_type; 00356 00357 allocator_type _M_node_allocator; 00358 _Map_allocator_type _M_map_allocator; 00359 00360 _Tp* _M_allocate_node() { 00361 return _M_node_allocator.allocate(__deque_buf_size(sizeof(_Tp))); 00362 } 00363 void _M_deallocate_node(_Tp* __p) { 00364 _M_node_allocator.deallocate(__p, __deque_buf_size(sizeof(_Tp))); 00365 } 00366 _Tp** _M_allocate_map(size_t __n) 00367 { return _M_map_allocator.allocate(__n); } 00368 void _M_deallocate_map(_Tp** __p, size_t __n) 00369 { _M_map_allocator.deallocate(__p, __n); } 00370 00371 _Tp** _M_map; 00372 size_t _M_map_size; 00373 }; 00374 00376 template <class _Tp, class _Alloc> 00377 class _Deque_alloc_base<_Tp, _Alloc, true> 00378 { 00379 public: 00380 typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type; 00381 allocator_type get_allocator() const { return allocator_type(); } 00382 00383 _Deque_alloc_base(const allocator_type&) : _M_map(0), _M_map_size(0) {} 00384 00385 protected: 00386 typedef typename _Alloc_traits<_Tp, _Alloc>::_Alloc_type _Node_alloc_type; 00387 typedef typename _Alloc_traits<_Tp*, _Alloc>::_Alloc_type _Map_alloc_type; 00388 00389 _Tp* _M_allocate_node() { 00390 return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp))); 00391 } 00392 void _M_deallocate_node(_Tp* __p) { 00393 _Node_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp))); 00394 } 00395 _Tp** _M_allocate_map(size_t __n) 00396 { return _Map_alloc_type::allocate(__n); } 00397 void _M_deallocate_map(_Tp** __p, size_t __n) 00398 { _Map_alloc_type::deallocate(__p, __n); } 00399 00400 _Tp** _M_map; 00401 size_t _M_map_size; 00402 }; 00403 00404 00415 template <class _Tp, class _Alloc> 00416 class _Deque_base 00417 : public _Deque_alloc_base<_Tp,_Alloc, 00418 _Alloc_traits<_Tp, _Alloc>::_S_instanceless> 00419 { 00420 public: 00421 typedef _Deque_alloc_base<_Tp,_Alloc, 00422 _Alloc_traits<_Tp, _Alloc>::_S_instanceless> 00423 _Base; 00424 typedef typename _Base::allocator_type allocator_type; 00425 typedef _Deque_iterator<_Tp,_Tp&,_Tp*> iterator; 00426 typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator; 00427 00428 _Deque_base(const allocator_type& __a, size_t __num_elements) 00429 : _Base(__a), _M_start(), _M_finish() 00430 { _M_initialize_map(__num_elements); } 00431 _Deque_base(const allocator_type& __a) 00432 : _Base(__a), _M_start(), _M_finish() {} 00433 ~_Deque_base(); 00434 00435 protected: 00436 void _M_initialize_map(size_t); 00437 void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish); 00438 void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish); 00439 enum { _S_initial_map_size = 8 }; 00440 00441 protected: 00442 iterator _M_start; 00443 iterator _M_finish; 00444 }; 00445 00446 00447 template <class _Tp, class _Alloc> 00448 _Deque_base<_Tp,_Alloc>::~_Deque_base() 00449 { 00450 if (_M_map) { 00451 _M_destroy_nodes(_M_start._M_node, _M_finish._M_node + 1); 00452 _M_deallocate_map(_M_map, _M_map_size); 00453 } 00454 } 00455 00465 template <class _Tp, class _Alloc> 00466 void 00467 _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements) 00468 { 00469 size_t __num_nodes = 00470 __num_elements / __deque_buf_size(sizeof(_Tp)) + 1; 00471 00472 _M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2); 00473 _M_map = _M_allocate_map(_M_map_size); 00474 00475 _Tp** __nstart = _M_map + (_M_map_size - __num_nodes) / 2; 00476 _Tp** __nfinish = __nstart + __num_nodes; 00477 00478 try 00479 { _M_create_nodes(__nstart, __nfinish); } 00480 catch(...) 00481 { 00482 _M_deallocate_map(_M_map, _M_map_size); 00483 _M_map = 0; 00484 _M_map_size = 0; 00485 __throw_exception_again; 00486 } 00487 00488 _M_start._M_set_node(__nstart); 00489 _M_finish._M_set_node(__nfinish - 1); 00490 _M_start._M_cur = _M_start._M_first; 00491 _M_finish._M_cur = _M_finish._M_first + 00492 __num_elements % __deque_buf_size(sizeof(_Tp)); 00493 } 00494 00495 template <class _Tp, class _Alloc> 00496 void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, _Tp** __nfinish) 00497 { 00498 _Tp** __cur; 00499 try { 00500 for (__cur = __nstart; __cur < __nfinish; ++__cur) 00501 *__cur = _M_allocate_node(); 00502 } 00503 catch(...) 00504 { 00505 _M_destroy_nodes(__nstart, __cur); 00506 __throw_exception_again; 00507 } 00508 } 00509 00510 template <class _Tp, class _Alloc> 00511 void 00512 _Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish) 00513 { 00514 for (_Tp** __n = __nstart; __n < __nfinish; ++__n) 00515 _M_deallocate_node(*__n); 00516 } 00517 00518 00599 template <class _Tp, class _Alloc = allocator<_Tp> > 00600 class deque : protected _Deque_base<_Tp, _Alloc> 00601 { 00602 // concept requirements 00603 __glibcpp_class_requires(_Tp, _SGIAssignableConcept) 00604 00605 typedef _Deque_base<_Tp, _Alloc> _Base; 00606 00607 public: 00608 typedef _Tp value_type; 00609 typedef value_type* pointer; 00610 typedef const value_type* const_pointer; 00611 typedef value_type& reference; 00612 typedef const value_type& const_reference; 00613 typedef size_t size_type; 00614 typedef ptrdiff_t difference_type; 00615 00616 typedef typename _Base::allocator_type allocator_type; 00617 allocator_type get_allocator() const { return _Base::get_allocator(); } 00618 00619 typedef typename _Base::iterator iterator; 00620 typedef typename _Base::const_iterator const_iterator; 00621 typedef reverse_iterator<const_iterator> const_reverse_iterator; 00622 typedef reverse_iterator<iterator> reverse_iterator; 00623 00624 protected: 00625 typedef pointer* _Map_pointer; 00626 static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); } 00627 00628 // Functions controlling memory layout, and nothing else. 00629 using _Base::_M_initialize_map; 00630 using _Base::_M_create_nodes; 00631 using _Base::_M_destroy_nodes; 00632 using _Base::_M_allocate_node; 00633 using _Base::_M_deallocate_node; 00634 using _Base::_M_allocate_map; 00635 using _Base::_M_deallocate_map; 00636 00643 using _Base::_M_map; 00644 using _Base::_M_map_size; 00645 using _Base::_M_start; 00646 using _Base::_M_finish; 00647 00648 public: // Basic accessors 00649 iterator begin() { return _M_start; } 00650 iterator end() { return _M_finish; } 00651 const_iterator begin() const { return _M_start; } 00652 const_iterator end() const { return _M_finish; } 00653 00654 reverse_iterator rbegin() { return reverse_iterator(_M_finish); } 00655 reverse_iterator rend() { return reverse_iterator(_M_start); } 00656 const_reverse_iterator rbegin() const 00657 { return const_reverse_iterator(_M_finish); } 00658 const_reverse_iterator rend() const 00659 { return const_reverse_iterator(_M_start); } 00660 00661 reference operator[](size_type __n) 00662 { return _M_start[difference_type(__n)]; } 00663 const_reference operator[](size_type __n) const 00664 { return _M_start[difference_type(__n)]; } 00665 00666 void _M_range_check(size_type __n) const { 00667 if (__n >= this->size()) 00668 __throw_out_of_range("deque"); 00669 } 00670 00671 reference at(size_type __n) 00672 { _M_range_check(__n); return (*this)[__n]; } 00673 const_reference at(size_type __n) const 00674 { _M_range_check(__n); return (*this)[__n]; } 00675 00676 reference front() { return *_M_start; } 00677 reference back() { 00678 iterator __tmp = _M_finish; 00679 --__tmp; 00680 return *__tmp; 00681 } 00682 const_reference front() const { return *_M_start; } 00683 const_reference back() const { 00684 const_iterator __tmp = _M_finish; 00685 --__tmp; 00686 return *__tmp; 00687 } 00688 00689 size_type size() const { return _M_finish - _M_start; } 00690 size_type max_size() const { return size_type(-1); } 00691 bool empty() const { return _M_finish == _M_start; } 00692 00693 public: // Constructor, destructor. 00694 explicit deque(const allocator_type& __a = allocator_type()) 00695 : _Base(__a, 0) {} 00696 deque(const deque& __x) : _Base(__x.get_allocator(), __x.size()) 00697 { uninitialized_copy(__x.begin(), __x.end(), _M_start); } 00698 deque(size_type __n, const value_type& __value, 00699 const allocator_type& __a = allocator_type()) : _Base(__a, __n) 00700 { _M_fill_initialize(__value); } 00701 00702 explicit 00703 deque(size_type __n) 00704 : _Base(allocator_type(), __n) 00705 { _M_fill_initialize(value_type()); } 00706 00707 // Check whether it's an integral type. If so, it's not an iterator. 00708 template<class _InputIterator> 00709 deque(_InputIterator __first, _InputIterator __last, 00710 const allocator_type& __a = allocator_type()) 00711 : _Base(__a) 00712 { 00713 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 00714 _M_initialize_dispatch(__first, __last, _Integral()); 00715 } 00716 00717 template<class _Integer> 00718 void 00719 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) 00720 { 00721 _M_initialize_map(__n); 00722 _M_fill_initialize(__x); 00723 } 00724 00725 template<class _InputIter> 00726 void 00727 _M_initialize_dispatch(_InputIter __first, _InputIter __last, __false_type) 00728 { 00729 typedef typename iterator_traits<_InputIter>::iterator_category _IterCategory; 00730 _M_range_initialize(__first, __last, _IterCategory()); 00731 } 00732 00733 ~deque() 00734 { _Destroy(_M_start, _M_finish); } 00735 00736 deque& operator= (const deque& __x) { 00737 const size_type __len = size(); 00738 if (&__x != this) { 00739 if (__len >= __x.size()) 00740 erase(copy(__x.begin(), __x.end(), _M_start), _M_finish); 00741 else { 00742 const_iterator __mid = __x.begin() + difference_type(__len); 00743 copy(__x.begin(), __mid, _M_start); 00744 insert(_M_finish, __mid, __x.end()); 00745 } 00746 } 00747 return *this; 00748 } 00749 00750 void swap(deque& __x) { 00751 std::swap(_M_start, __x._M_start); 00752 std::swap(_M_finish, __x._M_finish); 00753 std::swap(_M_map, __x._M_map); 00754 std::swap(_M_map_size, __x._M_map_size); 00755 } 00756 00757 public: 00758 // assign(), a generalized assignment member function. Two 00759 // versions: one that takes a count, and one that takes a range. 00760 // The range version is a member template, so we dispatch on whether 00761 // or not the type is an integer. 00762 00763 void _M_fill_assign(size_type __n, const _Tp& __val) { 00764 if (__n > size()) { 00765 fill(begin(), end(), __val); 00766 insert(end(), __n - size(), __val); 00767 } 00768 else { 00769 erase(begin() + __n, end()); 00770 fill(begin(), end(), __val); 00771 } 00772 } 00773 00774 void 00775 assign(size_type __n, const _Tp& __val) 00776 { _M_fill_assign(__n, __val); } 00777 00778 template<class _InputIterator> 00779 void 00780 assign(_InputIterator __first, _InputIterator __last) 00781 { 00782 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 00783 _M_assign_dispatch(__first, __last, _Integral()); 00784 } 00785 00786 private: // helper functions for assign() 00787 00788 template<class _Integer> 00789 void 00790 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 00791 { _M_fill_assign(static_cast<size_type>(__n), static_cast<_Tp>(__val)); } 00792 00793 template<class _InputIterator> 00794 void 00795 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, __false_type) 00796 { 00797 typedef typename iterator_traits<_InputIterator>::iterator_category _IterCategory; 00798 _M_assign_aux(__first, __last, _IterCategory()); 00799 } 00800 00801 template <class _InputIterator> 00802 void _M_assign_aux(_InputIterator __first, _InputIterator __last, 00803 input_iterator_tag); 00804 00805 template <class _ForwardIterator> 00806 void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 00807 forward_iterator_tag) { 00808 size_type __len = distance(__first, __last); 00809 if (__len > size()) { 00810 _ForwardIterator __mid = __first; 00811 advance(__mid, size()); 00812 copy(__first, __mid, begin()); 00813 insert(end(), __mid, __last); 00814 } 00815 else 00816 erase(copy(__first, __last, begin()), end()); 00817 } 00818 00819 public: // push_* and pop_* 00820 00821 void 00822 push_back(const value_type& __t) 00823 { 00824 if (_M_finish._M_cur != _M_finish._M_last - 1) { 00825 _Construct(_M_finish._M_cur, __t); 00826 ++_M_finish._M_cur; 00827 } 00828 else 00829 _M_push_back_aux(__t); 00830 } 00831 00832 void 00833 push_back() 00834 { 00835 if (_M_finish._M_cur != _M_finish._M_last - 1) { 00836 _Construct(_M_finish._M_cur); 00837 ++_M_finish._M_cur; 00838 } 00839 else 00840 _M_push_back_aux(); 00841 } 00842 00843 void 00844 push_front(const value_type& __t) 00845 { 00846 if (_M_start._M_cur != _M_start._M_first) { 00847 _Construct(_M_start._M_cur - 1, __t); 00848 --_M_start._M_cur; 00849 } 00850 else 00851 _M_push_front_aux(__t); 00852 } 00853 00854 void 00855 push_front() 00856 { 00857 if (_M_start._M_cur != _M_start._M_first) { 00858 _Construct(_M_start._M_cur - 1); 00859 --_M_start._M_cur; 00860 } 00861 else 00862 _M_push_front_aux(); 00863 } 00864 00865 00866 void 00867 pop_back() 00868 { 00869 if (_M_finish._M_cur != _M_finish._M_first) { 00870 --_M_finish._M_cur; 00871 _Destroy(_M_finish._M_cur); 00872 } 00873 else 00874 _M_pop_back_aux(); 00875 } 00876 00877 void 00878 pop_front() 00879 { 00880 if (_M_start._M_cur != _M_start._M_last - 1) { 00881 _Destroy(_M_start._M_cur); 00882 ++_M_start._M_cur; 00883 } 00884 else 00885 _M_pop_front_aux(); 00886 } 00887 00888 public: // Insert 00889 00890 iterator 00891 insert(iterator position, const value_type& __x) 00892 { 00893 if (position._M_cur == _M_start._M_cur) { 00894 push_front(__x); 00895 return _M_start; 00896 } 00897 else if (position._M_cur == _M_finish._M_cur) { 00898 push_back(__x); 00899 iterator __tmp = _M_finish; 00900 --__tmp; 00901 return __tmp; 00902 } 00903 else { 00904 return _M_insert_aux(position, __x); 00905 } 00906 } 00907 00908 iterator 00909 insert(iterator __position) 00910 { return insert(__position, value_type()); } 00911 00912 void 00913 insert(iterator __pos, size_type __n, const value_type& __x) 00914 { _M_fill_insert(__pos, __n, __x); } 00915 00916 void 00917 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x); 00918 00919 // Check whether it's an integral type. If so, it's not an iterator. 00920 template<class _InputIterator> 00921 void 00922 insert(iterator __pos, _InputIterator __first, _InputIterator __last) 00923 { 00924 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 00925 _M_insert_dispatch(__pos, __first, __last, _Integral()); 00926 } 00927 00928 template<class _Integer> 00929 void 00930 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, __true_type) 00931 { _M_fill_insert(__pos, static_cast<size_type>(__n), static_cast<value_type>(__x)); } 00932 00933 template<class _InputIterator> 00934 void 00935 _M_insert_dispatch(iterator __pos, 00936 _InputIterator __first, _InputIterator __last, 00937 __false_type) 00938 { 00939 typedef typename iterator_traits<_InputIterator>::iterator_category _IterCategory; 00940 insert(__pos, __first, __last, _IterCategory()); 00941 } 00942 00943 void resize(size_type __new_size, const value_type& __x) { 00944 const size_type __len = size(); 00945 if (__new_size < __len) 00946 erase(_M_start + __new_size, _M_finish); 00947 else 00948 insert(_M_finish, __new_size - __len, __x); 00949 } 00950 00951 void resize(size_type new_size) { resize(new_size, value_type()); } 00952 00953 public: // Erase 00954 iterator erase(iterator __pos) { 00955 iterator __next = __pos; 00956 ++__next; 00957 size_type __index = __pos - _M_start; 00958 if (__index < (size() >> 1)) { 00959 copy_backward(_M_start, __pos, __next); 00960 pop_front(); 00961 } 00962 else { 00963 copy(__next, _M_finish, __pos); 00964 pop_back(); 00965 } 00966 return _M_start + __index; 00967 } 00968 00969 iterator erase(iterator __first, iterator __last); 00970 void clear(); 00971 00972 protected: // Internal construction/destruction 00973 00974 void _M_fill_initialize(const value_type& __value); 00975 00976 template <class _InputIterator> 00977 void _M_range_initialize(_InputIterator __first, _InputIterator __last, 00978 input_iterator_tag); 00979 00980 template <class _ForwardIterator> 00981 void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, 00982 forward_iterator_tag); 00983 00984 protected: // Internal push_* and pop_* 00985 00986 void _M_push_back_aux(const value_type&); 00987 void _M_push_back_aux(); 00988 void _M_push_front_aux(const value_type&); 00989 void _M_push_front_aux(); 00990 void _M_pop_back_aux(); 00991 void _M_pop_front_aux(); 00992 00993 protected: // Internal insert functions 00994 00995 template <class _InputIterator> 00996 void insert(iterator __pos, _InputIterator __first, _InputIterator __last, 00997 input_iterator_tag); 00998 00999 template <class _ForwardIterator> 01000 void insert(iterator __pos, 01001 _ForwardIterator __first, _ForwardIterator __last, 01002 forward_iterator_tag); 01003 01004 iterator _M_insert_aux(iterator __pos, const value_type& __x); 01005 iterator _M_insert_aux(iterator __pos); 01006 void _M_insert_aux(iterator __pos, size_type __n, const value_type& __x); 01007 01008 template <class _ForwardIterator> 01009 void _M_insert_aux(iterator __pos, 01010 _ForwardIterator __first, _ForwardIterator __last, 01011 size_type __n); 01012 01013 iterator _M_reserve_elements_at_front(size_type __n) { 01014 size_type __vacancies = _M_start._M_cur - _M_start._M_first; 01015 if (__n > __vacancies) 01016 _M_new_elements_at_front(__n - __vacancies); 01017 return _M_start - difference_type(__n); 01018 } 01019 01020 iterator _M_reserve_elements_at_back(size_type __n) { 01021 size_type __vacancies = (_M_finish._M_last - _M_finish._M_cur) - 1; 01022 if (__n > __vacancies) 01023 _M_new_elements_at_back(__n - __vacancies); 01024 return _M_finish + difference_type(__n); 01025 } 01026 01027 void _M_new_elements_at_front(size_type __new_elements); 01028 void _M_new_elements_at_back(size_type __new_elements); 01029 01030 protected: // Allocation of _M_map and nodes 01031 01032 // Makes sure the _M_map has space for new nodes. Does not actually 01033 // add the nodes. Can invalidate _M_map pointers. (And consequently, 01034 // deque iterators.) 01035 01036 void _M_reserve_map_at_back (size_type __nodes_to_add = 1) { 01037 if (__nodes_to_add + 1 > _M_map_size - (_M_finish._M_node - _M_map)) 01038 _M_reallocate_map(__nodes_to_add, false); 01039 } 01040 01041 void _M_reserve_map_at_front (size_type __nodes_to_add = 1) { 01042 if (__nodes_to_add > size_type(_M_start._M_node - _M_map)) 01043 _M_reallocate_map(__nodes_to_add, true); 01044 } 01045 01046 void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front); 01047 }; 01048 01049 // Non-inline member functions 01050 01051 template <class _Tp, class _Alloc> 01052 template <class _InputIter> 01053 void deque<_Tp, _Alloc> 01054 ::_M_assign_aux(_InputIter __first, _InputIter __last, input_iterator_tag) 01055 { 01056 iterator __cur = begin(); 01057 for ( ; __first != __last && __cur != end(); ++__cur, ++__first) 01058 *__cur = *__first; 01059 if (__first == __last) 01060 erase(__cur, end()); 01061 else 01062 insert(end(), __first, __last); 01063 } 01064 01065 template <class _Tp, class _Alloc> 01066 void deque<_Tp, _Alloc>::_M_fill_insert(iterator __pos, 01067 size_type __n, const value_type& __x) 01068 { 01069 if (__pos._M_cur == _M_start._M_cur) { 01070 iterator __new_start = _M_reserve_elements_at_front(__n); 01071 try { 01072 uninitialized_fill(__new_start, _M_start, __x); 01073 _M_start = __new_start; 01074 } 01075 catch(...) 01076 { 01077 _M_destroy_nodes(__new_start._M_node, _M_start._M_node); 01078 __throw_exception_again; 01079 } 01080 } 01081 else if (__pos._M_cur == _M_finish._M_cur) { 01082 iterator __new_finish = _M_reserve_elements_at_back(__n); 01083 try { 01084 uninitialized_fill(_M_finish, __new_finish, __x); 01085 _M_finish = __new_finish; 01086 } 01087 catch(...) 01088 { 01089 _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1); 01090 __throw_exception_again; 01091 } 01092 } 01093 else 01094 _M_insert_aux(__pos, __n, __x); 01095 } 01096 01097 template <class _Tp, class _Alloc> 01098 typename deque<_Tp,_Alloc>::iterator 01099 deque<_Tp,_Alloc>::erase(iterator __first, iterator __last) 01100 { 01101 if (__first == _M_start && __last == _M_finish) { 01102 clear(); 01103 return _M_finish; 01104 } 01105 else { 01106 difference_type __n = __last - __first; 01107 difference_type __elems_before = __first - _M_start; 01108 if (static_cast<size_type>(__elems_before) < (size() - __n) / 2) { 01109 copy_backward(_M_start, __first, __last); 01110 iterator __new_start = _M_start + __n; 01111 _Destroy(_M_start, __new_start); 01112 _M_destroy_nodes(_M_start._M_node, __new_start._M_node); 01113 _M_start = __new_start; 01114 } 01115 else { 01116 copy(__last, _M_finish, __first); 01117 iterator __new_finish = _M_finish - __n; 01118 _Destroy(__new_finish, _M_finish); 01119 _M_destroy_nodes(__new_finish._M_node + 1, _M_finish._M_node + 1); 01120 _M_finish = __new_finish; 01121 } 01122 return _M_start + __elems_before; 01123 } 01124 } 01125 01126 template <class _Tp, class _Alloc> 01127 void deque<_Tp,_Alloc>::clear() 01128 { 01129 for (_Map_pointer __node = _M_start._M_node + 1; 01130 __node < _M_finish._M_node; 01131 ++__node) { 01132 _Destroy(*__node, *__node + _S_buffer_size()); 01133 _M_deallocate_node(*__node); 01134 } 01135 01136 if (_M_start._M_node != _M_finish._M_node) { 01137 _Destroy(_M_start._M_cur, _M_start._M_last); 01138 _Destroy(_M_finish._M_first, _M_finish._M_cur); 01139 _M_deallocate_node(_M_finish._M_first); 01140 } 01141 else 01142 _Destroy(_M_start._M_cur, _M_finish._M_cur); 01143 01144 _M_finish = _M_start; 01145 } 01146 01159 template <class _Tp, class _Alloc> 01160 void deque<_Tp,_Alloc>::_M_fill_initialize(const value_type& __value) 01161 { 01162 _Map_pointer __cur; 01163 try { 01164 for (__cur = _M_start._M_node; __cur < _M_finish._M_node; ++__cur) 01165 uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value); 01166 uninitialized_fill(_M_finish._M_first, _M_finish._M_cur, __value); 01167 } 01168 catch(...) 01169 { 01170 _Destroy(_M_start, iterator(*__cur, __cur)); 01171 __throw_exception_again; 01172 } 01173 } 01174 01187 template <class _Tp, class _Alloc> template <class _InputIterator> 01188 void deque<_Tp,_Alloc>::_M_range_initialize(_InputIterator __first, 01189 _InputIterator __last, 01190 input_iterator_tag) 01191 { 01192 _M_initialize_map(0); 01193 try { 01194 for ( ; __first != __last; ++__first) 01195 push_back(*__first); 01196 } 01197 catch(...) 01198 { 01199 clear(); 01200 __throw_exception_again; 01201 } 01202 } 01203 01204 template <class _Tp, class _Alloc> template <class _ForwardIterator> 01205 void deque<_Tp,_Alloc>::_M_range_initialize(_ForwardIterator __first, 01206 _ForwardIterator __last, 01207 forward_iterator_tag) 01208 { 01209 size_type __n = distance(__first, __last); 01210 _M_initialize_map(__n); 01211 01212 _Map_pointer __cur_node; 01213 try { 01214 for (__cur_node = _M_start._M_node; 01215 __cur_node < _M_finish._M_node; 01216 ++__cur_node) { 01217 _ForwardIterator __mid = __first; 01218 advance(__mid, _S_buffer_size()); 01219 uninitialized_copy(__first, __mid, *__cur_node); 01220 __first = __mid; 01221 } 01222 uninitialized_copy(__first, __last, _M_finish._M_first); 01223 } 01224 catch(...) 01225 { 01226 _Destroy(_M_start, iterator(*__cur_node, __cur_node)); 01227 __throw_exception_again; 01228 } 01229 } 01232 // Called only if _M_finish._M_cur == _M_finish._M_last - 1. 01233 template <class _Tp, class _Alloc> 01234 void 01235 deque<_Tp,_Alloc>::_M_push_back_aux(const value_type& __t) 01236 { 01237 value_type __t_copy = __t; 01238 _M_reserve_map_at_back(); 01239 *(_M_finish._M_node + 1) = _M_allocate_node(); 01240 try { 01241 _Construct(_M_finish._M_cur, __t_copy); 01242 _M_finish._M_set_node(_M_finish._M_node + 1); 01243 _M_finish._M_cur = _M_finish._M_first; 01244 } 01245 catch(...) 01246 { 01247 _M_deallocate_node(*(_M_finish._M_node + 1)); 01248 __throw_exception_again; 01249 } 01250 } 01251 01252 // Called only if _M_finish._M_cur == _M_finish._M_last - 1. 01253 template <class _Tp, class _Alloc> 01254 void 01255 deque<_Tp,_Alloc>::_M_push_back_aux() 01256 { 01257 _M_reserve_map_at_back(); 01258 *(_M_finish._M_node + 1) = _M_allocate_node(); 01259 try { 01260 _Construct(_M_finish._M_cur); 01261 _M_finish._M_set_node(_M_finish._M_node + 1); 01262 _M_finish._M_cur = _M_finish._M_first; 01263 } 01264 catch(...) 01265 { 01266 _M_deallocate_node(*(_M_finish._M_node + 1)); 01267 __throw_exception_again; 01268 } 01269 } 01270 01271 // Called only if _M_start._M_cur == _M_start._M_first. 01272 template <class _Tp, class _Alloc> 01273 void 01274 deque<_Tp,_Alloc>::_M_push_front_aux(const value_type& __t) 01275 { 01276 value_type __t_copy = __t; 01277 _M_reserve_map_at_front(); 01278 *(_M_start._M_node - 1) = _M_allocate_node(); 01279 try { 01280 _M_start._M_set_node(_M_start._M_node - 1); 01281 _M_start._M_cur = _M_start._M_last - 1; 01282 _Construct(_M_start._M_cur, __t_copy); 01283 } 01284 catch(...) 01285 { 01286 ++_M_start; 01287 _M_deallocate_node(*(_M_start._M_node - 1)); 01288 __throw_exception_again; 01289 } 01290 } 01291 01292 // Called only if _M_start._M_cur == _M_start._M_first. 01293 template <class _Tp, class _Alloc> 01294 void 01295 deque<_Tp,_Alloc>::_M_push_front_aux() 01296 { 01297 _M_reserve_map_at_front(); 01298 *(_M_start._M_node - 1) = _M_allocate_node(); 01299 try { 01300 _M_start._M_set_node(_M_start._M_node - 1); 01301 _M_start._M_cur = _M_start._M_last - 1; 01302 _Construct(_M_start._M_cur); 01303 } 01304 catch(...) 01305 { 01306 ++_M_start; 01307 _M_deallocate_node(*(_M_start._M_node - 1)); 01308 __throw_exception_again; 01309 } 01310 } 01311 01312 // Called only if _M_finish._M_cur == _M_finish._M_first. 01313 template <class _Tp, class _Alloc> 01314 void deque<_Tp,_Alloc>::_M_pop_back_aux() 01315 { 01316 _M_deallocate_node(_M_finish._M_first); 01317 _M_finish._M_set_node(_M_finish._M_node - 1); 01318 _M_finish._M_cur = _M_finish._M_last - 1; 01319 _Destroy(_M_finish._M_cur); 01320 } 01321 01322 // Called only if _M_start._M_cur == _M_start._M_last - 1. Note that 01323 // if the deque has at least one element (a precondition for this member 01324 // function), and if _M_start._M_cur == _M_start._M_last, then the deque 01325 // must have at least two nodes. 01326 template <class _Tp, class _Alloc> 01327 void deque<_Tp,_Alloc>::_M_pop_front_aux() 01328 { 01329 _Destroy(_M_start._M_cur); 01330 _M_deallocate_node(_M_start._M_first); 01331 _M_start._M_set_node(_M_start._M_node + 1); 01332 _M_start._M_cur = _M_start._M_first; 01333 } 01334 01335 template <class _Tp, class _Alloc> template <class _InputIterator> 01336 void deque<_Tp,_Alloc>::insert(iterator __pos, 01337 _InputIterator __first, _InputIterator __last, 01338 input_iterator_tag) 01339 { 01340 copy(__first, __last, inserter(*this, __pos)); 01341 } 01342 01343 template <class _Tp, class _Alloc> template <class _ForwardIterator> 01344 void 01345 deque<_Tp,_Alloc>::insert(iterator __pos, 01346 _ForwardIterator __first, _ForwardIterator __last, 01347 forward_iterator_tag) { 01348 size_type __n = distance(__first, __last); 01349 if (__pos._M_cur == _M_start._M_cur) { 01350 iterator __new_start = _M_reserve_elements_at_front(__n); 01351 try { 01352 uninitialized_copy(__first, __last, __new_start); 01353 _M_start = __new_start; 01354 } 01355 catch(...) 01356 { 01357 _M_destroy_nodes(__new_start._M_node, _M_start._M_node); 01358 __throw_exception_again; 01359 } 01360 } 01361 else if (__pos._M_cur == _M_finish._M_cur) { 01362 iterator __new_finish = _M_reserve_elements_at_back(__n); 01363 try { 01364 uninitialized_copy(__first, __last, _M_finish); 01365 _M_finish = __new_finish; 01366 } 01367 catch(...) 01368 { 01369 _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1); 01370 __throw_exception_again; 01371 } 01372 } 01373 else 01374 _M_insert_aux(__pos, __first, __last, __n); 01375 } 01376 01377 template <class _Tp, class _Alloc> 01378 typename deque<_Tp, _Alloc>::iterator 01379 deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, const value_type& __x) 01380 { 01381 difference_type __index = __pos - _M_start; 01382 value_type __x_copy = __x; 01383 if (static_cast<size_type>(__index) < size() / 2) { 01384 push_front(front()); 01385 iterator __front1 = _M_start; 01386 ++__front1; 01387 iterator __front2 = __front1; 01388 ++__front2; 01389 __pos = _M_start + __index; 01390 iterator __pos1 = __pos; 01391 ++__pos1; 01392 copy(__front2, __pos1, __front1); 01393 } 01394 else { 01395 push_back(back()); 01396 iterator __back1 = _M_finish; 01397 --__back1; 01398 iterator __back2 = __back1; 01399 --__back2; 01400 __pos = _M_start + __index; 01401 copy_backward(__pos, __back2, __back1); 01402 } 01403 *__pos = __x_copy; 01404 return __pos; 01405 } 01406 01407 template <class _Tp, class _Alloc> 01408 typename deque<_Tp,_Alloc>::iterator 01409 deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos) 01410 { 01411 difference_type __index = __pos - _M_start; 01412 if (static_cast<size_type>(__index) < size() / 2) { 01413 push_front(front()); 01414 iterator __front1 = _M_start; 01415 ++__front1; 01416 iterator __front2 = __front1; 01417 ++__front2; 01418 __pos = _M_start + __index; 01419 iterator __pos1 = __pos; 01420 ++__pos1; 01421 copy(__front2, __pos1, __front1); 01422 } 01423 else { 01424 push_back(back()); 01425 iterator __back1 = _M_finish; 01426 --__back1; 01427 iterator __back2 = __back1; 01428 --__back2; 01429 __pos = _M_start + __index; 01430 copy_backward(__pos, __back2, __back1); 01431 } 01432 *__pos = value_type(); 01433 return __pos; 01434 } 01435 01436 template <class _Tp, class _Alloc> 01437 void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, 01438 size_type __n, 01439 const value_type& __x) 01440 { 01441 const difference_type __elems_before = __pos - _M_start; 01442 size_type __length = this->size(); 01443 value_type __x_copy = __x; 01444 if (__elems_before < difference_type(__length / 2)) { 01445 iterator __new_start = _M_reserve_elements_at_front(__n); 01446 iterator __old_start = _M_start; 01447 __pos = _M_start + __elems_before; 01448 try { 01449 if (__elems_before >= difference_type(__n)) { 01450 iterator __start_n = _M_start + difference_type(__n); 01451 uninitialized_copy(_M_start, __start_n, __new_start); 01452 _M_start = __new_start; 01453 copy(__start_n, __pos, __old_start); 01454 fill(__pos - difference_type(__n), __pos, __x_copy); 01455 } 01456 else { 01457 __uninitialized_copy_fill(_M_start, __pos, __new_start, 01458 _M_start, __x_copy); 01459 _M_start = __new_start; 01460 fill(__old_start, __pos, __x_copy); 01461 } 01462 } 01463 catch(...) 01464 { 01465 _M_destroy_nodes(__new_start._M_node, _M_start._M_node); 01466 __throw_exception_again; 01467 } 01468 } 01469 else { 01470 iterator __new_finish = _M_reserve_elements_at_back(__n); 01471 iterator __old_finish = _M_finish; 01472 const difference_type __elems_after = 01473 difference_type(__length) - __elems_before; 01474 __pos = _M_finish - __elems_after; 01475 try { 01476 if (__elems_after > difference_type(__n)) { 01477 iterator __finish_n = _M_finish - difference_type(__n); 01478 uninitialized_copy(__finish_n, _M_finish, _M_finish); 01479 _M_finish = __new_finish; 01480 copy_backward(__pos, __finish_n, __old_finish); 01481 fill(__pos, __pos + difference_type(__n), __x_copy); 01482 } 01483 else { 01484 __uninitialized_fill_copy(_M_finish, __pos + difference_type(__n), 01485 __x_copy, __pos, _M_finish); 01486 _M_finish = __new_finish; 01487 fill(__pos, __old_finish, __x_copy); 01488 } 01489 } 01490 catch(...) 01491 { 01492 _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1); 01493 __throw_exception_again; 01494 } 01495 } 01496 } 01497 01498 template <class _Tp, class _Alloc> template <class _ForwardIterator> 01499 void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, 01500 _ForwardIterator __first, 01501 _ForwardIterator __last, 01502 size_type __n) 01503 { 01504 const difference_type __elemsbefore = __pos - _M_start; 01505 size_type __length = size(); 01506 if (static_cast<size_type>(__elemsbefore) < __length / 2) { 01507 iterator __new_start = _M_reserve_elements_at_front(__n); 01508 iterator __old_start = _M_start; 01509 __pos = _M_start + __elemsbefore; 01510 try { 01511 if (__elemsbefore >= difference_type(__n)) { 01512 iterator __start_n = _M_start + difference_type(__n); 01513 uninitialized_copy(_M_start, __start_n, __new_start); 01514 _M_start = __new_start; 01515 copy(__start_n, __pos, __old_start); 01516 copy(__first, __last, __pos - difference_type(__n)); 01517 } 01518 else { 01519 _ForwardIterator __mid = __first; 01520 advance(__mid, difference_type(__n) - __elemsbefore); 01521 __uninitialized_copy_copy(_M_start, __pos, __first, __mid, 01522 __new_start); 01523 _M_start = __new_start; 01524 copy(__mid, __last, __old_start); 01525 } 01526 } 01527 catch(...) 01528 { 01529 _M_destroy_nodes(__new_start._M_node, _M_start._M_node); 01530 __throw_exception_again; 01531 } 01532 } 01533 else { 01534 iterator __new_finish = _M_reserve_elements_at_back(__n); 01535 iterator __old_finish = _M_finish; 01536 const difference_type __elemsafter = 01537 difference_type(__length) - __elemsbefore; 01538 __pos = _M_finish - __elemsafter; 01539 try { 01540 if (__elemsafter > difference_type(__n)) { 01541 iterator __finish_n = _M_finish - difference_type(__n); 01542 uninitialized_copy(__finish_n, _M_finish, _M_finish); 01543 _M_finish = __new_finish; 01544 copy_backward(__pos, __finish_n, __old_finish); 01545 copy(__first, __last, __pos); 01546 } 01547 else { 01548 _ForwardIterator __mid = __first; 01549 advance(__mid, __elemsafter); 01550 __uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish); 01551 _M_finish = __new_finish; 01552 copy(__first, __mid, __pos); 01553 } 01554 } 01555 catch(...) 01556 { 01557 _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1); 01558 __throw_exception_again; 01559 } 01560 } 01561 } 01562 01563 template <class _Tp, class _Alloc> 01564 void deque<_Tp,_Alloc>::_M_new_elements_at_front(size_type __new_elems) 01565 { 01566 size_type __new_nodes 01567 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size(); 01568 _M_reserve_map_at_front(__new_nodes); 01569 size_type __i; 01570 try { 01571 for (__i = 1; __i <= __new_nodes; ++__i) 01572 *(_M_start._M_node - __i) = _M_allocate_node(); 01573 } 01574 catch(...) { 01575 for (size_type __j = 1; __j < __i; ++__j) 01576 _M_deallocate_node(*(_M_start._M_node - __j)); 01577 __throw_exception_again; 01578 } 01579 } 01580 01581 template <class _Tp, class _Alloc> 01582 void deque<_Tp,_Alloc>::_M_new_elements_at_back(size_type __new_elems) 01583 { 01584 size_type __new_nodes 01585 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size(); 01586 _M_reserve_map_at_back(__new_nodes); 01587 size_type __i; 01588 try { 01589 for (__i = 1; __i <= __new_nodes; ++__i) 01590 *(_M_finish._M_node + __i) = _M_allocate_node(); 01591 } 01592 catch(...) { 01593 for (size_type __j = 1; __j < __i; ++__j) 01594 _M_deallocate_node(*(_M_finish._M_node + __j)); 01595 __throw_exception_again; 01596 } 01597 } 01598 01599 template <class _Tp, class _Alloc> 01600 void deque<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add, 01601 bool __add_at_front) 01602 { 01603 size_type __old_num_nodes = _M_finish._M_node - _M_start._M_node + 1; 01604 size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; 01605 01606 _Map_pointer __new_nstart; 01607 if (_M_map_size > 2 * __new_num_nodes) { 01608 __new_nstart = _M_map + (_M_map_size - __new_num_nodes) / 2 01609 + (__add_at_front ? __nodes_to_add : 0); 01610 if (__new_nstart < _M_start._M_node) 01611 copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart); 01612 else 01613 copy_backward(_M_start._M_node, _M_finish._M_node + 1, 01614 __new_nstart + __old_num_nodes); 01615 } 01616 else { 01617 size_type __new_map_size = 01618 _M_map_size + max(_M_map_size, __nodes_to_add) + 2; 01619 01620 _Map_pointer __new_map = _M_allocate_map(__new_map_size); 01621 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 01622 + (__add_at_front ? __nodes_to_add : 0); 01623 copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart); 01624 _M_deallocate_map(_M_map, _M_map_size); 01625 01626 _M_map = __new_map; 01627 _M_map_size = __new_map_size; 01628 } 01629 01630 _M_start._M_set_node(__new_nstart); 01631 _M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); 01632 } 01633 01634 01635 // Nonmember functions. 01636 01637 template <class _Tp, class _Alloc> 01638 inline bool operator==(const deque<_Tp, _Alloc>& __x, 01639 const deque<_Tp, _Alloc>& __y) { 01640 return __x.size() == __y.size() && 01641 equal(__x.begin(), __x.end(), __y.begin()); 01642 } 01643 01644 template <class _Tp, class _Alloc> 01645 inline bool operator<(const deque<_Tp, _Alloc>& __x, 01646 const deque<_Tp, _Alloc>& __y) { 01647 return lexicographical_compare(__x.begin(), __x.end(), 01648 __y.begin(), __y.end()); 01649 } 01650 01651 template <class _Tp, class _Alloc> 01652 inline bool operator!=(const deque<_Tp, _Alloc>& __x, 01653 const deque<_Tp, _Alloc>& __y) { 01654 return !(__x == __y); 01655 } 01656 01657 template <class _Tp, class _Alloc> 01658 inline bool operator>(const deque<_Tp, _Alloc>& __x, 01659 const deque<_Tp, _Alloc>& __y) { 01660 return __y < __x; 01661 } 01662 01663 template <class _Tp, class _Alloc> 01664 inline bool operator<=(const deque<_Tp, _Alloc>& __x, 01665 const deque<_Tp, _Alloc>& __y) { 01666 return !(__y < __x); 01667 } 01668 template <class _Tp, class _Alloc> 01669 inline bool operator>=(const deque<_Tp, _Alloc>& __x, 01670 const deque<_Tp, _Alloc>& __y) { 01671 return !(__x < __y); 01672 } 01673 01674 template <class _Tp, class _Alloc> 01675 inline void swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y) { 01676 __x.swap(__y); 01677 } 01678 01679 } // namespace std 01680 01681 #endif /* __GLIBCPP_INTERNAL_DEQUE_H */ 01682

Generated on Wed Sep 29 13:54:51 2004 for libstdc++-v3 Source by doxygen 1.3.7