blob: c10bd3672e1130d5d4447ec5e283de657c463e8a [file] [log] [blame]
Howard Hinnantc51e1022010-05-11 19:42:16 +00001// -*- C++ -*-
2//===---------------------------- deque -----------------------------------===//
3//
Howard Hinnantc566dc32010-05-11 21:36:01 +00004// The LLVM Compiler Infrastructure
Howard Hinnantc51e1022010-05-11 19:42:16 +00005//
Howard Hinnantee11c312010-11-16 22:09:02 +00006// This file is dual licensed under the MIT and the University of Illinois Open
7// Source Licenses. See LICENSE.TXT for details.
Howard Hinnantc51e1022010-05-11 19:42:16 +00008//
9//===----------------------------------------------------------------------===//
10
11#ifndef _LIBCPP_DEQUE
12#define _LIBCPP_DEQUE
13
14/*
15 deque synopsis
16
17namespace std
18{
19
20template <class T, class Allocator = allocator<T> >
21class deque
22{
23public:
24 // types:
25 typedef T value_type;
26 typedef Allocator allocator_type;
27
28 typedef typename allocator_type::reference reference;
29 typedef typename allocator_type::const_reference const_reference;
30 typedef implementation-defined iterator;
31 typedef implementation-defined const_iterator;
32 typedef typename allocator_type::size_type size_type;
33 typedef typename allocator_type::difference_type difference_type;
34
35 typedef typename allocator_type::pointer pointer;
36 typedef typename allocator_type::const_pointer const_pointer;
37 typedef std::reverse_iterator<iterator> reverse_iterator;
38 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
39
40 // construct/copy/destroy:
Howard Hinnantad979ba2011-06-03 15:16:49 +000041 deque() noexcept(is_nothrow_default_constructible<allocator_type>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +000042 explicit deque(const allocator_type& a);
43 explicit deque(size_type n);
Marshall Clow68098692013-09-09 18:19:45 +000044 explicit deque(size_type n, const allocator_type& a); // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +000045 deque(size_type n, const value_type& v);
46 deque(size_type n, const value_type& v, const allocator_type& a);
47 template <class InputIterator>
48 deque(InputIterator f, InputIterator l);
49 template <class InputIterator>
50 deque(InputIterator f, InputIterator l, const allocator_type& a);
51 deque(const deque& c);
Howard Hinnant4931e092011-06-02 21:38:57 +000052 deque(deque&& c)
53 noexcept(is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +000054 deque(initializer_list<value_type> il, const Allocator& a = allocator_type());
55 deque(const deque& c, const allocator_type& a);
56 deque(deque&& c, const allocator_type& a);
57 ~deque();
58
59 deque& operator=(const deque& c);
Howard Hinnant4931e092011-06-02 21:38:57 +000060 deque& operator=(deque&& c)
61 noexcept(
62 allocator_type::propagate_on_container_move_assignment::value &&
63 is_nothrow_move_assignable<allocator_type>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +000064 deque& operator=(initializer_list<value_type> il);
65
66 template <class InputIterator>
67 void assign(InputIterator f, InputIterator l);
68 void assign(size_type n, const value_type& v);
69 void assign(initializer_list<value_type> il);
70
Howard Hinnantda2df912011-06-02 16:10:22 +000071 allocator_type get_allocator() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +000072
73 // iterators:
74
Howard Hinnantda2df912011-06-02 16:10:22 +000075 iterator begin() noexcept;
76 const_iterator begin() const noexcept;
77 iterator end() noexcept;
78 const_iterator end() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +000079
Howard Hinnantda2df912011-06-02 16:10:22 +000080 reverse_iterator rbegin() noexcept;
81 const_reverse_iterator rbegin() const noexcept;
82 reverse_iterator rend() noexcept;
83 const_reverse_iterator rend() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +000084
Howard Hinnantda2df912011-06-02 16:10:22 +000085 const_iterator cbegin() const noexcept;
86 const_iterator cend() const noexcept;
87 const_reverse_iterator crbegin() const noexcept;
88 const_reverse_iterator crend() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +000089
90 // capacity:
Howard Hinnantda2df912011-06-02 16:10:22 +000091 size_type size() const noexcept;
92 size_type max_size() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +000093 void resize(size_type n);
94 void resize(size_type n, const value_type& v);
95 void shrink_to_fit();
Howard Hinnantda2df912011-06-02 16:10:22 +000096 bool empty() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +000097
98 // element access:
99 reference operator[](size_type i);
100 const_reference operator[](size_type i) const;
101 reference at(size_type i);
102 const_reference at(size_type i) const;
103 reference front();
104 const_reference front() const;
105 reference back();
106 const_reference back() const;
107
108 // modifiers:
109 void push_front(const value_type& v);
110 void push_front(value_type&& v);
111 void push_back(const value_type& v);
112 void push_back(value_type&& v);
113 template <class... Args> void emplace_front(Args&&... args);
114 template <class... Args> void emplace_back(Args&&... args);
115 template <class... Args> iterator emplace(const_iterator p, Args&&... args);
116 iterator insert(const_iterator p, const value_type& v);
117 iterator insert(const_iterator p, value_type&& v);
118 iterator insert(const_iterator p, size_type n, const value_type& v);
119 template <class InputIterator>
Marshall Clow6b612cf2015-01-22 18:33:29 +0000120 iterator insert(const_iterator p, InputIterator f, InputIterator l);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000121 iterator insert(const_iterator p, initializer_list<value_type> il);
122 void pop_front();
123 void pop_back();
124 iterator erase(const_iterator p);
125 iterator erase(const_iterator f, const_iterator l);
Howard Hinnant4931e092011-06-02 21:38:57 +0000126 void swap(deque& c)
Marshall Clow8982dcd2015-07-13 20:04:56 +0000127 noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17
Howard Hinnantda2df912011-06-02 16:10:22 +0000128 void clear() noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000129};
130
131template <class T, class Allocator>
132 bool operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
133template <class T, class Allocator>
134 bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y);
135template <class T, class Allocator>
136 bool operator!=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
137template <class T, class Allocator>
138 bool operator> (const deque<T,Allocator>& x, const deque<T,Allocator>& y);
139template <class T, class Allocator>
140 bool operator>=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
141template <class T, class Allocator>
142 bool operator<=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
143
144// specialized algorithms:
145template <class T, class Allocator>
Howard Hinnant287548a2011-06-03 17:30:28 +0000146 void swap(deque<T,Allocator>& x, deque<T,Allocator>& y)
147 noexcept(noexcept(x.swap(y)));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000148
149} // std
150
151*/
152
Howard Hinnantaaaa52b2011-10-17 20:05:10 +0000153#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000154#pragma GCC system_header
Howard Hinnantaaaa52b2011-10-17 20:05:10 +0000155#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000156
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
Howard Hinnantc5a5fbd2011-11-29 16:45:27 +0000165#include <__undef_min_max>
166
Howard Hinnantc51e1022010-05-11 19:42:16 +0000167_LIBCPP_BEGIN_NAMESPACE_STD
168
169template <class _Tp, class _Allocator> class __deque_base;
Marshall Clow65cd4c62015-02-18 17:24:08 +0000170template <class _Tp, class _Allocator = allocator<_Tp> > class _LIBCPP_TYPE_VIS_ONLY deque;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000171
172template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,
173 class _DiffType, _DiffType _BlockSize>
Howard Hinnanta37d3cf2013-08-12 18:38:34 +0000174class _LIBCPP_TYPE_VIS_ONLY __deque_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000175
176template <class _RAIter,
177 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
178__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
179copy(_RAIter __f,
180 _RAIter __l,
181 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
182 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0);
183
184template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
185 class _OutputIterator>
186_OutputIterator
187copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
188 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
189 _OutputIterator __r);
190
191template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
192 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
193__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
194copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
195 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
196 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
197
198template <class _RAIter,
199 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
200__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
201copy_backward(_RAIter __f,
202 _RAIter __l,
203 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
204 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0);
205
206template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
207 class _OutputIterator>
208_OutputIterator
209copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
210 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
211 _OutputIterator __r);
212
213template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
214 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
215__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
216copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
217 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
218 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
219
220template <class _RAIter,
221 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
222__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
223move(_RAIter __f,
224 _RAIter __l,
225 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
226 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0);
227
228template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
229 class _OutputIterator>
230_OutputIterator
231move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
232 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
233 _OutputIterator __r);
234
235template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
236 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
237__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
238move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
239 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
240 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
241
242template <class _RAIter,
243 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
244__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
245move_backward(_RAIter __f,
246 _RAIter __l,
247 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
248 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0);
249
250template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
251 class _OutputIterator>
252_OutputIterator
253move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
254 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
255 _OutputIterator __r);
256
257template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
258 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
259__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
260move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
261 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
262 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
263
Evgeniy Stepanovc299de22015-11-06 22:02:29 +0000264template <class _ValueType, class _DiffType>
265struct __deque_block_size {
266 static const _DiffType value = sizeof(_ValueType) < 256 ? 4096 / sizeof(_ValueType) : 16;
267};
268
Howard Hinnantc51e1022010-05-11 19:42:16 +0000269template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,
Evgeniy Stepanovc299de22015-11-06 22:02:29 +0000270 class _DiffType, _DiffType _BS =
271#ifdef _LIBCPP_ABI_INCOMPLETE_TYPES_IN_DEQUE
272// Keep template parameter to avoid changing all template declarations thoughout
273// this file.
274 0
275#else
276 __deque_block_size<_ValueType, _DiffType>::value
277#endif
278 >
Howard Hinnanta37d3cf2013-08-12 18:38:34 +0000279class _LIBCPP_TYPE_VIS_ONLY __deque_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000280{
281 typedef _MapPointer __map_iterator;
282public:
283 typedef _Pointer pointer;
284 typedef _DiffType difference_type;
285private:
286 __map_iterator __m_iter_;
287 pointer __ptr_;
288
Evgeniy Stepanovc299de22015-11-06 22:02:29 +0000289 static const difference_type __block_size;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000290public:
291 typedef _ValueType value_type;
292 typedef random_access_iterator_tag iterator_category;
293 typedef _Reference reference;
294
Marshall Clow7a3a61d2013-08-06 16:14:36 +0000295 _LIBCPP_INLINE_VISIBILITY __deque_iterator() _NOEXCEPT
296#if _LIBCPP_STD_VER > 11
297 : __m_iter_(nullptr), __ptr_(nullptr)
298#endif
299 {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000300
Howard Hinnantc834c512011-11-29 18:15:50 +0000301 template <class _Pp, class _Rp, class _MP>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000302 _LIBCPP_INLINE_VISIBILITY
Evgeniy Stepanovc299de22015-11-06 22:02:29 +0000303 __deque_iterator(const __deque_iterator<value_type, _Pp, _Rp, _MP, difference_type, _BS>& __it,
Howard Hinnantc834c512011-11-29 18:15:50 +0000304 typename enable_if<is_convertible<_Pp, pointer>::value>::type* = 0) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000305 : __m_iter_(__it.__m_iter_), __ptr_(__it.__ptr_) {}
306
307 _LIBCPP_INLINE_VISIBILITY reference operator*() const {return *__ptr_;}
308 _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return __ptr_;}
309
310 _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator++()
311 {
312 if (++__ptr_ - *__m_iter_ == __block_size)
313 {
314 ++__m_iter_;
315 __ptr_ = *__m_iter_;
316 }
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--()
328 {
329 if (__ptr_ == *__m_iter_)
330 {
331 --__m_iter_;
332 __ptr_ = *__m_iter_ + __block_size;
333 }
334 --__ptr_;
335 return *this;
336 }
337
338 _LIBCPP_INLINE_VISIBILITY __deque_iterator operator--(int)
339 {
340 __deque_iterator __tmp = *this;
341 --(*this);
342 return __tmp;
343 }
344
345 _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator+=(difference_type __n)
346 {
347 if (__n != 0)
348 {
349 __n += __ptr_ - *__m_iter_;
350 if (__n > 0)
351 {
352 __m_iter_ += __n / __block_size;
353 __ptr_ = *__m_iter_ + __n % __block_size;
354 }
355 else // (__n < 0)
356 {
357 difference_type __z = __block_size - 1 - __n;
358 __m_iter_ -= __z / __block_size;
359 __ptr_ = *__m_iter_ + (__block_size - 1 - __z % __block_size);
360 }
361 }
362 return *this;
363 }
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000364
Howard Hinnantc51e1022010-05-11 19:42:16 +0000365 _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator-=(difference_type __n)
366 {
367 return *this += -__n;
368 }
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000369
Howard Hinnantc51e1022010-05-11 19:42:16 +0000370 _LIBCPP_INLINE_VISIBILITY __deque_iterator operator+(difference_type __n) const
371 {
372 __deque_iterator __t(*this);
373 __t += __n;
374 return __t;
375 }
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000376
Howard Hinnantc51e1022010-05-11 19:42:16 +0000377 _LIBCPP_INLINE_VISIBILITY __deque_iterator operator-(difference_type __n) const
378 {
379 __deque_iterator __t(*this);
380 __t -= __n;
381 return __t;
382 }
383
384 _LIBCPP_INLINE_VISIBILITY
385 friend __deque_iterator operator+(difference_type __n, const __deque_iterator& __it)
386 {return __it + __n;}
387
388 _LIBCPP_INLINE_VISIBILITY
389 friend difference_type operator-(const __deque_iterator& __x, const __deque_iterator& __y)
390 {
391 if (__x != __y)
392 return (__x.__m_iter_ - __y.__m_iter_) * __block_size
393 + (__x.__ptr_ - *__x.__m_iter_)
394 - (__y.__ptr_ - *__y.__m_iter_);
395 return 0;
396 }
397
398 _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const
399 {return *(*this + __n);}
400
401 _LIBCPP_INLINE_VISIBILITY friend
402 bool operator==(const __deque_iterator& __x, const __deque_iterator& __y)
403 {return __x.__ptr_ == __y.__ptr_;}
404
405 _LIBCPP_INLINE_VISIBILITY friend
406 bool operator!=(const __deque_iterator& __x, const __deque_iterator& __y)
407 {return !(__x == __y);}
408
409 _LIBCPP_INLINE_VISIBILITY friend
410 bool operator<(const __deque_iterator& __x, const __deque_iterator& __y)
411 {return __x.__m_iter_ < __y.__m_iter_ ||
412 (__x.__m_iter_ == __y.__m_iter_ && __x.__ptr_ < __y.__ptr_);}
413
414 _LIBCPP_INLINE_VISIBILITY friend
415 bool operator>(const __deque_iterator& __x, const __deque_iterator& __y)
416 {return __y < __x;}
417
418 _LIBCPP_INLINE_VISIBILITY friend
419 bool operator<=(const __deque_iterator& __x, const __deque_iterator& __y)
420 {return !(__y < __x);}
421
422 _LIBCPP_INLINE_VISIBILITY friend
423 bool operator>=(const __deque_iterator& __x, const __deque_iterator& __y)
424 {return !(__x < __y);}
425
426private:
Howard Hinnantda2df912011-06-02 16:10:22 +0000427 _LIBCPP_INLINE_VISIBILITY __deque_iterator(__map_iterator __m, pointer __p) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000428 : __m_iter_(__m), __ptr_(__p) {}
429
Howard Hinnantc834c512011-11-29 18:15:50 +0000430 template <class _Tp, class _Ap> friend class __deque_base;
Howard Hinnanta37d3cf2013-08-12 18:38:34 +0000431 template <class _Tp, class _Ap> friend class _LIBCPP_TYPE_VIS_ONLY deque;
Howard Hinnantc834c512011-11-29 18:15:50 +0000432 template <class _Vp, class _Pp, class _Rp, class _MP, class _Dp, _Dp>
Howard Hinnanta37d3cf2013-08-12 18:38:34 +0000433 friend class _LIBCPP_TYPE_VIS_ONLY __deque_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000434
435 template <class _RAIter,
436 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
437 friend
438 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
439 copy(_RAIter __f,
440 _RAIter __l,
441 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
442 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*);
443
444 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
445 class _OutputIterator>
446 friend
447 _OutputIterator
448 copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
449 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
450 _OutputIterator __r);
451
452 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
453 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
454 friend
455 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
456 copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
457 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
458 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
459
460 template <class _RAIter,
461 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
462 friend
463 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
464 copy_backward(_RAIter __f,
465 _RAIter __l,
466 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
467 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*);
468
469 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
470 class _OutputIterator>
471 friend
472 _OutputIterator
473 copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
474 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
475 _OutputIterator __r);
476
477 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
478 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
479 friend
480 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
481 copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
482 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
483 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
484
485 template <class _RAIter,
486 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
487 friend
488 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
489 move(_RAIter __f,
490 _RAIter __l,
491 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
492 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*);
493
494 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
495 class _OutputIterator>
496 friend
497 _OutputIterator
498 move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
499 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
500 _OutputIterator __r);
501
502 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
503 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
504 friend
505 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
506 move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
507 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
508 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
509
510 template <class _RAIter,
511 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
512 friend
513 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
514 move_backward(_RAIter __f,
515 _RAIter __l,
516 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
517 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*);
518
519 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
520 class _OutputIterator>
521 friend
522 _OutputIterator
523 move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
524 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
525 _OutputIterator __r);
526
527 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
528 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
529 friend
530 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
531 move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
532 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
533 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
534};
535
Evgeniy Stepanovc299de22015-11-06 22:02:29 +0000536template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,
537 class _DiffType, _DiffType _BlockSize>
538const _DiffType __deque_iterator<_ValueType, _Pointer, _Reference, _MapPointer,
539 _DiffType, _BlockSize>::__block_size =
540 __deque_block_size<_ValueType, _DiffType>::value;
541
Howard Hinnantc51e1022010-05-11 19:42:16 +0000542// copy
543
544template <class _RAIter,
545 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
546__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
547copy(_RAIter __f,
548 _RAIter __l,
549 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
550 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)
551{
552 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;
553 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;
Evgeniy Stepanovc299de22015-11-06 22:02:29 +0000554 const difference_type __block_size = __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::__block_size;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000555 while (__f != __l)
556 {
557 pointer __rb = __r.__ptr_;
Evgeniy Stepanovc299de22015-11-06 22:02:29 +0000558 pointer __re = *__r.__m_iter_ + __block_size;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000559 difference_type __bs = __re - __rb;
560 difference_type __n = __l - __f;
561 _RAIter __m = __l;
562 if (__n > __bs)
563 {
564 __n = __bs;
565 __m = __f + __n;
566 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000567 _VSTD::copy(__f, __m, __rb);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000568 __f = __m;
569 __r += __n;
570 }
571 return __r;
572}
573
574template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
575 class _OutputIterator>
576_OutputIterator
577copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
578 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
579 _OutputIterator __r)
580{
581 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
582 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
Evgeniy Stepanovc299de22015-11-06 22:02:29 +0000583 const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000584 difference_type __n = __l - __f;
585 while (__n > 0)
586 {
587 pointer __fb = __f.__ptr_;
Evgeniy Stepanovc299de22015-11-06 22:02:29 +0000588 pointer __fe = *__f.__m_iter_ + __block_size;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000589 difference_type __bs = __fe - __fb;
590 if (__bs > __n)
591 {
592 __bs = __n;
593 __fe = __fb + __bs;
594 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000595 __r = _VSTD::copy(__fb, __fe, __r);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000596 __n -= __bs;
597 __f += __bs;
598 }
599 return __r;
600}
601
602template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
603 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
604__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
605copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
606 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
607 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)
608{
609 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
610 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
Evgeniy Stepanovc299de22015-11-06 22:02:29 +0000611 const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000612 difference_type __n = __l - __f;
613 while (__n > 0)
614 {
615 pointer __fb = __f.__ptr_;
Evgeniy Stepanovc299de22015-11-06 22:02:29 +0000616 pointer __fe = *__f.__m_iter_ + __block_size;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000617 difference_type __bs = __fe - __fb;
618 if (__bs > __n)
619 {
620 __bs = __n;
621 __fe = __fb + __bs;
622 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000623 __r = _VSTD::copy(__fb, __fe, __r);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000624 __n -= __bs;
625 __f += __bs;
626 }
627 return __r;
628}
629
630// copy_backward
631
632template <class _RAIter,
633 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
634__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
635copy_backward(_RAIter __f,
636 _RAIter __l,
637 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
638 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)
639{
640 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;
641 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;
642 while (__f != __l)
643 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000644 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __rp = _VSTD::prev(__r);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000645 pointer __rb = *__rp.__m_iter_;
646 pointer __re = __rp.__ptr_ + 1;
647 difference_type __bs = __re - __rb;
648 difference_type __n = __l - __f;
649 _RAIter __m = __f;
650 if (__n > __bs)
651 {
652 __n = __bs;
653 __m = __l - __n;
654 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000655 _VSTD::copy_backward(__m, __l, __re);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000656 __l = __m;
657 __r -= __n;
658 }
659 return __r;
660}
661
662template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
663 class _OutputIterator>
664_OutputIterator
665copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
666 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
667 _OutputIterator __r)
668{
669 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
670 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
671 difference_type __n = __l - __f;
672 while (__n > 0)
673 {
674 --__l;
675 pointer __lb = *__l.__m_iter_;
676 pointer __le = __l.__ptr_ + 1;
677 difference_type __bs = __le - __lb;
678 if (__bs > __n)
679 {
680 __bs = __n;
681 __lb = __le - __bs;
682 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000683 __r = _VSTD::copy_backward(__lb, __le, __r);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000684 __n -= __bs;
685 __l -= __bs - 1;
686 }
687 return __r;
688}
689
690template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
691 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
692__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
693copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
694 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
695 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)
696{
697 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
698 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
699 difference_type __n = __l - __f;
700 while (__n > 0)
701 {
702 --__l;
703 pointer __lb = *__l.__m_iter_;
704 pointer __le = __l.__ptr_ + 1;
705 difference_type __bs = __le - __lb;
706 if (__bs > __n)
707 {
708 __bs = __n;
709 __lb = __le - __bs;
710 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000711 __r = _VSTD::copy_backward(__lb, __le, __r);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000712 __n -= __bs;
713 __l -= __bs - 1;
714 }
715 return __r;
716}
717
718// move
719
720template <class _RAIter,
721 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
722__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
723move(_RAIter __f,
724 _RAIter __l,
725 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
726 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)
727{
728 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;
729 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;
Evgeniy Stepanovc299de22015-11-06 22:02:29 +0000730 const difference_type __block_size = __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::__block_size;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000731 while (__f != __l)
732 {
733 pointer __rb = __r.__ptr_;
Evgeniy Stepanovc299de22015-11-06 22:02:29 +0000734 pointer __re = *__r.__m_iter_ + __block_size;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000735 difference_type __bs = __re - __rb;
736 difference_type __n = __l - __f;
737 _RAIter __m = __l;
738 if (__n > __bs)
739 {
740 __n = __bs;
741 __m = __f + __n;
742 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000743 _VSTD::move(__f, __m, __rb);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000744 __f = __m;
745 __r += __n;
746 }
747 return __r;
748}
749
750template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
751 class _OutputIterator>
752_OutputIterator
753move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
754 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
755 _OutputIterator __r)
756{
757 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
758 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
Evgeniy Stepanovc299de22015-11-06 22:02:29 +0000759 const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000760 difference_type __n = __l - __f;
761 while (__n > 0)
762 {
763 pointer __fb = __f.__ptr_;
Evgeniy Stepanovc299de22015-11-06 22:02:29 +0000764 pointer __fe = *__f.__m_iter_ + __block_size;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000765 difference_type __bs = __fe - __fb;
766 if (__bs > __n)
767 {
768 __bs = __n;
769 __fe = __fb + __bs;
770 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000771 __r = _VSTD::move(__fb, __fe, __r);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000772 __n -= __bs;
773 __f += __bs;
774 }
775 return __r;
776}
777
778template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
779 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
780__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
781move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
782 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
783 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)
784{
785 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
786 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
Evgeniy Stepanovc299de22015-11-06 22:02:29 +0000787 const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000788 difference_type __n = __l - __f;
789 while (__n > 0)
790 {
791 pointer __fb = __f.__ptr_;
Evgeniy Stepanovc299de22015-11-06 22:02:29 +0000792 pointer __fe = *__f.__m_iter_ + __block_size;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000793 difference_type __bs = __fe - __fb;
794 if (__bs > __n)
795 {
796 __bs = __n;
797 __fe = __fb + __bs;
798 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000799 __r = _VSTD::move(__fb, __fe, __r);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000800 __n -= __bs;
801 __f += __bs;
802 }
803 return __r;
804}
805
806// move_backward
807
808template <class _RAIter,
809 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
810__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
811move_backward(_RAIter __f,
812 _RAIter __l,
813 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
814 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)
815{
816 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;
817 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;
818 while (__f != __l)
819 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000820 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __rp = _VSTD::prev(__r);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000821 pointer __rb = *__rp.__m_iter_;
822 pointer __re = __rp.__ptr_ + 1;
823 difference_type __bs = __re - __rb;
824 difference_type __n = __l - __f;
825 _RAIter __m = __f;
826 if (__n > __bs)
827 {
828 __n = __bs;
829 __m = __l - __n;
830 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000831 _VSTD::move_backward(__m, __l, __re);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000832 __l = __m;
833 __r -= __n;
834 }
835 return __r;
836}
837
838template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
839 class _OutputIterator>
840_OutputIterator
841move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
842 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
843 _OutputIterator __r)
844{
845 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
846 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
847 difference_type __n = __l - __f;
848 while (__n > 0)
849 {
850 --__l;
851 pointer __lb = *__l.__m_iter_;
852 pointer __le = __l.__ptr_ + 1;
853 difference_type __bs = __le - __lb;
854 if (__bs > __n)
855 {
856 __bs = __n;
857 __lb = __le - __bs;
858 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000859 __r = _VSTD::move_backward(__lb, __le, __r);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000860 __n -= __bs;
861 __l -= __bs - 1;
862 }
863 return __r;
864}
865
866template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
867 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
868__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
869move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
870 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
871 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)
872{
873 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
874 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
875 difference_type __n = __l - __f;
876 while (__n > 0)
877 {
878 --__l;
879 pointer __lb = *__l.__m_iter_;
880 pointer __le = __l.__ptr_ + 1;
881 difference_type __bs = __le - __lb;
882 if (__bs > __n)
883 {
884 __bs = __n;
885 __lb = __le - __bs;
886 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000887 __r = _VSTD::move_backward(__lb, __le, __r);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000888 __n -= __bs;
889 __l -= __bs - 1;
890 }
891 return __r;
892}
893
894template <bool>
895class __deque_base_common
896{
897protected:
898 void __throw_length_error() const;
899 void __throw_out_of_range() const;
900};
901
902template <bool __b>
903void
904__deque_base_common<__b>::__throw_length_error() const
905{
906#ifndef _LIBCPP_NO_EXCEPTIONS
907 throw length_error("deque");
908#endif
909}
910
911template <bool __b>
912void
913__deque_base_common<__b>::__throw_out_of_range() const
914{
915#ifndef _LIBCPP_NO_EXCEPTIONS
916 throw out_of_range("deque");
917#endif
918}
919
920template <class _Tp, class _Allocator>
921class __deque_base
922 : protected __deque_base_common<true>
923{
924 __deque_base(const __deque_base& __c);
925 __deque_base& operator=(const __deque_base& __c);
926protected:
927 typedef _Tp value_type;
928 typedef _Allocator allocator_type;
929 typedef allocator_traits<allocator_type> __alloc_traits;
930 typedef value_type& reference;
931 typedef const value_type& const_reference;
932 typedef typename __alloc_traits::size_type size_type;
933 typedef typename __alloc_traits::difference_type difference_type;
934 typedef typename __alloc_traits::pointer pointer;
935 typedef typename __alloc_traits::const_pointer const_pointer;
936
Evgeniy Stepanovc299de22015-11-06 22:02:29 +0000937 static const difference_type __block_size;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000938
Marshall Clow940e01c2015-04-07 05:21:38 +0000939 typedef typename __rebind_alloc_helper<__alloc_traits, pointer>::type __pointer_allocator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000940 typedef allocator_traits<__pointer_allocator> __map_traits;
941 typedef typename __map_traits::pointer __map_pointer;
Marshall Clow940e01c2015-04-07 05:21:38 +0000942 typedef typename __rebind_alloc_helper<__alloc_traits, const_pointer>::type __const_pointer_allocator;
Howard Hinnantdcb73a32013-06-23 21:17:24 +0000943 typedef typename allocator_traits<__const_pointer_allocator>::const_pointer __map_const_pointer;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000944 typedef __split_buffer<pointer, __pointer_allocator> __map;
945
946 typedef __deque_iterator<value_type, pointer, reference, __map_pointer,
Evgeniy Stepanovc299de22015-11-06 22:02:29 +0000947 difference_type> iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000948 typedef __deque_iterator<value_type, const_pointer, const_reference, __map_const_pointer,
Evgeniy Stepanovc299de22015-11-06 22:02:29 +0000949 difference_type> const_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000950
951 __map __map_;
952 size_type __start_;
953 __compressed_pair<size_type, allocator_type> __size_;
954
Howard Hinnantda2df912011-06-02 16:10:22 +0000955 iterator begin() _NOEXCEPT;
956 const_iterator begin() const _NOEXCEPT;
957 iterator end() _NOEXCEPT;
958 const_iterator end() const _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000959
960 _LIBCPP_INLINE_VISIBILITY size_type& size() {return __size_.first();}
Howard Hinnantda2df912011-06-02 16:10:22 +0000961 _LIBCPP_INLINE_VISIBILITY
962 const size_type& size() const _NOEXCEPT {return __size_.first();}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000963 _LIBCPP_INLINE_VISIBILITY allocator_type& __alloc() {return __size_.second();}
Howard Hinnantda2df912011-06-02 16:10:22 +0000964 _LIBCPP_INLINE_VISIBILITY
965 const allocator_type& __alloc() const _NOEXCEPT {return __size_.second();}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000966
Howard Hinnantad979ba2011-06-03 15:16:49 +0000967 __deque_base()
968 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000969 explicit __deque_base(const allocator_type& __a);
Howard Hinnantca2fc222011-06-02 20:00:14 +0000970public:
Howard Hinnantc51e1022010-05-11 19:42:16 +0000971 ~__deque_base();
972
Howard Hinnant74279a52010-09-04 23:28:19 +0000973#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +0000974
Howard Hinnantca2fc222011-06-02 20:00:14 +0000975 __deque_base(__deque_base&& __c)
976 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000977 __deque_base(__deque_base&& __c, const allocator_type& __a);
978
Howard Hinnant74279a52010-09-04 23:28:19 +0000979#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantca2fc222011-06-02 20:00:14 +0000980 void swap(__deque_base& __c)
Marshall Clow8982dcd2015-07-13 20:04:56 +0000981#if _LIBCPP_STD_VER >= 14
982 _NOEXCEPT;
983#else
984 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
985 __is_nothrow_swappable<allocator_type>::value);
986#endif
Howard Hinnantca2fc222011-06-02 20:00:14 +0000987protected:
Howard Hinnantda2df912011-06-02 16:10:22 +0000988 void clear() _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000989
990 bool __invariants() const;
991
Howard Hinnant874ad9a2010-09-21 21:28:23 +0000992 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000993 void __move_assign(__deque_base& __c)
Howard Hinnant4931e092011-06-02 21:38:57 +0000994 _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&
995 is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000996 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000997 __map_ = _VSTD::move(__c.__map_);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000998 __start_ = __c.__start_;
999 size() = __c.size();
1000 __move_assign_alloc(__c);
1001 __c.__start_ = __c.size() = 0;
1002 }
1003
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001004 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001005 void __move_assign_alloc(__deque_base& __c)
Howard Hinnantca2fc222011-06-02 20:00:14 +00001006 _NOEXCEPT_(!__alloc_traits::propagate_on_container_move_assignment::value ||
1007 is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001008 {__move_assign_alloc(__c, integral_constant<bool,
1009 __alloc_traits::propagate_on_container_move_assignment::value>());}
1010
1011private:
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001012 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc2734962011-09-02 20:42:31 +00001013 void __move_assign_alloc(__deque_base& __c, true_type)
Howard Hinnantca2fc222011-06-02 20:00:14 +00001014 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001015 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001016 __alloc() = _VSTD::move(__c.__alloc());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001017 }
1018
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001019 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant28b24882011-12-01 20:21:04 +00001020 void __move_assign_alloc(__deque_base&, false_type) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001021 {}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001022};
1023
1024template <class _Tp, class _Allocator>
Evgeniy Stepanovc299de22015-11-06 22:02:29 +00001025const typename __deque_base<_Tp, _Allocator>::difference_type
1026 __deque_base<_Tp, _Allocator>::__block_size =
1027 __deque_block_size<value_type, difference_type>::value;
1028
1029template <class _Tp, class _Allocator>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001030bool
1031__deque_base<_Tp, _Allocator>::__invariants() const
1032{
1033 if (!__map_.__invariants())
1034 return false;
1035 if (__map_.size() >= size_type(-1) / __block_size)
1036 return false;
1037 for (typename __map::const_iterator __i = __map_.begin(), __e = __map_.end();
1038 __i != __e; ++__i)
1039 if (*__i == nullptr)
1040 return false;
1041 if (__map_.size() != 0)
1042 {
1043 if (size() >= __map_.size() * __block_size)
1044 return false;
1045 if (__start_ >= __map_.size() * __block_size - size())
1046 return false;
1047 }
1048 else
1049 {
1050 if (size() != 0)
1051 return false;
1052 if (__start_ != 0)
1053 return false;
1054 }
1055 return true;
1056}
1057
1058template <class _Tp, class _Allocator>
1059typename __deque_base<_Tp, _Allocator>::iterator
Howard Hinnantda2df912011-06-02 16:10:22 +00001060__deque_base<_Tp, _Allocator>::begin() _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001061{
1062 __map_pointer __mp = __map_.begin() + __start_ / __block_size;
1063 return iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size);
1064}
1065
1066template <class _Tp, class _Allocator>
1067typename __deque_base<_Tp, _Allocator>::const_iterator
Howard Hinnantda2df912011-06-02 16:10:22 +00001068__deque_base<_Tp, _Allocator>::begin() const _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001069{
Howard Hinnantdcb73a32013-06-23 21:17:24 +00001070 __map_const_pointer __mp = static_cast<__map_const_pointer>(__map_.begin() + __start_ / __block_size);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001071 return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size);
1072}
1073
1074template <class _Tp, class _Allocator>
1075typename __deque_base<_Tp, _Allocator>::iterator
Howard Hinnantda2df912011-06-02 16:10:22 +00001076__deque_base<_Tp, _Allocator>::end() _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001077{
1078 size_type __p = size() + __start_;
1079 __map_pointer __mp = __map_.begin() + __p / __block_size;
1080 return iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size);
1081}
1082
1083template <class _Tp, class _Allocator>
1084typename __deque_base<_Tp, _Allocator>::const_iterator
Howard Hinnantda2df912011-06-02 16:10:22 +00001085__deque_base<_Tp, _Allocator>::end() const _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001086{
1087 size_type __p = size() + __start_;
Howard Hinnantdcb73a32013-06-23 21:17:24 +00001088 __map_const_pointer __mp = static_cast<__map_const_pointer>(__map_.begin() + __p / __block_size);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001089 return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size);
1090}
1091
1092template <class _Tp, class _Allocator>
1093inline _LIBCPP_INLINE_VISIBILITY
1094__deque_base<_Tp, _Allocator>::__deque_base()
Howard Hinnantad979ba2011-06-03 15:16:49 +00001095 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001096 : __start_(0), __size_(0) {}
1097
1098template <class _Tp, class _Allocator>
1099inline _LIBCPP_INLINE_VISIBILITY
1100__deque_base<_Tp, _Allocator>::__deque_base(const allocator_type& __a)
1101 : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a) {}
1102
1103template <class _Tp, class _Allocator>
1104__deque_base<_Tp, _Allocator>::~__deque_base()
1105{
1106 clear();
1107 typename __map::iterator __i = __map_.begin();
1108 typename __map::iterator __e = __map_.end();
1109 for (; __i != __e; ++__i)
1110 __alloc_traits::deallocate(__alloc(), *__i, __block_size);
1111}
1112
Howard Hinnant74279a52010-09-04 23:28:19 +00001113#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001114
1115template <class _Tp, class _Allocator>
1116__deque_base<_Tp, _Allocator>::__deque_base(__deque_base&& __c)
Howard Hinnantca2fc222011-06-02 20:00:14 +00001117 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001118 : __map_(_VSTD::move(__c.__map_)),
1119 __start_(_VSTD::move(__c.__start_)),
1120 __size_(_VSTD::move(__c.__size_))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001121{
1122 __c.__start_ = 0;
1123 __c.size() = 0;
1124}
1125
1126template <class _Tp, class _Allocator>
1127__deque_base<_Tp, _Allocator>::__deque_base(__deque_base&& __c, const allocator_type& __a)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001128 : __map_(_VSTD::move(__c.__map_), __pointer_allocator(__a)),
1129 __start_(_VSTD::move(__c.__start_)),
1130 __size_(_VSTD::move(__c.size()), __a)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001131{
1132 if (__a == __c.__alloc())
1133 {
1134 __c.__start_ = 0;
1135 __c.size() = 0;
1136 }
1137 else
1138 {
1139 __map_.clear();
1140 __start_ = 0;
1141 size() = 0;
1142 }
1143}
1144
Howard Hinnant74279a52010-09-04 23:28:19 +00001145#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001146
1147template <class _Tp, class _Allocator>
1148void
1149__deque_base<_Tp, _Allocator>::swap(__deque_base& __c)
Marshall Clow8982dcd2015-07-13 20:04:56 +00001150#if _LIBCPP_STD_VER >= 14
1151 _NOEXCEPT
1152#else
1153 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
1154 __is_nothrow_swappable<allocator_type>::value)
1155#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001156{
1157 __map_.swap(__c.__map_);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001158 _VSTD::swap(__start_, __c.__start_);
1159 _VSTD::swap(size(), __c.size());
Marshall Clow8982dcd2015-07-13 20:04:56 +00001160 __swap_allocator(__alloc(), __c.__alloc());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001161}
1162
1163template <class _Tp, class _Allocator>
1164void
Howard Hinnantda2df912011-06-02 16:10:22 +00001165__deque_base<_Tp, _Allocator>::clear() _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001166{
1167 allocator_type& __a = __alloc();
1168 for (iterator __i = begin(), __e = end(); __i != __e; ++__i)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001169 __alloc_traits::destroy(__a, _VSTD::addressof(*__i));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001170 size() = 0;
1171 while (__map_.size() > 2)
1172 {
1173 __alloc_traits::deallocate(__a, __map_.front(), __block_size);
1174 __map_.pop_front();
1175 }
1176 switch (__map_.size())
1177 {
1178 case 1:
1179 __start_ = __block_size / 2;
1180 break;
1181 case 2:
1182 __start_ = __block_size;
1183 break;
1184 }
1185}
1186
Marshall Clow65cd4c62015-02-18 17:24:08 +00001187template <class _Tp, class _Allocator /*= allocator<_Tp>*/>
Howard Hinnanta37d3cf2013-08-12 18:38:34 +00001188class _LIBCPP_TYPE_VIS_ONLY deque
Howard Hinnantc51e1022010-05-11 19:42:16 +00001189 : private __deque_base<_Tp, _Allocator>
1190{
1191public:
1192 // types:
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001193
Howard Hinnantc51e1022010-05-11 19:42:16 +00001194 typedef _Tp value_type;
1195 typedef _Allocator allocator_type;
1196
1197 typedef __deque_base<value_type, allocator_type> __base;
1198
1199 typedef typename __base::__alloc_traits __alloc_traits;
1200 typedef typename __base::reference reference;
1201 typedef typename __base::const_reference const_reference;
1202 typedef typename __base::iterator iterator;
1203 typedef typename __base::const_iterator const_iterator;
1204 typedef typename __base::size_type size_type;
1205 typedef typename __base::difference_type difference_type;
1206
1207 typedef typename __base::pointer pointer;
1208 typedef typename __base::const_pointer const_pointer;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001209 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
1210 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001211
1212 // construct/copy/destroy:
Howard Hinnantad979ba2011-06-03 15:16:49 +00001213 _LIBCPP_INLINE_VISIBILITY
1214 deque()
1215 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
1216 {}
Marshall Clow7ed23a72014-03-05 19:06:20 +00001217 _LIBCPP_INLINE_VISIBILITY explicit deque(const allocator_type& __a) : __base(__a) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001218 explicit deque(size_type __n);
Marshall Clowbc4fcb42013-09-07 16:16:19 +00001219#if _LIBCPP_STD_VER > 11
1220 explicit deque(size_type __n, const _Allocator& __a);
1221#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001222 deque(size_type __n, const value_type& __v);
1223 deque(size_type __n, const value_type& __v, const allocator_type& __a);
1224 template <class _InputIter>
1225 deque(_InputIter __f, _InputIter __l,
1226 typename enable_if<__is_input_iterator<_InputIter>::value>::type* = 0);
1227 template <class _InputIter>
1228 deque(_InputIter __f, _InputIter __l, const allocator_type& __a,
1229 typename enable_if<__is_input_iterator<_InputIter>::value>::type* = 0);
1230 deque(const deque& __c);
1231 deque(const deque& __c, const allocator_type& __a);
Howard Hinnant33711792011-08-12 21:56:02 +00001232#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001233 deque(initializer_list<value_type> __il);
1234 deque(initializer_list<value_type> __il, const allocator_type& __a);
Howard Hinnant33711792011-08-12 21:56:02 +00001235#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001236
1237 deque& operator=(const deque& __c);
Howard Hinnant33711792011-08-12 21:56:02 +00001238#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001239 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001240 deque& operator=(initializer_list<value_type> __il) {assign(__il); return *this;}
Howard Hinnant33711792011-08-12 21:56:02 +00001241#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001242
Howard Hinnant74279a52010-09-04 23:28:19 +00001243#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantca2fc222011-06-02 20:00:14 +00001244 deque(deque&& __c) _NOEXCEPT_(is_nothrow_move_constructible<__base>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001245 deque(deque&& __c, const allocator_type& __a);
Howard Hinnantca2fc222011-06-02 20:00:14 +00001246 deque& operator=(deque&& __c)
Howard Hinnant4931e092011-06-02 21:38:57 +00001247 _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&
1248 is_nothrow_move_assignable<allocator_type>::value);
Howard Hinnant74279a52010-09-04 23:28:19 +00001249#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001250
1251 template <class _InputIter>
1252 void assign(_InputIter __f, _InputIter __l,
1253 typename enable_if<__is_input_iterator<_InputIter>::value &&
1254 !__is_random_access_iterator<_InputIter>::value>::type* = 0);
1255 template <class _RAIter>
1256 void assign(_RAIter __f, _RAIter __l,
1257 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0);
1258 void assign(size_type __n, const value_type& __v);
Howard Hinnant33711792011-08-12 21:56:02 +00001259#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001260 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001261 void assign(initializer_list<value_type> __il) {assign(__il.begin(), __il.end());}
Howard Hinnant33711792011-08-12 21:56:02 +00001262#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001263
Howard Hinnantda2df912011-06-02 16:10:22 +00001264 allocator_type get_allocator() const _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001265
1266 // iterators:
1267
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001268 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantda2df912011-06-02 16:10:22 +00001269 iterator begin() _NOEXCEPT {return __base::begin();}
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001270 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantda2df912011-06-02 16:10:22 +00001271 const_iterator begin() const _NOEXCEPT {return __base::begin();}
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001272 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantda2df912011-06-02 16:10:22 +00001273 iterator end() _NOEXCEPT {return __base::end();}
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001274 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantda2df912011-06-02 16:10:22 +00001275 const_iterator end() const _NOEXCEPT {return __base::end();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001276
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001277 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantda2df912011-06-02 16:10:22 +00001278 reverse_iterator rbegin() _NOEXCEPT
1279 {return reverse_iterator(__base::end());}
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001280 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantda2df912011-06-02 16:10:22 +00001281 const_reverse_iterator rbegin() const _NOEXCEPT
1282 {return const_reverse_iterator(__base::end());}
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001283 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantda2df912011-06-02 16:10:22 +00001284 reverse_iterator rend() _NOEXCEPT
1285 {return reverse_iterator(__base::begin());}
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001286 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantda2df912011-06-02 16:10:22 +00001287 const_reverse_iterator rend() const _NOEXCEPT
1288 {return const_reverse_iterator(__base::begin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001289
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001290 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantda2df912011-06-02 16:10:22 +00001291 const_iterator cbegin() const _NOEXCEPT
1292 {return __base::begin();}
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001293 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantda2df912011-06-02 16:10:22 +00001294 const_iterator cend() const _NOEXCEPT
1295 {return __base::end();}
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001296 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantda2df912011-06-02 16:10:22 +00001297 const_reverse_iterator crbegin() const _NOEXCEPT
1298 {return const_reverse_iterator(__base::end());}
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001299 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantda2df912011-06-02 16:10:22 +00001300 const_reverse_iterator crend() const _NOEXCEPT
1301 {return const_reverse_iterator(__base::begin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001302
1303 // capacity:
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001304 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantda2df912011-06-02 16:10:22 +00001305 size_type size() const _NOEXCEPT {return __base::size();}
1306 _LIBCPP_INLINE_VISIBILITY
1307 size_type max_size() const _NOEXCEPT
1308 {return __alloc_traits::max_size(__base::__alloc());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001309 void resize(size_type __n);
1310 void resize(size_type __n, const value_type& __v);
Howard Hinnant4931e092011-06-02 21:38:57 +00001311 void shrink_to_fit() _NOEXCEPT;
Howard Hinnantda2df912011-06-02 16:10:22 +00001312 _LIBCPP_INLINE_VISIBILITY
1313 bool empty() const _NOEXCEPT {return __base::size() == 0;}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001314
1315 // element access:
1316 reference operator[](size_type __i);
1317 const_reference operator[](size_type __i) const;
1318 reference at(size_type __i);
1319 const_reference at(size_type __i) const;
1320 reference front();
1321 const_reference front() const;
1322 reference back();
1323 const_reference back() const;
1324
1325 // 23.2.2.3 modifiers:
1326 void push_front(const value_type& __v);
1327 void push_back(const value_type& __v);
Howard Hinnant74279a52010-09-04 23:28:19 +00001328#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1329#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001330 template <class... _Args> void emplace_front(_Args&&... __args);
1331 template <class... _Args> void emplace_back(_Args&&... __args);
1332 template <class... _Args> iterator emplace(const_iterator __p, _Args&&... __args);
Howard Hinnant74279a52010-09-04 23:28:19 +00001333#endif // _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001334 void push_front(value_type&& __v);
1335 void push_back(value_type&& __v);
1336 iterator insert(const_iterator __p, value_type&& __v);
Howard Hinnant74279a52010-09-04 23:28:19 +00001337#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001338 iterator insert(const_iterator __p, const value_type& __v);
1339 iterator insert(const_iterator __p, size_type __n, const value_type& __v);
1340 template <class _InputIter>
Marshall Clow6b612cf2015-01-22 18:33:29 +00001341 iterator insert(const_iterator __p, _InputIter __f, _InputIter __l,
Howard Hinnantc51e1022010-05-11 19:42:16 +00001342 typename enable_if<__is_input_iterator<_InputIter>::value
Marshall Clow6b612cf2015-01-22 18:33:29 +00001343 &&!__is_forward_iterator<_InputIter>::value>::type* = 0);
1344 template <class _ForwardIterator>
1345 iterator insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l,
1346 typename enable_if<__is_forward_iterator<_ForwardIterator>::value
1347 &&!__is_bidirectional_iterator<_ForwardIterator>::value>::type* = 0);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001348 template <class _BiIter>
Marshall Clow6b612cf2015-01-22 18:33:29 +00001349 iterator insert(const_iterator __p, _BiIter __f, _BiIter __l,
Howard Hinnantc51e1022010-05-11 19:42:16 +00001350 typename enable_if<__is_bidirectional_iterator<_BiIter>::value>::type* = 0);
Howard Hinnant33711792011-08-12 21:56:02 +00001351#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001352 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001353 iterator insert(const_iterator __p, initializer_list<value_type> __il)
1354 {return insert(__p, __il.begin(), __il.end());}
Howard Hinnant33711792011-08-12 21:56:02 +00001355#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001356 void pop_front();
1357 void pop_back();
1358 iterator erase(const_iterator __p);
1359 iterator erase(const_iterator __f, const_iterator __l);
1360
Howard Hinnantca2fc222011-06-02 20:00:14 +00001361 void swap(deque& __c)
Marshall Clow8982dcd2015-07-13 20:04:56 +00001362#if _LIBCPP_STD_VER >= 14
1363 _NOEXCEPT;
1364#else
Howard Hinnantca2fc222011-06-02 20:00:14 +00001365 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
1366 __is_nothrow_swappable<allocator_type>::value);
Marshall Clow8982dcd2015-07-13 20:04:56 +00001367#endif
Howard Hinnantda2df912011-06-02 16:10:22 +00001368 void clear() _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001369
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001370 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001371 bool __invariants() const {return __base::__invariants();}
1372private:
Howard Hinnantdcb73a32013-06-23 21:17:24 +00001373 typedef typename __base::__map_const_pointer __map_const_pointer;
1374
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001375 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001376 static size_type __recommend_blocks(size_type __n)
1377 {
1378 return __n / __base::__block_size + (__n % __base::__block_size != 0);
1379 }
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001380 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001381 size_type __capacity() const
1382 {
1383 return __base::__map_.size() == 0 ? 0 : __base::__map_.size() * __base::__block_size - 1;
1384 }
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001385 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001386 size_type __front_spare() const
1387 {
1388 return __base::__start_;
1389 }
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001390 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001391 size_type __back_spare() const
1392 {
1393 return __capacity() - (__base::__start_ + __base::size());
1394 }
1395
1396 template <class _InpIter>
1397 void __append(_InpIter __f, _InpIter __l,
1398 typename enable_if<__is_input_iterator<_InpIter>::value &&
1399 !__is_forward_iterator<_InpIter>::value>::type* = 0);
1400 template <class _ForIter>
1401 void __append(_ForIter __f, _ForIter __l,
1402 typename enable_if<__is_forward_iterator<_ForIter>::value>::type* = 0);
1403 void __append(size_type __n);
1404 void __append(size_type __n, const value_type& __v);
1405 void __erase_to_end(const_iterator __f);
1406 void __add_front_capacity();
1407 void __add_front_capacity(size_type __n);
1408 void __add_back_capacity();
1409 void __add_back_capacity(size_type __n);
1410 iterator __move_and_check(iterator __f, iterator __l, iterator __r,
1411 const_pointer& __vt);
1412 iterator __move_backward_and_check(iterator __f, iterator __l, iterator __r,
1413 const_pointer& __vt);
1414 void __move_construct_and_check(iterator __f, iterator __l,
1415 iterator __r, const_pointer& __vt);
1416 void __move_construct_backward_and_check(iterator __f, iterator __l,
1417 iterator __r, const_pointer& __vt);
1418
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001419 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001420 void __copy_assign_alloc(const deque& __c)
1421 {__copy_assign_alloc(__c, integral_constant<bool,
1422 __alloc_traits::propagate_on_container_copy_assignment::value>());}
1423
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001424 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001425 void __copy_assign_alloc(const deque& __c, true_type)
1426 {
1427 if (__base::__alloc() != __c.__alloc())
1428 {
1429 clear();
1430 shrink_to_fit();
1431 }
1432 __base::__alloc() = __c.__alloc();
1433 __base::__map_.__alloc() = __c.__map_.__alloc();
1434 }
1435
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001436 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant28b24882011-12-01 20:21:04 +00001437 void __copy_assign_alloc(const deque&, false_type)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001438 {}
1439
Howard Hinnant4931e092011-06-02 21:38:57 +00001440 void __move_assign(deque& __c, true_type)
1441 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001442 void __move_assign(deque& __c, false_type);
1443};
1444
1445template <class _Tp, class _Allocator>
1446deque<_Tp, _Allocator>::deque(size_type __n)
1447{
1448 if (__n > 0)
1449 __append(__n);
1450}
1451
Marshall Clowbc4fcb42013-09-07 16:16:19 +00001452#if _LIBCPP_STD_VER > 11
1453template <class _Tp, class _Allocator>
1454deque<_Tp, _Allocator>::deque(size_type __n, const _Allocator& __a)
1455 : __base(__a)
1456{
1457 if (__n > 0)
1458 __append(__n);
1459}
1460#endif
1461
Howard Hinnantc51e1022010-05-11 19:42:16 +00001462template <class _Tp, class _Allocator>
1463deque<_Tp, _Allocator>::deque(size_type __n, const value_type& __v)
1464{
1465 if (__n > 0)
1466 __append(__n, __v);
1467}
1468
1469template <class _Tp, class _Allocator>
1470deque<_Tp, _Allocator>::deque(size_type __n, const value_type& __v, const allocator_type& __a)
1471 : __base(__a)
1472{
1473 if (__n > 0)
1474 __append(__n, __v);
1475}
1476
1477template <class _Tp, class _Allocator>
1478template <class _InputIter>
1479deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l,
1480 typename enable_if<__is_input_iterator<_InputIter>::value>::type*)
1481{
1482 __append(__f, __l);
1483}
1484
1485template <class _Tp, class _Allocator>
1486template <class _InputIter>
1487deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l, const allocator_type& __a,
1488 typename enable_if<__is_input_iterator<_InputIter>::value>::type*)
1489 : __base(__a)
1490{
1491 __append(__f, __l);
1492}
1493
1494template <class _Tp, class _Allocator>
1495deque<_Tp, _Allocator>::deque(const deque& __c)
1496 : __base(__alloc_traits::select_on_container_copy_construction(__c.__alloc()))
1497{
1498 __append(__c.begin(), __c.end());
1499}
1500
1501template <class _Tp, class _Allocator>
1502deque<_Tp, _Allocator>::deque(const deque& __c, const allocator_type& __a)
1503 : __base(__a)
1504{
1505 __append(__c.begin(), __c.end());
1506}
1507
Howard Hinnant33711792011-08-12 21:56:02 +00001508#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1509
Howard Hinnantc51e1022010-05-11 19:42:16 +00001510template <class _Tp, class _Allocator>
1511deque<_Tp, _Allocator>::deque(initializer_list<value_type> __il)
1512{
1513 __append(__il.begin(), __il.end());
1514}
1515
1516template <class _Tp, class _Allocator>
1517deque<_Tp, _Allocator>::deque(initializer_list<value_type> __il, const allocator_type& __a)
1518 : __base(__a)
1519{
1520 __append(__il.begin(), __il.end());
1521}
1522
Howard Hinnant33711792011-08-12 21:56:02 +00001523#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1524
Howard Hinnantc51e1022010-05-11 19:42:16 +00001525template <class _Tp, class _Allocator>
1526deque<_Tp, _Allocator>&
1527deque<_Tp, _Allocator>::operator=(const deque& __c)
1528{
1529 if (this != &__c)
1530 {
1531 __copy_assign_alloc(__c);
1532 assign(__c.begin(), __c.end());
1533 }
1534 return *this;
1535}
1536
Howard Hinnant74279a52010-09-04 23:28:19 +00001537#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001538
1539template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001540inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001541deque<_Tp, _Allocator>::deque(deque&& __c)
Howard Hinnantca2fc222011-06-02 20:00:14 +00001542 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001543 : __base(_VSTD::move(__c))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001544{
1545}
1546
1547template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001548inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001549deque<_Tp, _Allocator>::deque(deque&& __c, const allocator_type& __a)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001550 : __base(_VSTD::move(__c), __a)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001551{
1552 if (__a != __c.__alloc())
1553 {
Howard Hinnantc834c512011-11-29 18:15:50 +00001554 typedef move_iterator<iterator> _Ip;
1555 assign(_Ip(__c.begin()), _Ip(__c.end()));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001556 }
1557}
1558
1559template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001560inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001561deque<_Tp, _Allocator>&
1562deque<_Tp, _Allocator>::operator=(deque&& __c)
Howard Hinnant4931e092011-06-02 21:38:57 +00001563 _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&
1564 is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001565{
1566 __move_assign(__c, integral_constant<bool,
1567 __alloc_traits::propagate_on_container_move_assignment::value>());
1568 return *this;
1569}
1570
1571template <class _Tp, class _Allocator>
1572void
1573deque<_Tp, _Allocator>::__move_assign(deque& __c, false_type)
1574{
1575 if (__base::__alloc() != __c.__alloc())
1576 {
Howard Hinnantc834c512011-11-29 18:15:50 +00001577 typedef move_iterator<iterator> _Ip;
1578 assign(_Ip(__c.begin()), _Ip(__c.end()));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001579 }
1580 else
1581 __move_assign(__c, true_type());
1582}
1583
1584template <class _Tp, class _Allocator>
1585void
1586deque<_Tp, _Allocator>::__move_assign(deque& __c, true_type)
Howard Hinnant4931e092011-06-02 21:38:57 +00001587 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001588{
1589 clear();
1590 shrink_to_fit();
1591 __base::__move_assign(__c);
1592}
1593
Howard Hinnant74279a52010-09-04 23:28:19 +00001594#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001595
1596template <class _Tp, class _Allocator>
1597template <class _InputIter>
1598void
1599deque<_Tp, _Allocator>::assign(_InputIter __f, _InputIter __l,
1600 typename enable_if<__is_input_iterator<_InputIter>::value &&
1601 !__is_random_access_iterator<_InputIter>::value>::type*)
1602{
1603 iterator __i = __base::begin();
1604 iterator __e = __base::end();
Eric Fiseliera09a3b42014-10-27 19:28:20 +00001605 for (; __f != __l && __i != __e; ++__f, (void) ++__i)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001606 *__i = *__f;
1607 if (__f != __l)
1608 __append(__f, __l);
1609 else
1610 __erase_to_end(__i);
1611}
1612
1613template <class _Tp, class _Allocator>
1614template <class _RAIter>
1615void
1616deque<_Tp, _Allocator>::assign(_RAIter __f, _RAIter __l,
1617 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)
1618{
1619 if (static_cast<size_type>(__l - __f) > __base::size())
1620 {
1621 _RAIter __m = __f + __base::size();
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001622 _VSTD::copy(__f, __m, __base::begin());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001623 __append(__m, __l);
1624 }
1625 else
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001626 __erase_to_end(_VSTD::copy(__f, __l, __base::begin()));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001627}
1628
1629template <class _Tp, class _Allocator>
1630void
1631deque<_Tp, _Allocator>::assign(size_type __n, const value_type& __v)
1632{
1633 if (__n > __base::size())
1634 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001635 _VSTD::fill_n(__base::begin(), __base::size(), __v);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001636 __n -= __base::size();
1637 __append(__n, __v);
1638 }
1639 else
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001640 __erase_to_end(_VSTD::fill_n(__base::begin(), __n, __v));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001641}
1642
1643template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001644inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001645_Allocator
Howard Hinnantda2df912011-06-02 16:10:22 +00001646deque<_Tp, _Allocator>::get_allocator() const _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001647{
1648 return __base::__alloc();
1649}
1650
1651template <class _Tp, class _Allocator>
1652void
1653deque<_Tp, _Allocator>::resize(size_type __n)
1654{
1655 if (__n > __base::size())
1656 __append(__n - __base::size());
1657 else if (__n < __base::size())
1658 __erase_to_end(__base::begin() + __n);
1659}
1660
1661template <class _Tp, class _Allocator>
1662void
1663deque<_Tp, _Allocator>::resize(size_type __n, const value_type& __v)
1664{
1665 if (__n > __base::size())
1666 __append(__n - __base::size(), __v);
1667 else if (__n < __base::size())
1668 __erase_to_end(__base::begin() + __n);
1669}
1670
1671template <class _Tp, class _Allocator>
1672void
Howard Hinnant4931e092011-06-02 21:38:57 +00001673deque<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001674{
1675 allocator_type& __a = __base::__alloc();
1676 if (empty())
1677 {
1678 while (__base::__map_.size() > 0)
1679 {
1680 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
1681 __base::__map_.pop_back();
1682 }
1683 __base::__start_ = 0;
1684 }
1685 else
1686 {
1687 if (__front_spare() >= __base::__block_size)
1688 {
1689 __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
1690 __base::__map_.pop_front();
1691 __base::__start_ -= __base::__block_size;
1692 }
1693 if (__back_spare() >= __base::__block_size)
1694 {
1695 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
1696 __base::__map_.pop_back();
1697 }
1698 }
1699 __base::__map_.shrink_to_fit();
1700}
1701
1702template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001703inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001704typename deque<_Tp, _Allocator>::reference
1705deque<_Tp, _Allocator>::operator[](size_type __i)
1706{
1707 size_type __p = __base::__start_ + __i;
1708 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1709}
1710
1711template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001712inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001713typename deque<_Tp, _Allocator>::const_reference
1714deque<_Tp, _Allocator>::operator[](size_type __i) const
1715{
1716 size_type __p = __base::__start_ + __i;
1717 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1718}
1719
1720template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001721inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001722typename deque<_Tp, _Allocator>::reference
1723deque<_Tp, _Allocator>::at(size_type __i)
1724{
1725 if (__i >= __base::size())
1726 __base::__throw_out_of_range();
1727 size_type __p = __base::__start_ + __i;
1728 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1729}
1730
1731template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001732inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001733typename deque<_Tp, _Allocator>::const_reference
1734deque<_Tp, _Allocator>::at(size_type __i) const
1735{
1736 if (__i >= __base::size())
1737 __base::__throw_out_of_range();
1738 size_type __p = __base::__start_ + __i;
1739 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1740}
1741
1742template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001743inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001744typename deque<_Tp, _Allocator>::reference
1745deque<_Tp, _Allocator>::front()
1746{
1747 return *(*(__base::__map_.begin() + __base::__start_ / __base::__block_size)
1748 + __base::__start_ % __base::__block_size);
1749}
1750
1751template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001752inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001753typename deque<_Tp, _Allocator>::const_reference
1754deque<_Tp, _Allocator>::front() const
1755{
1756 return *(*(__base::__map_.begin() + __base::__start_ / __base::__block_size)
1757 + __base::__start_ % __base::__block_size);
1758}
1759
1760template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001761inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001762typename deque<_Tp, _Allocator>::reference
1763deque<_Tp, _Allocator>::back()
1764{
1765 size_type __p = __base::size() + __base::__start_ - 1;
1766 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1767}
1768
1769template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001770inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001771typename deque<_Tp, _Allocator>::const_reference
1772deque<_Tp, _Allocator>::back() const
1773{
1774 size_type __p = __base::size() + __base::__start_ - 1;
1775 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1776}
1777
1778template <class _Tp, class _Allocator>
1779void
1780deque<_Tp, _Allocator>::push_back(const value_type& __v)
1781{
1782 allocator_type& __a = __base::__alloc();
1783 if (__back_spare() == 0)
1784 __add_back_capacity();
1785 // __back_spare() >= 1
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001786 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), __v);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001787 ++__base::size();
1788}
1789
Howard Hinnant74279a52010-09-04 23:28:19 +00001790#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001791
1792template <class _Tp, class _Allocator>
1793void
1794deque<_Tp, _Allocator>::push_back(value_type&& __v)
1795{
1796 allocator_type& __a = __base::__alloc();
1797 if (__back_spare() == 0)
1798 __add_back_capacity();
1799 // __back_spare() >= 1
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001800 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::move(__v));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001801 ++__base::size();
1802}
1803
Howard Hinnant74279a52010-09-04 23:28:19 +00001804#ifndef _LIBCPP_HAS_NO_VARIADICS
1805
Howard Hinnantc51e1022010-05-11 19:42:16 +00001806template <class _Tp, class _Allocator>
1807template <class... _Args>
1808void
1809deque<_Tp, _Allocator>::emplace_back(_Args&&... __args)
1810{
1811 allocator_type& __a = __base::__alloc();
1812 if (__back_spare() == 0)
1813 __add_back_capacity();
1814 // __back_spare() >= 1
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001815 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001816 ++__base::size();
1817}
1818
Howard Hinnant74279a52010-09-04 23:28:19 +00001819#endif // _LIBCPP_HAS_NO_VARIADICS
1820#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001821
1822template <class _Tp, class _Allocator>
1823void
1824deque<_Tp, _Allocator>::push_front(const value_type& __v)
1825{
1826 allocator_type& __a = __base::__alloc();
1827 if (__front_spare() == 0)
1828 __add_front_capacity();
1829 // __front_spare() >= 1
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001830 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), __v);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001831 --__base::__start_;
1832 ++__base::size();
1833}
1834
Howard Hinnant74279a52010-09-04 23:28:19 +00001835#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001836
1837template <class _Tp, class _Allocator>
1838void
1839deque<_Tp, _Allocator>::push_front(value_type&& __v)
1840{
1841 allocator_type& __a = __base::__alloc();
1842 if (__front_spare() == 0)
1843 __add_front_capacity();
1844 // __front_spare() >= 1
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001845 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::move(__v));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001846 --__base::__start_;
1847 ++__base::size();
1848}
1849
Howard Hinnant74279a52010-09-04 23:28:19 +00001850#ifndef _LIBCPP_HAS_NO_VARIADICS
1851
Howard Hinnantc51e1022010-05-11 19:42:16 +00001852template <class _Tp, class _Allocator>
1853template <class... _Args>
1854void
1855deque<_Tp, _Allocator>::emplace_front(_Args&&... __args)
1856{
1857 allocator_type& __a = __base::__alloc();
1858 if (__front_spare() == 0)
1859 __add_front_capacity();
1860 // __front_spare() >= 1
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001861 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001862 --__base::__start_;
1863 ++__base::size();
1864}
1865
Howard Hinnant74279a52010-09-04 23:28:19 +00001866#endif // _LIBCPP_HAS_NO_VARIADICS
1867#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001868
1869template <class _Tp, class _Allocator>
1870typename deque<_Tp, _Allocator>::iterator
1871deque<_Tp, _Allocator>::insert(const_iterator __p, const value_type& __v)
1872{
1873 size_type __pos = __p - __base::begin();
1874 size_type __to_end = __base::size() - __pos;
1875 allocator_type& __a = __base::__alloc();
1876 if (__pos < __to_end)
1877 { // insert by shifting things backward
1878 if (__front_spare() == 0)
1879 __add_front_capacity();
1880 // __front_spare() >= 1
1881 if (__pos == 0)
1882 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001883 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), __v);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001884 --__base::__start_;
1885 ++__base::size();
1886 }
1887 else
1888 {
1889 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
1890 iterator __b = __base::begin();
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001891 iterator __bm1 = _VSTD::prev(__b);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001892 if (__vt == pointer_traits<const_pointer>::pointer_to(*__b))
1893 __vt = pointer_traits<const_pointer>::pointer_to(*__bm1);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001894 __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001895 --__base::__start_;
1896 ++__base::size();
1897 if (__pos > 1)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001898 __b = __move_and_check(_VSTD::next(__b), __b + __pos, __b, __vt);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001899 *__b = *__vt;
1900 }
1901 }
1902 else
1903 { // insert by shifting things forward
1904 if (__back_spare() == 0)
1905 __add_back_capacity();
1906 // __back_capacity >= 1
1907 size_type __de = __base::size() - __pos;
1908 if (__de == 0)
1909 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001910 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), __v);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001911 ++__base::size();
1912 }
1913 else
1914 {
1915 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
1916 iterator __e = __base::end();
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001917 iterator __em1 = _VSTD::prev(__e);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001918 if (__vt == pointer_traits<const_pointer>::pointer_to(*__em1))
1919 __vt = pointer_traits<const_pointer>::pointer_to(*__e);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001920 __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001921 ++__base::size();
1922 if (__de > 1)
1923 __e = __move_backward_and_check(__e - __de, __em1, __e, __vt);
1924 *--__e = *__vt;
1925 }
1926 }
1927 return __base::begin() + __pos;
1928}
1929
Howard Hinnant74279a52010-09-04 23:28:19 +00001930#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001931
1932template <class _Tp, class _Allocator>
1933typename deque<_Tp, _Allocator>::iterator
1934deque<_Tp, _Allocator>::insert(const_iterator __p, value_type&& __v)
1935{
1936 size_type __pos = __p - __base::begin();
1937 size_type __to_end = __base::size() - __pos;
1938 allocator_type& __a = __base::__alloc();
1939 if (__pos < __to_end)
1940 { // insert by shifting things backward
1941 if (__front_spare() == 0)
1942 __add_front_capacity();
1943 // __front_spare() >= 1
1944 if (__pos == 0)
1945 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001946 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::move(__v));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001947 --__base::__start_;
1948 ++__base::size();
1949 }
1950 else
1951 {
1952 iterator __b = __base::begin();
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001953 iterator __bm1 = _VSTD::prev(__b);
1954 __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001955 --__base::__start_;
1956 ++__base::size();
1957 if (__pos > 1)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001958 __b = _VSTD::move(_VSTD::next(__b), __b + __pos, __b);
1959 *__b = _VSTD::move(__v);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001960 }
1961 }
1962 else
1963 { // insert by shifting things forward
1964 if (__back_spare() == 0)
1965 __add_back_capacity();
1966 // __back_capacity >= 1
1967 size_type __de = __base::size() - __pos;
1968 if (__de == 0)
1969 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001970 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::move(__v));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001971 ++__base::size();
1972 }
1973 else
1974 {
1975 iterator __e = __base::end();
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001976 iterator __em1 = _VSTD::prev(__e);
1977 __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001978 ++__base::size();
1979 if (__de > 1)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001980 __e = _VSTD::move_backward(__e - __de, __em1, __e);
1981 *--__e = _VSTD::move(__v);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001982 }
1983 }
1984 return __base::begin() + __pos;
1985}
1986
Howard Hinnant74279a52010-09-04 23:28:19 +00001987#ifndef _LIBCPP_HAS_NO_VARIADICS
1988
Howard Hinnantc51e1022010-05-11 19:42:16 +00001989template <class _Tp, class _Allocator>
1990template <class... _Args>
1991typename deque<_Tp, _Allocator>::iterator
1992deque<_Tp, _Allocator>::emplace(const_iterator __p, _Args&&... __args)
1993{
1994 size_type __pos = __p - __base::begin();
1995 size_type __to_end = __base::size() - __pos;
1996 allocator_type& __a = __base::__alloc();
1997 if (__pos < __to_end)
1998 { // insert by shifting things backward
1999 if (__front_spare() == 0)
2000 __add_front_capacity();
2001 // __front_spare() >= 1
2002 if (__pos == 0)
2003 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002004 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002005 --__base::__start_;
2006 ++__base::size();
2007 }
2008 else
2009 {
Howard Hinnant800d2d22012-07-08 23:23:04 +00002010 value_type __tmp(_VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002011 iterator __b = __base::begin();
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002012 iterator __bm1 = _VSTD::prev(__b);
2013 __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002014 --__base::__start_;
2015 ++__base::size();
2016 if (__pos > 1)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002017 __b = _VSTD::move(_VSTD::next(__b), __b + __pos, __b);
Howard Hinnant800d2d22012-07-08 23:23:04 +00002018 *__b = _VSTD::move(__tmp);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002019 }
2020 }
2021 else
2022 { // insert by shifting things forward
2023 if (__back_spare() == 0)
2024 __add_back_capacity();
2025 // __back_capacity >= 1
2026 size_type __de = __base::size() - __pos;
2027 if (__de == 0)
2028 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002029 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002030 ++__base::size();
2031 }
2032 else
2033 {
Howard Hinnant800d2d22012-07-08 23:23:04 +00002034 value_type __tmp(_VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002035 iterator __e = __base::end();
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002036 iterator __em1 = _VSTD::prev(__e);
2037 __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002038 ++__base::size();
2039 if (__de > 1)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002040 __e = _VSTD::move_backward(__e - __de, __em1, __e);
Howard Hinnant800d2d22012-07-08 23:23:04 +00002041 *--__e = _VSTD::move(__tmp);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002042 }
2043 }
2044 return __base::begin() + __pos;
2045}
2046
Howard Hinnant74279a52010-09-04 23:28:19 +00002047#endif // _LIBCPP_HAS_NO_VARIADICS
2048#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00002049
2050template <class _Tp, class _Allocator>
2051typename deque<_Tp, _Allocator>::iterator
2052deque<_Tp, _Allocator>::insert(const_iterator __p, size_type __n, const value_type& __v)
2053{
2054 size_type __pos = __p - __base::begin();
2055 size_type __to_end = __base::size() - __pos;
2056 allocator_type& __a = __base::__alloc();
2057 if (__pos < __to_end)
2058 { // insert by shifting things backward
2059 if (__n > __front_spare())
2060 __add_front_capacity(__n - __front_spare());
2061 // __n <= __front_spare()
Howard Hinnantc51e1022010-05-11 19:42:16 +00002062 iterator __old_begin = __base::begin();
2063 iterator __i = __old_begin;
2064 if (__n > __pos)
2065 {
2066 for (size_type __m = __n - __pos; __m; --__m, --__base::__start_, ++__base::size())
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002067 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), __v);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002068 __n = __pos;
2069 }
2070 if (__n > 0)
2071 {
2072 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
2073 iterator __obn = __old_begin + __n;
2074 __move_construct_backward_and_check(__old_begin, __obn, __i, __vt);
2075 if (__n < __pos)
2076 __old_begin = __move_and_check(__obn, __old_begin + __pos, __old_begin, __vt);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002077 _VSTD::fill_n(__old_begin, __n, *__vt);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002078 }
2079 }
2080 else
2081 { // insert by shifting things forward
2082 size_type __back_capacity = __back_spare();
2083 if (__n > __back_capacity)
2084 __add_back_capacity(__n - __back_capacity);
2085 // __n <= __back_capacity
Howard Hinnantc51e1022010-05-11 19:42:16 +00002086 iterator __old_end = __base::end();
2087 iterator __i = __old_end;
2088 size_type __de = __base::size() - __pos;
2089 if (__n > __de)
2090 {
2091 for (size_type __m = __n - __de; __m; --__m, ++__i, ++__base::size())
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002092 __alloc_traits::construct(__a, _VSTD::addressof(*__i), __v);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002093 __n = __de;
2094 }
2095 if (__n > 0)
2096 {
2097 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
2098 iterator __oen = __old_end - __n;
2099 __move_construct_and_check(__oen, __old_end, __i, __vt);
2100 if (__n < __de)
2101 __old_end = __move_backward_and_check(__old_end - __de, __oen, __old_end, __vt);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002102 _VSTD::fill_n(__old_end - __n, __n, *__vt);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002103 }
2104 }
2105 return __base::begin() + __pos;
2106}
2107
2108template <class _Tp, class _Allocator>
2109template <class _InputIter>
2110typename deque<_Tp, _Allocator>::iterator
2111deque<_Tp, _Allocator>::insert(const_iterator __p, _InputIter __f, _InputIter __l,
2112 typename enable_if<__is_input_iterator<_InputIter>::value
Marshall Clow6b612cf2015-01-22 18:33:29 +00002113 &&!__is_forward_iterator<_InputIter>::value>::type*)
Howard Hinnantc51e1022010-05-11 19:42:16 +00002114{
2115 __split_buffer<value_type, allocator_type&> __buf(__base::__alloc());
2116 __buf.__construct_at_end(__f, __l);
2117 typedef typename __split_buffer<value_type, allocator_type&>::iterator __bi;
2118 return insert(__p, move_iterator<__bi>(__buf.begin()), move_iterator<__bi>(__buf.end()));
2119}
2120
2121template <class _Tp, class _Allocator>
Marshall Clow6b612cf2015-01-22 18:33:29 +00002122template <class _ForwardIterator>
2123typename deque<_Tp, _Allocator>::iterator
2124deque<_Tp, _Allocator>::insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l,
2125 typename enable_if<__is_forward_iterator<_ForwardIterator>::value
2126 &&!__is_bidirectional_iterator<_ForwardIterator>::value>::type*)
2127{
2128 size_type __n = _VSTD::distance(__f, __l);
2129 __split_buffer<value_type, allocator_type&> __buf(__n, 0, __base::__alloc());
2130 __buf.__construct_at_end(__f, __l);
2131 typedef typename __split_buffer<value_type, allocator_type&>::iterator __fwd;
2132 return insert(__p, move_iterator<__fwd>(__buf.begin()), move_iterator<__fwd>(__buf.end()));
2133}
2134
2135template <class _Tp, class _Allocator>
Howard Hinnantc51e1022010-05-11 19:42:16 +00002136template <class _BiIter>
2137typename deque<_Tp, _Allocator>::iterator
2138deque<_Tp, _Allocator>::insert(const_iterator __p, _BiIter __f, _BiIter __l,
2139 typename enable_if<__is_bidirectional_iterator<_BiIter>::value>::type*)
2140{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002141 size_type __n = _VSTD::distance(__f, __l);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002142 size_type __pos = __p - __base::begin();
2143 size_type __to_end = __base::size() - __pos;
2144 allocator_type& __a = __base::__alloc();
2145 if (__pos < __to_end)
2146 { // insert by shifting things backward
2147 if (__n > __front_spare())
2148 __add_front_capacity(__n - __front_spare());
2149 // __n <= __front_spare()
Howard Hinnantc51e1022010-05-11 19:42:16 +00002150 iterator __old_begin = __base::begin();
2151 iterator __i = __old_begin;
2152 _BiIter __m = __f;
2153 if (__n > __pos)
2154 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002155 __m = __pos < __n / 2 ? _VSTD::prev(__l, __pos) : _VSTD::next(__f, __n - __pos);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002156 for (_BiIter __j = __m; __j != __f; --__base::__start_, ++__base::size())
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002157 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), *--__j);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002158 __n = __pos;
2159 }
2160 if (__n > 0)
2161 {
2162 iterator __obn = __old_begin + __n;
2163 for (iterator __j = __obn; __j != __old_begin;)
2164 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002165 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), _VSTD::move(*--__j));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002166 --__base::__start_;
2167 ++__base::size();
2168 }
2169 if (__n < __pos)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002170 __old_begin = _VSTD::move(__obn, __old_begin + __pos, __old_begin);
2171 _VSTD::copy(__m, __l, __old_begin);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002172 }
2173 }
2174 else
2175 { // insert by shifting things forward
2176 size_type __back_capacity = __back_spare();
2177 if (__n > __back_capacity)
2178 __add_back_capacity(__n - __back_capacity);
2179 // __n <= __back_capacity
Howard Hinnantc51e1022010-05-11 19:42:16 +00002180 iterator __old_end = __base::end();
2181 iterator __i = __old_end;
2182 _BiIter __m = __l;
2183 size_type __de = __base::size() - __pos;
2184 if (__n > __de)
2185 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002186 __m = __de < __n / 2 ? _VSTD::next(__f, __de) : _VSTD::prev(__l, __n - __de);
Eric Fiseliera09a3b42014-10-27 19:28:20 +00002187 for (_BiIter __j = __m; __j != __l; ++__i, (void) ++__j, ++__base::size())
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002188 __alloc_traits::construct(__a, _VSTD::addressof(*__i), *__j);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002189 __n = __de;
2190 }
2191 if (__n > 0)
2192 {
2193 iterator __oen = __old_end - __n;
2194 for (iterator __j = __oen; __j != __old_end; ++__i, ++__j, ++__base::size())
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002195 __alloc_traits::construct(__a, _VSTD::addressof(*__i), _VSTD::move(*__j));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002196 if (__n < __de)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002197 __old_end = _VSTD::move_backward(__old_end - __de, __oen, __old_end);
2198 _VSTD::copy_backward(__f, __m, __old_end);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002199 }
2200 }
2201 return __base::begin() + __pos;
2202}
2203
2204template <class _Tp, class _Allocator>
2205template <class _InpIter>
2206void
2207deque<_Tp, _Allocator>::__append(_InpIter __f, _InpIter __l,
2208 typename enable_if<__is_input_iterator<_InpIter>::value &&
2209 !__is_forward_iterator<_InpIter>::value>::type*)
2210{
2211 for (; __f != __l; ++__f)
2212 push_back(*__f);
2213}
2214
2215template <class _Tp, class _Allocator>
2216template <class _ForIter>
2217void
2218deque<_Tp, _Allocator>::__append(_ForIter __f, _ForIter __l,
2219 typename enable_if<__is_forward_iterator<_ForIter>::value>::type*)
2220{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002221 size_type __n = _VSTD::distance(__f, __l);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002222 allocator_type& __a = __base::__alloc();
2223 size_type __back_capacity = __back_spare();
2224 if (__n > __back_capacity)
2225 __add_back_capacity(__n - __back_capacity);
2226 // __n <= __back_capacity
Eric Fiseliera09a3b42014-10-27 19:28:20 +00002227 for (iterator __i = __base::end(); __f != __l; ++__i, (void) ++__f, ++__base::size())
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002228 __alloc_traits::construct(__a, _VSTD::addressof(*__i), *__f);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002229}
2230
2231template <class _Tp, class _Allocator>
2232void
2233deque<_Tp, _Allocator>::__append(size_type __n)
2234{
2235 allocator_type& __a = __base::__alloc();
2236 size_type __back_capacity = __back_spare();
2237 if (__n > __back_capacity)
2238 __add_back_capacity(__n - __back_capacity);
2239 // __n <= __back_capacity
2240 for (iterator __i = __base::end(); __n; --__n, ++__i, ++__base::size())
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002241 __alloc_traits::construct(__a, _VSTD::addressof(*__i));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002242}
2243
2244template <class _Tp, class _Allocator>
2245void
2246deque<_Tp, _Allocator>::__append(size_type __n, const value_type& __v)
2247{
2248 allocator_type& __a = __base::__alloc();
2249 size_type __back_capacity = __back_spare();
2250 if (__n > __back_capacity)
2251 __add_back_capacity(__n - __back_capacity);
2252 // __n <= __back_capacity
2253 for (iterator __i = __base::end(); __n; --__n, ++__i, ++__base::size())
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002254 __alloc_traits::construct(__a, _VSTD::addressof(*__i), __v);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002255}
2256
2257// Create front capacity for one block of elements.
2258// Strong guarantee. Either do it or don't touch anything.
2259template <class _Tp, class _Allocator>
2260void
2261deque<_Tp, _Allocator>::__add_front_capacity()
2262{
2263 allocator_type& __a = __base::__alloc();
2264 if (__back_spare() >= __base::__block_size)
2265 {
2266 __base::__start_ += __base::__block_size;
2267 pointer __pt = __base::__map_.back();
2268 __base::__map_.pop_back();
2269 __base::__map_.push_front(__pt);
2270 }
2271 // Else if __base::__map_.size() < __base::__map_.capacity() then we need to allocate 1 buffer
2272 else if (__base::__map_.size() < __base::__map_.capacity())
2273 { // we can put the new buffer into the map, but don't shift things around
2274 // until all buffers are allocated. If we throw, we don't need to fix
2275 // anything up (any added buffers are undetectible)
2276 if (__base::__map_.__front_spare() > 0)
2277 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
2278 else
2279 {
2280 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2281 // Done allocating, reorder capacity
2282 pointer __pt = __base::__map_.back();
2283 __base::__map_.pop_back();
2284 __base::__map_.push_front(__pt);
2285 }
2286 __base::__start_ = __base::__map_.size() == 1 ?
2287 __base::__block_size / 2 :
2288 __base::__start_ + __base::__block_size;
2289 }
2290 // Else need to allocate 1 buffer, *and* we need to reallocate __map_.
2291 else
2292 {
2293 __split_buffer<pointer, typename __base::__pointer_allocator&>
2294 __buf(max<size_type>(2 * __base::__map_.capacity(), 1),
2295 0, __base::__map_.__alloc());
Marshall Clow5fd466b2015-03-09 17:08:51 +00002296
Marshall Clow8982dcd2015-07-13 20:04:56 +00002297 typedef __allocator_destructor<_Allocator> _Dp;
2298 unique_ptr<pointer, _Dp> __hold(
2299 __alloc_traits::allocate(__a, __base::__block_size),
2300 _Dp(__a, __base::__block_size));
2301 __buf.push_back(__hold.get());
2302 __hold.release();
2303
Howard Hinnantc51e1022010-05-11 19:42:16 +00002304 for (typename __base::__map_pointer __i = __base::__map_.begin();
2305 __i != __base::__map_.end(); ++__i)
2306 __buf.push_back(*__i);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002307 _VSTD::swap(__base::__map_.__first_, __buf.__first_);
2308 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
2309 _VSTD::swap(__base::__map_.__end_, __buf.__end_);
2310 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
Howard Hinnantc51e1022010-05-11 19:42:16 +00002311 __base::__start_ = __base::__map_.size() == 1 ?
2312 __base::__block_size / 2 :
2313 __base::__start_ + __base::__block_size;
2314 }
2315}
2316
2317// Create front capacity for __n elements.
2318// Strong guarantee. Either do it or don't touch anything.
2319template <class _Tp, class _Allocator>
2320void
2321deque<_Tp, _Allocator>::__add_front_capacity(size_type __n)
2322{
2323 allocator_type& __a = __base::__alloc();
2324 size_type __nb = __recommend_blocks(__n + __base::__map_.empty());
2325 // Number of unused blocks at back:
2326 size_type __back_capacity = __back_spare() / __base::__block_size;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002327 __back_capacity = _VSTD::min(__back_capacity, __nb); // don't take more than you need
Howard Hinnantc51e1022010-05-11 19:42:16 +00002328 __nb -= __back_capacity; // number of blocks need to allocate
2329 // If __nb == 0, then we have sufficient capacity.
2330 if (__nb == 0)
2331 {
2332 __base::__start_ += __base::__block_size * __back_capacity;
2333 for (; __back_capacity > 0; --__back_capacity)
2334 {
2335 pointer __pt = __base::__map_.back();
2336 __base::__map_.pop_back();
2337 __base::__map_.push_front(__pt);
2338 }
2339 }
2340 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers
2341 else if (__nb <= __base::__map_.capacity() - __base::__map_.size())
2342 { // we can put the new buffers into the map, but don't shift things around
2343 // until all buffers are allocated. If we throw, we don't need to fix
2344 // anything up (any added buffers are undetectible)
2345 for (; __nb > 0; --__nb, __base::__start_ += __base::__block_size - (__base::__map_.size() == 1))
2346 {
2347 if (__base::__map_.__front_spare() == 0)
2348 break;
2349 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
2350 }
2351 for (; __nb > 0; --__nb, ++__back_capacity)
2352 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2353 // Done allocating, reorder capacity
2354 __base::__start_ += __back_capacity * __base::__block_size;
2355 for (; __back_capacity > 0; --__back_capacity)
2356 {
2357 pointer __pt = __base::__map_.back();
2358 __base::__map_.pop_back();
2359 __base::__map_.push_front(__pt);
2360 }
2361 }
2362 // Else need to allocate __nb buffers, *and* we need to reallocate __map_.
2363 else
2364 {
2365 size_type __ds = (__nb + __back_capacity) * __base::__block_size - __base::__map_.empty();
2366 __split_buffer<pointer, typename __base::__pointer_allocator&>
2367 __buf(max<size_type>(2* __base::__map_.capacity(),
2368 __nb + __base::__map_.size()),
2369 0, __base::__map_.__alloc());
2370#ifndef _LIBCPP_NO_EXCEPTIONS
2371 try
2372 {
Howard Hinnant3b6579a2010-08-22 00:02:43 +00002373#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00002374 for (; __nb > 0; --__nb)
2375 __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2376#ifndef _LIBCPP_NO_EXCEPTIONS
2377 }
2378 catch (...)
2379 {
2380 for (typename __base::__map_pointer __i = __buf.begin();
2381 __i != __buf.end(); ++__i)
2382 __alloc_traits::deallocate(__a, *__i, __base::__block_size);
2383 throw;
2384 }
Howard Hinnant3b6579a2010-08-22 00:02:43 +00002385#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00002386 for (; __back_capacity > 0; --__back_capacity)
2387 {
2388 __buf.push_back(__base::__map_.back());
2389 __base::__map_.pop_back();
2390 }
2391 for (typename __base::__map_pointer __i = __base::__map_.begin();
2392 __i != __base::__map_.end(); ++__i)
2393 __buf.push_back(*__i);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002394 _VSTD::swap(__base::__map_.__first_, __buf.__first_);
2395 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
2396 _VSTD::swap(__base::__map_.__end_, __buf.__end_);
2397 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
Howard Hinnantc51e1022010-05-11 19:42:16 +00002398 __base::__start_ += __ds;
2399 }
2400}
2401
2402// Create back capacity for one block of elements.
2403// Strong guarantee. Either do it or don't touch anything.
2404template <class _Tp, class _Allocator>
2405void
2406deque<_Tp, _Allocator>::__add_back_capacity()
2407{
2408 allocator_type& __a = __base::__alloc();
2409 if (__front_spare() >= __base::__block_size)
2410 {
2411 __base::__start_ -= __base::__block_size;
2412 pointer __pt = __base::__map_.front();
2413 __base::__map_.pop_front();
2414 __base::__map_.push_back(__pt);
2415 }
2416 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers
2417 else if (__base::__map_.size() < __base::__map_.capacity())
2418 { // we can put the new buffer into the map, but don't shift things around
2419 // until it is allocated. If we throw, we don't need to fix
2420 // anything up (any added buffers are undetectible)
2421 if (__base::__map_.__back_spare() != 0)
2422 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2423 else
2424 {
2425 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
2426 // Done allocating, reorder capacity
2427 pointer __pt = __base::__map_.front();
2428 __base::__map_.pop_front();
2429 __base::__map_.push_back(__pt);
2430 }
2431 }
2432 // Else need to allocate 1 buffer, *and* we need to reallocate __map_.
2433 else
2434 {
2435 __split_buffer<pointer, typename __base::__pointer_allocator&>
2436 __buf(max<size_type>(2* __base::__map_.capacity(), 1),
2437 __base::__map_.size(),
2438 __base::__map_.__alloc());
Marshall Clow5fd466b2015-03-09 17:08:51 +00002439
Marshall Clow8982dcd2015-07-13 20:04:56 +00002440 typedef __allocator_destructor<_Allocator> _Dp;
2441 unique_ptr<pointer, _Dp> __hold(
2442 __alloc_traits::allocate(__a, __base::__block_size),
2443 _Dp(__a, __base::__block_size));
2444 __buf.push_back(__hold.get());
2445 __hold.release();
Marshall Clow5fd466b2015-03-09 17:08:51 +00002446
Howard Hinnantc51e1022010-05-11 19:42:16 +00002447 for (typename __base::__map_pointer __i = __base::__map_.end();
2448 __i != __base::__map_.begin();)
2449 __buf.push_front(*--__i);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002450 _VSTD::swap(__base::__map_.__first_, __buf.__first_);
2451 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
2452 _VSTD::swap(__base::__map_.__end_, __buf.__end_);
2453 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
Howard Hinnantc51e1022010-05-11 19:42:16 +00002454 }
2455}
2456
2457// Create back capacity for __n elements.
2458// Strong guarantee. Either do it or don't touch anything.
2459template <class _Tp, class _Allocator>
2460void
2461deque<_Tp, _Allocator>::__add_back_capacity(size_type __n)
2462{
2463 allocator_type& __a = __base::__alloc();
2464 size_type __nb = __recommend_blocks(__n + __base::__map_.empty());
2465 // Number of unused blocks at front:
2466 size_type __front_capacity = __front_spare() / __base::__block_size;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002467 __front_capacity = _VSTD::min(__front_capacity, __nb); // don't take more than you need
Howard Hinnantc51e1022010-05-11 19:42:16 +00002468 __nb -= __front_capacity; // number of blocks need to allocate
2469 // If __nb == 0, then we have sufficient capacity.
2470 if (__nb == 0)
2471 {
2472 __base::__start_ -= __base::__block_size * __front_capacity;
2473 for (; __front_capacity > 0; --__front_capacity)
2474 {
2475 pointer __pt = __base::__map_.front();
2476 __base::__map_.pop_front();
2477 __base::__map_.push_back(__pt);
2478 }
2479 }
2480 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers
2481 else if (__nb <= __base::__map_.capacity() - __base::__map_.size())
2482 { // we can put the new buffers into the map, but don't shift things around
2483 // until all buffers are allocated. If we throw, we don't need to fix
2484 // anything up (any added buffers are undetectible)
2485 for (; __nb > 0; --__nb)
2486 {
2487 if (__base::__map_.__back_spare() == 0)
2488 break;
2489 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2490 }
2491 for (; __nb > 0; --__nb, ++__front_capacity, __base::__start_ +=
2492 __base::__block_size - (__base::__map_.size() == 1))
2493 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
2494 // Done allocating, reorder capacity
2495 __base::__start_ -= __base::__block_size * __front_capacity;
2496 for (; __front_capacity > 0; --__front_capacity)
2497 {
2498 pointer __pt = __base::__map_.front();
2499 __base::__map_.pop_front();
2500 __base::__map_.push_back(__pt);
2501 }
2502 }
2503 // Else need to allocate __nb buffers, *and* we need to reallocate __map_.
2504 else
2505 {
2506 size_type __ds = __front_capacity * __base::__block_size;
2507 __split_buffer<pointer, typename __base::__pointer_allocator&>
2508 __buf(max<size_type>(2* __base::__map_.capacity(),
2509 __nb + __base::__map_.size()),
2510 __base::__map_.size() - __front_capacity,
2511 __base::__map_.__alloc());
2512#ifndef _LIBCPP_NO_EXCEPTIONS
2513 try
2514 {
Howard Hinnant3b6579a2010-08-22 00:02:43 +00002515#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00002516 for (; __nb > 0; --__nb)
2517 __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2518#ifndef _LIBCPP_NO_EXCEPTIONS
2519 }
2520 catch (...)
2521 {
2522 for (typename __base::__map_pointer __i = __buf.begin();
2523 __i != __buf.end(); ++__i)
2524 __alloc_traits::deallocate(__a, *__i, __base::__block_size);
2525 throw;
2526 }
Howard Hinnant3b6579a2010-08-22 00:02:43 +00002527#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00002528 for (; __front_capacity > 0; --__front_capacity)
2529 {
2530 __buf.push_back(__base::__map_.front());
2531 __base::__map_.pop_front();
2532 }
2533 for (typename __base::__map_pointer __i = __base::__map_.end();
2534 __i != __base::__map_.begin();)
2535 __buf.push_front(*--__i);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002536 _VSTD::swap(__base::__map_.__first_, __buf.__first_);
2537 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
2538 _VSTD::swap(__base::__map_.__end_, __buf.__end_);
2539 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
Howard Hinnantc51e1022010-05-11 19:42:16 +00002540 __base::__start_ -= __ds;
2541 }
2542}
2543
2544template <class _Tp, class _Allocator>
2545void
2546deque<_Tp, _Allocator>::pop_front()
2547{
2548 allocator_type& __a = __base::__alloc();
Howard Hinnantdcb73a32013-06-23 21:17:24 +00002549 __alloc_traits::destroy(__a, __to_raw_pointer(*(__base::__map_.begin() +
2550 __base::__start_ / __base::__block_size) +
2551 __base::__start_ % __base::__block_size));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002552 --__base::size();
2553 if (++__base::__start_ >= 2 * __base::__block_size)
2554 {
2555 __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
2556 __base::__map_.pop_front();
2557 __base::__start_ -= __base::__block_size;
2558 }
2559}
2560
2561template <class _Tp, class _Allocator>
2562void
2563deque<_Tp, _Allocator>::pop_back()
2564{
2565 allocator_type& __a = __base::__alloc();
2566 size_type __p = __base::size() + __base::__start_ - 1;
Howard Hinnantdcb73a32013-06-23 21:17:24 +00002567 __alloc_traits::destroy(__a, __to_raw_pointer(*(__base::__map_.begin() +
2568 __p / __base::__block_size) +
2569 __p % __base::__block_size));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002570 --__base::size();
2571 if (__back_spare() >= 2 * __base::__block_size)
2572 {
2573 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
2574 __base::__map_.pop_back();
2575 }
2576}
2577
2578// move assign [__f, __l) to [__r, __r + (__l-__f)).
2579// If __vt points into [__f, __l), then subtract (__f - __r) from __vt.
2580template <class _Tp, class _Allocator>
2581typename deque<_Tp, _Allocator>::iterator
2582deque<_Tp, _Allocator>::__move_and_check(iterator __f, iterator __l, iterator __r,
2583 const_pointer& __vt)
2584{
2585 // as if
2586 // for (; __f != __l; ++__f, ++__r)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002587 // *__r = _VSTD::move(*__f);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002588 difference_type __n = __l - __f;
2589 while (__n > 0)
2590 {
2591 pointer __fb = __f.__ptr_;
2592 pointer __fe = *__f.__m_iter_ + __base::__block_size;
2593 difference_type __bs = __fe - __fb;
2594 if (__bs > __n)
2595 {
2596 __bs = __n;
2597 __fe = __fb + __bs;
2598 }
2599 if (__fb <= __vt && __vt < __fe)
Howard Hinnantdcb73a32013-06-23 21:17:24 +00002600 __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) -= __f - __r).__ptr_;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002601 __r = _VSTD::move(__fb, __fe, __r);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002602 __n -= __bs;
2603 __f += __bs;
2604 }
2605 return __r;
2606}
2607
2608// move assign [__f, __l) to [__r - (__l-__f), __r) backwards.
2609// If __vt points into [__f, __l), then add (__r - __l) to __vt.
2610template <class _Tp, class _Allocator>
2611typename deque<_Tp, _Allocator>::iterator
2612deque<_Tp, _Allocator>::__move_backward_and_check(iterator __f, iterator __l, iterator __r,
2613 const_pointer& __vt)
2614{
2615 // as if
2616 // while (__f != __l)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002617 // *--__r = _VSTD::move(*--__l);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002618 difference_type __n = __l - __f;
2619 while (__n > 0)
2620 {
2621 --__l;
2622 pointer __lb = *__l.__m_iter_;
2623 pointer __le = __l.__ptr_ + 1;
2624 difference_type __bs = __le - __lb;
2625 if (__bs > __n)
2626 {
2627 __bs = __n;
2628 __lb = __le - __bs;
2629 }
2630 if (__lb <= __vt && __vt < __le)
Howard Hinnantdcb73a32013-06-23 21:17:24 +00002631 __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) += __r - __l - 1).__ptr_;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002632 __r = _VSTD::move_backward(__lb, __le, __r);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002633 __n -= __bs;
2634 __l -= __bs - 1;
2635 }
2636 return __r;
2637}
2638
2639// move construct [__f, __l) to [__r, __r + (__l-__f)).
2640// If __vt points into [__f, __l), then add (__r - __f) to __vt.
2641template <class _Tp, class _Allocator>
2642void
2643deque<_Tp, _Allocator>::__move_construct_and_check(iterator __f, iterator __l,
2644 iterator __r, const_pointer& __vt)
2645{
2646 allocator_type& __a = __base::__alloc();
2647 // as if
2648 // for (; __f != __l; ++__r, ++__f, ++__base::size())
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002649 // __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__f));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002650 difference_type __n = __l - __f;
2651 while (__n > 0)
2652 {
2653 pointer __fb = __f.__ptr_;
2654 pointer __fe = *__f.__m_iter_ + __base::__block_size;
2655 difference_type __bs = __fe - __fb;
2656 if (__bs > __n)
2657 {
2658 __bs = __n;
2659 __fe = __fb + __bs;
2660 }
2661 if (__fb <= __vt && __vt < __fe)
Howard Hinnantdcb73a32013-06-23 21:17:24 +00002662 __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) += __r - __f).__ptr_;
Howard Hinnantc51e1022010-05-11 19:42:16 +00002663 for (; __fb != __fe; ++__fb, ++__r, ++__base::size())
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002664 __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__fb));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002665 __n -= __bs;
2666 __f += __bs;
2667 }
2668}
2669
2670// move construct [__f, __l) to [__r - (__l-__f), __r) backwards.
2671// If __vt points into [__f, __l), then subtract (__l - __r) from __vt.
2672template <class _Tp, class _Allocator>
2673void
2674deque<_Tp, _Allocator>::__move_construct_backward_and_check(iterator __f, iterator __l,
2675 iterator __r, const_pointer& __vt)
2676{
2677 allocator_type& __a = __base::__alloc();
2678 // as if
2679 // for (iterator __j = __l; __j != __f;)
2680 // {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002681 // __alloc_traitsconstruct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__j));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002682 // --__base::__start_;
2683 // ++__base::size();
2684 // }
2685 difference_type __n = __l - __f;
2686 while (__n > 0)
2687 {
2688 --__l;
2689 pointer __lb = *__l.__m_iter_;
2690 pointer __le = __l.__ptr_ + 1;
2691 difference_type __bs = __le - __lb;
2692 if (__bs > __n)
2693 {
2694 __bs = __n;
2695 __lb = __le - __bs;
2696 }
2697 if (__lb <= __vt && __vt < __le)
Howard Hinnantdcb73a32013-06-23 21:17:24 +00002698 __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) -= __l - __r + 1).__ptr_;
Howard Hinnantc51e1022010-05-11 19:42:16 +00002699 while (__le != __lb)
2700 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002701 __alloc_traits::construct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__le));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002702 --__base::__start_;
2703 ++__base::size();
2704 }
2705 __n -= __bs;
2706 __l -= __bs - 1;
2707 }
2708}
2709
2710template <class _Tp, class _Allocator>
2711typename deque<_Tp, _Allocator>::iterator
2712deque<_Tp, _Allocator>::erase(const_iterator __f)
2713{
Howard Hinnantc51e1022010-05-11 19:42:16 +00002714 iterator __b = __base::begin();
2715 difference_type __pos = __f - __b;
2716 iterator __p = __b + __pos;
2717 allocator_type& __a = __base::__alloc();
Marshall Clowe7e39922015-06-05 22:34:19 +00002718 if (__pos <= (__base::size() - 1) / 2)
Howard Hinnantc51e1022010-05-11 19:42:16 +00002719 { // erase from front
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002720 _VSTD::move_backward(__b, __p, _VSTD::next(__p));
2721 __alloc_traits::destroy(__a, _VSTD::addressof(*__b));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002722 --__base::size();
2723 ++__base::__start_;
2724 if (__front_spare() >= 2 * __base::__block_size)
2725 {
2726 __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
2727 __base::__map_.pop_front();
2728 __base::__start_ -= __base::__block_size;
2729 }
2730 }
2731 else
2732 { // erase from back
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002733 iterator __i = _VSTD::move(_VSTD::next(__p), __base::end(), __p);
2734 __alloc_traits::destroy(__a, _VSTD::addressof(*__i));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002735 --__base::size();
2736 if (__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 return __base::begin() + __pos;
2743}
2744
2745template <class _Tp, class _Allocator>
2746typename deque<_Tp, _Allocator>::iterator
2747deque<_Tp, _Allocator>::erase(const_iterator __f, const_iterator __l)
2748{
2749 difference_type __n = __l - __f;
2750 iterator __b = __base::begin();
2751 difference_type __pos = __f - __b;
2752 iterator __p = __b + __pos;
2753 if (__n > 0)
2754 {
2755 allocator_type& __a = __base::__alloc();
Marshall Clowe7e39922015-06-05 22:34:19 +00002756 if (__pos <= (__base::size() - __n) / 2)
Howard Hinnantc51e1022010-05-11 19:42:16 +00002757 { // erase from front
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002758 iterator __i = _VSTD::move_backward(__b, __p, __p + __n);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002759 for (; __b != __i; ++__b)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002760 __alloc_traits::destroy(__a, _VSTD::addressof(*__b));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002761 __base::size() -= __n;
2762 __base::__start_ += __n;
2763 while (__front_spare() >= 2 * __base::__block_size)
2764 {
2765 __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
2766 __base::__map_.pop_front();
2767 __base::__start_ -= __base::__block_size;
2768 }
2769 }
2770 else
2771 { // erase from back
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002772 iterator __i = _VSTD::move(__p + __n, __base::end(), __p);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002773 for (iterator __e = __base::end(); __i != __e; ++__i)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002774 __alloc_traits::destroy(__a, _VSTD::addressof(*__i));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002775 __base::size() -= __n;
2776 while (__back_spare() >= 2 * __base::__block_size)
2777 {
2778 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
2779 __base::__map_.pop_back();
2780 }
2781 }
2782 }
2783 return __base::begin() + __pos;
2784}
2785
2786template <class _Tp, class _Allocator>
2787void
2788deque<_Tp, _Allocator>::__erase_to_end(const_iterator __f)
2789{
2790 iterator __e = __base::end();
2791 difference_type __n = __e - __f;
2792 if (__n > 0)
2793 {
2794 allocator_type& __a = __base::__alloc();
2795 iterator __b = __base::begin();
2796 difference_type __pos = __f - __b;
2797 for (iterator __p = __b + __pos; __p != __e; ++__p)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002798 __alloc_traits::destroy(__a, _VSTD::addressof(*__p));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002799 __base::size() -= __n;
2800 while (__back_spare() >= 2 * __base::__block_size)
2801 {
2802 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
2803 __base::__map_.pop_back();
2804 }
2805 }
2806}
2807
2808template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00002809inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002810void
2811deque<_Tp, _Allocator>::swap(deque& __c)
Marshall Clow8982dcd2015-07-13 20:04:56 +00002812#if _LIBCPP_STD_VER >= 14
2813 _NOEXCEPT
2814#else
2815 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
2816 __is_nothrow_swappable<allocator_type>::value)
2817#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00002818{
2819 __base::swap(__c);
2820}
2821
2822template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00002823inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002824void
Howard Hinnantda2df912011-06-02 16:10:22 +00002825deque<_Tp, _Allocator>::clear() _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00002826{
2827 __base::clear();
2828}
2829
2830template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00002831inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002832bool
2833operator==(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2834{
2835 const typename deque<_Tp, _Allocator>::size_type __sz = __x.size();
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002836 return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantc51e1022010-05-11 19:42:16 +00002837}
2838
2839template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00002840inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002841bool
2842operator!=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2843{
2844 return !(__x == __y);
2845}
2846
2847template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00002848inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002849bool
2850operator< (const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2851{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002852 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00002853}
2854
2855template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00002856inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002857bool
2858operator> (const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2859{
2860 return __y < __x;
2861}
2862
2863template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00002864inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002865bool
2866operator>=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2867{
2868 return !(__x < __y);
2869}
2870
2871template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00002872inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002873bool
2874operator<=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2875{
2876 return !(__y < __x);
2877}
2878
2879template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00002880inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002881void
2882swap(deque<_Tp, _Allocator>& __x, deque<_Tp, _Allocator>& __y)
Howard Hinnantca2fc222011-06-02 20:00:14 +00002883 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantc51e1022010-05-11 19:42:16 +00002884{
2885 __x.swap(__y);
2886}
2887
2888_LIBCPP_END_NAMESPACE_STD
2889
2890#endif // _LIBCPP_DEQUE