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