00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057 #ifndef _DEQUE_TCC
00058 #define _DEQUE_TCC 1
00059
00060 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
00061
00062 template <typename _Tp, typename _Alloc>
00063 deque<_Tp, _Alloc>&
00064 deque<_Tp, _Alloc>::
00065 operator=(const deque& __x)
00066 {
00067 const size_type __len = size();
00068 if (&__x != this)
00069 {
00070 if (__len >= __x.size())
00071 _M_erase_at_end(std::copy(__x.begin(), __x.end(),
00072 this->_M_impl._M_start));
00073 else
00074 {
00075 const_iterator __mid = __x.begin() + difference_type(__len);
00076 std::copy(__x.begin(), __mid, this->_M_impl._M_start);
00077 insert(this->_M_impl._M_finish, __mid, __x.end());
00078 }
00079 }
00080 return *this;
00081 }
00082
00083 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00084 template<typename _Tp, typename _Alloc>
00085 template<typename... _Args>
00086 void
00087 deque<_Tp, _Alloc>::
00088 emplace_front(_Args&&... __args)
00089 {
00090 if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
00091 {
00092 this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1,
00093 std::forward<_Args>(__args)...);
00094 --this->_M_impl._M_start._M_cur;
00095 }
00096 else
00097 _M_push_front_aux(std::forward<_Args>(__args)...);
00098 }
00099
00100 template<typename _Tp, typename _Alloc>
00101 template<typename... _Args>
00102 void
00103 deque<_Tp, _Alloc>::
00104 emplace_back(_Args&&... __args)
00105 {
00106 if (this->_M_impl._M_finish._M_cur
00107 != this->_M_impl._M_finish._M_last - 1)
00108 {
00109 this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
00110 std::forward<_Args>(__args)...);
00111 ++this->_M_impl._M_finish._M_cur;
00112 }
00113 else
00114 _M_push_back_aux(std::forward<_Args>(__args)...);
00115 }
00116 #endif
00117
00118 template <typename _Tp, typename _Alloc>
00119 typename deque<_Tp, _Alloc>::iterator
00120 deque<_Tp, _Alloc>::
00121 insert(iterator __position, const value_type& __x)
00122 {
00123 if (__position._M_cur == this->_M_impl._M_start._M_cur)
00124 {
00125 push_front(__x);
00126 return this->_M_impl._M_start;
00127 }
00128 else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
00129 {
00130 push_back(__x);
00131 iterator __tmp = this->_M_impl._M_finish;
00132 --__tmp;
00133 return __tmp;
00134 }
00135 else
00136 return _M_insert_aux(__position, __x);
00137 }
00138
00139 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00140 template<typename _Tp, typename _Alloc>
00141 template<typename... _Args>
00142 typename deque<_Tp, _Alloc>::iterator
00143 deque<_Tp, _Alloc>::
00144 emplace(iterator __position, _Args&&... __args)
00145 {
00146 if (__position._M_cur == this->_M_impl._M_start._M_cur)
00147 {
00148 push_front(std::forward<_Args>(__args)...);
00149 return this->_M_impl._M_start;
00150 }
00151 else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
00152 {
00153 push_back(std::forward<_Args>(__args)...);
00154 iterator __tmp = this->_M_impl._M_finish;
00155 --__tmp;
00156 return __tmp;
00157 }
00158 else
00159 return _M_insert_aux(__position, std::forward<_Args>(__args)...);
00160 }
00161 #endif
00162
00163 template <typename _Tp, typename _Alloc>
00164 typename deque<_Tp, _Alloc>::iterator
00165 deque<_Tp, _Alloc>::
00166 erase(iterator __position)
00167 {
00168 iterator __next = __position;
00169 ++__next;
00170 const difference_type __index = __position - begin();
00171 if (static_cast<size_type>(__index) < (size() >> 1))
00172 {
00173 if (__position != begin())
00174 _GLIBCXX_MOVE_BACKWARD3(begin(), __position, __next);
00175 pop_front();
00176 }
00177 else
00178 {
00179 if (__next != end())
00180 _GLIBCXX_MOVE3(__next, end(), __position);
00181 pop_back();
00182 }
00183 return begin() + __index;
00184 }
00185
00186 template <typename _Tp, typename _Alloc>
00187 typename deque<_Tp, _Alloc>::iterator
00188 deque<_Tp, _Alloc>::
00189 erase(iterator __first, iterator __last)
00190 {
00191 if (__first == begin() && __last == end())
00192 {
00193 clear();
00194 return end();
00195 }
00196 else
00197 {
00198 const difference_type __n = __last - __first;
00199 const difference_type __elems_before = __first - begin();
00200 if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2)
00201 {
00202 if (__first != begin())
00203 _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last);
00204 _M_erase_at_begin(begin() + __n);
00205 }
00206 else
00207 {
00208 if (__last != end())
00209 _GLIBCXX_MOVE3(__last, end(), __first);
00210 _M_erase_at_end(end() - __n);
00211 }
00212 return begin() + __elems_before;
00213 }
00214 }
00215
00216 template <typename _Tp, class _Alloc>
00217 template <typename _InputIterator>
00218 void
00219 deque<_Tp, _Alloc>::
00220 _M_assign_aux(_InputIterator __first, _InputIterator __last,
00221 std::input_iterator_tag)
00222 {
00223 iterator __cur = begin();
00224 for (; __first != __last && __cur != end(); ++__cur, ++__first)
00225 *__cur = *__first;
00226 if (__first == __last)
00227 _M_erase_at_end(__cur);
00228 else
00229 insert(end(), __first, __last);
00230 }
00231
00232 template <typename _Tp, typename _Alloc>
00233 void
00234 deque<_Tp, _Alloc>::
00235 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
00236 {
00237 if (__pos._M_cur == this->_M_impl._M_start._M_cur)
00238 {
00239 iterator __new_start = _M_reserve_elements_at_front(__n);
00240 __try
00241 {
00242 std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
00243 __x, _M_get_Tp_allocator());
00244 this->_M_impl._M_start = __new_start;
00245 }
00246 __catch(...)
00247 {
00248 _M_destroy_nodes(__new_start._M_node,
00249 this->_M_impl._M_start._M_node);
00250 __throw_exception_again;
00251 }
00252 }
00253 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
00254 {
00255 iterator __new_finish = _M_reserve_elements_at_back(__n);
00256 __try
00257 {
00258 std::__uninitialized_fill_a(this->_M_impl._M_finish,
00259 __new_finish, __x,
00260 _M_get_Tp_allocator());
00261 this->_M_impl._M_finish = __new_finish;
00262 }
00263 __catch(...)
00264 {
00265 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
00266 __new_finish._M_node + 1);
00267 __throw_exception_again;
00268 }
00269 }
00270 else
00271 _M_insert_aux(__pos, __n, __x);
00272 }
00273
00274 template <typename _Tp, typename _Alloc>
00275 void
00276 deque<_Tp, _Alloc>::
00277 _M_fill_initialize(const value_type& __value)
00278 {
00279 _Map_pointer __cur;
00280 __try
00281 {
00282 for (__cur = this->_M_impl._M_start._M_node;
00283 __cur < this->_M_impl._M_finish._M_node;
00284 ++__cur)
00285 std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
00286 __value, _M_get_Tp_allocator());
00287 std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
00288 this->_M_impl._M_finish._M_cur,
00289 __value, _M_get_Tp_allocator());
00290 }
00291 __catch(...)
00292 {
00293 std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
00294 _M_get_Tp_allocator());
00295 __throw_exception_again;
00296 }
00297 }
00298
00299 template <typename _Tp, typename _Alloc>
00300 template <typename _InputIterator>
00301 void
00302 deque<_Tp, _Alloc>::
00303 _M_range_initialize(_InputIterator __first, _InputIterator __last,
00304 std::input_iterator_tag)
00305 {
00306 this->_M_initialize_map(0);
00307 __try
00308 {
00309 for (; __first != __last; ++__first)
00310 push_back(*__first);
00311 }
00312 __catch(...)
00313 {
00314 clear();
00315 __throw_exception_again;
00316 }
00317 }
00318
00319 template <typename _Tp, typename _Alloc>
00320 template <typename _ForwardIterator>
00321 void
00322 deque<_Tp, _Alloc>::
00323 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
00324 std::forward_iterator_tag)
00325 {
00326 const size_type __n = std::distance(__first, __last);
00327 this->_M_initialize_map(__n);
00328
00329 _Map_pointer __cur_node;
00330 __try
00331 {
00332 for (__cur_node = this->_M_impl._M_start._M_node;
00333 __cur_node < this->_M_impl._M_finish._M_node;
00334 ++__cur_node)
00335 {
00336 _ForwardIterator __mid = __first;
00337 std::advance(__mid, _S_buffer_size());
00338 std::__uninitialized_copy_a(__first, __mid, *__cur_node,
00339 _M_get_Tp_allocator());
00340 __first = __mid;
00341 }
00342 std::__uninitialized_copy_a(__first, __last,
00343 this->_M_impl._M_finish._M_first,
00344 _M_get_Tp_allocator());
00345 }
00346 __catch(...)
00347 {
00348 std::_Destroy(this->_M_impl._M_start,
00349 iterator(*__cur_node, __cur_node),
00350 _M_get_Tp_allocator());
00351 __throw_exception_again;
00352 }
00353 }
00354
00355
00356 template<typename _Tp, typename _Alloc>
00357 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00358 template<typename... _Args>
00359 void
00360 deque<_Tp, _Alloc>::
00361 _M_push_back_aux(_Args&&... __args)
00362 #else
00363 void
00364 deque<_Tp, _Alloc>::
00365 _M_push_back_aux(const value_type& __t)
00366 #endif
00367 {
00368 _M_reserve_map_at_back();
00369 *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
00370 __try
00371 {
00372 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00373 this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
00374 std::forward<_Args>(__args)...);
00375 #else
00376 this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t);
00377 #endif
00378 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
00379 + 1);
00380 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
00381 }
00382 __catch(...)
00383 {
00384 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
00385 __throw_exception_again;
00386 }
00387 }
00388
00389
00390 template<typename _Tp, typename _Alloc>
00391 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00392 template<typename... _Args>
00393 void
00394 deque<_Tp, _Alloc>::
00395 _M_push_front_aux(_Args&&... __args)
00396 #else
00397 void
00398 deque<_Tp, _Alloc>::
00399 _M_push_front_aux(const value_type& __t)
00400 #endif
00401 {
00402 _M_reserve_map_at_front();
00403 *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
00404 __try
00405 {
00406 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
00407 - 1);
00408 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
00409 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00410 this->_M_impl.construct(this->_M_impl._M_start._M_cur,
00411 std::forward<_Args>(__args)...);
00412 #else
00413 this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t);
00414 #endif
00415 }
00416 __catch(...)
00417 {
00418 ++this->_M_impl._M_start;
00419 _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
00420 __throw_exception_again;
00421 }
00422 }
00423
00424
00425 template <typename _Tp, typename _Alloc>
00426 void deque<_Tp, _Alloc>::
00427 _M_pop_back_aux()
00428 {
00429 _M_deallocate_node(this->_M_impl._M_finish._M_first);
00430 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
00431 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
00432 this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
00433 }
00434
00435
00436
00437
00438
00439
00440 template <typename _Tp, typename _Alloc>
00441 void deque<_Tp, _Alloc>::
00442 _M_pop_front_aux()
00443 {
00444 this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
00445 _M_deallocate_node(this->_M_impl._M_start._M_first);
00446 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
00447 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
00448 }
00449
00450 template <typename _Tp, typename _Alloc>
00451 template <typename _InputIterator>
00452 void
00453 deque<_Tp, _Alloc>::
00454 _M_range_insert_aux(iterator __pos,
00455 _InputIterator __first, _InputIterator __last,
00456 std::input_iterator_tag)
00457 { std::copy(__first, __last, std::inserter(*this, __pos)); }
00458
00459 template <typename _Tp, typename _Alloc>
00460 template <typename _ForwardIterator>
00461 void
00462 deque<_Tp, _Alloc>::
00463 _M_range_insert_aux(iterator __pos,
00464 _ForwardIterator __first, _ForwardIterator __last,
00465 std::forward_iterator_tag)
00466 {
00467 const size_type __n = std::distance(__first, __last);
00468 if (__pos._M_cur == this->_M_impl._M_start._M_cur)
00469 {
00470 iterator __new_start = _M_reserve_elements_at_front(__n);
00471 __try
00472 {
00473 std::__uninitialized_copy_a(__first, __last, __new_start,
00474 _M_get_Tp_allocator());
00475 this->_M_impl._M_start = __new_start;
00476 }
00477 __catch(...)
00478 {
00479 _M_destroy_nodes(__new_start._M_node,
00480 this->_M_impl._M_start._M_node);
00481 __throw_exception_again;
00482 }
00483 }
00484 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
00485 {
00486 iterator __new_finish = _M_reserve_elements_at_back(__n);
00487 __try
00488 {
00489 std::__uninitialized_copy_a(__first, __last,
00490 this->_M_impl._M_finish,
00491 _M_get_Tp_allocator());
00492 this->_M_impl._M_finish = __new_finish;
00493 }
00494 __catch(...)
00495 {
00496 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
00497 __new_finish._M_node + 1);
00498 __throw_exception_again;
00499 }
00500 }
00501 else
00502 _M_insert_aux(__pos, __first, __last, __n);
00503 }
00504
00505 template<typename _Tp, typename _Alloc>
00506 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00507 template<typename... _Args>
00508 typename deque<_Tp, _Alloc>::iterator
00509 deque<_Tp, _Alloc>::
00510 _M_insert_aux(iterator __pos, _Args&&... __args)
00511 {
00512 value_type __x_copy(std::forward<_Args>(__args)...);
00513 #else
00514 typename deque<_Tp, _Alloc>::iterator
00515 deque<_Tp, _Alloc>::
00516 _M_insert_aux(iterator __pos, const value_type& __x)
00517 {
00518 value_type __x_copy = __x;
00519 #endif
00520 difference_type __index = __pos - this->_M_impl._M_start;
00521 if (static_cast<size_type>(__index) < size() / 2)
00522 {
00523 push_front(_GLIBCXX_MOVE(front()));
00524 iterator __front1 = this->_M_impl._M_start;
00525 ++__front1;
00526 iterator __front2 = __front1;
00527 ++__front2;
00528 __pos = this->_M_impl._M_start + __index;
00529 iterator __pos1 = __pos;
00530 ++__pos1;
00531 _GLIBCXX_MOVE3(__front2, __pos1, __front1);
00532 }
00533 else
00534 {
00535 push_back(_GLIBCXX_MOVE(back()));
00536 iterator __back1 = this->_M_impl._M_finish;
00537 --__back1;
00538 iterator __back2 = __back1;
00539 --__back2;
00540 __pos = this->_M_impl._M_start + __index;
00541 _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
00542 }
00543 *__pos = _GLIBCXX_MOVE(__x_copy);
00544 return __pos;
00545 }
00546
00547 template <typename _Tp, typename _Alloc>
00548 void
00549 deque<_Tp, _Alloc>::
00550 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
00551 {
00552 const difference_type __elems_before = __pos - this->_M_impl._M_start;
00553 const size_type __length = this->size();
00554 value_type __x_copy = __x;
00555 if (__elems_before < difference_type(__length / 2))
00556 {
00557 iterator __new_start = _M_reserve_elements_at_front(__n);
00558 iterator __old_start = this->_M_impl._M_start;
00559 __pos = this->_M_impl._M_start + __elems_before;
00560 __try
00561 {
00562 if (__elems_before >= difference_type(__n))
00563 {
00564 iterator __start_n = (this->_M_impl._M_start
00565 + difference_type(__n));
00566 std::__uninitialized_move_a(this->_M_impl._M_start,
00567 __start_n, __new_start,
00568 _M_get_Tp_allocator());
00569 this->_M_impl._M_start = __new_start;
00570 _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
00571 std::fill(__pos - difference_type(__n), __pos, __x_copy);
00572 }
00573 else
00574 {
00575 std::__uninitialized_move_fill(this->_M_impl._M_start,
00576 __pos, __new_start,
00577 this->_M_impl._M_start,
00578 __x_copy,
00579 _M_get_Tp_allocator());
00580 this->_M_impl._M_start = __new_start;
00581 std::fill(__old_start, __pos, __x_copy);
00582 }
00583 }
00584 __catch(...)
00585 {
00586 _M_destroy_nodes(__new_start._M_node,
00587 this->_M_impl._M_start._M_node);
00588 __throw_exception_again;
00589 }
00590 }
00591 else
00592 {
00593 iterator __new_finish = _M_reserve_elements_at_back(__n);
00594 iterator __old_finish = this->_M_impl._M_finish;
00595 const difference_type __elems_after =
00596 difference_type(__length) - __elems_before;
00597 __pos = this->_M_impl._M_finish - __elems_after;
00598 __try
00599 {
00600 if (__elems_after > difference_type(__n))
00601 {
00602 iterator __finish_n = (this->_M_impl._M_finish
00603 - difference_type(__n));
00604 std::__uninitialized_move_a(__finish_n,
00605 this->_M_impl._M_finish,
00606 this->_M_impl._M_finish,
00607 _M_get_Tp_allocator());
00608 this->_M_impl._M_finish = __new_finish;
00609 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
00610 std::fill(__pos, __pos + difference_type(__n), __x_copy);
00611 }
00612 else
00613 {
00614 std::__uninitialized_fill_move(this->_M_impl._M_finish,
00615 __pos + difference_type(__n),
00616 __x_copy, __pos,
00617 this->_M_impl._M_finish,
00618 _M_get_Tp_allocator());
00619 this->_M_impl._M_finish = __new_finish;
00620 std::fill(__pos, __old_finish, __x_copy);
00621 }
00622 }
00623 __catch(...)
00624 {
00625 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
00626 __new_finish._M_node + 1);
00627 __throw_exception_again;
00628 }
00629 }
00630 }
00631
00632 template <typename _Tp, typename _Alloc>
00633 template <typename _ForwardIterator>
00634 void
00635 deque<_Tp, _Alloc>::
00636 _M_insert_aux(iterator __pos,
00637 _ForwardIterator __first, _ForwardIterator __last,
00638 size_type __n)
00639 {
00640 const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
00641 const size_type __length = size();
00642 if (static_cast<size_type>(__elemsbefore) < __length / 2)
00643 {
00644 iterator __new_start = _M_reserve_elements_at_front(__n);
00645 iterator __old_start = this->_M_impl._M_start;
00646 __pos = this->_M_impl._M_start + __elemsbefore;
00647 __try
00648 {
00649 if (__elemsbefore >= difference_type(__n))
00650 {
00651 iterator __start_n = (this->_M_impl._M_start
00652 + difference_type(__n));
00653 std::__uninitialized_move_a(this->_M_impl._M_start,
00654 __start_n, __new_start,
00655 _M_get_Tp_allocator());
00656 this->_M_impl._M_start = __new_start;
00657 _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
00658 std::copy(__first, __last, __pos - difference_type(__n));
00659 }
00660 else
00661 {
00662 _ForwardIterator __mid = __first;
00663 std::advance(__mid, difference_type(__n) - __elemsbefore);
00664 std::__uninitialized_move_copy(this->_M_impl._M_start,
00665 __pos, __first, __mid,
00666 __new_start,
00667 _M_get_Tp_allocator());
00668 this->_M_impl._M_start = __new_start;
00669 std::copy(__mid, __last, __old_start);
00670 }
00671 }
00672 __catch(...)
00673 {
00674 _M_destroy_nodes(__new_start._M_node,
00675 this->_M_impl._M_start._M_node);
00676 __throw_exception_again;
00677 }
00678 }
00679 else
00680 {
00681 iterator __new_finish = _M_reserve_elements_at_back(__n);
00682 iterator __old_finish = this->_M_impl._M_finish;
00683 const difference_type __elemsafter =
00684 difference_type(__length) - __elemsbefore;
00685 __pos = this->_M_impl._M_finish - __elemsafter;
00686 __try
00687 {
00688 if (__elemsafter > difference_type(__n))
00689 {
00690 iterator __finish_n = (this->_M_impl._M_finish
00691 - difference_type(__n));
00692 std::__uninitialized_move_a(__finish_n,
00693 this->_M_impl._M_finish,
00694 this->_M_impl._M_finish,
00695 _M_get_Tp_allocator());
00696 this->_M_impl._M_finish = __new_finish;
00697 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
00698 std::copy(__first, __last, __pos);
00699 }
00700 else
00701 {
00702 _ForwardIterator __mid = __first;
00703 std::advance(__mid, __elemsafter);
00704 std::__uninitialized_copy_move(__mid, __last, __pos,
00705 this->_M_impl._M_finish,
00706 this->_M_impl._M_finish,
00707 _M_get_Tp_allocator());
00708 this->_M_impl._M_finish = __new_finish;
00709 std::copy(__first, __mid, __pos);
00710 }
00711 }
00712 __catch(...)
00713 {
00714 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
00715 __new_finish._M_node + 1);
00716 __throw_exception_again;
00717 }
00718 }
00719 }
00720
00721 template<typename _Tp, typename _Alloc>
00722 void
00723 deque<_Tp, _Alloc>::
00724 _M_destroy_data_aux(iterator __first, iterator __last)
00725 {
00726 for (_Map_pointer __node = __first._M_node + 1;
00727 __node < __last._M_node; ++__node)
00728 std::_Destroy(*__node, *__node + _S_buffer_size(),
00729 _M_get_Tp_allocator());
00730
00731 if (__first._M_node != __last._M_node)
00732 {
00733 std::_Destroy(__first._M_cur, __first._M_last,
00734 _M_get_Tp_allocator());
00735 std::_Destroy(__last._M_first, __last._M_cur,
00736 _M_get_Tp_allocator());
00737 }
00738 else
00739 std::_Destroy(__first._M_cur, __last._M_cur,
00740 _M_get_Tp_allocator());
00741 }
00742
00743 template <typename _Tp, typename _Alloc>
00744 void
00745 deque<_Tp, _Alloc>::
00746 _M_new_elements_at_front(size_type __new_elems)
00747 {
00748 if (this->max_size() - this->size() < __new_elems)
00749 __throw_length_error(__N("deque::_M_new_elements_at_front"));
00750
00751 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
00752 / _S_buffer_size());
00753 _M_reserve_map_at_front(__new_nodes);
00754 size_type __i;
00755 __try
00756 {
00757 for (__i = 1; __i <= __new_nodes; ++__i)
00758 *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
00759 }
00760 __catch(...)
00761 {
00762 for (size_type __j = 1; __j < __i; ++__j)
00763 _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
00764 __throw_exception_again;
00765 }
00766 }
00767
00768 template <typename _Tp, typename _Alloc>
00769 void
00770 deque<_Tp, _Alloc>::
00771 _M_new_elements_at_back(size_type __new_elems)
00772 {
00773 if (this->max_size() - this->size() < __new_elems)
00774 __throw_length_error(__N("deque::_M_new_elements_at_back"));
00775
00776 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
00777 / _S_buffer_size());
00778 _M_reserve_map_at_back(__new_nodes);
00779 size_type __i;
00780 __try
00781 {
00782 for (__i = 1; __i <= __new_nodes; ++__i)
00783 *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
00784 }
00785 __catch(...)
00786 {
00787 for (size_type __j = 1; __j < __i; ++__j)
00788 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
00789 __throw_exception_again;
00790 }
00791 }
00792
00793 template <typename _Tp, typename _Alloc>
00794 void
00795 deque<_Tp, _Alloc>::
00796 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
00797 {
00798 const size_type __old_num_nodes
00799 = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
00800 const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
00801
00802 _Map_pointer __new_nstart;
00803 if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
00804 {
00805 __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
00806 - __new_num_nodes) / 2
00807 + (__add_at_front ? __nodes_to_add : 0);
00808 if (__new_nstart < this->_M_impl._M_start._M_node)
00809 std::copy(this->_M_impl._M_start._M_node,
00810 this->_M_impl._M_finish._M_node + 1,
00811 __new_nstart);
00812 else
00813 std::copy_backward(this->_M_impl._M_start._M_node,
00814 this->_M_impl._M_finish._M_node + 1,
00815 __new_nstart + __old_num_nodes);
00816 }
00817 else
00818 {
00819 size_type __new_map_size = this->_M_impl._M_map_size
00820 + std::max(this->_M_impl._M_map_size,
00821 __nodes_to_add) + 2;
00822
00823 _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
00824 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
00825 + (__add_at_front ? __nodes_to_add : 0);
00826 std::copy(this->_M_impl._M_start._M_node,
00827 this->_M_impl._M_finish._M_node + 1,
00828 __new_nstart);
00829 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
00830
00831 this->_M_impl._M_map = __new_map;
00832 this->_M_impl._M_map_size = __new_map_size;
00833 }
00834
00835 this->_M_impl._M_start._M_set_node(__new_nstart);
00836 this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
00837 }
00838
00839
00840
00841 template<typename _Tp>
00842 void
00843 fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
00844 const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value)
00845 {
00846 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
00847
00848 for (typename _Self::_Map_pointer __node = __first._M_node + 1;
00849 __node < __last._M_node; ++__node)
00850 std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
00851
00852 if (__first._M_node != __last._M_node)
00853 {
00854 std::fill(__first._M_cur, __first._M_last, __value);
00855 std::fill(__last._M_first, __last._M_cur, __value);
00856 }
00857 else
00858 std::fill(__first._M_cur, __last._M_cur, __value);
00859 }
00860
00861 _GLIBCXX_END_NESTED_NAMESPACE
00862
00863 #endif