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