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