libstdc++
deque.tcc
Go to the documentation of this file.
1 // Deque implementation (out of line) -*- C++ -*-
2 
3 // Copyright (C) 2001-2017 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>&
93  operator=(const deque& __x)
94  {
95  if (&__x != this)
96  {
97 #if __cplusplus >= 201103L
98  if (_Alloc_traits::_S_propagate_on_copy_assign())
99  {
100  if (!_Alloc_traits::_S_always_equal()
101  && _M_get_Tp_allocator() != __x._M_get_Tp_allocator())
102  {
103  // Replacement allocator cannot free existing storage,
104  // so deallocate everything and take copy of __x's data.
105  _M_replace_map(__x, __x.get_allocator());
106  std::__alloc_on_copy(_M_get_Tp_allocator(),
107  __x._M_get_Tp_allocator());
108  return *this;
109  }
110  std::__alloc_on_copy(_M_get_Tp_allocator(),
111  __x._M_get_Tp_allocator());
112  }
113 #endif
114  const size_type __len = size();
115  if (__len >= __x.size())
116  _M_erase_at_end(std::copy(__x.begin(), __x.end(),
117  this->_M_impl._M_start));
118  else
119  {
120  const_iterator __mid = __x.begin() + difference_type(__len);
121  std::copy(__x.begin(), __mid, this->_M_impl._M_start);
122  _M_range_insert_aux(this->_M_impl._M_finish, __mid, __x.end(),
124  }
125  }
126  return *this;
127  }
128 
129 #if __cplusplus >= 201103L
130  template<typename _Tp, typename _Alloc>
131  template<typename... _Args>
132 #if __cplusplus > 201402L
133  typename deque<_Tp, _Alloc>::reference
134 #else
135  void
136 #endif
138  emplace_front(_Args&&... __args)
139  {
140  if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
141  {
142  _Alloc_traits::construct(this->_M_impl,
143  this->_M_impl._M_start._M_cur - 1,
144  std::forward<_Args>(__args)...);
145  --this->_M_impl._M_start._M_cur;
146  }
147  else
148  _M_push_front_aux(std::forward<_Args>(__args)...);
149 #if __cplusplus > 201402L
150  return front();
151 #endif
152  }
153 
154  template<typename _Tp, typename _Alloc>
155  template<typename... _Args>
156 #if __cplusplus > 201402L
157  typename deque<_Tp, _Alloc>::reference
158 #else
159  void
160 #endif
162  emplace_back(_Args&&... __args)
163  {
164  if (this->_M_impl._M_finish._M_cur
165  != this->_M_impl._M_finish._M_last - 1)
166  {
167  _Alloc_traits::construct(this->_M_impl,
168  this->_M_impl._M_finish._M_cur,
169  std::forward<_Args>(__args)...);
170  ++this->_M_impl._M_finish._M_cur;
171  }
172  else
173  _M_push_back_aux(std::forward<_Args>(__args)...);
174 #if __cplusplus > 201402L
175  return back();
176 #endif
177  }
178 #endif
179 
180 #if __cplusplus >= 201103L
181  template<typename _Tp, typename _Alloc>
182  template<typename... _Args>
185  emplace(const_iterator __position, _Args&&... __args)
186  {
187  if (__position._M_cur == this->_M_impl._M_start._M_cur)
188  {
189  emplace_front(std::forward<_Args>(__args)...);
190  return this->_M_impl._M_start;
191  }
192  else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
193  {
194  emplace_back(std::forward<_Args>(__args)...);
195  iterator __tmp = this->_M_impl._M_finish;
196  --__tmp;
197  return __tmp;
198  }
199  else
200  return _M_insert_aux(__position._M_const_cast(),
201  std::forward<_Args>(__args)...);
202  }
203 #endif
204 
205  template <typename _Tp, typename _Alloc>
208 #if __cplusplus >= 201103L
209  insert(const_iterator __position, const value_type& __x)
210 #else
211  insert(iterator __position, const value_type& __x)
212 #endif
213  {
214  if (__position._M_cur == this->_M_impl._M_start._M_cur)
215  {
216  push_front(__x);
217  return this->_M_impl._M_start;
218  }
219  else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
220  {
221  push_back(__x);
222  iterator __tmp = this->_M_impl._M_finish;
223  --__tmp;
224  return __tmp;
225  }
226  else
227  return _M_insert_aux(__position._M_const_cast(), __x);
228  }
229 
230  template <typename _Tp, typename _Alloc>
233  _M_erase(iterator __position)
234  {
235  iterator __next = __position;
236  ++__next;
237  const difference_type __index = __position - begin();
238  if (static_cast<size_type>(__index) < (size() >> 1))
239  {
240  if (__position != begin())
241  _GLIBCXX_MOVE_BACKWARD3(begin(), __position, __next);
242  pop_front();
243  }
244  else
245  {
246  if (__next != end())
247  _GLIBCXX_MOVE3(__next, end(), __position);
248  pop_back();
249  }
250  return begin() + __index;
251  }
252 
253  template <typename _Tp, typename _Alloc>
256  _M_erase(iterator __first, iterator __last)
257  {
258  if (__first == __last)
259  return __first;
260  else if (__first == begin() && __last == end())
261  {
262  clear();
263  return end();
264  }
265  else
266  {
267  const difference_type __n = __last - __first;
268  const difference_type __elems_before = __first - begin();
269  if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2)
270  {
271  if (__first != begin())
272  _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last);
273  _M_erase_at_begin(begin() + __n);
274  }
275  else
276  {
277  if (__last != end())
278  _GLIBCXX_MOVE3(__last, end(), __first);
279  _M_erase_at_end(end() - __n);
280  }
281  return begin() + __elems_before;
282  }
283  }
284 
285  template <typename _Tp, class _Alloc>
286  template <typename _InputIterator>
287  void
289  _M_assign_aux(_InputIterator __first, _InputIterator __last,
291  {
292  iterator __cur = begin();
293  for (; __first != __last && __cur != end(); ++__cur, ++__first)
294  *__cur = *__first;
295  if (__first == __last)
296  _M_erase_at_end(__cur);
297  else
298  _M_range_insert_aux(end(), __first, __last,
299  std::__iterator_category(__first));
300  }
301 
302  template <typename _Tp, typename _Alloc>
303  void
305  _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
306  {
307  if (__pos._M_cur == this->_M_impl._M_start._M_cur)
308  {
309  iterator __new_start = _M_reserve_elements_at_front(__n);
310  __try
311  {
312  std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
313  __x, _M_get_Tp_allocator());
314  this->_M_impl._M_start = __new_start;
315  }
316  __catch(...)
317  {
318  _M_destroy_nodes(__new_start._M_node,
319  this->_M_impl._M_start._M_node);
320  __throw_exception_again;
321  }
322  }
323  else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
324  {
325  iterator __new_finish = _M_reserve_elements_at_back(__n);
326  __try
327  {
328  std::__uninitialized_fill_a(this->_M_impl._M_finish,
329  __new_finish, __x,
330  _M_get_Tp_allocator());
331  this->_M_impl._M_finish = __new_finish;
332  }
333  __catch(...)
334  {
335  _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
336  __new_finish._M_node + 1);
337  __throw_exception_again;
338  }
339  }
340  else
341  _M_insert_aux(__pos, __n, __x);
342  }
343 
344 #if __cplusplus >= 201103L
345  template <typename _Tp, typename _Alloc>
346  void
348  _M_default_append(size_type __n)
349  {
350  if (__n)
351  {
352  iterator __new_finish = _M_reserve_elements_at_back(__n);
353  __try
354  {
355  std::__uninitialized_default_a(this->_M_impl._M_finish,
356  __new_finish,
357  _M_get_Tp_allocator());
358  this->_M_impl._M_finish = __new_finish;
359  }
360  __catch(...)
361  {
362  _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
363  __new_finish._M_node + 1);
364  __throw_exception_again;
365  }
366  }
367  }
368 
369  template <typename _Tp, typename _Alloc>
370  bool
373  {
374  const difference_type __front_capacity
375  = (this->_M_impl._M_start._M_cur - this->_M_impl._M_start._M_first);
376  if (__front_capacity == 0)
377  return false;
378 
379  const difference_type __back_capacity
380  = (this->_M_impl._M_finish._M_last - this->_M_impl._M_finish._M_cur);
381  if (__front_capacity + __back_capacity < _S_buffer_size())
382  return false;
383 
384  return std::__shrink_to_fit_aux<deque>::_S_do_it(*this);
385  }
386 #endif
387 
388  template <typename _Tp, typename _Alloc>
389  void
391  _M_fill_initialize(const value_type& __value)
392  {
393  _Map_pointer __cur;
394  __try
395  {
396  for (__cur = this->_M_impl._M_start._M_node;
397  __cur < this->_M_impl._M_finish._M_node;
398  ++__cur)
399  std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
400  __value, _M_get_Tp_allocator());
401  std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
402  this->_M_impl._M_finish._M_cur,
403  __value, _M_get_Tp_allocator());
404  }
405  __catch(...)
406  {
407  std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
408  _M_get_Tp_allocator());
409  __throw_exception_again;
410  }
411  }
412 
413  template <typename _Tp, typename _Alloc>
414  template <typename _InputIterator>
415  void
417  _M_range_initialize(_InputIterator __first, _InputIterator __last,
419  {
420  this->_M_initialize_map(0);
421  __try
422  {
423  for (; __first != __last; ++__first)
424 #if __cplusplus >= 201103L
425  emplace_back(*__first);
426 #else
427  push_back(*__first);
428 #endif
429  }
430  __catch(...)
431  {
432  clear();
433  __throw_exception_again;
434  }
435  }
436 
437  template <typename _Tp, typename _Alloc>
438  template <typename _ForwardIterator>
439  void
441  _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
443  {
444  const size_type __n = std::distance(__first, __last);
445  this->_M_initialize_map(__n);
446 
447  _Map_pointer __cur_node;
448  __try
449  {
450  for (__cur_node = this->_M_impl._M_start._M_node;
451  __cur_node < this->_M_impl._M_finish._M_node;
452  ++__cur_node)
453  {
454  _ForwardIterator __mid = __first;
455  std::advance(__mid, _S_buffer_size());
456  std::__uninitialized_copy_a(__first, __mid, *__cur_node,
457  _M_get_Tp_allocator());
458  __first = __mid;
459  }
460  std::__uninitialized_copy_a(__first, __last,
461  this->_M_impl._M_finish._M_first,
462  _M_get_Tp_allocator());
463  }
464  __catch(...)
465  {
466  std::_Destroy(this->_M_impl._M_start,
467  iterator(*__cur_node, __cur_node),
468  _M_get_Tp_allocator());
469  __throw_exception_again;
470  }
471  }
472 
473  // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1.
474  template<typename _Tp, typename _Alloc>
475 #if __cplusplus >= 201103L
476  template<typename... _Args>
477  void
479  _M_push_back_aux(_Args&&... __args)
480 #else
481  void
483  _M_push_back_aux(const value_type& __t)
484 #endif
485  {
486  _M_reserve_map_at_back();
487  *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
488  __try
489  {
490 #if __cplusplus >= 201103L
491  _Alloc_traits::construct(this->_M_impl,
492  this->_M_impl._M_finish._M_cur,
493  std::forward<_Args>(__args)...);
494 #else
495  this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t);
496 #endif
497  this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
498  + 1);
499  this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
500  }
501  __catch(...)
502  {
503  _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
504  __throw_exception_again;
505  }
506  }
507 
508  // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
509  template<typename _Tp, typename _Alloc>
510 #if __cplusplus >= 201103L
511  template<typename... _Args>
512  void
514  _M_push_front_aux(_Args&&... __args)
515 #else
516  void
518  _M_push_front_aux(const value_type& __t)
519 #endif
520  {
521  _M_reserve_map_at_front();
522  *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
523  __try
524  {
525  this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
526  - 1);
527  this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
528 #if __cplusplus >= 201103L
529  _Alloc_traits::construct(this->_M_impl,
530  this->_M_impl._M_start._M_cur,
531  std::forward<_Args>(__args)...);
532 #else
533  this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t);
534 #endif
535  }
536  __catch(...)
537  {
538  ++this->_M_impl._M_start;
539  _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
540  __throw_exception_again;
541  }
542  }
543 
544  // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
545  template <typename _Tp, typename _Alloc>
548  {
549  _M_deallocate_node(this->_M_impl._M_finish._M_first);
550  this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
551  this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
552  _Alloc_traits::destroy(_M_get_Tp_allocator(),
553  this->_M_impl._M_finish._M_cur);
554  }
555 
556  // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
557  // Note that if the deque has at least one element (a precondition for this
558  // member function), and if
559  // _M_impl._M_start._M_cur == _M_impl._M_start._M_last,
560  // then the deque must have at least two nodes.
561  template <typename _Tp, typename _Alloc>
564  {
565  _Alloc_traits::destroy(_M_get_Tp_allocator(),
566  this->_M_impl._M_start._M_cur);
567  _M_deallocate_node(this->_M_impl._M_start._M_first);
568  this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
569  this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
570  }
571 
572  template <typename _Tp, typename _Alloc>
573  template <typename _InputIterator>
574  void
577  _InputIterator __first, _InputIterator __last,
579  { std::copy(__first, __last, std::inserter(*this, __pos)); }
580 
581  template <typename _Tp, typename _Alloc>
582  template <typename _ForwardIterator>
583  void
586  _ForwardIterator __first, _ForwardIterator __last,
588  {
589  const size_type __n = std::distance(__first, __last);
590  if (__pos._M_cur == this->_M_impl._M_start._M_cur)
591  {
592  iterator __new_start = _M_reserve_elements_at_front(__n);
593  __try
594  {
595  std::__uninitialized_copy_a(__first, __last, __new_start,
596  _M_get_Tp_allocator());
597  this->_M_impl._M_start = __new_start;
598  }
599  __catch(...)
600  {
601  _M_destroy_nodes(__new_start._M_node,
602  this->_M_impl._M_start._M_node);
603  __throw_exception_again;
604  }
605  }
606  else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
607  {
608  iterator __new_finish = _M_reserve_elements_at_back(__n);
609  __try
610  {
611  std::__uninitialized_copy_a(__first, __last,
612  this->_M_impl._M_finish,
613  _M_get_Tp_allocator());
614  this->_M_impl._M_finish = __new_finish;
615  }
616  __catch(...)
617  {
618  _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
619  __new_finish._M_node + 1);
620  __throw_exception_again;
621  }
622  }
623  else
624  _M_insert_aux(__pos, __first, __last, __n);
625  }
626 
627  template<typename _Tp, typename _Alloc>
628 #if __cplusplus >= 201103L
629  template<typename... _Args>
632  _M_insert_aux(iterator __pos, _Args&&... __args)
633  {
634  value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy
635 #else
638  _M_insert_aux(iterator __pos, const value_type& __x)
639  {
640  value_type __x_copy = __x; // XXX copy
641 #endif
642  difference_type __index = __pos - this->_M_impl._M_start;
643  if (static_cast<size_type>(__index) < size() / 2)
644  {
645  push_front(_GLIBCXX_MOVE(front()));
646  iterator __front1 = this->_M_impl._M_start;
647  ++__front1;
648  iterator __front2 = __front1;
649  ++__front2;
650  __pos = this->_M_impl._M_start + __index;
651  iterator __pos1 = __pos;
652  ++__pos1;
653  _GLIBCXX_MOVE3(__front2, __pos1, __front1);
654  }
655  else
656  {
657  push_back(_GLIBCXX_MOVE(back()));
658  iterator __back1 = this->_M_impl._M_finish;
659  --__back1;
660  iterator __back2 = __back1;
661  --__back2;
662  __pos = this->_M_impl._M_start + __index;
663  _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
664  }
665  *__pos = _GLIBCXX_MOVE(__x_copy);
666  return __pos;
667  }
668 
669  template <typename _Tp, typename _Alloc>
670  void
672  _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
673  {
674  const difference_type __elems_before = __pos - this->_M_impl._M_start;
675  const size_type __length = this->size();
676  value_type __x_copy = __x;
677  if (__elems_before < difference_type(__length / 2))
678  {
679  iterator __new_start = _M_reserve_elements_at_front(__n);
680  iterator __old_start = this->_M_impl._M_start;
681  __pos = this->_M_impl._M_start + __elems_before;
682  __try
683  {
684  if (__elems_before >= difference_type(__n))
685  {
686  iterator __start_n = (this->_M_impl._M_start
687  + difference_type(__n));
688  std::__uninitialized_move_a(this->_M_impl._M_start,
689  __start_n, __new_start,
690  _M_get_Tp_allocator());
691  this->_M_impl._M_start = __new_start;
692  _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
693  std::fill(__pos - difference_type(__n), __pos, __x_copy);
694  }
695  else
696  {
697  std::__uninitialized_move_fill(this->_M_impl._M_start,
698  __pos, __new_start,
699  this->_M_impl._M_start,
700  __x_copy,
701  _M_get_Tp_allocator());
702  this->_M_impl._M_start = __new_start;
703  std::fill(__old_start, __pos, __x_copy);
704  }
705  }
706  __catch(...)
707  {
708  _M_destroy_nodes(__new_start._M_node,
709  this->_M_impl._M_start._M_node);
710  __throw_exception_again;
711  }
712  }
713  else
714  {
715  iterator __new_finish = _M_reserve_elements_at_back(__n);
716  iterator __old_finish = this->_M_impl._M_finish;
717  const difference_type __elems_after =
718  difference_type(__length) - __elems_before;
719  __pos = this->_M_impl._M_finish - __elems_after;
720  __try
721  {
722  if (__elems_after > difference_type(__n))
723  {
724  iterator __finish_n = (this->_M_impl._M_finish
725  - difference_type(__n));
726  std::__uninitialized_move_a(__finish_n,
727  this->_M_impl._M_finish,
728  this->_M_impl._M_finish,
729  _M_get_Tp_allocator());
730  this->_M_impl._M_finish = __new_finish;
731  _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
732  std::fill(__pos, __pos + difference_type(__n), __x_copy);
733  }
734  else
735  {
736  std::__uninitialized_fill_move(this->_M_impl._M_finish,
737  __pos + difference_type(__n),
738  __x_copy, __pos,
739  this->_M_impl._M_finish,
740  _M_get_Tp_allocator());
741  this->_M_impl._M_finish = __new_finish;
742  std::fill(__pos, __old_finish, __x_copy);
743  }
744  }
745  __catch(...)
746  {
747  _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
748  __new_finish._M_node + 1);
749  __throw_exception_again;
750  }
751  }
752  }
753 
754  template <typename _Tp, typename _Alloc>
755  template <typename _ForwardIterator>
756  void
759  _ForwardIterator __first, _ForwardIterator __last,
760  size_type __n)
761  {
762  const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
763  const size_type __length = size();
764  if (static_cast<size_type>(__elemsbefore) < __length / 2)
765  {
766  iterator __new_start = _M_reserve_elements_at_front(__n);
767  iterator __old_start = this->_M_impl._M_start;
768  __pos = this->_M_impl._M_start + __elemsbefore;
769  __try
770  {
771  if (__elemsbefore >= difference_type(__n))
772  {
773  iterator __start_n = (this->_M_impl._M_start
774  + difference_type(__n));
775  std::__uninitialized_move_a(this->_M_impl._M_start,
776  __start_n, __new_start,
777  _M_get_Tp_allocator());
778  this->_M_impl._M_start = __new_start;
779  _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
780  std::copy(__first, __last, __pos - difference_type(__n));
781  }
782  else
783  {
784  _ForwardIterator __mid = __first;
785  std::advance(__mid, difference_type(__n) - __elemsbefore);
786  std::__uninitialized_move_copy(this->_M_impl._M_start,
787  __pos, __first, __mid,
788  __new_start,
789  _M_get_Tp_allocator());
790  this->_M_impl._M_start = __new_start;
791  std::copy(__mid, __last, __old_start);
792  }
793  }
794  __catch(...)
795  {
796  _M_destroy_nodes(__new_start._M_node,
797  this->_M_impl._M_start._M_node);
798  __throw_exception_again;
799  }
800  }
801  else
802  {
803  iterator __new_finish = _M_reserve_elements_at_back(__n);
804  iterator __old_finish = this->_M_impl._M_finish;
805  const difference_type __elemsafter =
806  difference_type(__length) - __elemsbefore;
807  __pos = this->_M_impl._M_finish - __elemsafter;
808  __try
809  {
810  if (__elemsafter > difference_type(__n))
811  {
812  iterator __finish_n = (this->_M_impl._M_finish
813  - difference_type(__n));
814  std::__uninitialized_move_a(__finish_n,
815  this->_M_impl._M_finish,
816  this->_M_impl._M_finish,
817  _M_get_Tp_allocator());
818  this->_M_impl._M_finish = __new_finish;
819  _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
820  std::copy(__first, __last, __pos);
821  }
822  else
823  {
824  _ForwardIterator __mid = __first;
825  std::advance(__mid, __elemsafter);
826  std::__uninitialized_copy_move(__mid, __last, __pos,
827  this->_M_impl._M_finish,
828  this->_M_impl._M_finish,
829  _M_get_Tp_allocator());
830  this->_M_impl._M_finish = __new_finish;
831  std::copy(__first, __mid, __pos);
832  }
833  }
834  __catch(...)
835  {
836  _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
837  __new_finish._M_node + 1);
838  __throw_exception_again;
839  }
840  }
841  }
842 
843  template<typename _Tp, typename _Alloc>
844  void
846  _M_destroy_data_aux(iterator __first, iterator __last)
847  {
848  for (_Map_pointer __node = __first._M_node + 1;
849  __node < __last._M_node; ++__node)
850  std::_Destroy(*__node, *__node + _S_buffer_size(),
851  _M_get_Tp_allocator());
852 
853  if (__first._M_node != __last._M_node)
854  {
855  std::_Destroy(__first._M_cur, __first._M_last,
856  _M_get_Tp_allocator());
857  std::_Destroy(__last._M_first, __last._M_cur,
858  _M_get_Tp_allocator());
859  }
860  else
861  std::_Destroy(__first._M_cur, __last._M_cur,
862  _M_get_Tp_allocator());
863  }
864 
865  template <typename _Tp, typename _Alloc>
866  void
868  _M_new_elements_at_front(size_type __new_elems)
869  {
870  if (this->max_size() - this->size() < __new_elems)
871  __throw_length_error(__N("deque::_M_new_elements_at_front"));
872 
873  const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
874  / _S_buffer_size());
875  _M_reserve_map_at_front(__new_nodes);
876  size_type __i;
877  __try
878  {
879  for (__i = 1; __i <= __new_nodes; ++__i)
880  *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
881  }
882  __catch(...)
883  {
884  for (size_type __j = 1; __j < __i; ++__j)
885  _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
886  __throw_exception_again;
887  }
888  }
889 
890  template <typename _Tp, typename _Alloc>
891  void
893  _M_new_elements_at_back(size_type __new_elems)
894  {
895  if (this->max_size() - this->size() < __new_elems)
896  __throw_length_error(__N("deque::_M_new_elements_at_back"));
897 
898  const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
899  / _S_buffer_size());
900  _M_reserve_map_at_back(__new_nodes);
901  size_type __i;
902  __try
903  {
904  for (__i = 1; __i <= __new_nodes; ++__i)
905  *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
906  }
907  __catch(...)
908  {
909  for (size_type __j = 1; __j < __i; ++__j)
910  _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
911  __throw_exception_again;
912  }
913  }
914 
915  template <typename _Tp, typename _Alloc>
916  void
918  _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
919  {
920  const size_type __old_num_nodes
921  = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
922  const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
923 
924  _Map_pointer __new_nstart;
925  if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
926  {
927  __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
928  - __new_num_nodes) / 2
929  + (__add_at_front ? __nodes_to_add : 0);
930  if (__new_nstart < this->_M_impl._M_start._M_node)
931  std::copy(this->_M_impl._M_start._M_node,
932  this->_M_impl._M_finish._M_node + 1,
933  __new_nstart);
934  else
935  std::copy_backward(this->_M_impl._M_start._M_node,
936  this->_M_impl._M_finish._M_node + 1,
937  __new_nstart + __old_num_nodes);
938  }
939  else
940  {
941  size_type __new_map_size = this->_M_impl._M_map_size
942  + std::max(this->_M_impl._M_map_size,
943  __nodes_to_add) + 2;
944 
945  _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
946  __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
947  + (__add_at_front ? __nodes_to_add : 0);
948  std::copy(this->_M_impl._M_start._M_node,
949  this->_M_impl._M_finish._M_node + 1,
950  __new_nstart);
951  _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
952 
953  this->_M_impl._M_map = __new_map;
954  this->_M_impl._M_map_size = __new_map_size;
955  }
956 
957  this->_M_impl._M_start._M_set_node(__new_nstart);
958  this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
959  }
960 
961  // Overload for deque::iterators, exploiting the "segmented-iterator
962  // optimization".
963  template<typename _Tp>
964  void
965  fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
966  const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value)
967  {
968  typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
969 
970  for (typename _Self::_Map_pointer __node = __first._M_node + 1;
971  __node < __last._M_node; ++__node)
972  std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
973 
974  if (__first._M_node != __last._M_node)
975  {
976  std::fill(__first._M_cur, __first._M_last, __value);
977  std::fill(__last._M_first, __last._M_cur, __value);
978  }
979  else
980  std::fill(__first._M_cur, __last._M_cur, __value);
981  }
982 
983  template<typename _Tp>
988  {
989  typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
990  typedef typename _Self::difference_type difference_type;
991 
992  difference_type __len = __last - __first;
993  while (__len > 0)
994  {
995  const difference_type __clen
996  = std::min(__len, std::min(__first._M_last - __first._M_cur,
997  __result._M_last - __result._M_cur));
998  std::copy(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
999  __first += __clen;
1000  __result += __clen;
1001  __len -= __clen;
1002  }
1003  return __result;
1004  }
1005 
1006  template<typename _Tp>
1008  copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
1011  {
1012  typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
1013  typedef typename _Self::difference_type difference_type;
1014 
1015  difference_type __len = __last - __first;
1016  while (__len > 0)
1017  {
1018  difference_type __llen = __last._M_cur - __last._M_first;
1019  _Tp* __lend = __last._M_cur;
1020 
1021  difference_type __rlen = __result._M_cur - __result._M_first;
1022  _Tp* __rend = __result._M_cur;
1023 
1024  if (!__llen)
1025  {
1026  __llen = _Self::_S_buffer_size();
1027  __lend = *(__last._M_node - 1) + __llen;
1028  }
1029  if (!__rlen)
1030  {
1031  __rlen = _Self::_S_buffer_size();
1032  __rend = *(__result._M_node - 1) + __rlen;
1033  }
1034 
1035  const difference_type __clen = std::min(__len,
1036  std::min(__llen, __rlen));
1037  std::copy_backward(__lend - __clen, __lend, __rend);
1038  __last -= __clen;
1039  __result -= __clen;
1040  __len -= __clen;
1041  }
1042  return __result;
1043  }
1044 
1045 #if __cplusplus >= 201103L
1046  template<typename _Tp>
1051  {
1052  typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
1053  typedef typename _Self::difference_type difference_type;
1054 
1055  difference_type __len = __last - __first;
1056  while (__len > 0)
1057  {
1058  const difference_type __clen
1059  = std::min(__len, std::min(__first._M_last - __first._M_cur,
1060  __result._M_last - __result._M_cur));
1061  std::move(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
1062  __first += __clen;
1063  __result += __clen;
1064  __len -= __clen;
1065  }
1066  return __result;
1067  }
1068 
1069  template<typename _Tp>
1071  move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
1074  {
1075  typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
1076  typedef typename _Self::difference_type difference_type;
1077 
1078  difference_type __len = __last - __first;
1079  while (__len > 0)
1080  {
1081  difference_type __llen = __last._M_cur - __last._M_first;
1082  _Tp* __lend = __last._M_cur;
1083 
1084  difference_type __rlen = __result._M_cur - __result._M_first;
1085  _Tp* __rend = __result._M_cur;
1086 
1087  if (!__llen)
1088  {
1089  __llen = _Self::_S_buffer_size();
1090  __lend = *(__last._M_node - 1) + __llen;
1091  }
1092  if (!__rlen)
1093  {
1094  __rlen = _Self::_S_buffer_size();
1095  __rend = *(__result._M_node - 1) + __rlen;
1096  }
1097 
1098  const difference_type __clen = std::min(__len,
1099  std::min(__llen, __rlen));
1100  std::move_backward(__lend - __clen, __lend, __rend);
1101  __last -= __clen;
1102  __result -= __clen;
1103  __len -= __clen;
1104  }
1105  return __result;
1106  }
1107 #endif
1108 
1109 _GLIBCXX_END_NAMESPACE_CONTAINER
1110 } // namespace std
1111 
1112 #endif
A standard container using fixed-size memory allocation and constant-time manipulation of elements at...
Definition: stl_deque.h:831
allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
Definition: stl_deque.h:1157
A deque::iterator.
Definition: stl_deque.h:108
iterator end() noexcept
Definition: stl_deque.h:1183
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
insert_iterator< _Container > inserter(_Container &__x, _Iterator __i)
deque & operator=(const deque &__x)
Deque assignment operator.
Definition: deque.tcc:93
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list. ...
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
ISO C++ entities toplevel namespace is std.
void _M_new_elements_at_back(size_type __new_elements)
Memory-handling helpers for the previous internal insert functions.
Definition: deque.tcc:893
void _M_pop_back_aux()
Helper functions for push_* and pop_*.
Definition: deque.tcc:547
size_type size() const noexcept
Definition: stl_deque.h:1271
void _Destroy(_Tp *__pointer)
Definition: stl_construct.h:97
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
_GLIBCXX14_CONSTEXPR const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:219
void _M_pop_front_aux()
Helper functions for push_* and pop_*.
Definition: deque.tcc:563
Marking input iterators.
iterator emplace(const_iterator __position, _Args &&... __args)
Inserts an object in deque before specified iterator.
Definition: deque.tcc:185
_GLIBCXX17_CONSTEXPR void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
Forward iterators support a superset of input iterator operations.
iterator begin() noexcept
Definition: stl_deque.h:1166
void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
Memory-handling helpers for the major map.
Definition: deque.tcc:918
void _M_range_initialize(_InputIterator __first, _InputIterator __last, std::input_iterator_tag)
Fills the deque with whatever is in [first,last).
Definition: deque.tcc:417
void _M_fill_initialize(const value_type &__value)
Fills the deque with copies of value.
Definition: deque.tcc:391
Random-access iterators support a superset of bidirectional iterator operations.
void _M_push_front_aux(_Args &&... __args)
Helper functions for push_* and pop_*.
Definition: deque.tcc:514
_GLIBCXX14_CONSTEXPR const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:195
void _M_push_back_aux(_Args &&... __args)
Helper functions for push_* and pop_*.
Definition: deque.tcc:479
void _M_new_elements_at_front(size_type __new_elements)
Memory-handling helpers for the previous internal insert functions.
Definition: deque.tcc:868