xref: /freebsd/contrib/llvm-project/libcxx/include/deque (revision e6bfd18d21b225af6a0ed67ceeaf1293b7b9eba5)
1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP_DEQUE
11#define _LIBCPP_DEQUE
12
13/*
14    deque synopsis
15
16namespace std
17{
18
19template <class T, class Allocator = allocator<T> >
20class deque
21{
22public:
23    // types:
24    typedef T value_type;
25    typedef Allocator allocator_type;
26
27    typedef typename allocator_type::reference       reference;
28    typedef typename allocator_type::const_reference const_reference;
29    typedef implementation-defined                   iterator;
30    typedef implementation-defined                   const_iterator;
31    typedef typename allocator_type::size_type       size_type;
32    typedef typename allocator_type::difference_type difference_type;
33
34    typedef typename allocator_type::pointer         pointer;
35    typedef typename allocator_type::const_pointer   const_pointer;
36    typedef std::reverse_iterator<iterator>          reverse_iterator;
37    typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
38
39    // construct/copy/destroy:
40    deque() noexcept(is_nothrow_default_constructible<allocator_type>::value);
41    explicit deque(const allocator_type& a);
42    explicit deque(size_type n);
43    explicit deque(size_type n, const allocator_type& a); // C++14
44    deque(size_type n, const value_type& v);
45    deque(size_type n, const value_type& v, const allocator_type& a);
46    template <class InputIterator>
47        deque(InputIterator f, InputIterator l);
48    template <class InputIterator>
49        deque(InputIterator f, InputIterator l, const allocator_type& a);
50    deque(const deque& c);
51    deque(deque&& c)
52        noexcept(is_nothrow_move_constructible<allocator_type>::value);
53    deque(initializer_list<value_type> il, const Allocator& a = allocator_type());
54    deque(const deque& c, const allocator_type& a);
55    deque(deque&& c, const allocator_type& a);
56    ~deque();
57
58    deque& operator=(const deque& c);
59    deque& operator=(deque&& c)
60        noexcept(
61             allocator_type::propagate_on_container_move_assignment::value &&
62             is_nothrow_move_assignable<allocator_type>::value);
63    deque& operator=(initializer_list<value_type> il);
64
65    template <class InputIterator>
66        void assign(InputIterator f, InputIterator l);
67    void assign(size_type n, const value_type& v);
68    void assign(initializer_list<value_type> il);
69
70    allocator_type get_allocator() const noexcept;
71
72    // iterators:
73
74    iterator       begin() noexcept;
75    const_iterator begin() const noexcept;
76    iterator       end() noexcept;
77    const_iterator end() const noexcept;
78
79    reverse_iterator       rbegin() noexcept;
80    const_reverse_iterator rbegin() const noexcept;
81    reverse_iterator       rend() noexcept;
82    const_reverse_iterator rend() const noexcept;
83
84    const_iterator         cbegin() const noexcept;
85    const_iterator         cend() const noexcept;
86    const_reverse_iterator crbegin() const noexcept;
87    const_reverse_iterator crend() const noexcept;
88
89    // capacity:
90    size_type size() const noexcept;
91    size_type max_size() const noexcept;
92    void resize(size_type n);
93    void resize(size_type n, const value_type& v);
94    void shrink_to_fit();
95    bool empty() const noexcept;
96
97    // element access:
98    reference operator[](size_type i);
99    const_reference operator[](size_type i) const;
100    reference at(size_type i);
101    const_reference at(size_type i) const;
102    reference front();
103    const_reference front() const;
104    reference back();
105    const_reference back() const;
106
107    // modifiers:
108    void push_front(const value_type& v);
109    void push_front(value_type&& v);
110    void push_back(const value_type& v);
111    void push_back(value_type&& v);
112    template <class... Args> reference emplace_front(Args&&... args);  // reference in C++17
113    template <class... Args> reference emplace_back(Args&&... args);   // reference in C++17
114    template <class... Args> iterator emplace(const_iterator p, Args&&... args);
115    iterator insert(const_iterator p, const value_type& v);
116    iterator insert(const_iterator p, value_type&& v);
117    iterator insert(const_iterator p, size_type n, const value_type& v);
118    template <class InputIterator>
119        iterator insert(const_iterator p, InputIterator f, InputIterator l);
120    iterator insert(const_iterator p, initializer_list<value_type> il);
121    void pop_front();
122    void pop_back();
123    iterator erase(const_iterator p);
124    iterator erase(const_iterator f, const_iterator l);
125    void swap(deque& c)
126        noexcept(allocator_traits<allocator_type>::is_always_equal::value);  // C++17
127    void clear() noexcept;
128};
129
130template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
131   deque(InputIterator, InputIterator, Allocator = Allocator())
132   -> deque<typename iterator_traits<InputIterator>::value_type, Allocator>; // C++17
133
134template <class T, class Allocator>
135    bool operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
136template <class T, class Allocator>
137    bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y);
138template <class T, class Allocator>
139    bool operator!=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
140template <class T, class Allocator>
141    bool operator> (const deque<T,Allocator>& x, const deque<T,Allocator>& y);
142template <class T, class Allocator>
143    bool operator>=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
144template <class T, class Allocator>
145    bool operator<=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
146
147// specialized algorithms:
148template <class T, class Allocator>
149    void swap(deque<T,Allocator>& x, deque<T,Allocator>& y)
150         noexcept(noexcept(x.swap(y)));
151
152template <class T, class Allocator, class U>
153    typename deque<T, Allocator>::size_type
154    erase(deque<T, Allocator>& c, const U& value);       // C++20
155template <class T, class Allocator, class Predicate>
156    typename deque<T, Allocator>::size_type
157    erase_if(deque<T, Allocator>& c, Predicate pred);    // C++20
158
159}  // std
160
161*/
162
163#include <__algorithm/copy.h>
164#include <__algorithm/copy_backward.h>
165#include <__algorithm/equal.h>
166#include <__algorithm/fill_n.h>
167#include <__algorithm/lexicographical_compare.h>
168#include <__algorithm/min.h>
169#include <__algorithm/remove.h>
170#include <__algorithm/remove_if.h>
171#include <__algorithm/unwrap_iter.h>
172#include <__assert> // all public C++ headers provide the assertion handler
173#include <__config>
174#include <__format/enable_insertable.h>
175#include <__iterator/iterator_traits.h>
176#include <__iterator/next.h>
177#include <__iterator/prev.h>
178#include <__iterator/reverse_iterator.h>
179#include <__split_buffer>
180#include <__utility/forward.h>
181#include <__utility/move.h>
182#include <__utility/swap.h>
183#include <limits>
184#include <stdexcept>
185#include <type_traits>
186#include <version>
187
188#ifndef _LIBCPP_REMOVE_TRANSITIVE_INCLUDES
189#  include <algorithm>
190#  include <functional>
191#  include <iterator>
192#endif
193
194// standard-mandated includes
195
196// [iterator.range]
197#include <__iterator/access.h>
198#include <__iterator/data.h>
199#include <__iterator/empty.h>
200#include <__iterator/reverse_access.h>
201#include <__iterator/size.h>
202
203// [deque.syn]
204#include <compare>
205#include <initializer_list>
206
207#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
208#  pragma GCC system_header
209#endif
210
211_LIBCPP_PUSH_MACROS
212#include <__undef_macros>
213
214
215_LIBCPP_BEGIN_NAMESPACE_STD
216
217template <class _Tp, class _Allocator> class __deque_base;
218template <class _Tp, class _Allocator = allocator<_Tp> > class _LIBCPP_TEMPLATE_VIS deque;
219
220template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,
221          class _DiffType, _DiffType _BlockSize>
222class _LIBCPP_TEMPLATE_VIS __deque_iterator;
223
224template <class _RAIter,
225          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
226__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
227copy(_RAIter __f,
228     _RAIter __l,
229     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
230     typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type* = 0);
231
232template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
233          class _OutputIterator>
234_OutputIterator
235copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
236     __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
237     _OutputIterator __r);
238
239template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
240          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
241__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
242copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
243     __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
244     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
245
246template <class _RAIter,
247          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
248__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
249copy_backward(_RAIter __f,
250              _RAIter __l,
251              __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
252              typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type* = 0);
253
254template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
255          class _OutputIterator>
256_OutputIterator
257copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
258              __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
259              _OutputIterator __r);
260
261template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
262          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
263__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
264copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
265              __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
266              __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
267
268template <class _RAIter,
269          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
270__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
271move(_RAIter __f,
272     _RAIter __l,
273     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
274     typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type* = 0);
275
276template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
277          class _OutputIterator>
278_OutputIterator
279move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
280     __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
281     _OutputIterator __r);
282
283template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
284          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
285__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
286move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
287     __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
288     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
289
290template <class _RAIter,
291          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
292__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
293move_backward(_RAIter __f,
294              _RAIter __l,
295              __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
296              typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type* = 0);
297
298template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
299          class _OutputIterator>
300_OutputIterator
301move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
302              __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
303              _OutputIterator __r);
304
305template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
306          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
307__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
308move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
309              __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
310              __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
311
312template <class _ValueType, class _DiffType>
313struct __deque_block_size {
314  static const _DiffType value = sizeof(_ValueType) < 256 ? 4096 / sizeof(_ValueType) : 16;
315};
316
317template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,
318          class _DiffType, _DiffType _BS =
319#ifdef _LIBCPP_ABI_INCOMPLETE_TYPES_IN_DEQUE
320// Keep template parameter to avoid changing all template declarations thoughout
321// this file.
322                               0
323#else
324                               __deque_block_size<_ValueType, _DiffType>::value
325#endif
326          >
327class _LIBCPP_TEMPLATE_VIS __deque_iterator
328{
329    typedef _MapPointer __map_iterator;
330public:
331    typedef _Pointer  pointer;
332    typedef _DiffType difference_type;
333private:
334    __map_iterator __m_iter_;
335    pointer        __ptr_;
336
337    static const difference_type __block_size;
338public:
339    typedef _ValueType                  value_type;
340    typedef random_access_iterator_tag  iterator_category;
341    typedef _Reference                  reference;
342
343    _LIBCPP_INLINE_VISIBILITY __deque_iterator() _NOEXCEPT
344#if _LIBCPP_STD_VER > 11
345     : __m_iter_(nullptr), __ptr_(nullptr)
346#endif
347     {}
348
349    template <class _Pp, class _Rp, class _MP>
350    _LIBCPP_INLINE_VISIBILITY
351    __deque_iterator(const __deque_iterator<value_type, _Pp, _Rp, _MP, difference_type, _BS>& __it,
352                typename enable_if<is_convertible<_Pp, pointer>::value>::type* = 0) _NOEXCEPT
353        : __m_iter_(__it.__m_iter_), __ptr_(__it.__ptr_) {}
354
355    _LIBCPP_INLINE_VISIBILITY reference operator*() const {return *__ptr_;}
356    _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return __ptr_;}
357
358    _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator++()
359    {
360        if (++__ptr_ - *__m_iter_ == __block_size)
361        {
362            ++__m_iter_;
363            __ptr_ = *__m_iter_;
364        }
365        return *this;
366    }
367
368    _LIBCPP_INLINE_VISIBILITY __deque_iterator operator++(int)
369    {
370        __deque_iterator __tmp = *this;
371        ++(*this);
372        return __tmp;
373    }
374
375    _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator--()
376    {
377        if (__ptr_ == *__m_iter_)
378        {
379            --__m_iter_;
380            __ptr_ = *__m_iter_ + __block_size;
381        }
382        --__ptr_;
383        return *this;
384    }
385
386    _LIBCPP_INLINE_VISIBILITY __deque_iterator operator--(int)
387    {
388        __deque_iterator __tmp = *this;
389        --(*this);
390        return __tmp;
391    }
392
393    _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator+=(difference_type __n)
394    {
395        if (__n != 0)
396        {
397            __n += __ptr_ - *__m_iter_;
398            if (__n > 0)
399            {
400                __m_iter_ += __n / __block_size;
401                __ptr_ = *__m_iter_ + __n % __block_size;
402            }
403            else // (__n < 0)
404            {
405                difference_type __z = __block_size - 1 - __n;
406                __m_iter_ -= __z / __block_size;
407                __ptr_ = *__m_iter_ + (__block_size - 1 - __z % __block_size);
408            }
409        }
410        return *this;
411    }
412
413    _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator-=(difference_type __n)
414    {
415        return *this += -__n;
416    }
417
418    _LIBCPP_INLINE_VISIBILITY __deque_iterator operator+(difference_type __n) const
419    {
420        __deque_iterator __t(*this);
421        __t += __n;
422        return __t;
423    }
424
425    _LIBCPP_INLINE_VISIBILITY __deque_iterator operator-(difference_type __n) const
426    {
427        __deque_iterator __t(*this);
428        __t -= __n;
429        return __t;
430    }
431
432    _LIBCPP_INLINE_VISIBILITY
433    friend __deque_iterator operator+(difference_type __n, const __deque_iterator& __it)
434        {return __it + __n;}
435
436    _LIBCPP_INLINE_VISIBILITY
437    friend difference_type operator-(const __deque_iterator& __x, const __deque_iterator& __y)
438    {
439        if (__x != __y)
440            return (__x.__m_iter_ - __y.__m_iter_) * __block_size
441                 + (__x.__ptr_ - *__x.__m_iter_)
442                 - (__y.__ptr_ - *__y.__m_iter_);
443        return 0;
444    }
445
446    _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const
447        {return *(*this + __n);}
448
449    _LIBCPP_INLINE_VISIBILITY friend
450        bool operator==(const __deque_iterator& __x, const __deque_iterator& __y)
451        {return __x.__ptr_ == __y.__ptr_;}
452
453    _LIBCPP_INLINE_VISIBILITY friend
454        bool operator!=(const __deque_iterator& __x, const __deque_iterator& __y)
455        {return !(__x == __y);}
456
457    _LIBCPP_INLINE_VISIBILITY friend
458        bool operator<(const __deque_iterator& __x, const __deque_iterator& __y)
459        {return __x.__m_iter_ < __y.__m_iter_ ||
460               (__x.__m_iter_ == __y.__m_iter_ && __x.__ptr_ < __y.__ptr_);}
461
462    _LIBCPP_INLINE_VISIBILITY friend
463        bool operator>(const __deque_iterator& __x, const __deque_iterator& __y)
464        {return __y < __x;}
465
466    _LIBCPP_INLINE_VISIBILITY friend
467        bool operator<=(const __deque_iterator& __x, const __deque_iterator& __y)
468        {return !(__y < __x);}
469
470    _LIBCPP_INLINE_VISIBILITY friend
471        bool operator>=(const __deque_iterator& __x, const __deque_iterator& __y)
472        {return !(__x < __y);}
473
474private:
475    _LIBCPP_INLINE_VISIBILITY explicit __deque_iterator(__map_iterator __m, pointer __p) _NOEXCEPT
476        : __m_iter_(__m), __ptr_(__p) {}
477
478    template <class _Tp, class _Ap> friend class __deque_base;
479    template <class _Tp, class _Ap> friend class _LIBCPP_TEMPLATE_VIS deque;
480    template <class _Vp, class _Pp, class _Rp, class _MP, class _Dp, _Dp>
481        friend class _LIBCPP_TEMPLATE_VIS __deque_iterator;
482
483    template <class _RAIter,
484              class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
485    friend
486    __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
487    copy(_RAIter __f,
488         _RAIter __l,
489         __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
490         typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*);
491
492    template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
493              class _OutputIterator>
494    friend
495    _OutputIterator
496    copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
497         __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
498         _OutputIterator __r);
499
500    template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
501              class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
502    friend
503    __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
504    copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
505         __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
506         __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
507
508    template <class _RAIter,
509              class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
510    friend
511    __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
512    copy_backward(_RAIter __f,
513                  _RAIter __l,
514                  __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
515                  typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*);
516
517    template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
518              class _OutputIterator>
519    friend
520    _OutputIterator
521    copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
522                  __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
523                  _OutputIterator __r);
524
525    template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
526              class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
527    friend
528    __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
529    copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
530                  __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
531                  __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
532
533    template <class _RAIter,
534              class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
535    friend
536    __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
537    move(_RAIter __f,
538         _RAIter __l,
539         __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
540         typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*);
541
542    template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
543              class _OutputIterator>
544    friend
545    _OutputIterator
546    move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
547         __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
548         _OutputIterator __r);
549
550    template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
551              class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
552    friend
553    __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
554    move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
555         __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
556         __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
557
558    template <class _RAIter,
559              class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
560    friend
561    __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
562    move_backward(_RAIter __f,
563                  _RAIter __l,
564                  __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
565                  typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*);
566
567    template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
568              class _OutputIterator>
569    friend
570    _OutputIterator
571    move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
572                  __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
573                  _OutputIterator __r);
574
575    template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
576              class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
577    friend
578    __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
579    move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
580                  __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
581                  __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
582};
583
584template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,
585          class _DiffType, _DiffType _BlockSize>
586const _DiffType __deque_iterator<_ValueType, _Pointer, _Reference, _MapPointer,
587                                 _DiffType, _BlockSize>::__block_size =
588    __deque_block_size<_ValueType, _DiffType>::value;
589
590// copy
591
592template <class _RAIter,
593          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
594__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
595copy(_RAIter __f,
596     _RAIter __l,
597     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
598     typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*)
599{
600    typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;
601    typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;
602    const difference_type __block_size = __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::__block_size;
603    while (__f != __l)
604    {
605        pointer __rb = __r.__ptr_;
606        pointer __re = *__r.__m_iter_ + __block_size;
607        difference_type __bs = __re - __rb;
608        difference_type __n = __l - __f;
609        _RAIter __m = __l;
610        if (__n > __bs)
611        {
612            __n = __bs;
613            __m = __f + __n;
614        }
615        _VSTD::copy(__f, __m, __rb);
616        __f = __m;
617        __r += __n;
618    }
619    return __r;
620}
621
622template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
623          class _OutputIterator>
624_OutputIterator
625copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
626     __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
627     _OutputIterator __r)
628{
629    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
630    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
631    const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size;
632    difference_type __n = __l - __f;
633    while (__n > 0)
634    {
635        pointer __fb = __f.__ptr_;
636        pointer __fe = *__f.__m_iter_ + __block_size;
637        difference_type __bs = __fe - __fb;
638        if (__bs > __n)
639        {
640            __bs = __n;
641            __fe = __fb + __bs;
642        }
643        __r = _VSTD::copy(__fb, __fe, __r);
644        __n -= __bs;
645        __f += __bs;
646    }
647    return __r;
648}
649
650template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
651          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
652__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
653copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
654     __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
655     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)
656{
657    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
658    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
659    const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size;
660    difference_type __n = __l - __f;
661    while (__n > 0)
662    {
663        pointer __fb = __f.__ptr_;
664        pointer __fe = *__f.__m_iter_ + __block_size;
665        difference_type __bs = __fe - __fb;
666        if (__bs > __n)
667        {
668            __bs = __n;
669            __fe = __fb + __bs;
670        }
671        __r = _VSTD::copy(__fb, __fe, __r);
672        __n -= __bs;
673        __f += __bs;
674    }
675    return __r;
676}
677
678// copy_backward
679
680template <class _RAIter,
681          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
682__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
683copy_backward(_RAIter __f,
684              _RAIter __l,
685              __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
686              typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*)
687{
688    typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;
689    typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;
690    while (__f != __l)
691    {
692        __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __rp = _VSTD::prev(__r);
693        pointer __rb = *__rp.__m_iter_;
694        pointer __re = __rp.__ptr_ + 1;
695        difference_type __bs = __re - __rb;
696        difference_type __n = __l - __f;
697        _RAIter __m = __f;
698        if (__n > __bs)
699        {
700            __n = __bs;
701            __m = __l - __n;
702        }
703        _VSTD::copy_backward(__m, __l, __re);
704        __l = __m;
705        __r -= __n;
706    }
707    return __r;
708}
709
710template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
711          class _OutputIterator>
712_OutputIterator
713copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
714              __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
715              _OutputIterator __r)
716{
717    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
718    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
719    difference_type __n = __l - __f;
720    while (__n > 0)
721    {
722        --__l;
723        pointer __lb = *__l.__m_iter_;
724        pointer __le = __l.__ptr_ + 1;
725        difference_type __bs = __le - __lb;
726        if (__bs > __n)
727        {
728            __bs = __n;
729            __lb = __le - __bs;
730        }
731        __r = _VSTD::copy_backward(__lb, __le, __r);
732        __n -= __bs;
733        __l -= __bs - 1;
734    }
735    return __r;
736}
737
738template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
739          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
740__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
741copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
742              __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
743              __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)
744{
745    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
746    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
747    difference_type __n = __l - __f;
748    while (__n > 0)
749    {
750        --__l;
751        pointer __lb = *__l.__m_iter_;
752        pointer __le = __l.__ptr_ + 1;
753        difference_type __bs = __le - __lb;
754        if (__bs > __n)
755        {
756            __bs = __n;
757            __lb = __le - __bs;
758        }
759        __r = _VSTD::copy_backward(__lb, __le, __r);
760        __n -= __bs;
761        __l -= __bs - 1;
762    }
763    return __r;
764}
765
766// move
767
768template <class _RAIter,
769          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
770__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
771move(_RAIter __f,
772     _RAIter __l,
773     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
774     typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*)
775{
776    typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;
777    typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;
778    const difference_type __block_size = __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::__block_size;
779    while (__f != __l)
780    {
781        pointer __rb = __r.__ptr_;
782        pointer __re = *__r.__m_iter_ + __block_size;
783        difference_type __bs = __re - __rb;
784        difference_type __n = __l - __f;
785        _RAIter __m = __l;
786        if (__n > __bs)
787        {
788            __n = __bs;
789            __m = __f + __n;
790        }
791        _VSTD::move(__f, __m, __rb);
792        __f = __m;
793        __r += __n;
794    }
795    return __r;
796}
797
798template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
799          class _OutputIterator>
800_OutputIterator
801move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
802     __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
803     _OutputIterator __r)
804{
805    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
806    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
807    const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size;
808    difference_type __n = __l - __f;
809    while (__n > 0)
810    {
811        pointer __fb = __f.__ptr_;
812        pointer __fe = *__f.__m_iter_ + __block_size;
813        difference_type __bs = __fe - __fb;
814        if (__bs > __n)
815        {
816            __bs = __n;
817            __fe = __fb + __bs;
818        }
819        __r = _VSTD::move(__fb, __fe, __r);
820        __n -= __bs;
821        __f += __bs;
822    }
823    return __r;
824}
825
826template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
827          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
828__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
829move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
830     __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
831     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)
832{
833    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
834    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
835    const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size;
836    difference_type __n = __l - __f;
837    while (__n > 0)
838    {
839        pointer __fb = __f.__ptr_;
840        pointer __fe = *__f.__m_iter_ + __block_size;
841        difference_type __bs = __fe - __fb;
842        if (__bs > __n)
843        {
844            __bs = __n;
845            __fe = __fb + __bs;
846        }
847        __r = _VSTD::move(__fb, __fe, __r);
848        __n -= __bs;
849        __f += __bs;
850    }
851    return __r;
852}
853
854// move_backward
855
856template <class _RAIter,
857          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
858__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
859move_backward(_RAIter __f,
860              _RAIter __l,
861              __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
862              typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*)
863{
864    typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;
865    typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;
866    while (__f != __l)
867    {
868        __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __rp = _VSTD::prev(__r);
869        pointer __rb = *__rp.__m_iter_;
870        pointer __re = __rp.__ptr_ + 1;
871        difference_type __bs = __re - __rb;
872        difference_type __n = __l - __f;
873        _RAIter __m = __f;
874        if (__n > __bs)
875        {
876            __n = __bs;
877            __m = __l - __n;
878        }
879        _VSTD::move_backward(__m, __l, __re);
880        __l = __m;
881        __r -= __n;
882    }
883    return __r;
884}
885
886template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
887          class _OutputIterator>
888_OutputIterator
889move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
890              __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
891              _OutputIterator __r)
892{
893    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
894    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
895    difference_type __n = __l - __f;
896    while (__n > 0)
897    {
898        --__l;
899        pointer __lb = *__l.__m_iter_;
900        pointer __le = __l.__ptr_ + 1;
901        difference_type __bs = __le - __lb;
902        if (__bs > __n)
903        {
904            __bs = __n;
905            __lb = __le - __bs;
906        }
907        __r = _VSTD::move_backward(__lb, __le, __r);
908        __n -= __bs;
909        __l -= __bs - 1;
910    }
911    return __r;
912}
913
914template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
915          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
916__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
917move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
918              __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
919              __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)
920{
921    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
922    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
923    difference_type __n = __l - __f;
924    while (__n > 0)
925    {
926        --__l;
927        pointer __lb = *__l.__m_iter_;
928        pointer __le = __l.__ptr_ + 1;
929        difference_type __bs = __le - __lb;
930        if (__bs > __n)
931        {
932            __bs = __n;
933            __lb = __le - __bs;
934        }
935        __r = _VSTD::move_backward(__lb, __le, __r);
936        __n -= __bs;
937        __l -= __bs - 1;
938    }
939    return __r;
940}
941
942template <class _Tp, class _Allocator>
943class __deque_base
944{
945    __deque_base(const __deque_base& __c);
946    __deque_base& operator=(const __deque_base& __c);
947public:
948    typedef _Allocator                                allocator_type;
949    typedef allocator_traits<allocator_type>          __alloc_traits;
950    typedef typename __alloc_traits::size_type        size_type;
951
952    typedef _Tp                                       value_type;
953    typedef value_type&                               reference;
954    typedef const value_type&                         const_reference;
955    typedef typename __alloc_traits::difference_type  difference_type;
956    typedef typename __alloc_traits::pointer          pointer;
957    typedef typename __alloc_traits::const_pointer    const_pointer;
958
959    static const difference_type __block_size;
960
961    typedef typename __rebind_alloc_helper<__alloc_traits, pointer>::type __pointer_allocator;
962    typedef allocator_traits<__pointer_allocator>        __map_traits;
963    typedef typename __map_traits::pointer               __map_pointer;
964    typedef typename __rebind_alloc_helper<__alloc_traits, const_pointer>::type __const_pointer_allocator;
965    typedef typename allocator_traits<__const_pointer_allocator>::const_pointer __map_const_pointer;
966    typedef __split_buffer<pointer, __pointer_allocator> __map;
967
968    typedef __deque_iterator<value_type, pointer, reference, __map_pointer,
969                             difference_type>    iterator;
970    typedef __deque_iterator<value_type, const_pointer, const_reference, __map_const_pointer,
971                             difference_type>    const_iterator;
972
973    struct __deque_block_range {
974      explicit __deque_block_range(pointer __b, pointer __e) _NOEXCEPT : __begin_(__b), __end_(__e) {}
975      const pointer __begin_;
976      const pointer __end_;
977    };
978
979    struct __deque_range {
980      iterator __pos_;
981      const iterator __end_;
982
983      __deque_range(iterator __pos, iterator __e) _NOEXCEPT
984        : __pos_(__pos), __end_(__e) {}
985
986      explicit operator bool() const _NOEXCEPT {
987        return __pos_ != __end_;
988      }
989
990      __deque_range begin() const {
991        return *this;
992      }
993
994      __deque_range end() const {
995        return __deque_range(__end_, __end_);
996      }
997      __deque_block_range operator*() const _NOEXCEPT {
998         if (__pos_.__m_iter_ == __end_.__m_iter_) {
999          return __deque_block_range(__pos_.__ptr_, __end_.__ptr_);
1000        }
1001        return __deque_block_range(__pos_.__ptr_, *__pos_.__m_iter_ + __block_size);
1002      }
1003
1004      __deque_range& operator++() _NOEXCEPT {
1005        if (__pos_.__m_iter_ == __end_.__m_iter_) {
1006          __pos_ = __end_;
1007        } else {
1008          ++__pos_.__m_iter_;
1009          __pos_.__ptr_ = *__pos_.__m_iter_;
1010        }
1011        return *this;
1012      }
1013
1014
1015      friend bool operator==(__deque_range const& __lhs, __deque_range const& __rhs) {
1016        return __lhs.__pos_ == __rhs.__pos_;
1017      }
1018      friend bool operator!=(__deque_range const& __lhs, __deque_range const& __rhs) {
1019        return !(__lhs == __rhs);
1020      }
1021    };
1022
1023
1024
1025    struct _ConstructTransaction {
1026      _ConstructTransaction(__deque_base* __db, __deque_block_range& __r)
1027        : __pos_(__r.__begin_), __end_(__r.__end_), __begin_(__r.__begin_), __base_(__db) {}
1028
1029
1030      ~_ConstructTransaction() {
1031        __base_->size() += (__pos_ - __begin_);
1032      }
1033
1034      pointer __pos_;
1035      const pointer __end_;
1036    private:
1037      const pointer __begin_;
1038      __deque_base * const __base_;
1039    };
1040
1041protected:
1042    __map __map_;
1043    size_type __start_;
1044    __compressed_pair<size_type, allocator_type> __size_;
1045
1046    iterator       begin() _NOEXCEPT;
1047    const_iterator begin() const _NOEXCEPT;
1048    iterator       end() _NOEXCEPT;
1049    const_iterator end() const _NOEXCEPT;
1050
1051    _LIBCPP_INLINE_VISIBILITY size_type&            size()          {return __size_.first();}
1052    _LIBCPP_INLINE_VISIBILITY
1053    const size_type& size() const _NOEXCEPT {return __size_.first();}
1054    _LIBCPP_INLINE_VISIBILITY allocator_type&       __alloc()       {return __size_.second();}
1055    _LIBCPP_INLINE_VISIBILITY
1056    const allocator_type& __alloc() const _NOEXCEPT {return __size_.second();}
1057
1058    _LIBCPP_INLINE_VISIBILITY
1059    __deque_base()
1060        _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
1061    _LIBCPP_INLINE_VISIBILITY
1062    explicit __deque_base(const allocator_type& __a);
1063public:
1064    ~__deque_base();
1065
1066#ifndef _LIBCPP_CXX03_LANG
1067    __deque_base(__deque_base&& __c)
1068        _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
1069    __deque_base(__deque_base&& __c, const allocator_type& __a);
1070#endif // _LIBCPP_CXX03_LANG
1071
1072    void swap(__deque_base& __c)
1073#if _LIBCPP_STD_VER >= 14
1074        _NOEXCEPT;
1075#else
1076        _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
1077                    __is_nothrow_swappable<allocator_type>::value);
1078#endif
1079protected:
1080    void clear() _NOEXCEPT;
1081
1082    bool __invariants() const;
1083
1084    _LIBCPP_INLINE_VISIBILITY
1085    void __move_assign(__deque_base& __c)
1086        _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&
1087                   is_nothrow_move_assignable<allocator_type>::value)
1088    {
1089        __map_ = _VSTD::move(__c.__map_);
1090        __start_ = __c.__start_;
1091        size() = __c.size();
1092        __move_assign_alloc(__c);
1093        __c.__start_ = __c.size() = 0;
1094    }
1095
1096    _LIBCPP_INLINE_VISIBILITY
1097    void __move_assign_alloc(__deque_base& __c)
1098        _NOEXCEPT_(!__alloc_traits::propagate_on_container_move_assignment::value ||
1099                   is_nothrow_move_assignable<allocator_type>::value)
1100        {__move_assign_alloc(__c, integral_constant<bool,
1101                      __alloc_traits::propagate_on_container_move_assignment::value>());}
1102
1103private:
1104    _LIBCPP_INLINE_VISIBILITY
1105    void __move_assign_alloc(__deque_base& __c, true_type)
1106        _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
1107        {
1108            __alloc() = _VSTD::move(__c.__alloc());
1109        }
1110
1111    _LIBCPP_INLINE_VISIBILITY
1112    void __move_assign_alloc(__deque_base&, false_type) _NOEXCEPT
1113        {}
1114};
1115
1116template <class _Tp, class _Allocator>
1117const typename __deque_base<_Tp, _Allocator>::difference_type
1118    __deque_base<_Tp, _Allocator>::__block_size =
1119        __deque_block_size<value_type, difference_type>::value;
1120
1121template <class _Tp, class _Allocator>
1122bool
1123__deque_base<_Tp, _Allocator>::__invariants() const
1124{
1125    if (!__map_.__invariants())
1126        return false;
1127    if (__map_.size() >= size_type(-1) / __block_size)
1128        return false;
1129    for (typename __map::const_iterator __i = __map_.begin(), __e = __map_.end();
1130         __i != __e; ++__i)
1131        if (*__i == nullptr)
1132            return false;
1133    if (__map_.size() != 0)
1134    {
1135        if (size() >= __map_.size() * __block_size)
1136            return false;
1137        if (__start_ >= __map_.size() * __block_size - size())
1138            return false;
1139    }
1140    else
1141    {
1142        if (size() != 0)
1143            return false;
1144        if (__start_ != 0)
1145            return false;
1146    }
1147    return true;
1148}
1149
1150template <class _Tp, class _Allocator>
1151typename __deque_base<_Tp, _Allocator>::iterator
1152__deque_base<_Tp, _Allocator>::begin() _NOEXCEPT
1153{
1154    __map_pointer __mp = __map_.begin() + __start_ / __block_size;
1155    return iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size);
1156}
1157
1158template <class _Tp, class _Allocator>
1159typename __deque_base<_Tp, _Allocator>::const_iterator
1160__deque_base<_Tp, _Allocator>::begin() const _NOEXCEPT
1161{
1162    __map_const_pointer __mp = static_cast<__map_const_pointer>(__map_.begin() + __start_ / __block_size);
1163    return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size);
1164}
1165
1166template <class _Tp, class _Allocator>
1167typename __deque_base<_Tp, _Allocator>::iterator
1168__deque_base<_Tp, _Allocator>::end() _NOEXCEPT
1169{
1170    size_type __p = size() + __start_;
1171    __map_pointer __mp = __map_.begin() + __p / __block_size;
1172    return iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size);
1173}
1174
1175template <class _Tp, class _Allocator>
1176typename __deque_base<_Tp, _Allocator>::const_iterator
1177__deque_base<_Tp, _Allocator>::end() const _NOEXCEPT
1178{
1179    size_type __p = size() + __start_;
1180    __map_const_pointer __mp = static_cast<__map_const_pointer>(__map_.begin() + __p / __block_size);
1181    return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size);
1182}
1183
1184template <class _Tp, class _Allocator>
1185inline
1186__deque_base<_Tp, _Allocator>::__deque_base()
1187    _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
1188    : __start_(0), __size_(0, __default_init_tag()) {}
1189
1190template <class _Tp, class _Allocator>
1191inline
1192__deque_base<_Tp, _Allocator>::__deque_base(const allocator_type& __a)
1193    : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a) {}
1194
1195template <class _Tp, class _Allocator>
1196__deque_base<_Tp, _Allocator>::~__deque_base()
1197{
1198    clear();
1199    typename __map::iterator __i = __map_.begin();
1200    typename __map::iterator __e = __map_.end();
1201    for (; __i != __e; ++__i)
1202        __alloc_traits::deallocate(__alloc(), *__i, __block_size);
1203}
1204
1205#ifndef _LIBCPP_CXX03_LANG
1206
1207template <class _Tp, class _Allocator>
1208__deque_base<_Tp, _Allocator>::__deque_base(__deque_base&& __c)
1209    _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
1210    : __map_(_VSTD::move(__c.__map_)),
1211      __start_(_VSTD::move(__c.__start_)),
1212      __size_(_VSTD::move(__c.__size_))
1213{
1214    __c.__start_ = 0;
1215    __c.size() = 0;
1216}
1217
1218template <class _Tp, class _Allocator>
1219__deque_base<_Tp, _Allocator>::__deque_base(__deque_base&& __c, const allocator_type& __a)
1220    : __map_(_VSTD::move(__c.__map_), __pointer_allocator(__a)),
1221      __start_(_VSTD::move(__c.__start_)),
1222      __size_(_VSTD::move(__c.size()), __a)
1223{
1224    if (__a == __c.__alloc())
1225    {
1226        __c.__start_ = 0;
1227        __c.size() = 0;
1228    }
1229    else
1230    {
1231        __map_.clear();
1232        __start_ = 0;
1233        size() = 0;
1234    }
1235}
1236
1237#endif // _LIBCPP_CXX03_LANG
1238
1239template <class _Tp, class _Allocator>
1240void
1241__deque_base<_Tp, _Allocator>::swap(__deque_base& __c)
1242#if _LIBCPP_STD_VER >= 14
1243        _NOEXCEPT
1244#else
1245        _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
1246                    __is_nothrow_swappable<allocator_type>::value)
1247#endif
1248{
1249    __map_.swap(__c.__map_);
1250    _VSTD::swap(__start_, __c.__start_);
1251    _VSTD::swap(size(), __c.size());
1252    _VSTD::__swap_allocator(__alloc(), __c.__alloc());
1253}
1254
1255template <class _Tp, class _Allocator>
1256void
1257__deque_base<_Tp, _Allocator>::clear() _NOEXCEPT
1258{
1259    allocator_type& __a = __alloc();
1260    for (iterator __i = begin(), __e = end(); __i != __e; ++__i)
1261        __alloc_traits::destroy(__a, _VSTD::addressof(*__i));
1262    size() = 0;
1263    while (__map_.size() > 2)
1264    {
1265        __alloc_traits::deallocate(__a, __map_.front(), __block_size);
1266        __map_.pop_front();
1267    }
1268    switch (__map_.size())
1269    {
1270    case 1:
1271        __start_ = __block_size / 2;
1272        break;
1273    case 2:
1274        __start_ = __block_size;
1275        break;
1276    }
1277}
1278
1279template <class _Tp, class _Allocator /*= allocator<_Tp>*/>
1280class _LIBCPP_TEMPLATE_VIS deque
1281    : private __deque_base<_Tp, _Allocator>
1282{
1283public:
1284    // types:
1285
1286    typedef _Tp value_type;
1287    typedef _Allocator allocator_type;
1288
1289    static_assert((is_same<typename allocator_type::value_type, value_type>::value),
1290                  "Allocator::value_type must be same type as value_type");
1291
1292    typedef __deque_base<value_type, allocator_type>      __base;
1293
1294    typedef typename __base::__alloc_traits               __alloc_traits;
1295    typedef typename __base::reference                    reference;
1296    typedef typename __base::const_reference              const_reference;
1297    typedef typename __base::iterator                     iterator;
1298    typedef typename __base::const_iterator               const_iterator;
1299    typedef typename __base::size_type                    size_type;
1300    typedef typename __base::difference_type              difference_type;
1301
1302    typedef typename __base::pointer                      pointer;
1303    typedef typename __base::const_pointer                const_pointer;
1304    typedef _VSTD::reverse_iterator<iterator>             reverse_iterator;
1305    typedef _VSTD::reverse_iterator<const_iterator>       const_reverse_iterator;
1306
1307    using typename __base::__deque_range;
1308    using typename __base::__deque_block_range;
1309    using typename __base::_ConstructTransaction;
1310
1311    // construct/copy/destroy:
1312    _LIBCPP_INLINE_VISIBILITY
1313    deque()
1314        _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
1315        {}
1316    _LIBCPP_INLINE_VISIBILITY explicit deque(const allocator_type& __a) : __base(__a) {}
1317    explicit deque(size_type __n);
1318#if _LIBCPP_STD_VER > 11
1319    explicit deque(size_type __n, const _Allocator& __a);
1320#endif
1321    deque(size_type __n, const value_type& __v);
1322
1323    template <class = __enable_if_t<__is_allocator<_Allocator>::value> >
1324    deque(size_type __n, const value_type& __v, const allocator_type& __a) : __base(__a)
1325    {
1326        if (__n > 0)
1327            __append(__n, __v);
1328    }
1329
1330    template <class _InputIter>
1331        deque(_InputIter __f, _InputIter __l,
1332              typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type* = 0);
1333    template <class _InputIter>
1334        deque(_InputIter __f, _InputIter __l, const allocator_type& __a,
1335              typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type* = 0);
1336    deque(const deque& __c);
1337    deque(const deque& __c, const __type_identity_t<allocator_type>& __a);
1338
1339    deque& operator=(const deque& __c);
1340
1341#ifndef _LIBCPP_CXX03_LANG
1342    deque(initializer_list<value_type> __il);
1343    deque(initializer_list<value_type> __il, const allocator_type& __a);
1344
1345    _LIBCPP_INLINE_VISIBILITY
1346    deque& operator=(initializer_list<value_type> __il) {assign(__il); return *this;}
1347
1348    _LIBCPP_INLINE_VISIBILITY
1349    deque(deque&& __c) _NOEXCEPT_(is_nothrow_move_constructible<__base>::value);
1350    _LIBCPP_INLINE_VISIBILITY
1351    deque(deque&& __c, const __type_identity_t<allocator_type>& __a);
1352    _LIBCPP_INLINE_VISIBILITY
1353    deque& operator=(deque&& __c)
1354        _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&
1355                   is_nothrow_move_assignable<allocator_type>::value);
1356
1357    _LIBCPP_INLINE_VISIBILITY
1358    void assign(initializer_list<value_type> __il) {assign(__il.begin(), __il.end());}
1359#endif // _LIBCPP_CXX03_LANG
1360
1361    template <class _InputIter>
1362        void assign(_InputIter __f, _InputIter __l,
1363                    typename enable_if<__is_cpp17_input_iterator<_InputIter>::value &&
1364                                      !__is_cpp17_random_access_iterator<_InputIter>::value>::type* = 0);
1365    template <class _RAIter>
1366        void assign(_RAIter __f, _RAIter __l,
1367                    typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type* = 0);
1368    void assign(size_type __n, const value_type& __v);
1369
1370    _LIBCPP_INLINE_VISIBILITY
1371    allocator_type get_allocator() const _NOEXCEPT;
1372
1373    // iterators:
1374
1375    _LIBCPP_INLINE_VISIBILITY
1376    iterator       begin() _NOEXCEPT       {return __base::begin();}
1377    _LIBCPP_INLINE_VISIBILITY
1378    const_iterator begin() const _NOEXCEPT {return __base::begin();}
1379    _LIBCPP_INLINE_VISIBILITY
1380    iterator       end() _NOEXCEPT         {return __base::end();}
1381    _LIBCPP_INLINE_VISIBILITY
1382    const_iterator end()   const _NOEXCEPT {return __base::end();}
1383
1384    _LIBCPP_INLINE_VISIBILITY
1385    reverse_iterator       rbegin() _NOEXCEPT
1386        {return       reverse_iterator(__base::end());}
1387    _LIBCPP_INLINE_VISIBILITY
1388    const_reverse_iterator rbegin() const _NOEXCEPT
1389        {return const_reverse_iterator(__base::end());}
1390    _LIBCPP_INLINE_VISIBILITY
1391    reverse_iterator       rend() _NOEXCEPT
1392        {return       reverse_iterator(__base::begin());}
1393    _LIBCPP_INLINE_VISIBILITY
1394    const_reverse_iterator rend()   const _NOEXCEPT
1395        {return const_reverse_iterator(__base::begin());}
1396
1397    _LIBCPP_INLINE_VISIBILITY
1398    const_iterator         cbegin()  const _NOEXCEPT
1399        {return __base::begin();}
1400    _LIBCPP_INLINE_VISIBILITY
1401    const_iterator         cend()    const _NOEXCEPT
1402        {return __base::end();}
1403    _LIBCPP_INLINE_VISIBILITY
1404    const_reverse_iterator crbegin() const _NOEXCEPT
1405        {return const_reverse_iterator(__base::end());}
1406    _LIBCPP_INLINE_VISIBILITY
1407    const_reverse_iterator crend()   const _NOEXCEPT
1408        {return const_reverse_iterator(__base::begin());}
1409
1410    // capacity:
1411    _LIBCPP_INLINE_VISIBILITY
1412    size_type size() const _NOEXCEPT {return __base::size();}
1413    _LIBCPP_INLINE_VISIBILITY
1414    size_type max_size() const _NOEXCEPT
1415        {return _VSTD::min<size_type>(
1416            __alloc_traits::max_size(__base::__alloc()),
1417            numeric_limits<difference_type>::max());}
1418    void resize(size_type __n);
1419    void resize(size_type __n, const value_type& __v);
1420    void shrink_to_fit() _NOEXCEPT;
1421    _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1422    bool empty() const _NOEXCEPT {return __base::size() == 0;}
1423
1424    // element access:
1425    _LIBCPP_INLINE_VISIBILITY
1426    reference operator[](size_type __i) _NOEXCEPT;
1427    _LIBCPP_INLINE_VISIBILITY
1428    const_reference operator[](size_type __i) const _NOEXCEPT;
1429    _LIBCPP_INLINE_VISIBILITY
1430    reference at(size_type __i);
1431    _LIBCPP_INLINE_VISIBILITY
1432    const_reference at(size_type __i) const;
1433    _LIBCPP_INLINE_VISIBILITY
1434    reference front() _NOEXCEPT;
1435    _LIBCPP_INLINE_VISIBILITY
1436    const_reference front() const _NOEXCEPT;
1437    _LIBCPP_INLINE_VISIBILITY
1438    reference back() _NOEXCEPT;
1439    _LIBCPP_INLINE_VISIBILITY
1440    const_reference back() const _NOEXCEPT;
1441
1442    // 23.2.2.3 modifiers:
1443    void push_front(const value_type& __v);
1444    void push_back(const value_type& __v);
1445#ifndef _LIBCPP_CXX03_LANG
1446#if _LIBCPP_STD_VER > 14
1447    template <class... _Args> reference emplace_front(_Args&&... __args);
1448    template <class... _Args> reference emplace_back (_Args&&... __args);
1449#else
1450    template <class... _Args> void      emplace_front(_Args&&... __args);
1451    template <class... _Args> void      emplace_back (_Args&&... __args);
1452#endif
1453    template <class... _Args> iterator emplace(const_iterator __p, _Args&&... __args);
1454
1455    void push_front(value_type&& __v);
1456    void push_back(value_type&& __v);
1457    iterator insert(const_iterator __p, value_type&& __v);
1458
1459    _LIBCPP_INLINE_VISIBILITY
1460    iterator insert(const_iterator __p, initializer_list<value_type> __il)
1461        {return insert(__p, __il.begin(), __il.end());}
1462#endif // _LIBCPP_CXX03_LANG
1463    iterator insert(const_iterator __p, const value_type& __v);
1464    iterator insert(const_iterator __p, size_type __n, const value_type& __v);
1465    template <class _InputIter>
1466        iterator insert(const_iterator __p, _InputIter __f, _InputIter __l,
1467                         typename enable_if<__is_exactly_cpp17_input_iterator<_InputIter>::value>::type* = 0);
1468    template <class _ForwardIterator>
1469        iterator insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l,
1470                        typename enable_if<__is_exactly_cpp17_forward_iterator<_ForwardIterator>::value>::type* = 0);
1471    template <class _BiIter>
1472        iterator insert(const_iterator __p, _BiIter __f, _BiIter __l,
1473                         typename enable_if<__is_cpp17_bidirectional_iterator<_BiIter>::value>::type* = 0);
1474
1475    void pop_front();
1476    void pop_back();
1477    iterator erase(const_iterator __p);
1478    iterator erase(const_iterator __f, const_iterator __l);
1479
1480    _LIBCPP_INLINE_VISIBILITY
1481    void swap(deque& __c)
1482#if _LIBCPP_STD_VER >= 14
1483        _NOEXCEPT;
1484#else
1485        _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
1486                   __is_nothrow_swappable<allocator_type>::value);
1487#endif
1488    _LIBCPP_INLINE_VISIBILITY
1489    void clear() _NOEXCEPT;
1490
1491    _LIBCPP_INLINE_VISIBILITY
1492    bool __invariants() const {return __base::__invariants();}
1493
1494    typedef typename __base::__map_const_pointer __map_const_pointer;
1495
1496    _LIBCPP_INLINE_VISIBILITY
1497    static size_type __recommend_blocks(size_type __n)
1498    {
1499        return __n / __base::__block_size + (__n % __base::__block_size != 0);
1500    }
1501    _LIBCPP_INLINE_VISIBILITY
1502    size_type __capacity() const
1503    {
1504        return __base::__map_.size() == 0 ? 0 : __base::__map_.size() * __base::__block_size - 1;
1505    }
1506    _LIBCPP_INLINE_VISIBILITY
1507    size_type __block_count() const
1508    {
1509        return __base::__map_.size();
1510    }
1511
1512    _LIBCPP_INLINE_VISIBILITY
1513    size_type __front_spare() const
1514    {
1515        return __base::__start_;
1516    }
1517    _LIBCPP_INLINE_VISIBILITY
1518    size_type __front_spare_blocks() const {
1519      return __front_spare() / __base::__block_size;
1520    }
1521    _LIBCPP_INLINE_VISIBILITY
1522    size_type __back_spare() const
1523    {
1524        return __capacity() - (__base::__start_ + __base::size());
1525    }
1526    _LIBCPP_INLINE_VISIBILITY
1527    size_type __back_spare_blocks() const {
1528      return __back_spare() / __base::__block_size;
1529    }
1530
1531 private:
1532    _LIBCPP_INLINE_VISIBILITY
1533    bool __maybe_remove_front_spare(bool __keep_one = true) {
1534      if (__front_spare_blocks() >= 2 || (!__keep_one && __front_spare_blocks())) {
1535        __alloc_traits::deallocate(__base::__alloc(), __base::__map_.front(),
1536                                   __base::__block_size);
1537        __base::__map_.pop_front();
1538        __base::__start_ -= __base::__block_size;
1539        return true;
1540      }
1541      return false;
1542    }
1543
1544    _LIBCPP_INLINE_VISIBILITY
1545    bool __maybe_remove_back_spare(bool __keep_one = true) {
1546      if (__back_spare_blocks() >= 2 || (!__keep_one && __back_spare_blocks())) {
1547        __alloc_traits::deallocate(__base::__alloc(), __base::__map_.back(),
1548                                   __base::__block_size);
1549        __base::__map_.pop_back();
1550        return true;
1551      }
1552      return false;
1553    }
1554
1555    template <class _InpIter>
1556        void __append(_InpIter __f, _InpIter __l,
1557                 typename enable_if<__is_exactly_cpp17_input_iterator<_InpIter>::value>::type* = 0);
1558    template <class _ForIter>
1559        void __append(_ForIter __f, _ForIter __l,
1560                      typename enable_if<__is_cpp17_forward_iterator<_ForIter>::value>::type* = 0);
1561    void __append(size_type __n);
1562    void __append(size_type __n, const value_type& __v);
1563    void __erase_to_end(const_iterator __f);
1564    void __add_front_capacity();
1565    void __add_front_capacity(size_type __n);
1566    void __add_back_capacity();
1567    void __add_back_capacity(size_type __n);
1568    iterator __move_and_check(iterator __f, iterator __l, iterator __r,
1569                              const_pointer& __vt);
1570    iterator __move_backward_and_check(iterator __f, iterator __l, iterator __r,
1571                                       const_pointer& __vt);
1572    void __move_construct_and_check(iterator __f, iterator __l,
1573                                    iterator __r, const_pointer& __vt);
1574    void __move_construct_backward_and_check(iterator __f, iterator __l,
1575                                             iterator __r, const_pointer& __vt);
1576
1577    _LIBCPP_INLINE_VISIBILITY
1578    void __copy_assign_alloc(const deque& __c)
1579        {__copy_assign_alloc(__c, integral_constant<bool,
1580                      __alloc_traits::propagate_on_container_copy_assignment::value>());}
1581
1582    _LIBCPP_INLINE_VISIBILITY
1583    void __copy_assign_alloc(const deque& __c, true_type)
1584        {
1585            if (__base::__alloc() != __c.__alloc())
1586            {
1587                clear();
1588                shrink_to_fit();
1589            }
1590            __base::__alloc() = __c.__alloc();
1591            __base::__map_.__alloc() = __c.__map_.__alloc();
1592        }
1593
1594    _LIBCPP_INLINE_VISIBILITY
1595    void __copy_assign_alloc(const deque&, false_type)
1596        {}
1597
1598    void __move_assign(deque& __c, true_type)
1599        _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
1600    void __move_assign(deque& __c, false_type);
1601};
1602
1603#if _LIBCPP_STD_VER >= 17
1604template<class _InputIterator,
1605         class _Alloc = allocator<__iter_value_type<_InputIterator>>,
1606         class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
1607         class = enable_if_t<__is_allocator<_Alloc>::value>
1608         >
1609deque(_InputIterator, _InputIterator)
1610  -> deque<__iter_value_type<_InputIterator>, _Alloc>;
1611
1612template<class _InputIterator,
1613         class _Alloc,
1614         class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
1615         class = enable_if_t<__is_allocator<_Alloc>::value>
1616         >
1617deque(_InputIterator, _InputIterator, _Alloc)
1618  -> deque<__iter_value_type<_InputIterator>, _Alloc>;
1619#endif
1620
1621template <class _Tp, class _Allocator>
1622deque<_Tp, _Allocator>::deque(size_type __n)
1623{
1624    if (__n > 0)
1625        __append(__n);
1626}
1627
1628#if _LIBCPP_STD_VER > 11
1629template <class _Tp, class _Allocator>
1630deque<_Tp, _Allocator>::deque(size_type __n, const _Allocator& __a)
1631    : __base(__a)
1632{
1633    if (__n > 0)
1634        __append(__n);
1635}
1636#endif
1637
1638template <class _Tp, class _Allocator>
1639deque<_Tp, _Allocator>::deque(size_type __n, const value_type& __v)
1640{
1641    if (__n > 0)
1642        __append(__n, __v);
1643}
1644
1645template <class _Tp, class _Allocator>
1646template <class _InputIter>
1647deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l,
1648              typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type*)
1649{
1650    __append(__f, __l);
1651}
1652
1653template <class _Tp, class _Allocator>
1654template <class _InputIter>
1655deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l, const allocator_type& __a,
1656              typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type*)
1657    : __base(__a)
1658{
1659    __append(__f, __l);
1660}
1661
1662template <class _Tp, class _Allocator>
1663deque<_Tp, _Allocator>::deque(const deque& __c)
1664    : __base(__alloc_traits::select_on_container_copy_construction(__c.__alloc()))
1665{
1666    __append(__c.begin(), __c.end());
1667}
1668
1669template <class _Tp, class _Allocator>
1670deque<_Tp, _Allocator>::deque(const deque& __c, const __type_identity_t<allocator_type>& __a)
1671    : __base(__a)
1672{
1673    __append(__c.begin(), __c.end());
1674}
1675
1676template <class _Tp, class _Allocator>
1677deque<_Tp, _Allocator>&
1678deque<_Tp, _Allocator>::operator=(const deque& __c)
1679{
1680    if (this != _VSTD::addressof(__c))
1681    {
1682        __copy_assign_alloc(__c);
1683        assign(__c.begin(), __c.end());
1684    }
1685    return *this;
1686}
1687
1688#ifndef _LIBCPP_CXX03_LANG
1689
1690template <class _Tp, class _Allocator>
1691deque<_Tp, _Allocator>::deque(initializer_list<value_type> __il)
1692{
1693    __append(__il.begin(), __il.end());
1694}
1695
1696template <class _Tp, class _Allocator>
1697deque<_Tp, _Allocator>::deque(initializer_list<value_type> __il, const allocator_type& __a)
1698    : __base(__a)
1699{
1700    __append(__il.begin(), __il.end());
1701}
1702
1703template <class _Tp, class _Allocator>
1704inline
1705deque<_Tp, _Allocator>::deque(deque&& __c)
1706    _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1707    : __base(_VSTD::move(__c))
1708{
1709}
1710
1711template <class _Tp, class _Allocator>
1712inline
1713deque<_Tp, _Allocator>::deque(deque&& __c, const __type_identity_t<allocator_type>& __a)
1714    : __base(_VSTD::move(__c), __a)
1715{
1716    if (__a != __c.__alloc())
1717    {
1718        typedef move_iterator<iterator> _Ip;
1719        assign(_Ip(__c.begin()), _Ip(__c.end()));
1720    }
1721}
1722
1723template <class _Tp, class _Allocator>
1724inline
1725deque<_Tp, _Allocator>&
1726deque<_Tp, _Allocator>::operator=(deque&& __c)
1727        _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&
1728                   is_nothrow_move_assignable<allocator_type>::value)
1729{
1730    __move_assign(__c, integral_constant<bool,
1731          __alloc_traits::propagate_on_container_move_assignment::value>());
1732    return *this;
1733}
1734
1735template <class _Tp, class _Allocator>
1736void
1737deque<_Tp, _Allocator>::__move_assign(deque& __c, false_type)
1738{
1739    if (__base::__alloc() != __c.__alloc())
1740    {
1741        typedef move_iterator<iterator> _Ip;
1742        assign(_Ip(__c.begin()), _Ip(__c.end()));
1743    }
1744    else
1745        __move_assign(__c, true_type());
1746}
1747
1748template <class _Tp, class _Allocator>
1749void
1750deque<_Tp, _Allocator>::__move_assign(deque& __c, true_type)
1751    _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
1752{
1753    clear();
1754    shrink_to_fit();
1755    __base::__move_assign(__c);
1756}
1757
1758#endif // _LIBCPP_CXX03_LANG
1759
1760template <class _Tp, class _Allocator>
1761template <class _InputIter>
1762void
1763deque<_Tp, _Allocator>::assign(_InputIter __f, _InputIter __l,
1764                               typename enable_if<__is_cpp17_input_iterator<_InputIter>::value &&
1765                                                 !__is_cpp17_random_access_iterator<_InputIter>::value>::type*)
1766{
1767    iterator __i = __base::begin();
1768    iterator __e = __base::end();
1769    for (; __f != __l && __i != __e; ++__f, (void) ++__i)
1770        *__i = *__f;
1771    if (__f != __l)
1772        __append(__f, __l);
1773    else
1774        __erase_to_end(__i);
1775}
1776
1777template <class _Tp, class _Allocator>
1778template <class _RAIter>
1779void
1780deque<_Tp, _Allocator>::assign(_RAIter __f, _RAIter __l,
1781                               typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*)
1782{
1783    if (static_cast<size_type>(__l - __f) > __base::size())
1784    {
1785        _RAIter __m = __f + __base::size();
1786        _VSTD::copy(__f, __m, __base::begin());
1787        __append(__m, __l);
1788    }
1789    else
1790        __erase_to_end(_VSTD::copy(__f, __l, __base::begin()));
1791}
1792
1793template <class _Tp, class _Allocator>
1794void
1795deque<_Tp, _Allocator>::assign(size_type __n, const value_type& __v)
1796{
1797    if (__n > __base::size())
1798    {
1799        _VSTD::fill_n(__base::begin(), __base::size(), __v);
1800        __n -= __base::size();
1801        __append(__n, __v);
1802    }
1803    else
1804        __erase_to_end(_VSTD::fill_n(__base::begin(), __n, __v));
1805}
1806
1807template <class _Tp, class _Allocator>
1808inline
1809_Allocator
1810deque<_Tp, _Allocator>::get_allocator() const _NOEXCEPT
1811{
1812    return __base::__alloc();
1813}
1814
1815template <class _Tp, class _Allocator>
1816void
1817deque<_Tp, _Allocator>::resize(size_type __n)
1818{
1819    if (__n > __base::size())
1820        __append(__n - __base::size());
1821    else if (__n < __base::size())
1822        __erase_to_end(__base::begin() + __n);
1823}
1824
1825template <class _Tp, class _Allocator>
1826void
1827deque<_Tp, _Allocator>::resize(size_type __n, const value_type& __v)
1828{
1829    if (__n > __base::size())
1830        __append(__n - __base::size(), __v);
1831    else if (__n < __base::size())
1832        __erase_to_end(__base::begin() + __n);
1833}
1834
1835template <class _Tp, class _Allocator>
1836void
1837deque<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
1838{
1839    allocator_type& __a = __base::__alloc();
1840    if (empty())
1841    {
1842        while (__base::__map_.size() > 0)
1843        {
1844            __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
1845            __base::__map_.pop_back();
1846        }
1847        __base::__start_ = 0;
1848    }
1849    else
1850    {
1851      __maybe_remove_front_spare(/*__keep_one=*/false);
1852      __maybe_remove_back_spare(/*__keep_one=*/false);
1853    }
1854    __base::__map_.shrink_to_fit();
1855}
1856
1857template <class _Tp, class _Allocator>
1858inline
1859typename deque<_Tp, _Allocator>::reference
1860deque<_Tp, _Allocator>::operator[](size_type __i) _NOEXCEPT
1861{
1862    size_type __p = __base::__start_ + __i;
1863    return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1864}
1865
1866template <class _Tp, class _Allocator>
1867inline
1868typename deque<_Tp, _Allocator>::const_reference
1869deque<_Tp, _Allocator>::operator[](size_type __i) const _NOEXCEPT
1870{
1871    size_type __p = __base::__start_ + __i;
1872    return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1873}
1874
1875template <class _Tp, class _Allocator>
1876inline
1877typename deque<_Tp, _Allocator>::reference
1878deque<_Tp, _Allocator>::at(size_type __i)
1879{
1880    if (__i >= __base::size())
1881        _VSTD::__throw_out_of_range("deque");
1882    size_type __p = __base::__start_ + __i;
1883    return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1884}
1885
1886template <class _Tp, class _Allocator>
1887inline
1888typename deque<_Tp, _Allocator>::const_reference
1889deque<_Tp, _Allocator>::at(size_type __i) const
1890{
1891    if (__i >= __base::size())
1892        _VSTD::__throw_out_of_range("deque");
1893    size_type __p = __base::__start_ + __i;
1894    return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1895}
1896
1897template <class _Tp, class _Allocator>
1898inline
1899typename deque<_Tp, _Allocator>::reference
1900deque<_Tp, _Allocator>::front() _NOEXCEPT
1901{
1902    return *(*(__base::__map_.begin() + __base::__start_ / __base::__block_size)
1903                                      + __base::__start_ % __base::__block_size);
1904}
1905
1906template <class _Tp, class _Allocator>
1907inline
1908typename deque<_Tp, _Allocator>::const_reference
1909deque<_Tp, _Allocator>::front() const _NOEXCEPT
1910{
1911    return *(*(__base::__map_.begin() + __base::__start_ / __base::__block_size)
1912                                      + __base::__start_ % __base::__block_size);
1913}
1914
1915template <class _Tp, class _Allocator>
1916inline
1917typename deque<_Tp, _Allocator>::reference
1918deque<_Tp, _Allocator>::back() _NOEXCEPT
1919{
1920    size_type __p = __base::size() + __base::__start_ - 1;
1921    return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1922}
1923
1924template <class _Tp, class _Allocator>
1925inline
1926typename deque<_Tp, _Allocator>::const_reference
1927deque<_Tp, _Allocator>::back() const _NOEXCEPT
1928{
1929    size_type __p = __base::size() + __base::__start_ - 1;
1930    return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1931}
1932
1933template <class _Tp, class _Allocator>
1934void
1935deque<_Tp, _Allocator>::push_back(const value_type& __v)
1936{
1937    allocator_type& __a = __base::__alloc();
1938    if (__back_spare() == 0)
1939        __add_back_capacity();
1940    // __back_spare() >= 1
1941    __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), __v);
1942    ++__base::size();
1943}
1944
1945template <class _Tp, class _Allocator>
1946void
1947deque<_Tp, _Allocator>::push_front(const value_type& __v)
1948{
1949    allocator_type& __a = __base::__alloc();
1950    if (__front_spare() == 0)
1951        __add_front_capacity();
1952    // __front_spare() >= 1
1953    __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), __v);
1954    --__base::__start_;
1955    ++__base::size();
1956}
1957
1958#ifndef _LIBCPP_CXX03_LANG
1959template <class _Tp, class _Allocator>
1960void
1961deque<_Tp, _Allocator>::push_back(value_type&& __v)
1962{
1963    allocator_type& __a = __base::__alloc();
1964    if (__back_spare() == 0)
1965        __add_back_capacity();
1966    // __back_spare() >= 1
1967    __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::move(__v));
1968    ++__base::size();
1969}
1970
1971template <class _Tp, class _Allocator>
1972template <class... _Args>
1973#if _LIBCPP_STD_VER > 14
1974typename deque<_Tp, _Allocator>::reference
1975#else
1976void
1977#endif
1978deque<_Tp, _Allocator>::emplace_back(_Args&&... __args)
1979{
1980    allocator_type& __a = __base::__alloc();
1981    if (__back_spare() == 0)
1982        __add_back_capacity();
1983    // __back_spare() >= 1
1984    __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()),
1985                              _VSTD::forward<_Args>(__args)...);
1986    ++__base::size();
1987#if _LIBCPP_STD_VER > 14
1988    return *--__base::end();
1989#endif
1990}
1991
1992template <class _Tp, class _Allocator>
1993void
1994deque<_Tp, _Allocator>::push_front(value_type&& __v)
1995{
1996    allocator_type& __a = __base::__alloc();
1997    if (__front_spare() == 0)
1998        __add_front_capacity();
1999    // __front_spare() >= 1
2000    __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::move(__v));
2001    --__base::__start_;
2002    ++__base::size();
2003}
2004
2005
2006template <class _Tp, class _Allocator>
2007template <class... _Args>
2008#if _LIBCPP_STD_VER > 14
2009typename deque<_Tp, _Allocator>::reference
2010#else
2011void
2012#endif
2013deque<_Tp, _Allocator>::emplace_front(_Args&&... __args)
2014{
2015    allocator_type& __a = __base::__alloc();
2016    if (__front_spare() == 0)
2017        __add_front_capacity();
2018    // __front_spare() >= 1
2019    __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::forward<_Args>(__args)...);
2020    --__base::__start_;
2021    ++__base::size();
2022#if _LIBCPP_STD_VER > 14
2023    return *__base::begin();
2024#endif
2025}
2026
2027template <class _Tp, class _Allocator>
2028typename deque<_Tp, _Allocator>::iterator
2029deque<_Tp, _Allocator>::insert(const_iterator __p, value_type&& __v)
2030{
2031    size_type __pos = __p - __base::begin();
2032    size_type __to_end = __base::size() - __pos;
2033    allocator_type& __a = __base::__alloc();
2034    if (__pos < __to_end)
2035    {   // insert by shifting things backward
2036        if (__front_spare() == 0)
2037            __add_front_capacity();
2038        // __front_spare() >= 1
2039        if (__pos == 0)
2040        {
2041            __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::move(__v));
2042            --__base::__start_;
2043            ++__base::size();
2044        }
2045        else
2046        {
2047            iterator __b = __base::begin();
2048            iterator __bm1 = _VSTD::prev(__b);
2049            __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b));
2050            --__base::__start_;
2051            ++__base::size();
2052            if (__pos > 1)
2053                __b = _VSTD::move(_VSTD::next(__b), __b + __pos, __b);
2054            *__b = _VSTD::move(__v);
2055        }
2056    }
2057    else
2058    {   // insert by shifting things forward
2059        if (__back_spare() == 0)
2060            __add_back_capacity();
2061        // __back_capacity >= 1
2062        size_type __de = __base::size() - __pos;
2063        if (__de == 0)
2064        {
2065            __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::move(__v));
2066            ++__base::size();
2067        }
2068        else
2069        {
2070            iterator __e = __base::end();
2071            iterator __em1 = _VSTD::prev(__e);
2072            __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1));
2073            ++__base::size();
2074            if (__de > 1)
2075                __e = _VSTD::move_backward(__e - __de, __em1, __e);
2076            *--__e = _VSTD::move(__v);
2077        }
2078    }
2079    return __base::begin() + __pos;
2080}
2081
2082template <class _Tp, class _Allocator>
2083template <class... _Args>
2084typename deque<_Tp, _Allocator>::iterator
2085deque<_Tp, _Allocator>::emplace(const_iterator __p, _Args&&... __args)
2086{
2087    size_type __pos = __p - __base::begin();
2088    size_type __to_end = __base::size() - __pos;
2089    allocator_type& __a = __base::__alloc();
2090    if (__pos < __to_end)
2091    {   // insert by shifting things backward
2092        if (__front_spare() == 0)
2093            __add_front_capacity();
2094        // __front_spare() >= 1
2095        if (__pos == 0)
2096        {
2097            __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::forward<_Args>(__args)...);
2098            --__base::__start_;
2099            ++__base::size();
2100        }
2101        else
2102        {
2103            __temp_value<value_type, _Allocator> __tmp(this->__alloc(), _VSTD::forward<_Args>(__args)...);
2104            iterator __b = __base::begin();
2105            iterator __bm1 = _VSTD::prev(__b);
2106            __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b));
2107            --__base::__start_;
2108            ++__base::size();
2109            if (__pos > 1)
2110                __b = _VSTD::move(_VSTD::next(__b), __b + __pos, __b);
2111            *__b = _VSTD::move(__tmp.get());
2112        }
2113    }
2114    else
2115    {   // insert by shifting things forward
2116        if (__back_spare() == 0)
2117            __add_back_capacity();
2118        // __back_capacity >= 1
2119        size_type __de = __base::size() - __pos;
2120        if (__de == 0)
2121        {
2122            __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::forward<_Args>(__args)...);
2123            ++__base::size();
2124        }
2125        else
2126        {
2127            __temp_value<value_type, _Allocator> __tmp(this->__alloc(), _VSTD::forward<_Args>(__args)...);
2128            iterator __e = __base::end();
2129            iterator __em1 = _VSTD::prev(__e);
2130            __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1));
2131            ++__base::size();
2132            if (__de > 1)
2133                __e = _VSTD::move_backward(__e - __de, __em1, __e);
2134            *--__e = _VSTD::move(__tmp.get());
2135        }
2136    }
2137    return __base::begin() + __pos;
2138}
2139
2140#endif // _LIBCPP_CXX03_LANG
2141
2142
2143template <class _Tp, class _Allocator>
2144typename deque<_Tp, _Allocator>::iterator
2145deque<_Tp, _Allocator>::insert(const_iterator __p, const value_type& __v)
2146{
2147    size_type __pos = __p - __base::begin();
2148    size_type __to_end = __base::size() - __pos;
2149    allocator_type& __a = __base::__alloc();
2150    if (__pos < __to_end)
2151    {   // insert by shifting things backward
2152        if (__front_spare() == 0)
2153            __add_front_capacity();
2154        // __front_spare() >= 1
2155        if (__pos == 0)
2156        {
2157            __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), __v);
2158            --__base::__start_;
2159            ++__base::size();
2160        }
2161        else
2162        {
2163            const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
2164            iterator __b = __base::begin();
2165            iterator __bm1 = _VSTD::prev(__b);
2166            if (__vt == pointer_traits<const_pointer>::pointer_to(*__b))
2167                __vt = pointer_traits<const_pointer>::pointer_to(*__bm1);
2168            __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b));
2169            --__base::__start_;
2170            ++__base::size();
2171            if (__pos > 1)
2172                __b = __move_and_check(_VSTD::next(__b), __b + __pos, __b, __vt);
2173            *__b = *__vt;
2174        }
2175    }
2176    else
2177    {   // insert by shifting things forward
2178        if (__back_spare() == 0)
2179            __add_back_capacity();
2180        // __back_capacity >= 1
2181        size_type __de = __base::size() - __pos;
2182        if (__de == 0)
2183        {
2184            __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), __v);
2185            ++__base::size();
2186        }
2187        else
2188        {
2189            const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
2190            iterator __e = __base::end();
2191            iterator __em1 = _VSTD::prev(__e);
2192            if (__vt == pointer_traits<const_pointer>::pointer_to(*__em1))
2193                __vt = pointer_traits<const_pointer>::pointer_to(*__e);
2194            __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1));
2195            ++__base::size();
2196            if (__de > 1)
2197                __e = __move_backward_and_check(__e - __de, __em1, __e, __vt);
2198            *--__e = *__vt;
2199        }
2200    }
2201    return __base::begin() + __pos;
2202}
2203
2204template <class _Tp, class _Allocator>
2205typename deque<_Tp, _Allocator>::iterator
2206deque<_Tp, _Allocator>::insert(const_iterator __p, size_type __n, const value_type& __v)
2207{
2208    size_type __pos = __p - __base::begin();
2209    size_type __to_end = __base::size() - __pos;
2210    allocator_type& __a = __base::__alloc();
2211    if (__pos < __to_end)
2212    {   // insert by shifting things backward
2213        if (__n > __front_spare())
2214            __add_front_capacity(__n - __front_spare());
2215        // __n <= __front_spare()
2216        iterator __old_begin = __base::begin();
2217        iterator __i = __old_begin;
2218        if (__n > __pos)
2219        {
2220            for (size_type __m = __n - __pos; __m; --__m, --__base::__start_, ++__base::size())
2221                __alloc_traits::construct(__a, _VSTD::addressof(*--__i), __v);
2222            __n = __pos;
2223        }
2224        if (__n > 0)
2225        {
2226            const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
2227            iterator __obn = __old_begin + __n;
2228            __move_construct_backward_and_check(__old_begin, __obn, __i, __vt);
2229            if (__n < __pos)
2230                __old_begin = __move_and_check(__obn, __old_begin + __pos, __old_begin, __vt);
2231            _VSTD::fill_n(__old_begin, __n, *__vt);
2232        }
2233    }
2234    else
2235    {   // insert by shifting things forward
2236        size_type __back_capacity = __back_spare();
2237        if (__n > __back_capacity)
2238            __add_back_capacity(__n - __back_capacity);
2239        // __n <= __back_capacity
2240        iterator __old_end = __base::end();
2241        iterator __i = __old_end;
2242        size_type __de = __base::size() - __pos;
2243        if (__n > __de)
2244        {
2245            for (size_type __m = __n - __de; __m; --__m, (void) ++__i, ++__base::size())
2246                __alloc_traits::construct(__a, _VSTD::addressof(*__i), __v);
2247            __n = __de;
2248        }
2249        if (__n > 0)
2250        {
2251            const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
2252            iterator __oen = __old_end - __n;
2253            __move_construct_and_check(__oen, __old_end, __i, __vt);
2254            if (__n < __de)
2255                __old_end = __move_backward_and_check(__old_end - __de, __oen, __old_end, __vt);
2256            _VSTD::fill_n(__old_end - __n, __n, *__vt);
2257        }
2258    }
2259    return __base::begin() + __pos;
2260}
2261
2262template <class _Tp, class _Allocator>
2263template <class _InputIter>
2264typename deque<_Tp, _Allocator>::iterator
2265deque<_Tp, _Allocator>::insert(const_iterator __p, _InputIter __f, _InputIter __l,
2266                               typename enable_if<__is_exactly_cpp17_input_iterator<_InputIter>::value>::type*)
2267{
2268    __split_buffer<value_type, allocator_type&> __buf(__base::__alloc());
2269    __buf.__construct_at_end(__f, __l);
2270    typedef typename __split_buffer<value_type, allocator_type&>::iterator __bi;
2271    return insert(__p, move_iterator<__bi>(__buf.begin()), move_iterator<__bi>(__buf.end()));
2272}
2273
2274template <class _Tp, class _Allocator>
2275template <class _ForwardIterator>
2276typename deque<_Tp, _Allocator>::iterator
2277deque<_Tp, _Allocator>::insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l,
2278                               typename enable_if<__is_exactly_cpp17_forward_iterator<_ForwardIterator>::value>::type*)
2279{
2280    size_type __n = _VSTD::distance(__f, __l);
2281    __split_buffer<value_type, allocator_type&> __buf(__n, 0, __base::__alloc());
2282    __buf.__construct_at_end(__f, __l);
2283    typedef typename __split_buffer<value_type, allocator_type&>::iterator __fwd;
2284    return insert(__p, move_iterator<__fwd>(__buf.begin()), move_iterator<__fwd>(__buf.end()));
2285}
2286
2287template <class _Tp, class _Allocator>
2288template <class _BiIter>
2289typename deque<_Tp, _Allocator>::iterator
2290deque<_Tp, _Allocator>::insert(const_iterator __p, _BiIter __f, _BiIter __l,
2291                               typename enable_if<__is_cpp17_bidirectional_iterator<_BiIter>::value>::type*)
2292{
2293    size_type __n = _VSTD::distance(__f, __l);
2294    size_type __pos = __p - __base::begin();
2295    size_type __to_end = __base::size() - __pos;
2296    allocator_type& __a = __base::__alloc();
2297    if (__pos < __to_end)
2298    {   // insert by shifting things backward
2299        if (__n > __front_spare())
2300            __add_front_capacity(__n - __front_spare());
2301        // __n <= __front_spare()
2302        iterator __old_begin = __base::begin();
2303        iterator __i = __old_begin;
2304        _BiIter __m = __f;
2305        if (__n > __pos)
2306        {
2307            __m = __pos < __n / 2 ? _VSTD::prev(__l, __pos) : _VSTD::next(__f, __n - __pos);
2308            for (_BiIter __j = __m; __j != __f; --__base::__start_, ++__base::size())
2309                __alloc_traits::construct(__a, _VSTD::addressof(*--__i), *--__j);
2310            __n = __pos;
2311        }
2312        if (__n > 0)
2313        {
2314            iterator __obn = __old_begin + __n;
2315            for (iterator __j = __obn; __j != __old_begin;)
2316            {
2317                __alloc_traits::construct(__a, _VSTD::addressof(*--__i), _VSTD::move(*--__j));
2318                --__base::__start_;
2319                ++__base::size();
2320            }
2321            if (__n < __pos)
2322                __old_begin = _VSTD::move(__obn, __old_begin + __pos, __old_begin);
2323            _VSTD::copy(__m, __l, __old_begin);
2324        }
2325    }
2326    else
2327    {   // insert by shifting things forward
2328        size_type __back_capacity = __back_spare();
2329        if (__n > __back_capacity)
2330            __add_back_capacity(__n - __back_capacity);
2331        // __n <= __back_capacity
2332        iterator __old_end = __base::end();
2333        iterator __i = __old_end;
2334        _BiIter __m = __l;
2335        size_type __de = __base::size() - __pos;
2336        if (__n > __de)
2337        {
2338            __m = __de < __n / 2 ? _VSTD::next(__f, __de) : _VSTD::prev(__l, __n - __de);
2339            for (_BiIter __j = __m; __j != __l; ++__i, (void) ++__j, ++__base::size())
2340                __alloc_traits::construct(__a, _VSTD::addressof(*__i), *__j);
2341            __n = __de;
2342        }
2343        if (__n > 0)
2344        {
2345            iterator __oen = __old_end - __n;
2346            for (iterator __j = __oen; __j != __old_end; ++__i, (void) ++__j, ++__base::size())
2347                __alloc_traits::construct(__a, _VSTD::addressof(*__i), _VSTD::move(*__j));
2348            if (__n < __de)
2349                __old_end = _VSTD::move_backward(__old_end - __de, __oen, __old_end);
2350            _VSTD::copy_backward(__f, __m, __old_end);
2351        }
2352    }
2353    return __base::begin() + __pos;
2354}
2355
2356template <class _Tp, class _Allocator>
2357template <class _InpIter>
2358void
2359deque<_Tp, _Allocator>::__append(_InpIter __f, _InpIter __l,
2360                                 typename enable_if<__is_exactly_cpp17_input_iterator<_InpIter>::value>::type*)
2361{
2362    for (; __f != __l; ++__f)
2363#ifdef _LIBCPP_CXX03_LANG
2364        push_back(*__f);
2365#else
2366        emplace_back(*__f);
2367#endif
2368}
2369
2370template <class _Tp, class _Allocator>
2371template <class _ForIter>
2372void
2373deque<_Tp, _Allocator>::__append(_ForIter __f, _ForIter __l,
2374                                 typename enable_if<__is_cpp17_forward_iterator<_ForIter>::value>::type*)
2375{
2376    size_type __n = _VSTD::distance(__f, __l);
2377    allocator_type& __a = __base::__alloc();
2378    size_type __back_capacity = __back_spare();
2379    if (__n > __back_capacity)
2380        __add_back_capacity(__n - __back_capacity);
2381    // __n <= __back_capacity
2382    for (__deque_block_range __br : __deque_range(__base::end(), __base::end() + __n)) {
2383      _ConstructTransaction __tx(this, __br);
2384      for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_, (void)++__f) {
2385        __alloc_traits::construct(__a, _VSTD::__to_address(__tx.__pos_), *__f);
2386      }
2387    }
2388}
2389
2390template <class _Tp, class _Allocator>
2391void
2392deque<_Tp, _Allocator>::__append(size_type __n)
2393{
2394    allocator_type& __a = __base::__alloc();
2395    size_type __back_capacity = __back_spare();
2396    if (__n > __back_capacity)
2397        __add_back_capacity(__n - __back_capacity);
2398    // __n <= __back_capacity
2399    for (__deque_block_range __br : __deque_range(__base::end(), __base::end() + __n)) {
2400      _ConstructTransaction __tx(this, __br);
2401      for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) {
2402        __alloc_traits::construct(__a, _VSTD::__to_address(__tx.__pos_));
2403      }
2404    }
2405}
2406
2407template <class _Tp, class _Allocator>
2408void
2409deque<_Tp, _Allocator>::__append(size_type __n, const value_type& __v)
2410{
2411    allocator_type& __a = __base::__alloc();
2412    size_type __back_capacity = __back_spare();
2413    if (__n > __back_capacity)
2414        __add_back_capacity(__n - __back_capacity);
2415    // __n <= __back_capacity
2416    for (__deque_block_range __br : __deque_range(__base::end(), __base::end() + __n)) {
2417      _ConstructTransaction __tx(this, __br);
2418      for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) {
2419        __alloc_traits::construct(__a, _VSTD::__to_address(__tx.__pos_), __v);
2420      }
2421    }
2422
2423}
2424
2425// Create front capacity for one block of elements.
2426// Strong guarantee.  Either do it or don't touch anything.
2427template <class _Tp, class _Allocator>
2428void
2429deque<_Tp, _Allocator>::__add_front_capacity()
2430{
2431    allocator_type& __a = __base::__alloc();
2432    if (__back_spare() >= __base::__block_size)
2433    {
2434        __base::__start_ += __base::__block_size;
2435        pointer __pt = __base::__map_.back();
2436        __base::__map_.pop_back();
2437        __base::__map_.push_front(__pt);
2438    }
2439    // Else if __base::__map_.size() < __base::__map_.capacity() then we need to allocate 1 buffer
2440    else if (__base::__map_.size() < __base::__map_.capacity())
2441    {   // we can put the new buffer into the map, but don't shift things around
2442        // until all buffers are allocated.  If we throw, we don't need to fix
2443        // anything up (any added buffers are undetectible)
2444        if (__base::__map_.__front_spare() > 0)
2445            __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
2446        else
2447        {
2448            __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2449            // Done allocating, reorder capacity
2450            pointer __pt = __base::__map_.back();
2451            __base::__map_.pop_back();
2452            __base::__map_.push_front(__pt);
2453        }
2454        __base::__start_ = __base::__map_.size() == 1 ?
2455                               __base::__block_size / 2 :
2456                               __base::__start_ + __base::__block_size;
2457    }
2458    // Else need to allocate 1 buffer, *and* we need to reallocate __map_.
2459    else
2460    {
2461        __split_buffer<pointer, typename __base::__pointer_allocator&>
2462            __buf(max<size_type>(2 * __base::__map_.capacity(), 1),
2463                  0, __base::__map_.__alloc());
2464
2465        typedef __allocator_destructor<_Allocator> _Dp;
2466        unique_ptr<pointer, _Dp> __hold(
2467            __alloc_traits::allocate(__a, __base::__block_size),
2468                _Dp(__a, __base::__block_size));
2469        __buf.push_back(__hold.get());
2470        __hold.release();
2471
2472        for (typename __base::__map_pointer __i = __base::__map_.begin();
2473                __i != __base::__map_.end(); ++__i)
2474            __buf.push_back(*__i);
2475        _VSTD::swap(__base::__map_.__first_, __buf.__first_);
2476        _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
2477        _VSTD::swap(__base::__map_.__end_, __buf.__end_);
2478        _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
2479        __base::__start_ = __base::__map_.size() == 1 ?
2480                               __base::__block_size / 2 :
2481                               __base::__start_ + __base::__block_size;
2482    }
2483}
2484
2485// Create front capacity for __n elements.
2486// Strong guarantee.  Either do it or don't touch anything.
2487template <class _Tp, class _Allocator>
2488void
2489deque<_Tp, _Allocator>::__add_front_capacity(size_type __n)
2490{
2491    allocator_type& __a = __base::__alloc();
2492    size_type __nb = __recommend_blocks(__n + __base::__map_.empty());
2493    // Number of unused blocks at back:
2494    size_type __back_capacity = __back_spare() / __base::__block_size;
2495    __back_capacity = _VSTD::min(__back_capacity, __nb);  // don't take more than you need
2496    __nb -= __back_capacity;  // number of blocks need to allocate
2497    // If __nb == 0, then we have sufficient capacity.
2498    if (__nb == 0)
2499    {
2500        __base::__start_ += __base::__block_size * __back_capacity;
2501        for (; __back_capacity > 0; --__back_capacity)
2502        {
2503            pointer __pt = __base::__map_.back();
2504            __base::__map_.pop_back();
2505            __base::__map_.push_front(__pt);
2506        }
2507    }
2508    // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers
2509    else if (__nb <= __base::__map_.capacity() - __base::__map_.size())
2510    {   // we can put the new buffers into the map, but don't shift things around
2511        // until all buffers are allocated.  If we throw, we don't need to fix
2512        // anything up (any added buffers are undetectible)
2513        for (; __nb > 0; --__nb, __base::__start_ += __base::__block_size - (__base::__map_.size() == 1))
2514        {
2515            if (__base::__map_.__front_spare() == 0)
2516                break;
2517            __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
2518        }
2519        for (; __nb > 0; --__nb, ++__back_capacity)
2520            __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2521        // Done allocating, reorder capacity
2522        __base::__start_ += __back_capacity * __base::__block_size;
2523        for (; __back_capacity > 0; --__back_capacity)
2524        {
2525            pointer __pt = __base::__map_.back();
2526            __base::__map_.pop_back();
2527            __base::__map_.push_front(__pt);
2528        }
2529    }
2530    // Else need to allocate __nb buffers, *and* we need to reallocate __map_.
2531    else
2532    {
2533        size_type __ds = (__nb + __back_capacity) * __base::__block_size - __base::__map_.empty();
2534        __split_buffer<pointer, typename __base::__pointer_allocator&>
2535            __buf(max<size_type>(2* __base::__map_.capacity(),
2536                                 __nb + __base::__map_.size()),
2537                  0, __base::__map_.__alloc());
2538#ifndef _LIBCPP_NO_EXCEPTIONS
2539        try
2540        {
2541#endif // _LIBCPP_NO_EXCEPTIONS
2542            for (; __nb > 0; --__nb)
2543                __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2544#ifndef _LIBCPP_NO_EXCEPTIONS
2545        }
2546        catch (...)
2547        {
2548            for (typename __base::__map_pointer __i = __buf.begin();
2549                    __i != __buf.end(); ++__i)
2550                __alloc_traits::deallocate(__a, *__i, __base::__block_size);
2551            throw;
2552        }
2553#endif // _LIBCPP_NO_EXCEPTIONS
2554        for (; __back_capacity > 0; --__back_capacity)
2555        {
2556            __buf.push_back(__base::__map_.back());
2557            __base::__map_.pop_back();
2558        }
2559        for (typename __base::__map_pointer __i = __base::__map_.begin();
2560                __i != __base::__map_.end(); ++__i)
2561            __buf.push_back(*__i);
2562        _VSTD::swap(__base::__map_.__first_, __buf.__first_);
2563        _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
2564        _VSTD::swap(__base::__map_.__end_, __buf.__end_);
2565        _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
2566        __base::__start_ += __ds;
2567    }
2568}
2569
2570// Create back capacity for one block of elements.
2571// Strong guarantee.  Either do it or don't touch anything.
2572template <class _Tp, class _Allocator>
2573void
2574deque<_Tp, _Allocator>::__add_back_capacity()
2575{
2576    allocator_type& __a = __base::__alloc();
2577    if (__front_spare() >= __base::__block_size)
2578    {
2579        __base::__start_ -= __base::__block_size;
2580        pointer __pt = __base::__map_.front();
2581        __base::__map_.pop_front();
2582        __base::__map_.push_back(__pt);
2583    }
2584    // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers
2585    else if (__base::__map_.size() < __base::__map_.capacity())
2586    {   // we can put the new buffer into the map, but don't shift things around
2587        // until it is allocated.  If we throw, we don't need to fix
2588        // anything up (any added buffers are undetectible)
2589        if (__base::__map_.__back_spare() != 0)
2590            __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2591        else
2592        {
2593            __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
2594            // Done allocating, reorder capacity
2595            pointer __pt = __base::__map_.front();
2596            __base::__map_.pop_front();
2597            __base::__map_.push_back(__pt);
2598        }
2599    }
2600    // Else need to allocate 1 buffer, *and* we need to reallocate __map_.
2601    else
2602    {
2603        __split_buffer<pointer, typename __base::__pointer_allocator&>
2604            __buf(max<size_type>(2* __base::__map_.capacity(), 1),
2605                  __base::__map_.size(),
2606                  __base::__map_.__alloc());
2607
2608        typedef __allocator_destructor<_Allocator> _Dp;
2609        unique_ptr<pointer, _Dp> __hold(
2610            __alloc_traits::allocate(__a, __base::__block_size),
2611                _Dp(__a, __base::__block_size));
2612        __buf.push_back(__hold.get());
2613        __hold.release();
2614
2615        for (typename __base::__map_pointer __i = __base::__map_.end();
2616                __i != __base::__map_.begin();)
2617            __buf.push_front(*--__i);
2618        _VSTD::swap(__base::__map_.__first_, __buf.__first_);
2619        _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
2620        _VSTD::swap(__base::__map_.__end_, __buf.__end_);
2621        _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
2622    }
2623}
2624
2625// Create back capacity for __n elements.
2626// Strong guarantee.  Either do it or don't touch anything.
2627template <class _Tp, class _Allocator>
2628void
2629deque<_Tp, _Allocator>::__add_back_capacity(size_type __n)
2630{
2631    allocator_type& __a = __base::__alloc();
2632    size_type __nb = __recommend_blocks(__n + __base::__map_.empty());
2633    // Number of unused blocks at front:
2634    size_type __front_capacity = __front_spare() / __base::__block_size;
2635    __front_capacity = _VSTD::min(__front_capacity, __nb);  // don't take more than you need
2636    __nb -= __front_capacity;  // number of blocks need to allocate
2637    // If __nb == 0, then we have sufficient capacity.
2638    if (__nb == 0)
2639    {
2640        __base::__start_ -= __base::__block_size * __front_capacity;
2641        for (; __front_capacity > 0; --__front_capacity)
2642        {
2643            pointer __pt = __base::__map_.front();
2644            __base::__map_.pop_front();
2645            __base::__map_.push_back(__pt);
2646        }
2647    }
2648    // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers
2649    else if (__nb <= __base::__map_.capacity() - __base::__map_.size())
2650    {   // we can put the new buffers into the map, but don't shift things around
2651        // until all buffers are allocated.  If we throw, we don't need to fix
2652        // anything up (any added buffers are undetectible)
2653        for (; __nb > 0; --__nb)
2654        {
2655            if (__base::__map_.__back_spare() == 0)
2656                break;
2657            __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2658        }
2659        for (; __nb > 0; --__nb, ++__front_capacity, __base::__start_ +=
2660                                 __base::__block_size - (__base::__map_.size() == 1))
2661            __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
2662        // Done allocating, reorder capacity
2663        __base::__start_ -= __base::__block_size * __front_capacity;
2664        for (; __front_capacity > 0; --__front_capacity)
2665        {
2666            pointer __pt = __base::__map_.front();
2667            __base::__map_.pop_front();
2668            __base::__map_.push_back(__pt);
2669        }
2670    }
2671    // Else need to allocate __nb buffers, *and* we need to reallocate __map_.
2672    else
2673    {
2674        size_type __ds = __front_capacity * __base::__block_size;
2675        __split_buffer<pointer, typename __base::__pointer_allocator&>
2676            __buf(max<size_type>(2* __base::__map_.capacity(),
2677                                 __nb + __base::__map_.size()),
2678                  __base::__map_.size() - __front_capacity,
2679                  __base::__map_.__alloc());
2680#ifndef _LIBCPP_NO_EXCEPTIONS
2681        try
2682        {
2683#endif // _LIBCPP_NO_EXCEPTIONS
2684            for (; __nb > 0; --__nb)
2685                __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2686#ifndef _LIBCPP_NO_EXCEPTIONS
2687        }
2688        catch (...)
2689        {
2690            for (typename __base::__map_pointer __i = __buf.begin();
2691                    __i != __buf.end(); ++__i)
2692                __alloc_traits::deallocate(__a, *__i, __base::__block_size);
2693            throw;
2694        }
2695#endif // _LIBCPP_NO_EXCEPTIONS
2696        for (; __front_capacity > 0; --__front_capacity)
2697        {
2698            __buf.push_back(__base::__map_.front());
2699            __base::__map_.pop_front();
2700        }
2701        for (typename __base::__map_pointer __i = __base::__map_.end();
2702                __i != __base::__map_.begin();)
2703            __buf.push_front(*--__i);
2704        _VSTD::swap(__base::__map_.__first_, __buf.__first_);
2705        _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
2706        _VSTD::swap(__base::__map_.__end_, __buf.__end_);
2707        _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
2708        __base::__start_ -= __ds;
2709    }
2710}
2711
2712template <class _Tp, class _Allocator>
2713void
2714deque<_Tp, _Allocator>::pop_front()
2715{
2716    allocator_type& __a = __base::__alloc();
2717    __alloc_traits::destroy(__a, _VSTD::__to_address(*(__base::__map_.begin() +
2718                                                    __base::__start_ / __base::__block_size) +
2719                                                    __base::__start_ % __base::__block_size));
2720    --__base::size();
2721    ++__base::__start_;
2722    __maybe_remove_front_spare();
2723}
2724
2725template <class _Tp, class _Allocator>
2726void
2727deque<_Tp, _Allocator>::pop_back()
2728{
2729    _LIBCPP_ASSERT(!empty(), "deque::pop_back called on an empty deque");
2730    allocator_type& __a = __base::__alloc();
2731    size_type __p = __base::size() + __base::__start_ - 1;
2732    __alloc_traits::destroy(__a, _VSTD::__to_address(*(__base::__map_.begin() +
2733                                                    __p / __base::__block_size) +
2734                                                    __p % __base::__block_size));
2735    --__base::size();
2736    __maybe_remove_back_spare();
2737}
2738
2739// move assign [__f, __l) to [__r, __r + (__l-__f)).
2740// If __vt points into [__f, __l), then subtract (__f - __r) from __vt.
2741template <class _Tp, class _Allocator>
2742typename deque<_Tp, _Allocator>::iterator
2743deque<_Tp, _Allocator>::__move_and_check(iterator __f, iterator __l, iterator __r,
2744                                         const_pointer& __vt)
2745{
2746    // as if
2747    //   for (; __f != __l; ++__f, ++__r)
2748    //       *__r = _VSTD::move(*__f);
2749    difference_type __n = __l - __f;
2750    while (__n > 0)
2751    {
2752        pointer __fb = __f.__ptr_;
2753        pointer __fe = *__f.__m_iter_ + __base::__block_size;
2754        difference_type __bs = __fe - __fb;
2755        if (__bs > __n)
2756        {
2757            __bs = __n;
2758            __fe = __fb + __bs;
2759        }
2760        if (__fb <= __vt && __vt < __fe)
2761            __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) -= __f - __r).__ptr_;
2762        __r = _VSTD::move(__fb, __fe, __r);
2763        __n -= __bs;
2764        __f += __bs;
2765    }
2766    return __r;
2767}
2768
2769// move assign [__f, __l) to [__r - (__l-__f), __r) backwards.
2770// If __vt points into [__f, __l), then add (__r - __l) to __vt.
2771template <class _Tp, class _Allocator>
2772typename deque<_Tp, _Allocator>::iterator
2773deque<_Tp, _Allocator>::__move_backward_and_check(iterator __f, iterator __l, iterator __r,
2774                                                  const_pointer& __vt)
2775{
2776    // as if
2777    //   while (__f != __l)
2778    //       *--__r = _VSTD::move(*--__l);
2779    difference_type __n = __l - __f;
2780    while (__n > 0)
2781    {
2782        --__l;
2783        pointer __lb = *__l.__m_iter_;
2784        pointer __le = __l.__ptr_ + 1;
2785        difference_type __bs = __le - __lb;
2786        if (__bs > __n)
2787        {
2788            __bs = __n;
2789            __lb = __le - __bs;
2790        }
2791        if (__lb <= __vt && __vt < __le)
2792            __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) += __r - __l - 1).__ptr_;
2793        __r = _VSTD::move_backward(__lb, __le, __r);
2794        __n -= __bs;
2795        __l -= __bs - 1;
2796    }
2797    return __r;
2798}
2799
2800// move construct [__f, __l) to [__r, __r + (__l-__f)).
2801// If __vt points into [__f, __l), then add (__r - __f) to __vt.
2802template <class _Tp, class _Allocator>
2803void
2804deque<_Tp, _Allocator>::__move_construct_and_check(iterator __f, iterator __l,
2805                                                   iterator __r, const_pointer& __vt)
2806{
2807    allocator_type& __a = __base::__alloc();
2808    // as if
2809    //   for (; __f != __l; ++__r, ++__f, ++__base::size())
2810    //       __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__f));
2811    difference_type __n = __l - __f;
2812    while (__n > 0)
2813    {
2814        pointer __fb = __f.__ptr_;
2815        pointer __fe = *__f.__m_iter_ + __base::__block_size;
2816        difference_type __bs = __fe - __fb;
2817        if (__bs > __n)
2818        {
2819            __bs = __n;
2820            __fe = __fb + __bs;
2821        }
2822        if (__fb <= __vt && __vt < __fe)
2823            __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) += __r - __f).__ptr_;
2824        for (; __fb != __fe; ++__fb, ++__r, ++__base::size())
2825            __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__fb));
2826        __n -= __bs;
2827        __f += __bs;
2828    }
2829}
2830
2831// move construct [__f, __l) to [__r - (__l-__f), __r) backwards.
2832// If __vt points into [__f, __l), then subtract (__l - __r) from __vt.
2833template <class _Tp, class _Allocator>
2834void
2835deque<_Tp, _Allocator>::__move_construct_backward_and_check(iterator __f, iterator __l,
2836                                                            iterator __r, const_pointer& __vt)
2837{
2838    allocator_type& __a = __base::__alloc();
2839    // as if
2840    //   for (iterator __j = __l; __j != __f;)
2841    //   {
2842    //       __alloc_traitsconstruct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__j));
2843    //       --__base::__start_;
2844    //       ++__base::size();
2845    //   }
2846    difference_type __n = __l - __f;
2847    while (__n > 0)
2848    {
2849        --__l;
2850        pointer __lb = *__l.__m_iter_;
2851        pointer __le = __l.__ptr_ + 1;
2852        difference_type __bs = __le - __lb;
2853        if (__bs > __n)
2854        {
2855            __bs = __n;
2856            __lb = __le - __bs;
2857        }
2858        if (__lb <= __vt && __vt < __le)
2859            __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) -= __l - __r + 1).__ptr_;
2860        while (__le != __lb)
2861        {
2862            __alloc_traits::construct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__le));
2863            --__base::__start_;
2864            ++__base::size();
2865        }
2866        __n -= __bs;
2867        __l -= __bs - 1;
2868    }
2869}
2870
2871template <class _Tp, class _Allocator>
2872typename deque<_Tp, _Allocator>::iterator
2873deque<_Tp, _Allocator>::erase(const_iterator __f)
2874{
2875    iterator __b = __base::begin();
2876    difference_type __pos = __f - __b;
2877    iterator __p = __b + __pos;
2878    allocator_type& __a = __base::__alloc();
2879    if (static_cast<size_t>(__pos) <= (__base::size() - 1) / 2)
2880    {   // erase from front
2881        _VSTD::move_backward(__b, __p, _VSTD::next(__p));
2882        __alloc_traits::destroy(__a, _VSTD::addressof(*__b));
2883        --__base::size();
2884        ++__base::__start_;
2885        __maybe_remove_front_spare();
2886    }
2887    else
2888    {   // erase from back
2889        iterator __i = _VSTD::move(_VSTD::next(__p), __base::end(), __p);
2890        __alloc_traits::destroy(__a, _VSTD::addressof(*__i));
2891        --__base::size();
2892        __maybe_remove_back_spare();
2893    }
2894    return __base::begin() + __pos;
2895}
2896
2897template <class _Tp, class _Allocator>
2898typename deque<_Tp, _Allocator>::iterator
2899deque<_Tp, _Allocator>::erase(const_iterator __f, const_iterator __l)
2900{
2901    difference_type __n = __l - __f;
2902    iterator __b = __base::begin();
2903    difference_type __pos = __f - __b;
2904    iterator __p = __b + __pos;
2905    if (__n > 0)
2906    {
2907        allocator_type& __a = __base::__alloc();
2908        if (static_cast<size_t>(__pos) <= (__base::size() - __n) / 2)
2909        {   // erase from front
2910            iterator __i = _VSTD::move_backward(__b, __p, __p + __n);
2911            for (; __b != __i; ++__b)
2912                __alloc_traits::destroy(__a, _VSTD::addressof(*__b));
2913            __base::size() -= __n;
2914            __base::__start_ += __n;
2915            while (__maybe_remove_front_spare()) {
2916            }
2917        }
2918        else
2919        {   // erase from back
2920            iterator __i = _VSTD::move(__p + __n, __base::end(), __p);
2921            for (iterator __e = __base::end(); __i != __e; ++__i)
2922                __alloc_traits::destroy(__a, _VSTD::addressof(*__i));
2923            __base::size() -= __n;
2924            while (__maybe_remove_back_spare()) {
2925            }
2926        }
2927    }
2928    return __base::begin() + __pos;
2929}
2930
2931template <class _Tp, class _Allocator>
2932void
2933deque<_Tp, _Allocator>::__erase_to_end(const_iterator __f)
2934{
2935    iterator __e = __base::end();
2936    difference_type __n = __e - __f;
2937    if (__n > 0)
2938    {
2939        allocator_type& __a = __base::__alloc();
2940        iterator __b = __base::begin();
2941        difference_type __pos = __f - __b;
2942        for (iterator __p = __b + __pos; __p != __e; ++__p)
2943            __alloc_traits::destroy(__a, _VSTD::addressof(*__p));
2944        __base::size() -= __n;
2945        while (__maybe_remove_back_spare()) {
2946        }
2947    }
2948}
2949
2950template <class _Tp, class _Allocator>
2951inline
2952void
2953deque<_Tp, _Allocator>::swap(deque& __c)
2954#if _LIBCPP_STD_VER >= 14
2955        _NOEXCEPT
2956#else
2957        _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
2958                    __is_nothrow_swappable<allocator_type>::value)
2959#endif
2960{
2961    __base::swap(__c);
2962}
2963
2964template <class _Tp, class _Allocator>
2965inline
2966void
2967deque<_Tp, _Allocator>::clear() _NOEXCEPT
2968{
2969    __base::clear();
2970}
2971
2972template <class _Tp, class _Allocator>
2973inline _LIBCPP_INLINE_VISIBILITY
2974bool
2975operator==(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2976{
2977    const typename deque<_Tp, _Allocator>::size_type __sz = __x.size();
2978    return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
2979}
2980
2981template <class _Tp, class _Allocator>
2982inline _LIBCPP_INLINE_VISIBILITY
2983bool
2984operator!=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2985{
2986    return !(__x == __y);
2987}
2988
2989template <class _Tp, class _Allocator>
2990inline _LIBCPP_INLINE_VISIBILITY
2991bool
2992operator< (const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2993{
2994    return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2995}
2996
2997template <class _Tp, class _Allocator>
2998inline _LIBCPP_INLINE_VISIBILITY
2999bool
3000operator> (const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
3001{
3002    return __y < __x;
3003}
3004
3005template <class _Tp, class _Allocator>
3006inline _LIBCPP_INLINE_VISIBILITY
3007bool
3008operator>=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
3009{
3010    return !(__x < __y);
3011}
3012
3013template <class _Tp, class _Allocator>
3014inline _LIBCPP_INLINE_VISIBILITY
3015bool
3016operator<=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
3017{
3018    return !(__y < __x);
3019}
3020
3021template <class _Tp, class _Allocator>
3022inline _LIBCPP_INLINE_VISIBILITY
3023void
3024swap(deque<_Tp, _Allocator>& __x, deque<_Tp, _Allocator>& __y)
3025    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
3026{
3027    __x.swap(__y);
3028}
3029
3030#if _LIBCPP_STD_VER > 17
3031template <class _Tp, class _Allocator, class _Up>
3032inline _LIBCPP_INLINE_VISIBILITY typename deque<_Tp, _Allocator>::size_type
3033erase(deque<_Tp, _Allocator>& __c, const _Up& __v) {
3034  auto __old_size = __c.size();
3035  __c.erase(_VSTD::remove(__c.begin(), __c.end(), __v), __c.end());
3036  return __old_size - __c.size();
3037}
3038
3039template <class _Tp, class _Allocator, class _Predicate>
3040inline _LIBCPP_INLINE_VISIBILITY typename deque<_Tp, _Allocator>::size_type
3041erase_if(deque<_Tp, _Allocator>& __c, _Predicate __pred) {
3042  auto __old_size = __c.size();
3043  __c.erase(_VSTD::remove_if(__c.begin(), __c.end(), __pred), __c.end());
3044  return __old_size - __c.size();
3045}
3046
3047template <>
3048inline constexpr bool __format::__enable_insertable<std::deque<char>> = true;
3049#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
3050template <>
3051inline constexpr bool __format::__enable_insertable<std::deque<wchar_t>> = true;
3052#endif
3053
3054#endif // _LIBCPP_STD_VER > 17
3055
3056_LIBCPP_END_NAMESPACE_STD
3057
3058_LIBCPP_POP_MACROS
3059
3060#endif // _LIBCPP_DEQUE
3061