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