Clang Project

include/c++/7/bits/deque.tcc
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
59namespace 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       _M_range_insert_aux(this->_M_impl._M_finish, __mid, __x.end(),
123   std::random_access_iterator_tag());
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
137      deque<_Tp, _Alloc>::
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
161      deque<_Tp, _Alloc>::
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>
183      typename deque<_Tp, _Alloc>::iterator
184      deque<_Tp, _Alloc>::
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>
206    typename deque<_Tp, _Alloc>::iterator
207    deque<_Tp, _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>
231    typename deque<_Tp, _Alloc>::iterator
232    deque<_Tp, _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>
254    typename deque<_Tp, _Alloc>::iterator
255    deque<_Tp, _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
288      deque<_Tp, _Alloc>::
289      _M_assign_aux(_InputIterator __first, _InputIterator __last,
290     std::input_iterator_tag)
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
304    deque<_Tp, _Alloc>::
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
347    deque<_Tp, _Alloc>::
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
371    deque<_Tp, _Alloc>::
372    _M_shrink_to_fit()
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
390    deque<_Tp, _Alloc>::
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
416      deque<_Tp, _Alloc>::
417      _M_range_initialize(_InputIterator __first, _InputIterator __last,
418                          std::input_iterator_tag)
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
440      deque<_Tp, _Alloc>::
441      _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
442                          std::forward_iterator_tag)
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
478      deque<_Tp, _Alloc>::
479      _M_push_back_aux(_Args&&... __args)
480#else
481      void
482      deque<_Tp, _Alloc>::
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
513      deque<_Tp, _Alloc>::
514      _M_push_front_aux(_Args&&... __args)
515#else
516      void
517      deque<_Tp, _Alloc>::
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>
546    void deque<_Tp, _Alloc>::
547    _M_pop_back_aux()
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>
562    void deque<_Tp, _Alloc>::
563    _M_pop_front_aux()
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
575      deque<_Tp, _Alloc>::
576      _M_range_insert_aux(iterator __pos,
577                          _InputIterator __first, _InputIterator __last,
578                          std::input_iterator_tag)
579      { std::copy(__first, __last, std::inserter(*this, __pos)); }
580
581  template <typename _Tp, typename _Alloc>
582    template <typename _ForwardIterator>
583      void
584      deque<_Tp, _Alloc>::
585      _M_range_insert_aux(iterator __pos,
586                          _ForwardIterator __first, _ForwardIterator __last,
587                          std::forward_iterator_tag)
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>
630      typename deque<_Tp, _Alloc>::iterator
631      deque<_Tp, _Alloc>::
632      _M_insert_aux(iterator __pos, _Args&&... __args)
633      {
634 value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy
635#else
636    typename deque<_Tp, _Alloc>::iterator
637      deque<_Tp, _Alloc>::
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
671    deque<_Tp, _Alloc>::
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
757      deque<_Tp, _Alloc>::
758      _M_insert_aux(iterator __pos,
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
845     deque<_Tp, _Alloc>::
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
867    deque<_Tp, _Alloc>::
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
892    deque<_Tp, _Alloc>::
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
917    deque<_Tp, _Alloc>::
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>
984    _Deque_iterator<_Tp, _Tp&, _Tp*>
985    copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
986  _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
987  _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
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>
1007    _Deque_iterator<_Tp, _Tp&, _Tp*>
1008    copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
1009   _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
1010   _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
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>
1047    _Deque_iterator<_Tp, _Tp&, _Tp*>
1048    move(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
1049  _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
1050  _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
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>
1070    _Deque_iterator<_Tp, _Tp&, _Tp*>
1071    move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
1072   _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
1073   _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
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
1113
std::deque::_M_default_initialize
std::deque::emplace_front
std::deque::emplace_back
std::deque::emplace
std::deque::insert
std::deque::_M_erase
std::deque::_M_erase
std::deque::_M_assign_aux
std::deque::_M_fill_insert
std::deque::_M_default_append
std::deque::_M_shrink_to_fit
std::deque::_M_fill_initialize
std::deque::_M_range_initialize
std::deque::_M_range_initialize
std::deque::_M_push_back_aux
std::deque::_M_push_front_aux
std::deque::_M_pop_back_aux
std::deque::_M_pop_front_aux
std::deque::_M_range_insert_aux
std::deque::_M_range_insert_aux
std::deque::_M_insert_aux
std::deque::_M_insert_aux
std::deque::_M_insert_aux
std::deque::_M_destroy_data_aux
std::deque::_M_new_elements_at_front
std::deque::_M_new_elements_at_back
std::deque::_M_reallocate_map
CodeThinker, Enjoy your reading code