libstdc++
deque.tcc
1 // Deque implementation (out of line) -*- C++ -*-
2 
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
4 // Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
10 // any later version.
11 
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
16 
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20 
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
25 
26 /*
27  *
28  * Copyright (c) 1994
29  * Hewlett-Packard Company
30  *
31  * Permission to use, copy, modify, distribute and sell this software
32  * and its documentation for any purpose is hereby granted without fee,
33  * provided that the above copyright notice appear in all copies and
34  * that both that copyright notice and this permission notice appear
35  * in supporting documentation. Hewlett-Packard Company makes no
36  * representations about the suitability of this software for any
37  * purpose. It is provided "as is" without express or implied warranty.
38  *
39  *
40  * Copyright (c) 1997
41  * Silicon Graphics Computer Systems, Inc.
42  *
43  * Permission to use, copy, modify, distribute and sell this software
44  * and its documentation for any purpose is hereby granted without fee,
45  * provided that the above copyright notice appear in all copies and
46  * that both that copyright notice and this permission notice appear
47  * in supporting documentation. Silicon Graphics makes no
48  * representations about the suitability of this software for any
49  * purpose. It is provided "as is" without express or implied warranty.
50  */
51 
52 /** @file deque.tcc
53  * This is an internal header file, included by other library headers.
54  * You should not attempt to use it directly.
55  */
56 
57 #ifndef _DEQUE_TCC
58 #define _DEQUE_TCC 1
59 
60 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
61 
62  template <typename _Tp, typename _Alloc>
63  deque<_Tp, _Alloc>&
64  deque<_Tp, _Alloc>::
65  operator=(const deque& __x)
66  {
67  const size_type __len = size();
68  if (&__x != this)
69  {
70  if (__len >= __x.size())
71  _M_erase_at_end(std::copy(__x.begin(), __x.end(),
72  this->_M_impl._M_start));
73  else
74  {
75  const_iterator __mid = __x.begin() + difference_type(__len);
76  std::copy(__x.begin(), __mid, this->_M_impl._M_start);
77  insert(this->_M_impl._M_finish, __mid, __x.end());
78  }
79  }
80  return *this;
81  }
82 
83 #ifdef __GXX_EXPERIMENTAL_CXX0X__
84  template<typename _Tp, typename _Alloc>
85  template<typename... _Args>
86  void
87  deque<_Tp, _Alloc>::
88  emplace_front(_Args&&... __args)
89  {
90  if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
91  {
92  this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1,
93  std::forward<_Args>(__args)...);
94  --this->_M_impl._M_start._M_cur;
95  }
96  else
97  _M_push_front_aux(std::forward<_Args>(__args)...);
98  }
99 
100  template<typename _Tp, typename _Alloc>
101  template<typename... _Args>
102  void
103  deque<_Tp, _Alloc>::
104  emplace_back(_Args&&... __args)
105  {
106  if (this->_M_impl._M_finish._M_cur
107  != this->_M_impl._M_finish._M_last - 1)
108  {
109  this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
110  std::forward<_Args>(__args)...);
111  ++this->_M_impl._M_finish._M_cur;
112  }
113  else
114  _M_push_back_aux(std::forward<_Args>(__args)...);
115  }
116 #endif
117 
118  template <typename _Tp, typename _Alloc>
119  typename deque<_Tp, _Alloc>::iterator
120  deque<_Tp, _Alloc>::
121  insert(iterator __position, const value_type& __x)
122  {
123  if (__position._M_cur == this->_M_impl._M_start._M_cur)
124  {
125  push_front(__x);
126  return this->_M_impl._M_start;
127  }
128  else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
129  {
130  push_back(__x);
131  iterator __tmp = this->_M_impl._M_finish;
132  --__tmp;
133  return __tmp;
134  }
135  else
136  return _M_insert_aux(__position, __x);
137  }
138 
139 #ifdef __GXX_EXPERIMENTAL_CXX0X__
140  template<typename _Tp, typename _Alloc>
141  template<typename... _Args>
142  typename deque<_Tp, _Alloc>::iterator
143  deque<_Tp, _Alloc>::
144  emplace(iterator __position, _Args&&... __args)
145  {
146  if (__position._M_cur == this->_M_impl._M_start._M_cur)
147  {
148  push_front(std::forward<_Args>(__args)...);
149  return this->_M_impl._M_start;
150  }
151  else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
152  {
153  push_back(std::forward<_Args>(__args)...);
154  iterator __tmp = this->_M_impl._M_finish;
155  --__tmp;
156  return __tmp;
157  }
158  else
159  return _M_insert_aux(__position, std::forward<_Args>(__args)...);
160  }
161 #endif
162 
163  template <typename _Tp, typename _Alloc>
164  typename deque<_Tp, _Alloc>::iterator
165  deque<_Tp, _Alloc>::
166  erase(iterator __position)
167  {
168  iterator __next = __position;
169  ++__next;
170  const difference_type __index = __position - begin();
171  if (static_cast<size_type>(__index) < (size() >> 1))
172  {
173  if (__position != begin())
174  _GLIBCXX_MOVE_BACKWARD3(begin(), __position, __next);
175  pop_front();
176  }
177  else
178  {
179  if (__next != end())
180  _GLIBCXX_MOVE3(__next, end(), __position);
181  pop_back();
182  }
183  return begin() + __index;
184  }
185 
186  template <typename _Tp, typename _Alloc>
187  typename deque<_Tp, _Alloc>::iterator
188  deque<_Tp, _Alloc>::
189  erase(iterator __first, iterator __last)
190  {
191  if (__first == begin() && __last == end())
192  {
193  clear();
194  return end();
195  }
196  else
197  {
198  const difference_type __n = __last - __first;
199  const difference_type __elems_before = __first - begin();
200  if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2)
201  {
202  if (__first != begin())
203  _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last);
204  _M_erase_at_begin(begin() + __n);
205  }
206  else
207  {
208  if (__last != end())
209  _GLIBCXX_MOVE3(__last, end(), __first);
210  _M_erase_at_end(end() - __n);
211  }
212  return begin() + __elems_before;
213  }
214  }
215 
216  template <typename _Tp, class _Alloc>
217  template <typename _InputIterator>
218  void
219  deque<_Tp, _Alloc>::
220  _M_assign_aux(_InputIterator __first, _InputIterator __last,
221  std::input_iterator_tag)
222  {
223  iterator __cur = begin();
224  for (; __first != __last && __cur != end(); ++__cur, ++__first)
225  *__cur = *__first;
226  if (__first == __last)
227  _M_erase_at_end(__cur);
228  else
229  insert(end(), __first, __last);
230  }
231 
232  template <typename _Tp, typename _Alloc>
233  void
234  deque<_Tp, _Alloc>::
235  _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
236  {
237  if (__pos._M_cur == this->_M_impl._M_start._M_cur)
238  {
239  iterator __new_start = _M_reserve_elements_at_front(__n);
240  __try
241  {
242  std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
243  __x, _M_get_Tp_allocator());
244  this->_M_impl._M_start = __new_start;
245  }
246  __catch(...)
247  {
248  _M_destroy_nodes(__new_start._M_node,
249  this->_M_impl._M_start._M_node);
250  __throw_exception_again;
251  }
252  }
253  else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
254  {
255  iterator __new_finish = _M_reserve_elements_at_back(__n);
256  __try
257  {
258  std::__uninitialized_fill_a(this->_M_impl._M_finish,
259  __new_finish, __x,
260  _M_get_Tp_allocator());
261  this->_M_impl._M_finish = __new_finish;
262  }
263  __catch(...)
264  {
265  _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
266  __new_finish._M_node + 1);
267  __throw_exception_again;
268  }
269  }
270  else
271  _M_insert_aux(__pos, __n, __x);
272  }
273 
274  template <typename _Tp, typename _Alloc>
275  void
276  deque<_Tp, _Alloc>::
277  _M_fill_initialize(const value_type& __value)
278  {
279  _Map_pointer __cur;
280  __try
281  {
282  for (__cur = this->_M_impl._M_start._M_node;
283  __cur < this->_M_impl._M_finish._M_node;
284  ++__cur)
285  std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
286  __value, _M_get_Tp_allocator());
287  std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
288  this->_M_impl._M_finish._M_cur,
289  __value, _M_get_Tp_allocator());
290  }
291  __catch(...)
292  {
293  std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
294  _M_get_Tp_allocator());
295  __throw_exception_again;
296  }
297  }
298 
299  template <typename _Tp, typename _Alloc>
300  template <typename _InputIterator>
301  void
302  deque<_Tp, _Alloc>::
303  _M_range_initialize(_InputIterator __first, _InputIterator __last,
304  std::input_iterator_tag)
305  {
306  this->_M_initialize_map(0);
307  __try
308  {
309  for (; __first != __last; ++__first)
310  push_back(*__first);
311  }
312  __catch(...)
313  {
314  clear();
315  __throw_exception_again;
316  }
317  }
318 
319  template <typename _Tp, typename _Alloc>
320  template <typename _ForwardIterator>
321  void
322  deque<_Tp, _Alloc>::
323  _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
324  std::forward_iterator_tag)
325  {
326  const size_type __n = std::distance(__first, __last);
327  this->_M_initialize_map(__n);
328 
329  _Map_pointer __cur_node;
330  __try
331  {
332  for (__cur_node = this->_M_impl._M_start._M_node;
333  __cur_node < this->_M_impl._M_finish._M_node;
334  ++__cur_node)
335  {
336  _ForwardIterator __mid = __first;
337  std::advance(__mid, _S_buffer_size());
338  std::__uninitialized_copy_a(__first, __mid, *__cur_node,
339  _M_get_Tp_allocator());
340  __first = __mid;
341  }
342  std::__uninitialized_copy_a(__first, __last,
343  this->_M_impl._M_finish._M_first,
344  _M_get_Tp_allocator());
345  }
346  __catch(...)
347  {
348  std::_Destroy(this->_M_impl._M_start,
349  iterator(*__cur_node, __cur_node),
350  _M_get_Tp_allocator());
351  __throw_exception_again;
352  }
353  }
354 
355  // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1.
356  template<typename _Tp, typename _Alloc>
357 #ifdef __GXX_EXPERIMENTAL_CXX0X__
358  template<typename... _Args>
359  void
360  deque<_Tp, _Alloc>::
361  _M_push_back_aux(_Args&&... __args)
362 #else
363  void
364  deque<_Tp, _Alloc>::
365  _M_push_back_aux(const value_type& __t)
366 #endif
367  {
368  _M_reserve_map_at_back();
369  *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
370  __try
371  {
372 #ifdef __GXX_EXPERIMENTAL_CXX0X__
373  this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
374  std::forward<_Args>(__args)...);
375 #else
376  this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t);
377 #endif
378  this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
379  + 1);
380  this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
381  }
382  __catch(...)
383  {
384  _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
385  __throw_exception_again;
386  }
387  }
388 
389  // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
390  template<typename _Tp, typename _Alloc>
391 #ifdef __GXX_EXPERIMENTAL_CXX0X__
392  template<typename... _Args>
393  void
394  deque<_Tp, _Alloc>::
395  _M_push_front_aux(_Args&&... __args)
396 #else
397  void
398  deque<_Tp, _Alloc>::
399  _M_push_front_aux(const value_type& __t)
400 #endif
401  {
402  _M_reserve_map_at_front();
403  *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
404  __try
405  {
406  this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
407  - 1);
408  this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
409 #ifdef __GXX_EXPERIMENTAL_CXX0X__
410  this->_M_impl.construct(this->_M_impl._M_start._M_cur,
411  std::forward<_Args>(__args)...);
412 #else
413  this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t);
414 #endif
415  }
416  __catch(...)
417  {
418  ++this->_M_impl._M_start;
419  _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
420  __throw_exception_again;
421  }
422  }
423 
424  // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
425  template <typename _Tp, typename _Alloc>
426  void deque<_Tp, _Alloc>::
427  _M_pop_back_aux()
428  {
429  _M_deallocate_node(this->_M_impl._M_finish._M_first);
430  this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
431  this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
432  this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
433  }
434 
435  // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
436  // Note that if the deque has at least one element (a precondition for this
437  // member function), and if
438  // _M_impl._M_start._M_cur == _M_impl._M_start._M_last,
439  // then the deque must have at least two nodes.
440  template <typename _Tp, typename _Alloc>
441  void deque<_Tp, _Alloc>::
442  _M_pop_front_aux()
443  {
444  this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
445  _M_deallocate_node(this->_M_impl._M_start._M_first);
446  this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
447  this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
448  }
449 
450  template <typename _Tp, typename _Alloc>
451  template <typename _InputIterator>
452  void
453  deque<_Tp, _Alloc>::
454  _M_range_insert_aux(iterator __pos,
455  _InputIterator __first, _InputIterator __last,
456  std::input_iterator_tag)
457  { std::copy(__first, __last, std::inserter(*this, __pos)); }
458 
459  template <typename _Tp, typename _Alloc>
460  template <typename _ForwardIterator>
461  void
462  deque<_Tp, _Alloc>::
463  _M_range_insert_aux(iterator __pos,
464  _ForwardIterator __first, _ForwardIterator __last,
465  std::forward_iterator_tag)
466  {
467  const size_type __n = std::distance(__first, __last);
468  if (__pos._M_cur == this->_M_impl._M_start._M_cur)
469  {
470  iterator __new_start = _M_reserve_elements_at_front(__n);
471  __try
472  {
473  std::__uninitialized_copy_a(__first, __last, __new_start,
474  _M_get_Tp_allocator());
475  this->_M_impl._M_start = __new_start;
476  }
477  __catch(...)
478  {
479  _M_destroy_nodes(__new_start._M_node,
480  this->_M_impl._M_start._M_node);
481  __throw_exception_again;
482  }
483  }
484  else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
485  {
486  iterator __new_finish = _M_reserve_elements_at_back(__n);
487  __try
488  {
489  std::__uninitialized_copy_a(__first, __last,
490  this->_M_impl._M_finish,
491  _M_get_Tp_allocator());
492  this->_M_impl._M_finish = __new_finish;
493  }
494  __catch(...)
495  {
496  _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
497  __new_finish._M_node + 1);
498  __throw_exception_again;
499  }
500  }
501  else
502  _M_insert_aux(__pos, __first, __last, __n);
503  }
504 
505  template<typename _Tp, typename _Alloc>
506 #ifdef __GXX_EXPERIMENTAL_CXX0X__
507  template<typename... _Args>
508  typename deque<_Tp, _Alloc>::iterator
509  deque<_Tp, _Alloc>::
510  _M_insert_aux(iterator __pos, _Args&&... __args)
511  {
512  value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy
513 #else
514  typename deque<_Tp, _Alloc>::iterator
515  deque<_Tp, _Alloc>::
516  _M_insert_aux(iterator __pos, const value_type& __x)
517  {
518  value_type __x_copy = __x; // XXX copy
519 #endif
520  difference_type __index = __pos - this->_M_impl._M_start;
521  if (static_cast<size_type>(__index) < size() / 2)
522  {
523  push_front(_GLIBCXX_MOVE(front()));
524  iterator __front1 = this->_M_impl._M_start;
525  ++__front1;
526  iterator __front2 = __front1;
527  ++__front2;
528  __pos = this->_M_impl._M_start + __index;
529  iterator __pos1 = __pos;
530  ++__pos1;
531  _GLIBCXX_MOVE3(__front2, __pos1, __front1);
532  }
533  else
534  {
535  push_back(_GLIBCXX_MOVE(back()));
536  iterator __back1 = this->_M_impl._M_finish;
537  --__back1;
538  iterator __back2 = __back1;
539  --__back2;
540  __pos = this->_M_impl._M_start + __index;
541  _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
542  }
543  *__pos = _GLIBCXX_MOVE(__x_copy);
544  return __pos;
545  }
546 
547  template <typename _Tp, typename _Alloc>
548  void
549  deque<_Tp, _Alloc>::
550  _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
551  {
552  const difference_type __elems_before = __pos - this->_M_impl._M_start;
553  const size_type __length = this->size();
554  value_type __x_copy = __x;
555  if (__elems_before < difference_type(__length / 2))
556  {
557  iterator __new_start = _M_reserve_elements_at_front(__n);
558  iterator __old_start = this->_M_impl._M_start;
559  __pos = this->_M_impl._M_start + __elems_before;
560  __try
561  {
562  if (__elems_before >= difference_type(__n))
563  {
564  iterator __start_n = (this->_M_impl._M_start
565  + difference_type(__n));
566  std::__uninitialized_move_a(this->_M_impl._M_start,
567  __start_n, __new_start,
568  _M_get_Tp_allocator());
569  this->_M_impl._M_start = __new_start;
570  _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
571  std::fill(__pos - difference_type(__n), __pos, __x_copy);
572  }
573  else
574  {
575  std::__uninitialized_move_fill(this->_M_impl._M_start,
576  __pos, __new_start,
577  this->_M_impl._M_start,
578  __x_copy,
579  _M_get_Tp_allocator());
580  this->_M_impl._M_start = __new_start;
581  std::fill(__old_start, __pos, __x_copy);
582  }
583  }
584  __catch(...)
585  {
586  _M_destroy_nodes(__new_start._M_node,
587  this->_M_impl._M_start._M_node);
588  __throw_exception_again;
589  }
590  }
591  else
592  {
593  iterator __new_finish = _M_reserve_elements_at_back(__n);
594  iterator __old_finish = this->_M_impl._M_finish;
595  const difference_type __elems_after =
596  difference_type(__length) - __elems_before;
597  __pos = this->_M_impl._M_finish - __elems_after;
598  __try
599  {
600  if (__elems_after > difference_type(__n))
601  {
602  iterator __finish_n = (this->_M_impl._M_finish
603  - difference_type(__n));
604  std::__uninitialized_move_a(__finish_n,
605  this->_M_impl._M_finish,
606  this->_M_impl._M_finish,
607  _M_get_Tp_allocator());
608  this->_M_impl._M_finish = __new_finish;
609  _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
610  std::fill(__pos, __pos + difference_type(__n), __x_copy);
611  }
612  else
613  {
614  std::__uninitialized_fill_move(this->_M_impl._M_finish,
615  __pos + difference_type(__n),
616  __x_copy, __pos,
617  this->_M_impl._M_finish,
618  _M_get_Tp_allocator());
619  this->_M_impl._M_finish = __new_finish;
620  std::fill(__pos, __old_finish, __x_copy);
621  }
622  }
623  __catch(...)
624  {
625  _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
626  __new_finish._M_node + 1);
627  __throw_exception_again;
628  }
629  }
630  }
631 
632  template <typename _Tp, typename _Alloc>
633  template <typename _ForwardIterator>
634  void
635  deque<_Tp, _Alloc>::
636  _M_insert_aux(iterator __pos,
637  _ForwardIterator __first, _ForwardIterator __last,
638  size_type __n)
639  {
640  const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
641  const size_type __length = size();
642  if (static_cast<size_type>(__elemsbefore) < __length / 2)
643  {
644  iterator __new_start = _M_reserve_elements_at_front(__n);
645  iterator __old_start = this->_M_impl._M_start;
646  __pos = this->_M_impl._M_start + __elemsbefore;
647  __try
648  {
649  if (__elemsbefore >= difference_type(__n))
650  {
651  iterator __start_n = (this->_M_impl._M_start
652  + difference_type(__n));
653  std::__uninitialized_move_a(this->_M_impl._M_start,
654  __start_n, __new_start,
655  _M_get_Tp_allocator());
656  this->_M_impl._M_start = __new_start;
657  _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
658  std::copy(__first, __last, __pos - difference_type(__n));
659  }
660  else
661  {
662  _ForwardIterator __mid = __first;
663  std::advance(__mid, difference_type(__n) - __elemsbefore);
664  std::__uninitialized_move_copy(this->_M_impl._M_start,
665  __pos, __first, __mid,
666  __new_start,
667  _M_get_Tp_allocator());
668  this->_M_impl._M_start = __new_start;
669  std::copy(__mid, __last, __old_start);
670  }
671  }
672  __catch(...)
673  {
674  _M_destroy_nodes(__new_start._M_node,
675  this->_M_impl._M_start._M_node);
676  __throw_exception_again;
677  }
678  }
679  else
680  {
681  iterator __new_finish = _M_reserve_elements_at_back(__n);
682  iterator __old_finish = this->_M_impl._M_finish;
683  const difference_type __elemsafter =
684  difference_type(__length) - __elemsbefore;
685  __pos = this->_M_impl._M_finish - __elemsafter;
686  __try
687  {
688  if (__elemsafter > difference_type(__n))
689  {
690  iterator __finish_n = (this->_M_impl._M_finish
691  - difference_type(__n));
692  std::__uninitialized_move_a(__finish_n,
693  this->_M_impl._M_finish,
694  this->_M_impl._M_finish,
695  _M_get_Tp_allocator());
696  this->_M_impl._M_finish = __new_finish;
697  _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
698  std::copy(__first, __last, __pos);
699  }
700  else
701  {
702  _ForwardIterator __mid = __first;
703  std::advance(__mid, __elemsafter);
704  std::__uninitialized_copy_move(__mid, __last, __pos,
705  this->_M_impl._M_finish,
706  this->_M_impl._M_finish,
707  _M_get_Tp_allocator());
708  this->_M_impl._M_finish = __new_finish;
709  std::copy(__first, __mid, __pos);
710  }
711  }
712  __catch(...)
713  {
714  _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
715  __new_finish._M_node + 1);
716  __throw_exception_again;
717  }
718  }
719  }
720 
721  template<typename _Tp, typename _Alloc>
722  void
723  deque<_Tp, _Alloc>::
724  _M_destroy_data_aux(iterator __first, iterator __last)
725  {
726  for (_Map_pointer __node = __first._M_node + 1;
727  __node < __last._M_node; ++__node)
728  std::_Destroy(*__node, *__node + _S_buffer_size(),
729  _M_get_Tp_allocator());
730 
731  if (__first._M_node != __last._M_node)
732  {
733  std::_Destroy(__first._M_cur, __first._M_last,
734  _M_get_Tp_allocator());
735  std::_Destroy(__last._M_first, __last._M_cur,
736  _M_get_Tp_allocator());
737  }
738  else
739  std::_Destroy(__first._M_cur, __last._M_cur,
740  _M_get_Tp_allocator());
741  }
742 
743  template <typename _Tp, typename _Alloc>
744  void
745  deque<_Tp, _Alloc>::
746  _M_new_elements_at_front(size_type __new_elems)
747  {
748  if (this->max_size() - this->size() < __new_elems)
749  __throw_length_error(__N("deque::_M_new_elements_at_front"));
750 
751  const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
752  / _S_buffer_size());
753  _M_reserve_map_at_front(__new_nodes);
754  size_type __i;
755  __try
756  {
757  for (__i = 1; __i <= __new_nodes; ++__i)
758  *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
759  }
760  __catch(...)
761  {
762  for (size_type __j = 1; __j < __i; ++__j)
763  _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
764  __throw_exception_again;
765  }
766  }
767 
768  template <typename _Tp, typename _Alloc>
769  void
770  deque<_Tp, _Alloc>::
771  _M_new_elements_at_back(size_type __new_elems)
772  {
773  if (this->max_size() - this->size() < __new_elems)
774  __throw_length_error(__N("deque::_M_new_elements_at_back"));
775 
776  const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
777  / _S_buffer_size());
778  _M_reserve_map_at_back(__new_nodes);
779  size_type __i;
780  __try
781  {
782  for (__i = 1; __i <= __new_nodes; ++__i)
783  *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
784  }
785  __catch(...)
786  {
787  for (size_type __j = 1; __j < __i; ++__j)
788  _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
789  __throw_exception_again;
790  }
791  }
792 
793  template <typename _Tp, typename _Alloc>
794  void
795  deque<_Tp, _Alloc>::
796  _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
797  {
798  const size_type __old_num_nodes
799  = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
800  const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
801 
802  _Map_pointer __new_nstart;
803  if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
804  {
805  __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
806  - __new_num_nodes) / 2
807  + (__add_at_front ? __nodes_to_add : 0);
808  if (__new_nstart < this->_M_impl._M_start._M_node)
809  std::copy(this->_M_impl._M_start._M_node,
810  this->_M_impl._M_finish._M_node + 1,
811  __new_nstart);
812  else
813  std::copy_backward(this->_M_impl._M_start._M_node,
814  this->_M_impl._M_finish._M_node + 1,
815  __new_nstart + __old_num_nodes);
816  }
817  else
818  {
819  size_type __new_map_size = this->_M_impl._M_map_size
820  + std::max(this->_M_impl._M_map_size,
821  __nodes_to_add) + 2;
822 
823  _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
824  __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
825  + (__add_at_front ? __nodes_to_add : 0);
826  std::copy(this->_M_impl._M_start._M_node,
827  this->_M_impl._M_finish._M_node + 1,
828  __new_nstart);
829  _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
830 
831  this->_M_impl._M_map = __new_map;
832  this->_M_impl._M_map_size = __new_map_size;
833  }
834 
835  this->_M_impl._M_start._M_set_node(__new_nstart);
836  this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
837  }
838 
839  // Overload for deque::iterators, exploiting the "segmented-iterator
840  // optimization". NB: leave const_iterators alone!
841  template<typename _Tp>
842  void
843  fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
844  const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value)
845  {
846  typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
847 
848  for (typename _Self::_Map_pointer __node = __first._M_node + 1;
849  __node < __last._M_node; ++__node)
850  std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
851 
852  if (__first._M_node != __last._M_node)
853  {
854  std::fill(__first._M_cur, __first._M_last, __value);
855  std::fill(__last._M_first, __last._M_cur, __value);
856  }
857  else
858  std::fill(__first._M_cur, __last._M_cur, __value);
859  }
860 
861 _GLIBCXX_END_NESTED_NAMESPACE
862 
863 #endif