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