← Back to branch summary

~ubuntu-branches/ubuntu/vivid/emscripten/vivid

« back to all changes in this revision

Viewing changes to system/include/libcxx/deque

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2013-05-02 13:11:51 UTC
  • Revision ID: package-import@ubuntu.com-20130502131151-q8dvteqr1ef2x7xz
Tags: upstream-1.4.1~20130504~adb56cb
Import upstream version 1.4.1~20130504~adb56cb

Show diffs side-by-side

added added

removed removed

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