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
00058 #ifndef _DEQUE_TCC
00059 #define _DEQUE_TCC 1
00060
00061 namespace std _GLIBCXX_VISIBILITY(default)
00062 {
00063 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
00064
00065 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00066 template <typename _Tp, typename _Alloc>
00067 void
00068 deque<_Tp, _Alloc>::
00069 _M_default_initialize()
00070 {
00071 _Map_pointer __cur;
00072 __try
00073 {
00074 for (__cur = this->_M_impl._M_start._M_node;
00075 __cur < this->_M_impl._M_finish._M_node;
00076 ++__cur)
00077 std::__uninitialized_default_a(*__cur, *__cur + _S_buffer_size(),
00078 _M_get_Tp_allocator());
00079 std::__uninitialized_default_a(this->_M_impl._M_finish._M_first,
00080 this->_M_impl._M_finish._M_cur,
00081 _M_get_Tp_allocator());
00082 }
00083 __catch(...)
00084 {
00085 std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
00086 _M_get_Tp_allocator());
00087 __throw_exception_again;
00088 }
00089 }
00090 #endif
00091
00092 template <typename _Tp, typename _Alloc>
00093 deque<_Tp, _Alloc>&
00094 deque<_Tp, _Alloc>::
00095 operator=(const deque& __x)
00096 {
00097 const size_type __len = size();
00098 if (&__x != this)
00099 {
00100 if (__len >= __x.size())
00101 _M_erase_at_end(std::copy(__x.begin(), __x.end(),
00102 this->_M_impl._M_start));
00103 else
00104 {
00105 const_iterator __mid = __x.begin() + difference_type(__len);
00106 std::copy(__x.begin(), __mid, this->_M_impl._M_start);
00107 insert(this->_M_impl._M_finish, __mid, __x.end());
00108 }
00109 }
00110 return *this;
00111 }
00112
00113 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00114 template<typename _Tp, typename _Alloc>
00115 template<typename... _Args>
00116 void
00117 deque<_Tp, _Alloc>::
00118 emplace_front(_Args&&... __args)
00119 {
00120 if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
00121 {
00122 this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1,
00123 std::forward<_Args>(__args)...);
00124 --this->_M_impl._M_start._M_cur;
00125 }
00126 else
00127 _M_push_front_aux(std::forward<_Args>(__args)...);
00128 }
00129
00130 template<typename _Tp, typename _Alloc>
00131 template<typename... _Args>
00132 void
00133 deque<_Tp, _Alloc>::
00134 emplace_back(_Args&&... __args)
00135 {
00136 if (this->_M_impl._M_finish._M_cur
00137 != this->_M_impl._M_finish._M_last - 1)
00138 {
00139 this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
00140 std::forward<_Args>(__args)...);
00141 ++this->_M_impl._M_finish._M_cur;
00142 }
00143 else
00144 _M_push_back_aux(std::forward<_Args>(__args)...);
00145 }
00146 #endif
00147
00148 template <typename _Tp, typename _Alloc>
00149 typename deque<_Tp, _Alloc>::iterator
00150 deque<_Tp, _Alloc>::
00151 insert(iterator __position, const value_type& __x)
00152 {
00153 if (__position._M_cur == this->_M_impl._M_start._M_cur)
00154 {
00155 push_front(__x);
00156 return this->_M_impl._M_start;
00157 }
00158 else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
00159 {
00160 push_back(__x);
00161 iterator __tmp = this->_M_impl._M_finish;
00162 --__tmp;
00163 return __tmp;
00164 }
00165 else
00166 return _M_insert_aux(__position, __x);
00167 }
00168
00169 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00170 template<typename _Tp, typename _Alloc>
00171 template<typename... _Args>
00172 typename deque<_Tp, _Alloc>::iterator
00173 deque<_Tp, _Alloc>::
00174 emplace(iterator __position, _Args&&... __args)
00175 {
00176 if (__position._M_cur == this->_M_impl._M_start._M_cur)
00177 {
00178 push_front(std::forward<_Args>(__args)...);
00179 return this->_M_impl._M_start;
00180 }
00181 else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
00182 {
00183 push_back(std::forward<_Args>(__args)...);
00184 iterator __tmp = this->_M_impl._M_finish;
00185 --__tmp;
00186 return __tmp;
00187 }
00188 else
00189 return _M_insert_aux(__position, std::forward<_Args>(__args)...);
00190 }
00191 #endif
00192
00193 template <typename _Tp, typename _Alloc>
00194 typename deque<_Tp, _Alloc>::iterator
00195 deque<_Tp, _Alloc>::
00196 erase(iterator __position)
00197 {
00198 iterator __next = __position;
00199 ++__next;
00200 const difference_type __index = __position - begin();
00201 if (static_cast<size_type>(__index) < (size() >> 1))
00202 {
00203 if (__position != begin())
00204 _GLIBCXX_MOVE_BACKWARD3(begin(), __position, __next);
00205 pop_front();
00206 }
00207 else
00208 {
00209 if (__next != end())
00210 _GLIBCXX_MOVE3(__next, end(), __position);
00211 pop_back();
00212 }
00213 return begin() + __index;
00214 }
00215
00216 template <typename _Tp, typename _Alloc>
00217 typename deque<_Tp, _Alloc>::iterator
00218 deque<_Tp, _Alloc>::
00219 erase(iterator __first, iterator __last)
00220 {
00221 if (__first == begin() && __last == end())
00222 {
00223 clear();
00224 return end();
00225 }
00226 else
00227 {
00228 const difference_type __n = __last - __first;
00229 const difference_type __elems_before = __first - begin();
00230 if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2)
00231 {
00232 if (__first != begin())
00233 _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last);
00234 _M_erase_at_begin(begin() + __n);
00235 }
00236 else
00237 {
00238 if (__last != end())
00239 _GLIBCXX_MOVE3(__last, end(), __first);
00240 _M_erase_at_end(end() - __n);
00241 }
00242 return begin() + __elems_before;
00243 }
00244 }
00245
00246 template <typename _Tp, class _Alloc>
00247 template <typename _InputIterator>
00248 void
00249 deque<_Tp, _Alloc>::
00250 _M_assign_aux(_InputIterator __first, _InputIterator __last,
00251 std::input_iterator_tag)
00252 {
00253 iterator __cur = begin();
00254 for (; __first != __last && __cur != end(); ++__cur, ++__first)
00255 *__cur = *__first;
00256 if (__first == __last)
00257 _M_erase_at_end(__cur);
00258 else
00259 insert(end(), __first, __last);
00260 }
00261
00262 template <typename _Tp, typename _Alloc>
00263 void
00264 deque<_Tp, _Alloc>::
00265 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
00266 {
00267 if (__pos._M_cur == this->_M_impl._M_start._M_cur)
00268 {
00269 iterator __new_start = _M_reserve_elements_at_front(__n);
00270 __try
00271 {
00272 std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
00273 __x, _M_get_Tp_allocator());
00274 this->_M_impl._M_start = __new_start;
00275 }
00276 __catch(...)
00277 {
00278 _M_destroy_nodes(__new_start._M_node,
00279 this->_M_impl._M_start._M_node);
00280 __throw_exception_again;
00281 }
00282 }
00283 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
00284 {
00285 iterator __new_finish = _M_reserve_elements_at_back(__n);
00286 __try
00287 {
00288 std::__uninitialized_fill_a(this->_M_impl._M_finish,
00289 __new_finish, __x,
00290 _M_get_Tp_allocator());
00291 this->_M_impl._M_finish = __new_finish;
00292 }
00293 __catch(...)
00294 {
00295 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
00296 __new_finish._M_node + 1);
00297 __throw_exception_again;
00298 }
00299 }
00300 else
00301 _M_insert_aux(__pos, __n, __x);
00302 }
00303
00304 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00305 template <typename _Tp, typename _Alloc>
00306 void
00307 deque<_Tp, _Alloc>::
00308 _M_default_append(size_type __n)
00309 {
00310 if (__n)
00311 {
00312 iterator __new_finish = _M_reserve_elements_at_back(__n);
00313 __try
00314 {
00315 std::__uninitialized_default_a(this->_M_impl._M_finish,
00316 __new_finish,
00317 _M_get_Tp_allocator());
00318 this->_M_impl._M_finish = __new_finish;
00319 }
00320 __catch(...)
00321 {
00322 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
00323 __new_finish._M_node + 1);
00324 __throw_exception_again;
00325 }
00326 }
00327 }
00328 #endif
00329
00330 template <typename _Tp, typename _Alloc>
00331 void
00332 deque<_Tp, _Alloc>::
00333 _M_fill_initialize(const value_type& __value)
00334 {
00335 _Map_pointer __cur;
00336 __try
00337 {
00338 for (__cur = this->_M_impl._M_start._M_node;
00339 __cur < this->_M_impl._M_finish._M_node;
00340 ++__cur)
00341 std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
00342 __value, _M_get_Tp_allocator());
00343 std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
00344 this->_M_impl._M_finish._M_cur,
00345 __value, _M_get_Tp_allocator());
00346 }
00347 __catch(...)
00348 {
00349 std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
00350 _M_get_Tp_allocator());
00351 __throw_exception_again;
00352 }
00353 }
00354
00355 template <typename _Tp, typename _Alloc>
00356 template <typename _InputIterator>
00357 void
00358 deque<_Tp, _Alloc>::
00359 _M_range_initialize(_InputIterator __first, _InputIterator __last,
00360 std::input_iterator_tag)
00361 {
00362 this->_M_initialize_map(0);
00363 __try
00364 {
00365 for (; __first != __last; ++__first)
00366 push_back(*__first);
00367 }
00368 __catch(...)
00369 {
00370 clear();
00371 __throw_exception_again;
00372 }
00373 }
00374
00375 template <typename _Tp, typename _Alloc>
00376 template <typename _ForwardIterator>
00377 void
00378 deque<_Tp, _Alloc>::
00379 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
00380 std::forward_iterator_tag)
00381 {
00382 const size_type __n = std::distance(__first, __last);
00383 this->_M_initialize_map(__n);
00384
00385 _Map_pointer __cur_node;
00386 __try
00387 {
00388 for (__cur_node = this->_M_impl._M_start._M_node;
00389 __cur_node < this->_M_impl._M_finish._M_node;
00390 ++__cur_node)
00391 {
00392 _ForwardIterator __mid = __first;
00393 std::advance(__mid, _S_buffer_size());
00394 std::__uninitialized_copy_a(__first, __mid, *__cur_node,
00395 _M_get_Tp_allocator());
00396 __first = __mid;
00397 }
00398 std::__uninitialized_copy_a(__first, __last,
00399 this->_M_impl._M_finish._M_first,
00400 _M_get_Tp_allocator());
00401 }
00402 __catch(...)
00403 {
00404 std::_Destroy(this->_M_impl._M_start,
00405 iterator(*__cur_node, __cur_node),
00406 _M_get_Tp_allocator());
00407 __throw_exception_again;
00408 }
00409 }
00410
00411
00412 template<typename _Tp, typename _Alloc>
00413 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00414 template<typename... _Args>
00415 void
00416 deque<_Tp, _Alloc>::
00417 _M_push_back_aux(_Args&&... __args)
00418 #else
00419 void
00420 deque<_Tp, _Alloc>::
00421 _M_push_back_aux(const value_type& __t)
00422 #endif
00423 {
00424 _M_reserve_map_at_back();
00425 *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
00426 __try
00427 {
00428 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00429 this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
00430 std::forward<_Args>(__args)...);
00431 #else
00432 this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t);
00433 #endif
00434 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
00435 + 1);
00436 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
00437 }
00438 __catch(...)
00439 {
00440 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
00441 __throw_exception_again;
00442 }
00443 }
00444
00445
00446 template<typename _Tp, typename _Alloc>
00447 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00448 template<typename... _Args>
00449 void
00450 deque<_Tp, _Alloc>::
00451 _M_push_front_aux(_Args&&... __args)
00452 #else
00453 void
00454 deque<_Tp, _Alloc>::
00455 _M_push_front_aux(const value_type& __t)
00456 #endif
00457 {
00458 _M_reserve_map_at_front();
00459 *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
00460 __try
00461 {
00462 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
00463 - 1);
00464 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
00465 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00466 this->_M_impl.construct(this->_M_impl._M_start._M_cur,
00467 std::forward<_Args>(__args)...);
00468 #else
00469 this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t);
00470 #endif
00471 }
00472 __catch(...)
00473 {
00474 ++this->_M_impl._M_start;
00475 _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
00476 __throw_exception_again;
00477 }
00478 }
00479
00480
00481 template <typename _Tp, typename _Alloc>
00482 void deque<_Tp, _Alloc>::
00483 _M_pop_back_aux()
00484 {
00485 _M_deallocate_node(this->_M_impl._M_finish._M_first);
00486 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
00487 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
00488 this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
00489 }
00490
00491
00492
00493
00494
00495
00496 template <typename _Tp, typename _Alloc>
00497 void deque<_Tp, _Alloc>::
00498 _M_pop_front_aux()
00499 {
00500 this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
00501 _M_deallocate_node(this->_M_impl._M_start._M_first);
00502 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
00503 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
00504 }
00505
00506 template <typename _Tp, typename _Alloc>
00507 template <typename _InputIterator>
00508 void
00509 deque<_Tp, _Alloc>::
00510 _M_range_insert_aux(iterator __pos,
00511 _InputIterator __first, _InputIterator __last,
00512 std::input_iterator_tag)
00513 { std::copy(__first, __last, std::inserter(*this, __pos)); }
00514
00515 template <typename _Tp, typename _Alloc>
00516 template <typename _ForwardIterator>
00517 void
00518 deque<_Tp, _Alloc>::
00519 _M_range_insert_aux(iterator __pos,
00520 _ForwardIterator __first, _ForwardIterator __last,
00521 std::forward_iterator_tag)
00522 {
00523 const size_type __n = std::distance(__first, __last);
00524 if (__pos._M_cur == this->_M_impl._M_start._M_cur)
00525 {
00526 iterator __new_start = _M_reserve_elements_at_front(__n);
00527 __try
00528 {
00529 std::__uninitialized_copy_a(__first, __last, __new_start,
00530 _M_get_Tp_allocator());
00531 this->_M_impl._M_start = __new_start;
00532 }
00533 __catch(...)
00534 {
00535 _M_destroy_nodes(__new_start._M_node,
00536 this->_M_impl._M_start._M_node);
00537 __throw_exception_again;
00538 }
00539 }
00540 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
00541 {
00542 iterator __new_finish = _M_reserve_elements_at_back(__n);
00543 __try
00544 {
00545 std::__uninitialized_copy_a(__first, __last,
00546 this->_M_impl._M_finish,
00547 _M_get_Tp_allocator());
00548 this->_M_impl._M_finish = __new_finish;
00549 }
00550 __catch(...)
00551 {
00552 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
00553 __new_finish._M_node + 1);
00554 __throw_exception_again;
00555 }
00556 }
00557 else
00558 _M_insert_aux(__pos, __first, __last, __n);
00559 }
00560
00561 template<typename _Tp, typename _Alloc>
00562 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00563 template<typename... _Args>
00564 typename deque<_Tp, _Alloc>::iterator
00565 deque<_Tp, _Alloc>::
00566 _M_insert_aux(iterator __pos, _Args&&... __args)
00567 {
00568 value_type __x_copy(std::forward<_Args>(__args)...);
00569 #else
00570 typename deque<_Tp, _Alloc>::iterator
00571 deque<_Tp, _Alloc>::
00572 _M_insert_aux(iterator __pos, const value_type& __x)
00573 {
00574 value_type __x_copy = __x;
00575 #endif
00576 difference_type __index = __pos - this->_M_impl._M_start;
00577 if (static_cast<size_type>(__index) < size() / 2)
00578 {
00579 push_front(_GLIBCXX_MOVE(front()));
00580 iterator __front1 = this->_M_impl._M_start;
00581 ++__front1;
00582 iterator __front2 = __front1;
00583 ++__front2;
00584 __pos = this->_M_impl._M_start + __index;
00585 iterator __pos1 = __pos;
00586 ++__pos1;
00587 _GLIBCXX_MOVE3(__front2, __pos1, __front1);
00588 }
00589 else
00590 {
00591 push_back(_GLIBCXX_MOVE(back()));
00592 iterator __back1 = this->_M_impl._M_finish;
00593 --__back1;
00594 iterator __back2 = __back1;
00595 --__back2;
00596 __pos = this->_M_impl._M_start + __index;
00597 _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
00598 }
00599 *__pos = _GLIBCXX_MOVE(__x_copy);
00600 return __pos;
00601 }
00602
00603 template <typename _Tp, typename _Alloc>
00604 void
00605 deque<_Tp, _Alloc>::
00606 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
00607 {
00608 const difference_type __elems_before = __pos - this->_M_impl._M_start;
00609 const size_type __length = this->size();
00610 value_type __x_copy = __x;
00611 if (__elems_before < difference_type(__length / 2))
00612 {
00613 iterator __new_start = _M_reserve_elements_at_front(__n);
00614 iterator __old_start = this->_M_impl._M_start;
00615 __pos = this->_M_impl._M_start + __elems_before;
00616 __try
00617 {
00618 if (__elems_before >= difference_type(__n))
00619 {
00620 iterator __start_n = (this->_M_impl._M_start
00621 + difference_type(__n));
00622 std::__uninitialized_move_a(this->_M_impl._M_start,
00623 __start_n, __new_start,
00624 _M_get_Tp_allocator());
00625 this->_M_impl._M_start = __new_start;
00626 _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
00627 std::fill(__pos - difference_type(__n), __pos, __x_copy);
00628 }
00629 else
00630 {
00631 std::__uninitialized_move_fill(this->_M_impl._M_start,
00632 __pos, __new_start,
00633 this->_M_impl._M_start,
00634 __x_copy,
00635 _M_get_Tp_allocator());
00636 this->_M_impl._M_start = __new_start;
00637 std::fill(__old_start, __pos, __x_copy);
00638 }
00639 }
00640 __catch(...)
00641 {
00642 _M_destroy_nodes(__new_start._M_node,
00643 this->_M_impl._M_start._M_node);
00644 __throw_exception_again;
00645 }
00646 }
00647 else
00648 {
00649 iterator __new_finish = _M_reserve_elements_at_back(__n);
00650 iterator __old_finish = this->_M_impl._M_finish;
00651 const difference_type __elems_after =
00652 difference_type(__length) - __elems_before;
00653 __pos = this->_M_impl._M_finish - __elems_after;
00654 __try
00655 {
00656 if (__elems_after > difference_type(__n))
00657 {
00658 iterator __finish_n = (this->_M_impl._M_finish
00659 - difference_type(__n));
00660 std::__uninitialized_move_a(__finish_n,
00661 this->_M_impl._M_finish,
00662 this->_M_impl._M_finish,
00663 _M_get_Tp_allocator());
00664 this->_M_impl._M_finish = __new_finish;
00665 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
00666 std::fill(__pos, __pos + difference_type(__n), __x_copy);
00667 }
00668 else
00669 {
00670 std::__uninitialized_fill_move(this->_M_impl._M_finish,
00671 __pos + difference_type(__n),
00672 __x_copy, __pos,
00673 this->_M_impl._M_finish,
00674 _M_get_Tp_allocator());
00675 this->_M_impl._M_finish = __new_finish;
00676 std::fill(__pos, __old_finish, __x_copy);
00677 }
00678 }
00679 __catch(...)
00680 {
00681 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
00682 __new_finish._M_node + 1);
00683 __throw_exception_again;
00684 }
00685 }
00686 }
00687
00688 template <typename _Tp, typename _Alloc>
00689 template <typename _ForwardIterator>
00690 void
00691 deque<_Tp, _Alloc>::
00692 _M_insert_aux(iterator __pos,
00693 _ForwardIterator __first, _ForwardIterator __last,
00694 size_type __n)
00695 {
00696 const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
00697 const size_type __length = size();
00698 if (static_cast<size_type>(__elemsbefore) < __length / 2)
00699 {
00700 iterator __new_start = _M_reserve_elements_at_front(__n);
00701 iterator __old_start = this->_M_impl._M_start;
00702 __pos = this->_M_impl._M_start + __elemsbefore;
00703 __try
00704 {
00705 if (__elemsbefore >= difference_type(__n))
00706 {
00707 iterator __start_n = (this->_M_impl._M_start
00708 + difference_type(__n));
00709 std::__uninitialized_move_a(this->_M_impl._M_start,
00710 __start_n, __new_start,
00711 _M_get_Tp_allocator());
00712 this->_M_impl._M_start = __new_start;
00713 _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
00714 std::copy(__first, __last, __pos - difference_type(__n));
00715 }
00716 else
00717 {
00718 _ForwardIterator __mid = __first;
00719 std::advance(__mid, difference_type(__n) - __elemsbefore);
00720 std::__uninitialized_move_copy(this->_M_impl._M_start,
00721 __pos, __first, __mid,
00722 __new_start,
00723 _M_get_Tp_allocator());
00724 this->_M_impl._M_start = __new_start;
00725 std::copy(__mid, __last, __old_start);
00726 }
00727 }
00728 __catch(...)
00729 {
00730 _M_destroy_nodes(__new_start._M_node,
00731 this->_M_impl._M_start._M_node);
00732 __throw_exception_again;
00733 }
00734 }
00735 else
00736 {
00737 iterator __new_finish = _M_reserve_elements_at_back(__n);
00738 iterator __old_finish = this->_M_impl._M_finish;
00739 const difference_type __elemsafter =
00740 difference_type(__length) - __elemsbefore;
00741 __pos = this->_M_impl._M_finish - __elemsafter;
00742 __try
00743 {
00744 if (__elemsafter > difference_type(__n))
00745 {
00746 iterator __finish_n = (this->_M_impl._M_finish
00747 - difference_type(__n));
00748 std::__uninitialized_move_a(__finish_n,
00749 this->_M_impl._M_finish,
00750 this->_M_impl._M_finish,
00751 _M_get_Tp_allocator());
00752 this->_M_impl._M_finish = __new_finish;
00753 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
00754 std::copy(__first, __last, __pos);
00755 }
00756 else
00757 {
00758 _ForwardIterator __mid = __first;
00759 std::advance(__mid, __elemsafter);
00760 std::__uninitialized_copy_move(__mid, __last, __pos,
00761 this->_M_impl._M_finish,
00762 this->_M_impl._M_finish,
00763 _M_get_Tp_allocator());
00764 this->_M_impl._M_finish = __new_finish;
00765 std::copy(__first, __mid, __pos);
00766 }
00767 }
00768 __catch(...)
00769 {
00770 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
00771 __new_finish._M_node + 1);
00772 __throw_exception_again;
00773 }
00774 }
00775 }
00776
00777 template<typename _Tp, typename _Alloc>
00778 void
00779 deque<_Tp, _Alloc>::
00780 _M_destroy_data_aux(iterator __first, iterator __last)
00781 {
00782 for (_Map_pointer __node = __first._M_node + 1;
00783 __node < __last._M_node; ++__node)
00784 std::_Destroy(*__node, *__node + _S_buffer_size(),
00785 _M_get_Tp_allocator());
00786
00787 if (__first._M_node != __last._M_node)
00788 {
00789 std::_Destroy(__first._M_cur, __first._M_last,
00790 _M_get_Tp_allocator());
00791 std::_Destroy(__last._M_first, __last._M_cur,
00792 _M_get_Tp_allocator());
00793 }
00794 else
00795 std::_Destroy(__first._M_cur, __last._M_cur,
00796 _M_get_Tp_allocator());
00797 }
00798
00799 template <typename _Tp, typename _Alloc>
00800 void
00801 deque<_Tp, _Alloc>::
00802 _M_new_elements_at_front(size_type __new_elems)
00803 {
00804 if (this->max_size() - this->size() < __new_elems)
00805 __throw_length_error(__N("deque::_M_new_elements_at_front"));
00806
00807 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
00808 / _S_buffer_size());
00809 _M_reserve_map_at_front(__new_nodes);
00810 size_type __i;
00811 __try
00812 {
00813 for (__i = 1; __i <= __new_nodes; ++__i)
00814 *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
00815 }
00816 __catch(...)
00817 {
00818 for (size_type __j = 1; __j < __i; ++__j)
00819 _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
00820 __throw_exception_again;
00821 }
00822 }
00823
00824 template <typename _Tp, typename _Alloc>
00825 void
00826 deque<_Tp, _Alloc>::
00827 _M_new_elements_at_back(size_type __new_elems)
00828 {
00829 if (this->max_size() - this->size() < __new_elems)
00830 __throw_length_error(__N("deque::_M_new_elements_at_back"));
00831
00832 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
00833 / _S_buffer_size());
00834 _M_reserve_map_at_back(__new_nodes);
00835 size_type __i;
00836 __try
00837 {
00838 for (__i = 1; __i <= __new_nodes; ++__i)
00839 *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
00840 }
00841 __catch(...)
00842 {
00843 for (size_type __j = 1; __j < __i; ++__j)
00844 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
00845 __throw_exception_again;
00846 }
00847 }
00848
00849 template <typename _Tp, typename _Alloc>
00850 void
00851 deque<_Tp, _Alloc>::
00852 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
00853 {
00854 const size_type __old_num_nodes
00855 = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
00856 const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
00857
00858 _Map_pointer __new_nstart;
00859 if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
00860 {
00861 __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
00862 - __new_num_nodes) / 2
00863 + (__add_at_front ? __nodes_to_add : 0);
00864 if (__new_nstart < this->_M_impl._M_start._M_node)
00865 std::copy(this->_M_impl._M_start._M_node,
00866 this->_M_impl._M_finish._M_node + 1,
00867 __new_nstart);
00868 else
00869 std::copy_backward(this->_M_impl._M_start._M_node,
00870 this->_M_impl._M_finish._M_node + 1,
00871 __new_nstart + __old_num_nodes);
00872 }
00873 else
00874 {
00875 size_type __new_map_size = this->_M_impl._M_map_size
00876 + std::max(this->_M_impl._M_map_size,
00877 __nodes_to_add) + 2;
00878
00879 _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
00880 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
00881 + (__add_at_front ? __nodes_to_add : 0);
00882 std::copy(this->_M_impl._M_start._M_node,
00883 this->_M_impl._M_finish._M_node + 1,
00884 __new_nstart);
00885 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
00886
00887 this->_M_impl._M_map = __new_map;
00888 this->_M_impl._M_map_size = __new_map_size;
00889 }
00890
00891 this->_M_impl._M_start._M_set_node(__new_nstart);
00892 this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
00893 }
00894
00895
00896
00897 template<typename _Tp>
00898 void
00899 fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
00900 const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value)
00901 {
00902 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
00903
00904 for (typename _Self::_Map_pointer __node = __first._M_node + 1;
00905 __node < __last._M_node; ++__node)
00906 std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
00907
00908 if (__first._M_node != __last._M_node)
00909 {
00910 std::fill(__first._M_cur, __first._M_last, __value);
00911 std::fill(__last._M_first, __last._M_cur, __value);
00912 }
00913 else
00914 std::fill(__first._M_cur, __last._M_cur, __value);
00915 }
00916
00917 template<typename _Tp>
00918 _Deque_iterator<_Tp, _Tp&, _Tp*>
00919 copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
00920 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
00921 _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
00922 {
00923 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
00924 typedef typename _Self::difference_type difference_type;
00925
00926 difference_type __len = __last - __first;
00927 while (__len > 0)
00928 {
00929 const difference_type __clen
00930 = std::min(__len, std::min(__first._M_last - __first._M_cur,
00931 __result._M_last - __result._M_cur));
00932 std::copy(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
00933 __first += __clen;
00934 __result += __clen;
00935 __len -= __clen;
00936 }
00937 return __result;
00938 }
00939
00940 template<typename _Tp>
00941 _Deque_iterator<_Tp, _Tp&, _Tp*>
00942 copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
00943 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
00944 _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
00945 {
00946 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
00947 typedef typename _Self::difference_type difference_type;
00948
00949 difference_type __len = __last - __first;
00950 while (__len > 0)
00951 {
00952 difference_type __llen = __last._M_cur - __last._M_first;
00953 _Tp* __lend = __last._M_cur;
00954
00955 difference_type __rlen = __result._M_cur - __result._M_first;
00956 _Tp* __rend = __result._M_cur;
00957
00958 if (!__llen)
00959 {
00960 __llen = _Self::_S_buffer_size();
00961 __lend = *(__last._M_node - 1) + __llen;
00962 }
00963 if (!__rlen)
00964 {
00965 __rlen = _Self::_S_buffer_size();
00966 __rend = *(__result._M_node - 1) + __rlen;
00967 }
00968
00969 const difference_type __clen = std::min(__len,
00970 std::min(__llen, __rlen));
00971 std::copy_backward(__lend - __clen, __lend, __rend);
00972 __last -= __clen;
00973 __result -= __clen;
00974 __len -= __clen;
00975 }
00976 return __result;
00977 }
00978
00979 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00980 template<typename _Tp>
00981 _Deque_iterator<_Tp, _Tp&, _Tp*>
00982 move(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
00983 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
00984 _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
00985 {
00986 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
00987 typedef typename _Self::difference_type difference_type;
00988
00989 difference_type __len = __last - __first;
00990 while (__len > 0)
00991 {
00992 const difference_type __clen
00993 = std::min(__len, std::min(__first._M_last - __first._M_cur,
00994 __result._M_last - __result._M_cur));
00995 std::move(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
00996 __first += __clen;
00997 __result += __clen;
00998 __len -= __clen;
00999 }
01000 return __result;
01001 }
01002
01003 template<typename _Tp>
01004 _Deque_iterator<_Tp, _Tp&, _Tp*>
01005 move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
01006 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
01007 _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
01008 {
01009 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
01010 typedef typename _Self::difference_type difference_type;
01011
01012 difference_type __len = __last - __first;
01013 while (__len > 0)
01014 {
01015 difference_type __llen = __last._M_cur - __last._M_first;
01016 _Tp* __lend = __last._M_cur;
01017
01018 difference_type __rlen = __result._M_cur - __result._M_first;
01019 _Tp* __rend = __result._M_cur;
01020
01021 if (!__llen)
01022 {
01023 __llen = _Self::_S_buffer_size();
01024 __lend = *(__last._M_node - 1) + __llen;
01025 }
01026 if (!__rlen)
01027 {
01028 __rlen = _Self::_S_buffer_size();
01029 __rend = *(__result._M_node - 1) + __rlen;
01030 }
01031
01032 const difference_type __clen = std::min(__len,
01033 std::min(__llen, __rlen));
01034 std::move_backward(__lend - __clen, __lend, __rend);
01035 __last -= __clen;
01036 __result -= __clen;
01037 __len -= __clen;
01038 }
01039 return __result;
01040 }
01041 #endif
01042
01043 _GLIBCXX_END_NAMESPACE_CONTAINER
01044 }
01045
01046 #endif