Coverage Report

Created: 2020-02-25 14:32

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