blob: 5e152e425d0bb0ba56511df76020a376df71e337 [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
264template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,
265 class _DiffType, _DiffType _BlockSize>
Howard Hinnanta37d3cf2013-08-12 18:38:34 +0000266class _LIBCPP_TYPE_VIS_ONLY __deque_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000267{
268 typedef _MapPointer __map_iterator;
269public:
270 typedef _Pointer pointer;
271 typedef _DiffType difference_type;
272private:
273 __map_iterator __m_iter_;
274 pointer __ptr_;
275
276 static const difference_type __block_size = _BlockSize;
277public:
278 typedef _ValueType value_type;
279 typedef random_access_iterator_tag iterator_category;
280 typedef _Reference reference;
281
Marshall Clow7a3a61d2013-08-06 16:14:36 +0000282 _LIBCPP_INLINE_VISIBILITY __deque_iterator() _NOEXCEPT
283#if _LIBCPP_STD_VER > 11
284 : __m_iter_(nullptr), __ptr_(nullptr)
285#endif
286 {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000287
Howard Hinnantc834c512011-11-29 18:15:50 +0000288 template <class _Pp, class _Rp, class _MP>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000289 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +0000290 __deque_iterator(const __deque_iterator<value_type, _Pp, _Rp, _MP, difference_type, __block_size>& __it,
291 typename enable_if<is_convertible<_Pp, pointer>::value>::type* = 0) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000292 : __m_iter_(__it.__m_iter_), __ptr_(__it.__ptr_) {}
293
294 _LIBCPP_INLINE_VISIBILITY reference operator*() const {return *__ptr_;}
295 _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return __ptr_;}
296
297 _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator++()
298 {
299 if (++__ptr_ - *__m_iter_ == __block_size)
300 {
301 ++__m_iter_;
302 __ptr_ = *__m_iter_;
303 }
304 return *this;
305 }
306
307 _LIBCPP_INLINE_VISIBILITY __deque_iterator operator++(int)
308 {
309 __deque_iterator __tmp = *this;
310 ++(*this);
311 return __tmp;
312 }
313
314 _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator--()
315 {
316 if (__ptr_ == *__m_iter_)
317 {
318 --__m_iter_;
319 __ptr_ = *__m_iter_ + __block_size;
320 }
321 --__ptr_;
322 return *this;
323 }
324
325 _LIBCPP_INLINE_VISIBILITY __deque_iterator operator--(int)
326 {
327 __deque_iterator __tmp = *this;
328 --(*this);
329 return __tmp;
330 }
331
332 _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator+=(difference_type __n)
333 {
334 if (__n != 0)
335 {
336 __n += __ptr_ - *__m_iter_;
337 if (__n > 0)
338 {
339 __m_iter_ += __n / __block_size;
340 __ptr_ = *__m_iter_ + __n % __block_size;
341 }
342 else // (__n < 0)
343 {
344 difference_type __z = __block_size - 1 - __n;
345 __m_iter_ -= __z / __block_size;
346 __ptr_ = *__m_iter_ + (__block_size - 1 - __z % __block_size);
347 }
348 }
349 return *this;
350 }
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000351
Howard Hinnantc51e1022010-05-11 19:42:16 +0000352 _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator-=(difference_type __n)
353 {
354 return *this += -__n;
355 }
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000356
Howard Hinnantc51e1022010-05-11 19:42:16 +0000357 _LIBCPP_INLINE_VISIBILITY __deque_iterator operator+(difference_type __n) const
358 {
359 __deque_iterator __t(*this);
360 __t += __n;
361 return __t;
362 }
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000363
Howard Hinnantc51e1022010-05-11 19:42:16 +0000364 _LIBCPP_INLINE_VISIBILITY __deque_iterator operator-(difference_type __n) const
365 {
366 __deque_iterator __t(*this);
367 __t -= __n;
368 return __t;
369 }
370
371 _LIBCPP_INLINE_VISIBILITY
372 friend __deque_iterator operator+(difference_type __n, const __deque_iterator& __it)
373 {return __it + __n;}
374
375 _LIBCPP_INLINE_VISIBILITY
376 friend difference_type operator-(const __deque_iterator& __x, const __deque_iterator& __y)
377 {
378 if (__x != __y)
379 return (__x.__m_iter_ - __y.__m_iter_) * __block_size
380 + (__x.__ptr_ - *__x.__m_iter_)
381 - (__y.__ptr_ - *__y.__m_iter_);
382 return 0;
383 }
384
385 _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const
386 {return *(*this + __n);}
387
388 _LIBCPP_INLINE_VISIBILITY friend
389 bool operator==(const __deque_iterator& __x, const __deque_iterator& __y)
390 {return __x.__ptr_ == __y.__ptr_;}
391
392 _LIBCPP_INLINE_VISIBILITY friend
393 bool operator!=(const __deque_iterator& __x, const __deque_iterator& __y)
394 {return !(__x == __y);}
395
396 _LIBCPP_INLINE_VISIBILITY friend
397 bool operator<(const __deque_iterator& __x, const __deque_iterator& __y)
398 {return __x.__m_iter_ < __y.__m_iter_ ||
399 (__x.__m_iter_ == __y.__m_iter_ && __x.__ptr_ < __y.__ptr_);}
400
401 _LIBCPP_INLINE_VISIBILITY friend
402 bool operator>(const __deque_iterator& __x, const __deque_iterator& __y)
403 {return __y < __x;}
404
405 _LIBCPP_INLINE_VISIBILITY friend
406 bool operator<=(const __deque_iterator& __x, const __deque_iterator& __y)
407 {return !(__y < __x);}
408
409 _LIBCPP_INLINE_VISIBILITY friend
410 bool operator>=(const __deque_iterator& __x, const __deque_iterator& __y)
411 {return !(__x < __y);}
412
413private:
Howard Hinnantda2df912011-06-02 16:10:22 +0000414 _LIBCPP_INLINE_VISIBILITY __deque_iterator(__map_iterator __m, pointer __p) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000415 : __m_iter_(__m), __ptr_(__p) {}
416
Howard Hinnantc834c512011-11-29 18:15:50 +0000417 template <class _Tp, class _Ap> friend class __deque_base;
Howard Hinnanta37d3cf2013-08-12 18:38:34 +0000418 template <class _Tp, class _Ap> friend class _LIBCPP_TYPE_VIS_ONLY deque;
Howard Hinnantc834c512011-11-29 18:15:50 +0000419 template <class _Vp, class _Pp, class _Rp, class _MP, class _Dp, _Dp>
Howard Hinnanta37d3cf2013-08-12 18:38:34 +0000420 friend class _LIBCPP_TYPE_VIS_ONLY __deque_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000421
422 template <class _RAIter,
423 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
424 friend
425 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
426 copy(_RAIter __f,
427 _RAIter __l,
428 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
429 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*);
430
431 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
432 class _OutputIterator>
433 friend
434 _OutputIterator
435 copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
436 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
437 _OutputIterator __r);
438
439 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
440 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
441 friend
442 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
443 copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
444 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
445 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
446
447 template <class _RAIter,
448 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
449 friend
450 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
451 copy_backward(_RAIter __f,
452 _RAIter __l,
453 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
454 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*);
455
456 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
457 class _OutputIterator>
458 friend
459 _OutputIterator
460 copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
461 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
462 _OutputIterator __r);
463
464 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
465 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
466 friend
467 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
468 copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
469 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
470 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
471
472 template <class _RAIter,
473 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
474 friend
475 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
476 move(_RAIter __f,
477 _RAIter __l,
478 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
479 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*);
480
481 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
482 class _OutputIterator>
483 friend
484 _OutputIterator
485 move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
486 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
487 _OutputIterator __r);
488
489 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
490 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
491 friend
492 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
493 move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
494 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
495 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
496
497 template <class _RAIter,
498 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
499 friend
500 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
501 move_backward(_RAIter __f,
502 _RAIter __l,
503 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
504 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*);
505
506 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
507 class _OutputIterator>
508 friend
509 _OutputIterator
510 move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
511 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
512 _OutputIterator __r);
513
514 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
515 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
516 friend
517 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
518 move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
519 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
520 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
521};
522
523// copy
524
525template <class _RAIter,
526 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
527__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
528copy(_RAIter __f,
529 _RAIter __l,
530 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
531 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)
532{
533 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;
534 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;
535 while (__f != __l)
536 {
537 pointer __rb = __r.__ptr_;
538 pointer __re = *__r.__m_iter_ + _B2;
539 difference_type __bs = __re - __rb;
540 difference_type __n = __l - __f;
541 _RAIter __m = __l;
542 if (__n > __bs)
543 {
544 __n = __bs;
545 __m = __f + __n;
546 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000547 _VSTD::copy(__f, __m, __rb);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000548 __f = __m;
549 __r += __n;
550 }
551 return __r;
552}
553
554template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
555 class _OutputIterator>
556_OutputIterator
557copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
558 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
559 _OutputIterator __r)
560{
561 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
562 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
563 difference_type __n = __l - __f;
564 while (__n > 0)
565 {
566 pointer __fb = __f.__ptr_;
567 pointer __fe = *__f.__m_iter_ + _B1;
568 difference_type __bs = __fe - __fb;
569 if (__bs > __n)
570 {
571 __bs = __n;
572 __fe = __fb + __bs;
573 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000574 __r = _VSTD::copy(__fb, __fe, __r);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000575 __n -= __bs;
576 __f += __bs;
577 }
578 return __r;
579}
580
581template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
582 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
583__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
584copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
585 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
586 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)
587{
588 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
589 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
590 difference_type __n = __l - __f;
591 while (__n > 0)
592 {
593 pointer __fb = __f.__ptr_;
594 pointer __fe = *__f.__m_iter_ + _B1;
595 difference_type __bs = __fe - __fb;
596 if (__bs > __n)
597 {
598 __bs = __n;
599 __fe = __fb + __bs;
600 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000601 __r = _VSTD::copy(__fb, __fe, __r);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000602 __n -= __bs;
603 __f += __bs;
604 }
605 return __r;
606}
607
608// copy_backward
609
610template <class _RAIter,
611 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
612__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
613copy_backward(_RAIter __f,
614 _RAIter __l,
615 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
616 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)
617{
618 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;
619 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;
620 while (__f != __l)
621 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000622 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __rp = _VSTD::prev(__r);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000623 pointer __rb = *__rp.__m_iter_;
624 pointer __re = __rp.__ptr_ + 1;
625 difference_type __bs = __re - __rb;
626 difference_type __n = __l - __f;
627 _RAIter __m = __f;
628 if (__n > __bs)
629 {
630 __n = __bs;
631 __m = __l - __n;
632 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000633 _VSTD::copy_backward(__m, __l, __re);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000634 __l = __m;
635 __r -= __n;
636 }
637 return __r;
638}
639
640template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
641 class _OutputIterator>
642_OutputIterator
643copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
644 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
645 _OutputIterator __r)
646{
647 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
648 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
649 difference_type __n = __l - __f;
650 while (__n > 0)
651 {
652 --__l;
653 pointer __lb = *__l.__m_iter_;
654 pointer __le = __l.__ptr_ + 1;
655 difference_type __bs = __le - __lb;
656 if (__bs > __n)
657 {
658 __bs = __n;
659 __lb = __le - __bs;
660 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000661 __r = _VSTD::copy_backward(__lb, __le, __r);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000662 __n -= __bs;
663 __l -= __bs - 1;
664 }
665 return __r;
666}
667
668template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
669 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
670__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
671copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
672 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
673 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)
674{
675 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
676 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
677 difference_type __n = __l - __f;
678 while (__n > 0)
679 {
680 --__l;
681 pointer __lb = *__l.__m_iter_;
682 pointer __le = __l.__ptr_ + 1;
683 difference_type __bs = __le - __lb;
684 if (__bs > __n)
685 {
686 __bs = __n;
687 __lb = __le - __bs;
688 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000689 __r = _VSTD::copy_backward(__lb, __le, __r);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000690 __n -= __bs;
691 __l -= __bs - 1;
692 }
693 return __r;
694}
695
696// move
697
698template <class _RAIter,
699 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
700__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
701move(_RAIter __f,
702 _RAIter __l,
703 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
704 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)
705{
706 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;
707 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;
708 while (__f != __l)
709 {
710 pointer __rb = __r.__ptr_;
711 pointer __re = *__r.__m_iter_ + _B2;
712 difference_type __bs = __re - __rb;
713 difference_type __n = __l - __f;
714 _RAIter __m = __l;
715 if (__n > __bs)
716 {
717 __n = __bs;
718 __m = __f + __n;
719 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000720 _VSTD::move(__f, __m, __rb);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000721 __f = __m;
722 __r += __n;
723 }
724 return __r;
725}
726
727template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
728 class _OutputIterator>
729_OutputIterator
730move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
731 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
732 _OutputIterator __r)
733{
734 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
735 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
736 difference_type __n = __l - __f;
737 while (__n > 0)
738 {
739 pointer __fb = __f.__ptr_;
740 pointer __fe = *__f.__m_iter_ + _B1;
741 difference_type __bs = __fe - __fb;
742 if (__bs > __n)
743 {
744 __bs = __n;
745 __fe = __fb + __bs;
746 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000747 __r = _VSTD::move(__fb, __fe, __r);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000748 __n -= __bs;
749 __f += __bs;
750 }
751 return __r;
752}
753
754template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
755 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
756__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
757move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
758 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
759 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)
760{
761 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
762 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
763 difference_type __n = __l - __f;
764 while (__n > 0)
765 {
766 pointer __fb = __f.__ptr_;
767 pointer __fe = *__f.__m_iter_ + _B1;
768 difference_type __bs = __fe - __fb;
769 if (__bs > __n)
770 {
771 __bs = __n;
772 __fe = __fb + __bs;
773 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000774 __r = _VSTD::move(__fb, __fe, __r);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000775 __n -= __bs;
776 __f += __bs;
777 }
778 return __r;
779}
780
781// move_backward
782
783template <class _RAIter,
784 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
785__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
786move_backward(_RAIter __f,
787 _RAIter __l,
788 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
789 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)
790{
791 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;
792 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;
793 while (__f != __l)
794 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000795 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __rp = _VSTD::prev(__r);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000796 pointer __rb = *__rp.__m_iter_;
797 pointer __re = __rp.__ptr_ + 1;
798 difference_type __bs = __re - __rb;
799 difference_type __n = __l - __f;
800 _RAIter __m = __f;
801 if (__n > __bs)
802 {
803 __n = __bs;
804 __m = __l - __n;
805 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000806 _VSTD::move_backward(__m, __l, __re);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000807 __l = __m;
808 __r -= __n;
809 }
810 return __r;
811}
812
813template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
814 class _OutputIterator>
815_OutputIterator
816move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
817 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
818 _OutputIterator __r)
819{
820 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
821 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
822 difference_type __n = __l - __f;
823 while (__n > 0)
824 {
825 --__l;
826 pointer __lb = *__l.__m_iter_;
827 pointer __le = __l.__ptr_ + 1;
828 difference_type __bs = __le - __lb;
829 if (__bs > __n)
830 {
831 __bs = __n;
832 __lb = __le - __bs;
833 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000834 __r = _VSTD::move_backward(__lb, __le, __r);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000835 __n -= __bs;
836 __l -= __bs - 1;
837 }
838 return __r;
839}
840
841template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
842 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
843__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
844move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
845 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
846 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)
847{
848 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
849 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
850 difference_type __n = __l - __f;
851 while (__n > 0)
852 {
853 --__l;
854 pointer __lb = *__l.__m_iter_;
855 pointer __le = __l.__ptr_ + 1;
856 difference_type __bs = __le - __lb;
857 if (__bs > __n)
858 {
859 __bs = __n;
860 __lb = __le - __bs;
861 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000862 __r = _VSTD::move_backward(__lb, __le, __r);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000863 __n -= __bs;
864 __l -= __bs - 1;
865 }
866 return __r;
867}
868
869template <bool>
870class __deque_base_common
871{
872protected:
873 void __throw_length_error() const;
874 void __throw_out_of_range() const;
875};
876
877template <bool __b>
878void
879__deque_base_common<__b>::__throw_length_error() const
880{
881#ifndef _LIBCPP_NO_EXCEPTIONS
882 throw length_error("deque");
883#endif
884}
885
886template <bool __b>
887void
888__deque_base_common<__b>::__throw_out_of_range() const
889{
890#ifndef _LIBCPP_NO_EXCEPTIONS
891 throw out_of_range("deque");
892#endif
893}
894
895template <class _Tp, class _Allocator>
896class __deque_base
897 : protected __deque_base_common<true>
898{
899 __deque_base(const __deque_base& __c);
900 __deque_base& operator=(const __deque_base& __c);
901protected:
902 typedef _Tp value_type;
903 typedef _Allocator allocator_type;
904 typedef allocator_traits<allocator_type> __alloc_traits;
905 typedef value_type& reference;
906 typedef const value_type& const_reference;
907 typedef typename __alloc_traits::size_type size_type;
908 typedef typename __alloc_traits::difference_type difference_type;
909 typedef typename __alloc_traits::pointer pointer;
910 typedef typename __alloc_traits::const_pointer const_pointer;
911
912 static const difference_type __block_size = sizeof(value_type) < 256 ? 4096 / sizeof(value_type) : 16;
913
Marshall Clow940e01c2015-04-07 05:21:38 +0000914 typedef typename __rebind_alloc_helper<__alloc_traits, pointer>::type __pointer_allocator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000915 typedef allocator_traits<__pointer_allocator> __map_traits;
916 typedef typename __map_traits::pointer __map_pointer;
Marshall Clow940e01c2015-04-07 05:21:38 +0000917 typedef typename __rebind_alloc_helper<__alloc_traits, const_pointer>::type __const_pointer_allocator;
Howard Hinnantdcb73a32013-06-23 21:17:24 +0000918 typedef typename allocator_traits<__const_pointer_allocator>::const_pointer __map_const_pointer;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000919 typedef __split_buffer<pointer, __pointer_allocator> __map;
920
921 typedef __deque_iterator<value_type, pointer, reference, __map_pointer,
922 difference_type, __block_size> iterator;
923 typedef __deque_iterator<value_type, const_pointer, const_reference, __map_const_pointer,
924 difference_type, __block_size> const_iterator;
925
926 __map __map_;
927 size_type __start_;
928 __compressed_pair<size_type, allocator_type> __size_;
929
Howard Hinnantda2df912011-06-02 16:10:22 +0000930 iterator begin() _NOEXCEPT;
931 const_iterator begin() const _NOEXCEPT;
932 iterator end() _NOEXCEPT;
933 const_iterator end() const _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000934
935 _LIBCPP_INLINE_VISIBILITY size_type& size() {return __size_.first();}
Howard Hinnantda2df912011-06-02 16:10:22 +0000936 _LIBCPP_INLINE_VISIBILITY
937 const size_type& size() const _NOEXCEPT {return __size_.first();}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000938 _LIBCPP_INLINE_VISIBILITY allocator_type& __alloc() {return __size_.second();}
Howard Hinnantda2df912011-06-02 16:10:22 +0000939 _LIBCPP_INLINE_VISIBILITY
940 const allocator_type& __alloc() const _NOEXCEPT {return __size_.second();}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000941
Howard Hinnantad979ba2011-06-03 15:16:49 +0000942 __deque_base()
943 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000944 explicit __deque_base(const allocator_type& __a);
Howard Hinnantca2fc222011-06-02 20:00:14 +0000945public:
Howard Hinnantc51e1022010-05-11 19:42:16 +0000946 ~__deque_base();
947
Howard Hinnant74279a52010-09-04 23:28:19 +0000948#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +0000949
Howard Hinnantca2fc222011-06-02 20:00:14 +0000950 __deque_base(__deque_base&& __c)
951 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000952 __deque_base(__deque_base&& __c, const allocator_type& __a);
953
Howard Hinnant74279a52010-09-04 23:28:19 +0000954#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantca2fc222011-06-02 20:00:14 +0000955 void swap(__deque_base& __c)
Marshall Clow8982dcd2015-07-13 20:04:56 +0000956#if _LIBCPP_STD_VER >= 14
957 _NOEXCEPT;
958#else
959 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
960 __is_nothrow_swappable<allocator_type>::value);
961#endif
Howard Hinnantca2fc222011-06-02 20:00:14 +0000962protected:
Howard Hinnantda2df912011-06-02 16:10:22 +0000963 void clear() _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000964
965 bool __invariants() const;
966
Howard Hinnant874ad9a2010-09-21 21:28:23 +0000967 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000968 void __move_assign(__deque_base& __c)
Howard Hinnant4931e092011-06-02 21:38:57 +0000969 _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&
970 is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000971 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000972 __map_ = _VSTD::move(__c.__map_);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000973 __start_ = __c.__start_;
974 size() = __c.size();
975 __move_assign_alloc(__c);
976 __c.__start_ = __c.size() = 0;
977 }
978
Howard Hinnant874ad9a2010-09-21 21:28:23 +0000979 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000980 void __move_assign_alloc(__deque_base& __c)
Howard Hinnantca2fc222011-06-02 20:00:14 +0000981 _NOEXCEPT_(!__alloc_traits::propagate_on_container_move_assignment::value ||
982 is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000983 {__move_assign_alloc(__c, integral_constant<bool,
984 __alloc_traits::propagate_on_container_move_assignment::value>());}
985
986private:
Howard Hinnant874ad9a2010-09-21 21:28:23 +0000987 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc2734962011-09-02 20:42:31 +0000988 void __move_assign_alloc(__deque_base& __c, true_type)
Howard Hinnantca2fc222011-06-02 20:00:14 +0000989 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000990 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000991 __alloc() = _VSTD::move(__c.__alloc());
Howard Hinnantc51e1022010-05-11 19:42:16 +0000992 }
993
Howard Hinnant874ad9a2010-09-21 21:28:23 +0000994 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant28b24882011-12-01 20:21:04 +0000995 void __move_assign_alloc(__deque_base&, false_type) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000996 {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000997};
998
999template <class _Tp, class _Allocator>
1000bool
1001__deque_base<_Tp, _Allocator>::__invariants() const
1002{
1003 if (!__map_.__invariants())
1004 return false;
1005 if (__map_.size() >= size_type(-1) / __block_size)
1006 return false;
1007 for (typename __map::const_iterator __i = __map_.begin(), __e = __map_.end();
1008 __i != __e; ++__i)
1009 if (*__i == nullptr)
1010 return false;
1011 if (__map_.size() != 0)
1012 {
1013 if (size() >= __map_.size() * __block_size)
1014 return false;
1015 if (__start_ >= __map_.size() * __block_size - size())
1016 return false;
1017 }
1018 else
1019 {
1020 if (size() != 0)
1021 return false;
1022 if (__start_ != 0)
1023 return false;
1024 }
1025 return true;
1026}
1027
1028template <class _Tp, class _Allocator>
1029typename __deque_base<_Tp, _Allocator>::iterator
Howard Hinnantda2df912011-06-02 16:10:22 +00001030__deque_base<_Tp, _Allocator>::begin() _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001031{
1032 __map_pointer __mp = __map_.begin() + __start_ / __block_size;
1033 return iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size);
1034}
1035
1036template <class _Tp, class _Allocator>
1037typename __deque_base<_Tp, _Allocator>::const_iterator
Howard Hinnantda2df912011-06-02 16:10:22 +00001038__deque_base<_Tp, _Allocator>::begin() const _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001039{
Howard Hinnantdcb73a32013-06-23 21:17:24 +00001040 __map_const_pointer __mp = static_cast<__map_const_pointer>(__map_.begin() + __start_ / __block_size);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001041 return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size);
1042}
1043
1044template <class _Tp, class _Allocator>
1045typename __deque_base<_Tp, _Allocator>::iterator
Howard Hinnantda2df912011-06-02 16:10:22 +00001046__deque_base<_Tp, _Allocator>::end() _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001047{
1048 size_type __p = size() + __start_;
1049 __map_pointer __mp = __map_.begin() + __p / __block_size;
1050 return iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size);
1051}
1052
1053template <class _Tp, class _Allocator>
1054typename __deque_base<_Tp, _Allocator>::const_iterator
Howard Hinnantda2df912011-06-02 16:10:22 +00001055__deque_base<_Tp, _Allocator>::end() const _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001056{
1057 size_type __p = size() + __start_;
Howard Hinnantdcb73a32013-06-23 21:17:24 +00001058 __map_const_pointer __mp = static_cast<__map_const_pointer>(__map_.begin() + __p / __block_size);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001059 return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size);
1060}
1061
1062template <class _Tp, class _Allocator>
1063inline _LIBCPP_INLINE_VISIBILITY
1064__deque_base<_Tp, _Allocator>::__deque_base()
Howard Hinnantad979ba2011-06-03 15:16:49 +00001065 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001066 : __start_(0), __size_(0) {}
1067
1068template <class _Tp, class _Allocator>
1069inline _LIBCPP_INLINE_VISIBILITY
1070__deque_base<_Tp, _Allocator>::__deque_base(const allocator_type& __a)
1071 : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a) {}
1072
1073template <class _Tp, class _Allocator>
1074__deque_base<_Tp, _Allocator>::~__deque_base()
1075{
1076 clear();
1077 typename __map::iterator __i = __map_.begin();
1078 typename __map::iterator __e = __map_.end();
1079 for (; __i != __e; ++__i)
1080 __alloc_traits::deallocate(__alloc(), *__i, __block_size);
1081}
1082
Howard Hinnant74279a52010-09-04 23:28:19 +00001083#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001084
1085template <class _Tp, class _Allocator>
1086__deque_base<_Tp, _Allocator>::__deque_base(__deque_base&& __c)
Howard Hinnantca2fc222011-06-02 20:00:14 +00001087 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001088 : __map_(_VSTD::move(__c.__map_)),
1089 __start_(_VSTD::move(__c.__start_)),
1090 __size_(_VSTD::move(__c.__size_))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001091{
1092 __c.__start_ = 0;
1093 __c.size() = 0;
1094}
1095
1096template <class _Tp, class _Allocator>
1097__deque_base<_Tp, _Allocator>::__deque_base(__deque_base&& __c, const allocator_type& __a)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001098 : __map_(_VSTD::move(__c.__map_), __pointer_allocator(__a)),
1099 __start_(_VSTD::move(__c.__start_)),
1100 __size_(_VSTD::move(__c.size()), __a)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001101{
1102 if (__a == __c.__alloc())
1103 {
1104 __c.__start_ = 0;
1105 __c.size() = 0;
1106 }
1107 else
1108 {
1109 __map_.clear();
1110 __start_ = 0;
1111 size() = 0;
1112 }
1113}
1114
Howard Hinnant74279a52010-09-04 23:28:19 +00001115#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001116
1117template <class _Tp, class _Allocator>
1118void
1119__deque_base<_Tp, _Allocator>::swap(__deque_base& __c)
Marshall Clow8982dcd2015-07-13 20:04:56 +00001120#if _LIBCPP_STD_VER >= 14
1121 _NOEXCEPT
1122#else
1123 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
1124 __is_nothrow_swappable<allocator_type>::value)
1125#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001126{
1127 __map_.swap(__c.__map_);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001128 _VSTD::swap(__start_, __c.__start_);
1129 _VSTD::swap(size(), __c.size());
Marshall Clow8982dcd2015-07-13 20:04:56 +00001130 __swap_allocator(__alloc(), __c.__alloc());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001131}
1132
1133template <class _Tp, class _Allocator>
1134void
Howard Hinnantda2df912011-06-02 16:10:22 +00001135__deque_base<_Tp, _Allocator>::clear() _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001136{
1137 allocator_type& __a = __alloc();
1138 for (iterator __i = begin(), __e = end(); __i != __e; ++__i)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001139 __alloc_traits::destroy(__a, _VSTD::addressof(*__i));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001140 size() = 0;
1141 while (__map_.size() > 2)
1142 {
1143 __alloc_traits::deallocate(__a, __map_.front(), __block_size);
1144 __map_.pop_front();
1145 }
1146 switch (__map_.size())
1147 {
1148 case 1:
1149 __start_ = __block_size / 2;
1150 break;
1151 case 2:
1152 __start_ = __block_size;
1153 break;
1154 }
1155}
1156
Marshall Clow65cd4c62015-02-18 17:24:08 +00001157template <class _Tp, class _Allocator /*= allocator<_Tp>*/>
Howard Hinnanta37d3cf2013-08-12 18:38:34 +00001158class _LIBCPP_TYPE_VIS_ONLY deque
Howard Hinnantc51e1022010-05-11 19:42:16 +00001159 : private __deque_base<_Tp, _Allocator>
1160{
1161public:
1162 // types:
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001163
Howard Hinnantc51e1022010-05-11 19:42:16 +00001164 typedef _Tp value_type;
1165 typedef _Allocator allocator_type;
1166
1167 typedef __deque_base<value_type, allocator_type> __base;
1168
1169 typedef typename __base::__alloc_traits __alloc_traits;
1170 typedef typename __base::reference reference;
1171 typedef typename __base::const_reference const_reference;
1172 typedef typename __base::iterator iterator;
1173 typedef typename __base::const_iterator const_iterator;
1174 typedef typename __base::size_type size_type;
1175 typedef typename __base::difference_type difference_type;
1176
1177 typedef typename __base::pointer pointer;
1178 typedef typename __base::const_pointer const_pointer;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001179 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
1180 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001181
1182 // construct/copy/destroy:
Howard Hinnantad979ba2011-06-03 15:16:49 +00001183 _LIBCPP_INLINE_VISIBILITY
1184 deque()
1185 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
1186 {}
Marshall Clow7ed23a72014-03-05 19:06:20 +00001187 _LIBCPP_INLINE_VISIBILITY explicit deque(const allocator_type& __a) : __base(__a) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001188 explicit deque(size_type __n);
Marshall Clowbc4fcb42013-09-07 16:16:19 +00001189#if _LIBCPP_STD_VER > 11
1190 explicit deque(size_type __n, const _Allocator& __a);
1191#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001192 deque(size_type __n, const value_type& __v);
1193 deque(size_type __n, const value_type& __v, const allocator_type& __a);
1194 template <class _InputIter>
1195 deque(_InputIter __f, _InputIter __l,
1196 typename enable_if<__is_input_iterator<_InputIter>::value>::type* = 0);
1197 template <class _InputIter>
1198 deque(_InputIter __f, _InputIter __l, const allocator_type& __a,
1199 typename enable_if<__is_input_iterator<_InputIter>::value>::type* = 0);
1200 deque(const deque& __c);
1201 deque(const deque& __c, const allocator_type& __a);
Howard Hinnant33711792011-08-12 21:56:02 +00001202#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001203 deque(initializer_list<value_type> __il);
1204 deque(initializer_list<value_type> __il, const allocator_type& __a);
Howard Hinnant33711792011-08-12 21:56:02 +00001205#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001206
1207 deque& operator=(const deque& __c);
Howard Hinnant33711792011-08-12 21:56:02 +00001208#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001209 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001210 deque& operator=(initializer_list<value_type> __il) {assign(__il); return *this;}
Howard Hinnant33711792011-08-12 21:56:02 +00001211#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001212
Howard Hinnant74279a52010-09-04 23:28:19 +00001213#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantca2fc222011-06-02 20:00:14 +00001214 deque(deque&& __c) _NOEXCEPT_(is_nothrow_move_constructible<__base>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001215 deque(deque&& __c, const allocator_type& __a);
Howard Hinnantca2fc222011-06-02 20:00:14 +00001216 deque& operator=(deque&& __c)
Howard Hinnant4931e092011-06-02 21:38:57 +00001217 _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&
1218 is_nothrow_move_assignable<allocator_type>::value);
Howard Hinnant74279a52010-09-04 23:28:19 +00001219#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001220
1221 template <class _InputIter>
1222 void assign(_InputIter __f, _InputIter __l,
1223 typename enable_if<__is_input_iterator<_InputIter>::value &&
1224 !__is_random_access_iterator<_InputIter>::value>::type* = 0);
1225 template <class _RAIter>
1226 void assign(_RAIter __f, _RAIter __l,
1227 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0);
1228 void assign(size_type __n, const value_type& __v);
Howard Hinnant33711792011-08-12 21:56:02 +00001229#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001230 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001231 void assign(initializer_list<value_type> __il) {assign(__il.begin(), __il.end());}
Howard Hinnant33711792011-08-12 21:56:02 +00001232#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001233
Howard Hinnantda2df912011-06-02 16:10:22 +00001234 allocator_type get_allocator() const _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001235
1236 // iterators:
1237
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001238 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantda2df912011-06-02 16:10:22 +00001239 iterator begin() _NOEXCEPT {return __base::begin();}
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001240 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantda2df912011-06-02 16:10:22 +00001241 const_iterator begin() const _NOEXCEPT {return __base::begin();}
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001242 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantda2df912011-06-02 16:10:22 +00001243 iterator end() _NOEXCEPT {return __base::end();}
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001244 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantda2df912011-06-02 16:10:22 +00001245 const_iterator end() const _NOEXCEPT {return __base::end();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001246
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001247 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantda2df912011-06-02 16:10:22 +00001248 reverse_iterator rbegin() _NOEXCEPT
1249 {return reverse_iterator(__base::end());}
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001250 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantda2df912011-06-02 16:10:22 +00001251 const_reverse_iterator rbegin() const _NOEXCEPT
1252 {return const_reverse_iterator(__base::end());}
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001253 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantda2df912011-06-02 16:10:22 +00001254 reverse_iterator rend() _NOEXCEPT
1255 {return reverse_iterator(__base::begin());}
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001256 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantda2df912011-06-02 16:10:22 +00001257 const_reverse_iterator rend() const _NOEXCEPT
1258 {return const_reverse_iterator(__base::begin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001259
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001260 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantda2df912011-06-02 16:10:22 +00001261 const_iterator cbegin() const _NOEXCEPT
1262 {return __base::begin();}
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001263 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantda2df912011-06-02 16:10:22 +00001264 const_iterator cend() const _NOEXCEPT
1265 {return __base::end();}
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001266 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantda2df912011-06-02 16:10:22 +00001267 const_reverse_iterator crbegin() const _NOEXCEPT
1268 {return const_reverse_iterator(__base::end());}
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001269 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantda2df912011-06-02 16:10:22 +00001270 const_reverse_iterator crend() const _NOEXCEPT
1271 {return const_reverse_iterator(__base::begin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001272
1273 // capacity:
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001274 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantda2df912011-06-02 16:10:22 +00001275 size_type size() const _NOEXCEPT {return __base::size();}
1276 _LIBCPP_INLINE_VISIBILITY
1277 size_type max_size() const _NOEXCEPT
1278 {return __alloc_traits::max_size(__base::__alloc());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001279 void resize(size_type __n);
1280 void resize(size_type __n, const value_type& __v);
Howard Hinnant4931e092011-06-02 21:38:57 +00001281 void shrink_to_fit() _NOEXCEPT;
Howard Hinnantda2df912011-06-02 16:10:22 +00001282 _LIBCPP_INLINE_VISIBILITY
1283 bool empty() const _NOEXCEPT {return __base::size() == 0;}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001284
1285 // element access:
1286 reference operator[](size_type __i);
1287 const_reference operator[](size_type __i) const;
1288 reference at(size_type __i);
1289 const_reference at(size_type __i) const;
1290 reference front();
1291 const_reference front() const;
1292 reference back();
1293 const_reference back() const;
1294
1295 // 23.2.2.3 modifiers:
1296 void push_front(const value_type& __v);
1297 void push_back(const value_type& __v);
Howard Hinnant74279a52010-09-04 23:28:19 +00001298#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1299#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001300 template <class... _Args> void emplace_front(_Args&&... __args);
1301 template <class... _Args> void emplace_back(_Args&&... __args);
1302 template <class... _Args> iterator emplace(const_iterator __p, _Args&&... __args);
Howard Hinnant74279a52010-09-04 23:28:19 +00001303#endif // _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001304 void push_front(value_type&& __v);
1305 void push_back(value_type&& __v);
1306 iterator insert(const_iterator __p, value_type&& __v);
Howard Hinnant74279a52010-09-04 23:28:19 +00001307#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001308 iterator insert(const_iterator __p, const value_type& __v);
1309 iterator insert(const_iterator __p, size_type __n, const value_type& __v);
1310 template <class _InputIter>
Marshall Clow6b612cf2015-01-22 18:33:29 +00001311 iterator insert(const_iterator __p, _InputIter __f, _InputIter __l,
Howard Hinnantc51e1022010-05-11 19:42:16 +00001312 typename enable_if<__is_input_iterator<_InputIter>::value
Marshall Clow6b612cf2015-01-22 18:33:29 +00001313 &&!__is_forward_iterator<_InputIter>::value>::type* = 0);
1314 template <class _ForwardIterator>
1315 iterator insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l,
1316 typename enable_if<__is_forward_iterator<_ForwardIterator>::value
1317 &&!__is_bidirectional_iterator<_ForwardIterator>::value>::type* = 0);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001318 template <class _BiIter>
Marshall Clow6b612cf2015-01-22 18:33:29 +00001319 iterator insert(const_iterator __p, _BiIter __f, _BiIter __l,
Howard Hinnantc51e1022010-05-11 19:42:16 +00001320 typename enable_if<__is_bidirectional_iterator<_BiIter>::value>::type* = 0);
Howard Hinnant33711792011-08-12 21:56:02 +00001321#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001322 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001323 iterator insert(const_iterator __p, initializer_list<value_type> __il)
1324 {return insert(__p, __il.begin(), __il.end());}
Howard Hinnant33711792011-08-12 21:56:02 +00001325#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001326 void pop_front();
1327 void pop_back();
1328 iterator erase(const_iterator __p);
1329 iterator erase(const_iterator __f, const_iterator __l);
1330
Howard Hinnantca2fc222011-06-02 20:00:14 +00001331 void swap(deque& __c)
Marshall Clow8982dcd2015-07-13 20:04:56 +00001332#if _LIBCPP_STD_VER >= 14
1333 _NOEXCEPT;
1334#else
Howard Hinnantca2fc222011-06-02 20:00:14 +00001335 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
1336 __is_nothrow_swappable<allocator_type>::value);
Marshall Clow8982dcd2015-07-13 20:04:56 +00001337#endif
Howard Hinnantda2df912011-06-02 16:10:22 +00001338 void clear() _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001339
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001340 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001341 bool __invariants() const {return __base::__invariants();}
1342private:
Howard Hinnantdcb73a32013-06-23 21:17:24 +00001343 typedef typename __base::__map_const_pointer __map_const_pointer;
1344
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001345 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001346 static size_type __recommend_blocks(size_type __n)
1347 {
1348 return __n / __base::__block_size + (__n % __base::__block_size != 0);
1349 }
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001350 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001351 size_type __capacity() const
1352 {
1353 return __base::__map_.size() == 0 ? 0 : __base::__map_.size() * __base::__block_size - 1;
1354 }
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001355 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001356 size_type __front_spare() const
1357 {
1358 return __base::__start_;
1359 }
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001360 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001361 size_type __back_spare() const
1362 {
1363 return __capacity() - (__base::__start_ + __base::size());
1364 }
1365
1366 template <class _InpIter>
1367 void __append(_InpIter __f, _InpIter __l,
1368 typename enable_if<__is_input_iterator<_InpIter>::value &&
1369 !__is_forward_iterator<_InpIter>::value>::type* = 0);
1370 template <class _ForIter>
1371 void __append(_ForIter __f, _ForIter __l,
1372 typename enable_if<__is_forward_iterator<_ForIter>::value>::type* = 0);
1373 void __append(size_type __n);
1374 void __append(size_type __n, const value_type& __v);
1375 void __erase_to_end(const_iterator __f);
1376 void __add_front_capacity();
1377 void __add_front_capacity(size_type __n);
1378 void __add_back_capacity();
1379 void __add_back_capacity(size_type __n);
1380 iterator __move_and_check(iterator __f, iterator __l, iterator __r,
1381 const_pointer& __vt);
1382 iterator __move_backward_and_check(iterator __f, iterator __l, iterator __r,
1383 const_pointer& __vt);
1384 void __move_construct_and_check(iterator __f, iterator __l,
1385 iterator __r, const_pointer& __vt);
1386 void __move_construct_backward_and_check(iterator __f, iterator __l,
1387 iterator __r, const_pointer& __vt);
1388
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001389 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001390 void __copy_assign_alloc(const deque& __c)
1391 {__copy_assign_alloc(__c, integral_constant<bool,
1392 __alloc_traits::propagate_on_container_copy_assignment::value>());}
1393
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001394 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001395 void __copy_assign_alloc(const deque& __c, true_type)
1396 {
1397 if (__base::__alloc() != __c.__alloc())
1398 {
1399 clear();
1400 shrink_to_fit();
1401 }
1402 __base::__alloc() = __c.__alloc();
1403 __base::__map_.__alloc() = __c.__map_.__alloc();
1404 }
1405
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001406 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant28b24882011-12-01 20:21:04 +00001407 void __copy_assign_alloc(const deque&, false_type)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001408 {}
1409
Howard Hinnant4931e092011-06-02 21:38:57 +00001410 void __move_assign(deque& __c, true_type)
1411 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001412 void __move_assign(deque& __c, false_type);
1413};
1414
1415template <class _Tp, class _Allocator>
1416deque<_Tp, _Allocator>::deque(size_type __n)
1417{
1418 if (__n > 0)
1419 __append(__n);
1420}
1421
Marshall Clowbc4fcb42013-09-07 16:16:19 +00001422#if _LIBCPP_STD_VER > 11
1423template <class _Tp, class _Allocator>
1424deque<_Tp, _Allocator>::deque(size_type __n, const _Allocator& __a)
1425 : __base(__a)
1426{
1427 if (__n > 0)
1428 __append(__n);
1429}
1430#endif
1431
Howard Hinnantc51e1022010-05-11 19:42:16 +00001432template <class _Tp, class _Allocator>
1433deque<_Tp, _Allocator>::deque(size_type __n, const value_type& __v)
1434{
1435 if (__n > 0)
1436 __append(__n, __v);
1437}
1438
1439template <class _Tp, class _Allocator>
1440deque<_Tp, _Allocator>::deque(size_type __n, const value_type& __v, const allocator_type& __a)
1441 : __base(__a)
1442{
1443 if (__n > 0)
1444 __append(__n, __v);
1445}
1446
1447template <class _Tp, class _Allocator>
1448template <class _InputIter>
1449deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l,
1450 typename enable_if<__is_input_iterator<_InputIter>::value>::type*)
1451{
1452 __append(__f, __l);
1453}
1454
1455template <class _Tp, class _Allocator>
1456template <class _InputIter>
1457deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l, const allocator_type& __a,
1458 typename enable_if<__is_input_iterator<_InputIter>::value>::type*)
1459 : __base(__a)
1460{
1461 __append(__f, __l);
1462}
1463
1464template <class _Tp, class _Allocator>
1465deque<_Tp, _Allocator>::deque(const deque& __c)
1466 : __base(__alloc_traits::select_on_container_copy_construction(__c.__alloc()))
1467{
1468 __append(__c.begin(), __c.end());
1469}
1470
1471template <class _Tp, class _Allocator>
1472deque<_Tp, _Allocator>::deque(const deque& __c, const allocator_type& __a)
1473 : __base(__a)
1474{
1475 __append(__c.begin(), __c.end());
1476}
1477
Howard Hinnant33711792011-08-12 21:56:02 +00001478#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1479
Howard Hinnantc51e1022010-05-11 19:42:16 +00001480template <class _Tp, class _Allocator>
1481deque<_Tp, _Allocator>::deque(initializer_list<value_type> __il)
1482{
1483 __append(__il.begin(), __il.end());
1484}
1485
1486template <class _Tp, class _Allocator>
1487deque<_Tp, _Allocator>::deque(initializer_list<value_type> __il, const allocator_type& __a)
1488 : __base(__a)
1489{
1490 __append(__il.begin(), __il.end());
1491}
1492
Howard Hinnant33711792011-08-12 21:56:02 +00001493#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1494
Howard Hinnantc51e1022010-05-11 19:42:16 +00001495template <class _Tp, class _Allocator>
1496deque<_Tp, _Allocator>&
1497deque<_Tp, _Allocator>::operator=(const deque& __c)
1498{
1499 if (this != &__c)
1500 {
1501 __copy_assign_alloc(__c);
1502 assign(__c.begin(), __c.end());
1503 }
1504 return *this;
1505}
1506
Howard Hinnant74279a52010-09-04 23:28:19 +00001507#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001508
1509template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001510inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001511deque<_Tp, _Allocator>::deque(deque&& __c)
Howard Hinnantca2fc222011-06-02 20:00:14 +00001512 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001513 : __base(_VSTD::move(__c))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001514{
1515}
1516
1517template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001518inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001519deque<_Tp, _Allocator>::deque(deque&& __c, const allocator_type& __a)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001520 : __base(_VSTD::move(__c), __a)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001521{
1522 if (__a != __c.__alloc())
1523 {
Howard Hinnantc834c512011-11-29 18:15:50 +00001524 typedef move_iterator<iterator> _Ip;
1525 assign(_Ip(__c.begin()), _Ip(__c.end()));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001526 }
1527}
1528
1529template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001530inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001531deque<_Tp, _Allocator>&
1532deque<_Tp, _Allocator>::operator=(deque&& __c)
Howard Hinnant4931e092011-06-02 21:38:57 +00001533 _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&
1534 is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001535{
1536 __move_assign(__c, integral_constant<bool,
1537 __alloc_traits::propagate_on_container_move_assignment::value>());
1538 return *this;
1539}
1540
1541template <class _Tp, class _Allocator>
1542void
1543deque<_Tp, _Allocator>::__move_assign(deque& __c, false_type)
1544{
1545 if (__base::__alloc() != __c.__alloc())
1546 {
Howard Hinnantc834c512011-11-29 18:15:50 +00001547 typedef move_iterator<iterator> _Ip;
1548 assign(_Ip(__c.begin()), _Ip(__c.end()));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001549 }
1550 else
1551 __move_assign(__c, true_type());
1552}
1553
1554template <class _Tp, class _Allocator>
1555void
1556deque<_Tp, _Allocator>::__move_assign(deque& __c, true_type)
Howard Hinnant4931e092011-06-02 21:38:57 +00001557 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001558{
1559 clear();
1560 shrink_to_fit();
1561 __base::__move_assign(__c);
1562}
1563
Howard Hinnant74279a52010-09-04 23:28:19 +00001564#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001565
1566template <class _Tp, class _Allocator>
1567template <class _InputIter>
1568void
1569deque<_Tp, _Allocator>::assign(_InputIter __f, _InputIter __l,
1570 typename enable_if<__is_input_iterator<_InputIter>::value &&
1571 !__is_random_access_iterator<_InputIter>::value>::type*)
1572{
1573 iterator __i = __base::begin();
1574 iterator __e = __base::end();
Eric Fiseliera09a3b42014-10-27 19:28:20 +00001575 for (; __f != __l && __i != __e; ++__f, (void) ++__i)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001576 *__i = *__f;
1577 if (__f != __l)
1578 __append(__f, __l);
1579 else
1580 __erase_to_end(__i);
1581}
1582
1583template <class _Tp, class _Allocator>
1584template <class _RAIter>
1585void
1586deque<_Tp, _Allocator>::assign(_RAIter __f, _RAIter __l,
1587 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)
1588{
1589 if (static_cast<size_type>(__l - __f) > __base::size())
1590 {
1591 _RAIter __m = __f + __base::size();
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001592 _VSTD::copy(__f, __m, __base::begin());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001593 __append(__m, __l);
1594 }
1595 else
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001596 __erase_to_end(_VSTD::copy(__f, __l, __base::begin()));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001597}
1598
1599template <class _Tp, class _Allocator>
1600void
1601deque<_Tp, _Allocator>::assign(size_type __n, const value_type& __v)
1602{
1603 if (__n > __base::size())
1604 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001605 _VSTD::fill_n(__base::begin(), __base::size(), __v);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001606 __n -= __base::size();
1607 __append(__n, __v);
1608 }
1609 else
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001610 __erase_to_end(_VSTD::fill_n(__base::begin(), __n, __v));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001611}
1612
1613template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001614inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001615_Allocator
Howard Hinnantda2df912011-06-02 16:10:22 +00001616deque<_Tp, _Allocator>::get_allocator() const _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001617{
1618 return __base::__alloc();
1619}
1620
1621template <class _Tp, class _Allocator>
1622void
1623deque<_Tp, _Allocator>::resize(size_type __n)
1624{
1625 if (__n > __base::size())
1626 __append(__n - __base::size());
1627 else if (__n < __base::size())
1628 __erase_to_end(__base::begin() + __n);
1629}
1630
1631template <class _Tp, class _Allocator>
1632void
1633deque<_Tp, _Allocator>::resize(size_type __n, const value_type& __v)
1634{
1635 if (__n > __base::size())
1636 __append(__n - __base::size(), __v);
1637 else if (__n < __base::size())
1638 __erase_to_end(__base::begin() + __n);
1639}
1640
1641template <class _Tp, class _Allocator>
1642void
Howard Hinnant4931e092011-06-02 21:38:57 +00001643deque<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001644{
1645 allocator_type& __a = __base::__alloc();
1646 if (empty())
1647 {
1648 while (__base::__map_.size() > 0)
1649 {
1650 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
1651 __base::__map_.pop_back();
1652 }
1653 __base::__start_ = 0;
1654 }
1655 else
1656 {
1657 if (__front_spare() >= __base::__block_size)
1658 {
1659 __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
1660 __base::__map_.pop_front();
1661 __base::__start_ -= __base::__block_size;
1662 }
1663 if (__back_spare() >= __base::__block_size)
1664 {
1665 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
1666 __base::__map_.pop_back();
1667 }
1668 }
1669 __base::__map_.shrink_to_fit();
1670}
1671
1672template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001673inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001674typename deque<_Tp, _Allocator>::reference
1675deque<_Tp, _Allocator>::operator[](size_type __i)
1676{
1677 size_type __p = __base::__start_ + __i;
1678 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1679}
1680
1681template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001682inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001683typename deque<_Tp, _Allocator>::const_reference
1684deque<_Tp, _Allocator>::operator[](size_type __i) const
1685{
1686 size_type __p = __base::__start_ + __i;
1687 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1688}
1689
1690template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001691inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001692typename deque<_Tp, _Allocator>::reference
1693deque<_Tp, _Allocator>::at(size_type __i)
1694{
1695 if (__i >= __base::size())
1696 __base::__throw_out_of_range();
1697 size_type __p = __base::__start_ + __i;
1698 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1699}
1700
1701template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001702inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001703typename deque<_Tp, _Allocator>::const_reference
1704deque<_Tp, _Allocator>::at(size_type __i) const
1705{
1706 if (__i >= __base::size())
1707 __base::__throw_out_of_range();
1708 size_type __p = __base::__start_ + __i;
1709 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1710}
1711
1712template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001713inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001714typename deque<_Tp, _Allocator>::reference
1715deque<_Tp, _Allocator>::front()
1716{
1717 return *(*(__base::__map_.begin() + __base::__start_ / __base::__block_size)
1718 + __base::__start_ % __base::__block_size);
1719}
1720
1721template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001722inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001723typename deque<_Tp, _Allocator>::const_reference
1724deque<_Tp, _Allocator>::front() const
1725{
1726 return *(*(__base::__map_.begin() + __base::__start_ / __base::__block_size)
1727 + __base::__start_ % __base::__block_size);
1728}
1729
1730template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001731inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001732typename deque<_Tp, _Allocator>::reference
1733deque<_Tp, _Allocator>::back()
1734{
1735 size_type __p = __base::size() + __base::__start_ - 1;
1736 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1737}
1738
1739template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00001740inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001741typename deque<_Tp, _Allocator>::const_reference
1742deque<_Tp, _Allocator>::back() const
1743{
1744 size_type __p = __base::size() + __base::__start_ - 1;
1745 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
1746}
1747
1748template <class _Tp, class _Allocator>
1749void
1750deque<_Tp, _Allocator>::push_back(const value_type& __v)
1751{
1752 allocator_type& __a = __base::__alloc();
1753 if (__back_spare() == 0)
1754 __add_back_capacity();
1755 // __back_spare() >= 1
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001756 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), __v);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001757 ++__base::size();
1758}
1759
Howard Hinnant74279a52010-09-04 23:28:19 +00001760#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001761
1762template <class _Tp, class _Allocator>
1763void
1764deque<_Tp, _Allocator>::push_back(value_type&& __v)
1765{
1766 allocator_type& __a = __base::__alloc();
1767 if (__back_spare() == 0)
1768 __add_back_capacity();
1769 // __back_spare() >= 1
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001770 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::move(__v));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001771 ++__base::size();
1772}
1773
Howard Hinnant74279a52010-09-04 23:28:19 +00001774#ifndef _LIBCPP_HAS_NO_VARIADICS
1775
Howard Hinnantc51e1022010-05-11 19:42:16 +00001776template <class _Tp, class _Allocator>
1777template <class... _Args>
1778void
1779deque<_Tp, _Allocator>::emplace_back(_Args&&... __args)
1780{
1781 allocator_type& __a = __base::__alloc();
1782 if (__back_spare() == 0)
1783 __add_back_capacity();
1784 // __back_spare() >= 1
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001785 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001786 ++__base::size();
1787}
1788
Howard Hinnant74279a52010-09-04 23:28:19 +00001789#endif // _LIBCPP_HAS_NO_VARIADICS
1790#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001791
1792template <class _Tp, class _Allocator>
1793void
1794deque<_Tp, _Allocator>::push_front(const value_type& __v)
1795{
1796 allocator_type& __a = __base::__alloc();
1797 if (__front_spare() == 0)
1798 __add_front_capacity();
1799 // __front_spare() >= 1
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001800 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), __v);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001801 --__base::__start_;
1802 ++__base::size();
1803}
1804
Howard Hinnant74279a52010-09-04 23:28:19 +00001805#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001806
1807template <class _Tp, class _Allocator>
1808void
1809deque<_Tp, _Allocator>::push_front(value_type&& __v)
1810{
1811 allocator_type& __a = __base::__alloc();
1812 if (__front_spare() == 0)
1813 __add_front_capacity();
1814 // __front_spare() >= 1
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001815 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::move(__v));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001816 --__base::__start_;
1817 ++__base::size();
1818}
1819
Howard Hinnant74279a52010-09-04 23:28:19 +00001820#ifndef _LIBCPP_HAS_NO_VARIADICS
1821
Howard Hinnantc51e1022010-05-11 19:42:16 +00001822template <class _Tp, class _Allocator>
1823template <class... _Args>
1824void
1825deque<_Tp, _Allocator>::emplace_front(_Args&&... __args)
1826{
1827 allocator_type& __a = __base::__alloc();
1828 if (__front_spare() == 0)
1829 __add_front_capacity();
1830 // __front_spare() >= 1
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001831 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001832 --__base::__start_;
1833 ++__base::size();
1834}
1835
Howard Hinnant74279a52010-09-04 23:28:19 +00001836#endif // _LIBCPP_HAS_NO_VARIADICS
1837#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001838
1839template <class _Tp, class _Allocator>
1840typename deque<_Tp, _Allocator>::iterator
1841deque<_Tp, _Allocator>::insert(const_iterator __p, const value_type& __v)
1842{
1843 size_type __pos = __p - __base::begin();
1844 size_type __to_end = __base::size() - __pos;
1845 allocator_type& __a = __base::__alloc();
1846 if (__pos < __to_end)
1847 { // insert by shifting things backward
1848 if (__front_spare() == 0)
1849 __add_front_capacity();
1850 // __front_spare() >= 1
1851 if (__pos == 0)
1852 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001853 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), __v);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001854 --__base::__start_;
1855 ++__base::size();
1856 }
1857 else
1858 {
1859 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
1860 iterator __b = __base::begin();
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001861 iterator __bm1 = _VSTD::prev(__b);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001862 if (__vt == pointer_traits<const_pointer>::pointer_to(*__b))
1863 __vt = pointer_traits<const_pointer>::pointer_to(*__bm1);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001864 __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001865 --__base::__start_;
1866 ++__base::size();
1867 if (__pos > 1)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001868 __b = __move_and_check(_VSTD::next(__b), __b + __pos, __b, __vt);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001869 *__b = *__vt;
1870 }
1871 }
1872 else
1873 { // insert by shifting things forward
1874 if (__back_spare() == 0)
1875 __add_back_capacity();
1876 // __back_capacity >= 1
1877 size_type __de = __base::size() - __pos;
1878 if (__de == 0)
1879 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001880 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), __v);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001881 ++__base::size();
1882 }
1883 else
1884 {
1885 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
1886 iterator __e = __base::end();
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001887 iterator __em1 = _VSTD::prev(__e);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001888 if (__vt == pointer_traits<const_pointer>::pointer_to(*__em1))
1889 __vt = pointer_traits<const_pointer>::pointer_to(*__e);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001890 __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001891 ++__base::size();
1892 if (__de > 1)
1893 __e = __move_backward_and_check(__e - __de, __em1, __e, __vt);
1894 *--__e = *__vt;
1895 }
1896 }
1897 return __base::begin() + __pos;
1898}
1899
Howard Hinnant74279a52010-09-04 23:28:19 +00001900#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001901
1902template <class _Tp, class _Allocator>
1903typename deque<_Tp, _Allocator>::iterator
1904deque<_Tp, _Allocator>::insert(const_iterator __p, value_type&& __v)
1905{
1906 size_type __pos = __p - __base::begin();
1907 size_type __to_end = __base::size() - __pos;
1908 allocator_type& __a = __base::__alloc();
1909 if (__pos < __to_end)
1910 { // insert by shifting things backward
1911 if (__front_spare() == 0)
1912 __add_front_capacity();
1913 // __front_spare() >= 1
1914 if (__pos == 0)
1915 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001916 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::move(__v));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001917 --__base::__start_;
1918 ++__base::size();
1919 }
1920 else
1921 {
1922 iterator __b = __base::begin();
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001923 iterator __bm1 = _VSTD::prev(__b);
1924 __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001925 --__base::__start_;
1926 ++__base::size();
1927 if (__pos > 1)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001928 __b = _VSTD::move(_VSTD::next(__b), __b + __pos, __b);
1929 *__b = _VSTD::move(__v);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001930 }
1931 }
1932 else
1933 { // insert by shifting things forward
1934 if (__back_spare() == 0)
1935 __add_back_capacity();
1936 // __back_capacity >= 1
1937 size_type __de = __base::size() - __pos;
1938 if (__de == 0)
1939 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001940 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::move(__v));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001941 ++__base::size();
1942 }
1943 else
1944 {
1945 iterator __e = __base::end();
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001946 iterator __em1 = _VSTD::prev(__e);
1947 __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001948 ++__base::size();
1949 if (__de > 1)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001950 __e = _VSTD::move_backward(__e - __de, __em1, __e);
1951 *--__e = _VSTD::move(__v);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001952 }
1953 }
1954 return __base::begin() + __pos;
1955}
1956
Howard Hinnant74279a52010-09-04 23:28:19 +00001957#ifndef _LIBCPP_HAS_NO_VARIADICS
1958
Howard Hinnantc51e1022010-05-11 19:42:16 +00001959template <class _Tp, class _Allocator>
1960template <class... _Args>
1961typename deque<_Tp, _Allocator>::iterator
1962deque<_Tp, _Allocator>::emplace(const_iterator __p, _Args&&... __args)
1963{
1964 size_type __pos = __p - __base::begin();
1965 size_type __to_end = __base::size() - __pos;
1966 allocator_type& __a = __base::__alloc();
1967 if (__pos < __to_end)
1968 { // insert by shifting things backward
1969 if (__front_spare() == 0)
1970 __add_front_capacity();
1971 // __front_spare() >= 1
1972 if (__pos == 0)
1973 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001974 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001975 --__base::__start_;
1976 ++__base::size();
1977 }
1978 else
1979 {
Howard Hinnant800d2d22012-07-08 23:23:04 +00001980 value_type __tmp(_VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001981 iterator __b = __base::begin();
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001982 iterator __bm1 = _VSTD::prev(__b);
1983 __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001984 --__base::__start_;
1985 ++__base::size();
1986 if (__pos > 1)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001987 __b = _VSTD::move(_VSTD::next(__b), __b + __pos, __b);
Howard Hinnant800d2d22012-07-08 23:23:04 +00001988 *__b = _VSTD::move(__tmp);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001989 }
1990 }
1991 else
1992 { // insert by shifting things forward
1993 if (__back_spare() == 0)
1994 __add_back_capacity();
1995 // __back_capacity >= 1
1996 size_type __de = __base::size() - __pos;
1997 if (__de == 0)
1998 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001999 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002000 ++__base::size();
2001 }
2002 else
2003 {
Howard Hinnant800d2d22012-07-08 23:23:04 +00002004 value_type __tmp(_VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002005 iterator __e = __base::end();
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002006 iterator __em1 = _VSTD::prev(__e);
2007 __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002008 ++__base::size();
2009 if (__de > 1)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002010 __e = _VSTD::move_backward(__e - __de, __em1, __e);
Howard Hinnant800d2d22012-07-08 23:23:04 +00002011 *--__e = _VSTD::move(__tmp);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002012 }
2013 }
2014 return __base::begin() + __pos;
2015}
2016
Howard Hinnant74279a52010-09-04 23:28:19 +00002017#endif // _LIBCPP_HAS_NO_VARIADICS
2018#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00002019
2020template <class _Tp, class _Allocator>
2021typename deque<_Tp, _Allocator>::iterator
2022deque<_Tp, _Allocator>::insert(const_iterator __p, size_type __n, const value_type& __v)
2023{
2024 size_type __pos = __p - __base::begin();
2025 size_type __to_end = __base::size() - __pos;
2026 allocator_type& __a = __base::__alloc();
2027 if (__pos < __to_end)
2028 { // insert by shifting things backward
2029 if (__n > __front_spare())
2030 __add_front_capacity(__n - __front_spare());
2031 // __n <= __front_spare()
2032 size_type __old_n = __n;
2033 iterator __old_begin = __base::begin();
2034 iterator __i = __old_begin;
2035 if (__n > __pos)
2036 {
2037 for (size_type __m = __n - __pos; __m; --__m, --__base::__start_, ++__base::size())
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002038 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), __v);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002039 __n = __pos;
2040 }
2041 if (__n > 0)
2042 {
2043 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
2044 iterator __obn = __old_begin + __n;
2045 __move_construct_backward_and_check(__old_begin, __obn, __i, __vt);
2046 if (__n < __pos)
2047 __old_begin = __move_and_check(__obn, __old_begin + __pos, __old_begin, __vt);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002048 _VSTD::fill_n(__old_begin, __n, *__vt);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002049 }
2050 }
2051 else
2052 { // insert by shifting things forward
2053 size_type __back_capacity = __back_spare();
2054 if (__n > __back_capacity)
2055 __add_back_capacity(__n - __back_capacity);
2056 // __n <= __back_capacity
2057 size_type __old_n = __n;
2058 iterator __old_end = __base::end();
2059 iterator __i = __old_end;
2060 size_type __de = __base::size() - __pos;
2061 if (__n > __de)
2062 {
2063 for (size_type __m = __n - __de; __m; --__m, ++__i, ++__base::size())
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002064 __alloc_traits::construct(__a, _VSTD::addressof(*__i), __v);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002065 __n = __de;
2066 }
2067 if (__n > 0)
2068 {
2069 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v);
2070 iterator __oen = __old_end - __n;
2071 __move_construct_and_check(__oen, __old_end, __i, __vt);
2072 if (__n < __de)
2073 __old_end = __move_backward_and_check(__old_end - __de, __oen, __old_end, __vt);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002074 _VSTD::fill_n(__old_end - __n, __n, *__vt);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002075 }
2076 }
2077 return __base::begin() + __pos;
2078}
2079
2080template <class _Tp, class _Allocator>
2081template <class _InputIter>
2082typename deque<_Tp, _Allocator>::iterator
2083deque<_Tp, _Allocator>::insert(const_iterator __p, _InputIter __f, _InputIter __l,
2084 typename enable_if<__is_input_iterator<_InputIter>::value
Marshall Clow6b612cf2015-01-22 18:33:29 +00002085 &&!__is_forward_iterator<_InputIter>::value>::type*)
Howard Hinnantc51e1022010-05-11 19:42:16 +00002086{
2087 __split_buffer<value_type, allocator_type&> __buf(__base::__alloc());
2088 __buf.__construct_at_end(__f, __l);
2089 typedef typename __split_buffer<value_type, allocator_type&>::iterator __bi;
2090 return insert(__p, move_iterator<__bi>(__buf.begin()), move_iterator<__bi>(__buf.end()));
2091}
2092
2093template <class _Tp, class _Allocator>
Marshall Clow6b612cf2015-01-22 18:33:29 +00002094template <class _ForwardIterator>
2095typename deque<_Tp, _Allocator>::iterator
2096deque<_Tp, _Allocator>::insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l,
2097 typename enable_if<__is_forward_iterator<_ForwardIterator>::value
2098 &&!__is_bidirectional_iterator<_ForwardIterator>::value>::type*)
2099{
2100 size_type __n = _VSTD::distance(__f, __l);
2101 __split_buffer<value_type, allocator_type&> __buf(__n, 0, __base::__alloc());
2102 __buf.__construct_at_end(__f, __l);
2103 typedef typename __split_buffer<value_type, allocator_type&>::iterator __fwd;
2104 return insert(__p, move_iterator<__fwd>(__buf.begin()), move_iterator<__fwd>(__buf.end()));
2105}
2106
2107template <class _Tp, class _Allocator>
Howard Hinnantc51e1022010-05-11 19:42:16 +00002108template <class _BiIter>
2109typename deque<_Tp, _Allocator>::iterator
2110deque<_Tp, _Allocator>::insert(const_iterator __p, _BiIter __f, _BiIter __l,
2111 typename enable_if<__is_bidirectional_iterator<_BiIter>::value>::type*)
2112{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002113 size_type __n = _VSTD::distance(__f, __l);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002114 size_type __pos = __p - __base::begin();
2115 size_type __to_end = __base::size() - __pos;
2116 allocator_type& __a = __base::__alloc();
2117 if (__pos < __to_end)
2118 { // insert by shifting things backward
2119 if (__n > __front_spare())
2120 __add_front_capacity(__n - __front_spare());
2121 // __n <= __front_spare()
2122 size_type __old_n = __n;
2123 iterator __old_begin = __base::begin();
2124 iterator __i = __old_begin;
2125 _BiIter __m = __f;
2126 if (__n > __pos)
2127 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002128 __m = __pos < __n / 2 ? _VSTD::prev(__l, __pos) : _VSTD::next(__f, __n - __pos);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002129 for (_BiIter __j = __m; __j != __f; --__base::__start_, ++__base::size())
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002130 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), *--__j);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002131 __n = __pos;
2132 }
2133 if (__n > 0)
2134 {
2135 iterator __obn = __old_begin + __n;
2136 for (iterator __j = __obn; __j != __old_begin;)
2137 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002138 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), _VSTD::move(*--__j));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002139 --__base::__start_;
2140 ++__base::size();
2141 }
2142 if (__n < __pos)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002143 __old_begin = _VSTD::move(__obn, __old_begin + __pos, __old_begin);
2144 _VSTD::copy(__m, __l, __old_begin);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002145 }
2146 }
2147 else
2148 { // insert by shifting things forward
2149 size_type __back_capacity = __back_spare();
2150 if (__n > __back_capacity)
2151 __add_back_capacity(__n - __back_capacity);
2152 // __n <= __back_capacity
2153 size_type __old_n = __n;
2154 iterator __old_end = __base::end();
2155 iterator __i = __old_end;
2156 _BiIter __m = __l;
2157 size_type __de = __base::size() - __pos;
2158 if (__n > __de)
2159 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002160 __m = __de < __n / 2 ? _VSTD::next(__f, __de) : _VSTD::prev(__l, __n - __de);
Eric Fiseliera09a3b42014-10-27 19:28:20 +00002161 for (_BiIter __j = __m; __j != __l; ++__i, (void) ++__j, ++__base::size())
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002162 __alloc_traits::construct(__a, _VSTD::addressof(*__i), *__j);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002163 __n = __de;
2164 }
2165 if (__n > 0)
2166 {
2167 iterator __oen = __old_end - __n;
2168 for (iterator __j = __oen; __j != __old_end; ++__i, ++__j, ++__base::size())
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002169 __alloc_traits::construct(__a, _VSTD::addressof(*__i), _VSTD::move(*__j));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002170 if (__n < __de)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002171 __old_end = _VSTD::move_backward(__old_end - __de, __oen, __old_end);
2172 _VSTD::copy_backward(__f, __m, __old_end);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002173 }
2174 }
2175 return __base::begin() + __pos;
2176}
2177
2178template <class _Tp, class _Allocator>
2179template <class _InpIter>
2180void
2181deque<_Tp, _Allocator>::__append(_InpIter __f, _InpIter __l,
2182 typename enable_if<__is_input_iterator<_InpIter>::value &&
2183 !__is_forward_iterator<_InpIter>::value>::type*)
2184{
2185 for (; __f != __l; ++__f)
2186 push_back(*__f);
2187}
2188
2189template <class _Tp, class _Allocator>
2190template <class _ForIter>
2191void
2192deque<_Tp, _Allocator>::__append(_ForIter __f, _ForIter __l,
2193 typename enable_if<__is_forward_iterator<_ForIter>::value>::type*)
2194{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002195 size_type __n = _VSTD::distance(__f, __l);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002196 allocator_type& __a = __base::__alloc();
2197 size_type __back_capacity = __back_spare();
2198 if (__n > __back_capacity)
2199 __add_back_capacity(__n - __back_capacity);
2200 // __n <= __back_capacity
Eric Fiseliera09a3b42014-10-27 19:28:20 +00002201 for (iterator __i = __base::end(); __f != __l; ++__i, (void) ++__f, ++__base::size())
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002202 __alloc_traits::construct(__a, _VSTD::addressof(*__i), *__f);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002203}
2204
2205template <class _Tp, class _Allocator>
2206void
2207deque<_Tp, _Allocator>::__append(size_type __n)
2208{
2209 allocator_type& __a = __base::__alloc();
2210 size_type __back_capacity = __back_spare();
2211 if (__n > __back_capacity)
2212 __add_back_capacity(__n - __back_capacity);
2213 // __n <= __back_capacity
2214 for (iterator __i = __base::end(); __n; --__n, ++__i, ++__base::size())
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002215 __alloc_traits::construct(__a, _VSTD::addressof(*__i));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002216}
2217
2218template <class _Tp, class _Allocator>
2219void
2220deque<_Tp, _Allocator>::__append(size_type __n, const value_type& __v)
2221{
2222 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
2227 for (iterator __i = __base::end(); __n; --__n, ++__i, ++__base::size())
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002228 __alloc_traits::construct(__a, _VSTD::addressof(*__i), __v);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002229}
2230
2231// Create front capacity for one block of elements.
2232// Strong guarantee. Either do it or don't touch anything.
2233template <class _Tp, class _Allocator>
2234void
2235deque<_Tp, _Allocator>::__add_front_capacity()
2236{
2237 allocator_type& __a = __base::__alloc();
2238 if (__back_spare() >= __base::__block_size)
2239 {
2240 __base::__start_ += __base::__block_size;
2241 pointer __pt = __base::__map_.back();
2242 __base::__map_.pop_back();
2243 __base::__map_.push_front(__pt);
2244 }
2245 // Else if __base::__map_.size() < __base::__map_.capacity() then we need to allocate 1 buffer
2246 else if (__base::__map_.size() < __base::__map_.capacity())
2247 { // we can put the new buffer into the map, but don't shift things around
2248 // until all buffers are allocated. If we throw, we don't need to fix
2249 // anything up (any added buffers are undetectible)
2250 if (__base::__map_.__front_spare() > 0)
2251 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
2252 else
2253 {
2254 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2255 // Done allocating, reorder capacity
2256 pointer __pt = __base::__map_.back();
2257 __base::__map_.pop_back();
2258 __base::__map_.push_front(__pt);
2259 }
2260 __base::__start_ = __base::__map_.size() == 1 ?
2261 __base::__block_size / 2 :
2262 __base::__start_ + __base::__block_size;
2263 }
2264 // Else need to allocate 1 buffer, *and* we need to reallocate __map_.
2265 else
2266 {
2267 __split_buffer<pointer, typename __base::__pointer_allocator&>
2268 __buf(max<size_type>(2 * __base::__map_.capacity(), 1),
2269 0, __base::__map_.__alloc());
Marshall Clow5fd466b2015-03-09 17:08:51 +00002270
Marshall Clow8982dcd2015-07-13 20:04:56 +00002271 typedef __allocator_destructor<_Allocator> _Dp;
2272 unique_ptr<pointer, _Dp> __hold(
2273 __alloc_traits::allocate(__a, __base::__block_size),
2274 _Dp(__a, __base::__block_size));
2275 __buf.push_back(__hold.get());
2276 __hold.release();
2277
Howard Hinnantc51e1022010-05-11 19:42:16 +00002278 for (typename __base::__map_pointer __i = __base::__map_.begin();
2279 __i != __base::__map_.end(); ++__i)
2280 __buf.push_back(*__i);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002281 _VSTD::swap(__base::__map_.__first_, __buf.__first_);
2282 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
2283 _VSTD::swap(__base::__map_.__end_, __buf.__end_);
2284 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
Howard Hinnantc51e1022010-05-11 19:42:16 +00002285 __base::__start_ = __base::__map_.size() == 1 ?
2286 __base::__block_size / 2 :
2287 __base::__start_ + __base::__block_size;
2288 }
2289}
2290
2291// Create front capacity for __n elements.
2292// Strong guarantee. Either do it or don't touch anything.
2293template <class _Tp, class _Allocator>
2294void
2295deque<_Tp, _Allocator>::__add_front_capacity(size_type __n)
2296{
2297 allocator_type& __a = __base::__alloc();
2298 size_type __nb = __recommend_blocks(__n + __base::__map_.empty());
2299 // Number of unused blocks at back:
2300 size_type __back_capacity = __back_spare() / __base::__block_size;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002301 __back_capacity = _VSTD::min(__back_capacity, __nb); // don't take more than you need
Howard Hinnantc51e1022010-05-11 19:42:16 +00002302 __nb -= __back_capacity; // number of blocks need to allocate
2303 // If __nb == 0, then we have sufficient capacity.
2304 if (__nb == 0)
2305 {
2306 __base::__start_ += __base::__block_size * __back_capacity;
2307 for (; __back_capacity > 0; --__back_capacity)
2308 {
2309 pointer __pt = __base::__map_.back();
2310 __base::__map_.pop_back();
2311 __base::__map_.push_front(__pt);
2312 }
2313 }
2314 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers
2315 else if (__nb <= __base::__map_.capacity() - __base::__map_.size())
2316 { // we can put the new buffers into the map, but don't shift things around
2317 // until all buffers are allocated. If we throw, we don't need to fix
2318 // anything up (any added buffers are undetectible)
2319 for (; __nb > 0; --__nb, __base::__start_ += __base::__block_size - (__base::__map_.size() == 1))
2320 {
2321 if (__base::__map_.__front_spare() == 0)
2322 break;
2323 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
2324 }
2325 for (; __nb > 0; --__nb, ++__back_capacity)
2326 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2327 // Done allocating, reorder capacity
2328 __base::__start_ += __back_capacity * __base::__block_size;
2329 for (; __back_capacity > 0; --__back_capacity)
2330 {
2331 pointer __pt = __base::__map_.back();
2332 __base::__map_.pop_back();
2333 __base::__map_.push_front(__pt);
2334 }
2335 }
2336 // Else need to allocate __nb buffers, *and* we need to reallocate __map_.
2337 else
2338 {
2339 size_type __ds = (__nb + __back_capacity) * __base::__block_size - __base::__map_.empty();
2340 __split_buffer<pointer, typename __base::__pointer_allocator&>
2341 __buf(max<size_type>(2* __base::__map_.capacity(),
2342 __nb + __base::__map_.size()),
2343 0, __base::__map_.__alloc());
2344#ifndef _LIBCPP_NO_EXCEPTIONS
2345 try
2346 {
Howard Hinnant3b6579a2010-08-22 00:02:43 +00002347#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00002348 for (; __nb > 0; --__nb)
2349 __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2350#ifndef _LIBCPP_NO_EXCEPTIONS
2351 }
2352 catch (...)
2353 {
2354 for (typename __base::__map_pointer __i = __buf.begin();
2355 __i != __buf.end(); ++__i)
2356 __alloc_traits::deallocate(__a, *__i, __base::__block_size);
2357 throw;
2358 }
Howard Hinnant3b6579a2010-08-22 00:02:43 +00002359#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00002360 for (; __back_capacity > 0; --__back_capacity)
2361 {
2362 __buf.push_back(__base::__map_.back());
2363 __base::__map_.pop_back();
2364 }
2365 for (typename __base::__map_pointer __i = __base::__map_.begin();
2366 __i != __base::__map_.end(); ++__i)
2367 __buf.push_back(*__i);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002368 _VSTD::swap(__base::__map_.__first_, __buf.__first_);
2369 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
2370 _VSTD::swap(__base::__map_.__end_, __buf.__end_);
2371 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
Howard Hinnantc51e1022010-05-11 19:42:16 +00002372 __base::__start_ += __ds;
2373 }
2374}
2375
2376// Create back capacity for one block of elements.
2377// Strong guarantee. Either do it or don't touch anything.
2378template <class _Tp, class _Allocator>
2379void
2380deque<_Tp, _Allocator>::__add_back_capacity()
2381{
2382 allocator_type& __a = __base::__alloc();
2383 if (__front_spare() >= __base::__block_size)
2384 {
2385 __base::__start_ -= __base::__block_size;
2386 pointer __pt = __base::__map_.front();
2387 __base::__map_.pop_front();
2388 __base::__map_.push_back(__pt);
2389 }
2390 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers
2391 else if (__base::__map_.size() < __base::__map_.capacity())
2392 { // we can put the new buffer into the map, but don't shift things around
2393 // until it is allocated. If we throw, we don't need to fix
2394 // anything up (any added buffers are undetectible)
2395 if (__base::__map_.__back_spare() != 0)
2396 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2397 else
2398 {
2399 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
2400 // Done allocating, reorder capacity
2401 pointer __pt = __base::__map_.front();
2402 __base::__map_.pop_front();
2403 __base::__map_.push_back(__pt);
2404 }
2405 }
2406 // Else need to allocate 1 buffer, *and* we need to reallocate __map_.
2407 else
2408 {
2409 __split_buffer<pointer, typename __base::__pointer_allocator&>
2410 __buf(max<size_type>(2* __base::__map_.capacity(), 1),
2411 __base::__map_.size(),
2412 __base::__map_.__alloc());
Marshall Clow5fd466b2015-03-09 17:08:51 +00002413
Marshall Clow8982dcd2015-07-13 20:04:56 +00002414 typedef __allocator_destructor<_Allocator> _Dp;
2415 unique_ptr<pointer, _Dp> __hold(
2416 __alloc_traits::allocate(__a, __base::__block_size),
2417 _Dp(__a, __base::__block_size));
2418 __buf.push_back(__hold.get());
2419 __hold.release();
Marshall Clow5fd466b2015-03-09 17:08:51 +00002420
Howard Hinnantc51e1022010-05-11 19:42:16 +00002421 for (typename __base::__map_pointer __i = __base::__map_.end();
2422 __i != __base::__map_.begin();)
2423 __buf.push_front(*--__i);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002424 _VSTD::swap(__base::__map_.__first_, __buf.__first_);
2425 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
2426 _VSTD::swap(__base::__map_.__end_, __buf.__end_);
2427 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
Howard Hinnantc51e1022010-05-11 19:42:16 +00002428 }
2429}
2430
2431// Create back capacity for __n elements.
2432// Strong guarantee. Either do it or don't touch anything.
2433template <class _Tp, class _Allocator>
2434void
2435deque<_Tp, _Allocator>::__add_back_capacity(size_type __n)
2436{
2437 allocator_type& __a = __base::__alloc();
2438 size_type __nb = __recommend_blocks(__n + __base::__map_.empty());
2439 // Number of unused blocks at front:
2440 size_type __front_capacity = __front_spare() / __base::__block_size;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002441 __front_capacity = _VSTD::min(__front_capacity, __nb); // don't take more than you need
Howard Hinnantc51e1022010-05-11 19:42:16 +00002442 __nb -= __front_capacity; // number of blocks need to allocate
2443 // If __nb == 0, then we have sufficient capacity.
2444 if (__nb == 0)
2445 {
2446 __base::__start_ -= __base::__block_size * __front_capacity;
2447 for (; __front_capacity > 0; --__front_capacity)
2448 {
2449 pointer __pt = __base::__map_.front();
2450 __base::__map_.pop_front();
2451 __base::__map_.push_back(__pt);
2452 }
2453 }
2454 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers
2455 else if (__nb <= __base::__map_.capacity() - __base::__map_.size())
2456 { // we can put the new buffers into the map, but don't shift things around
2457 // until all buffers are allocated. If we throw, we don't need to fix
2458 // anything up (any added buffers are undetectible)
2459 for (; __nb > 0; --__nb)
2460 {
2461 if (__base::__map_.__back_spare() == 0)
2462 break;
2463 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2464 }
2465 for (; __nb > 0; --__nb, ++__front_capacity, __base::__start_ +=
2466 __base::__block_size - (__base::__map_.size() == 1))
2467 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size));
2468 // Done allocating, reorder capacity
2469 __base::__start_ -= __base::__block_size * __front_capacity;
2470 for (; __front_capacity > 0; --__front_capacity)
2471 {
2472 pointer __pt = __base::__map_.front();
2473 __base::__map_.pop_front();
2474 __base::__map_.push_back(__pt);
2475 }
2476 }
2477 // Else need to allocate __nb buffers, *and* we need to reallocate __map_.
2478 else
2479 {
2480 size_type __ds = __front_capacity * __base::__block_size;
2481 __split_buffer<pointer, typename __base::__pointer_allocator&>
2482 __buf(max<size_type>(2* __base::__map_.capacity(),
2483 __nb + __base::__map_.size()),
2484 __base::__map_.size() - __front_capacity,
2485 __base::__map_.__alloc());
2486#ifndef _LIBCPP_NO_EXCEPTIONS
2487 try
2488 {
Howard Hinnant3b6579a2010-08-22 00:02:43 +00002489#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00002490 for (; __nb > 0; --__nb)
2491 __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size));
2492#ifndef _LIBCPP_NO_EXCEPTIONS
2493 }
2494 catch (...)
2495 {
2496 for (typename __base::__map_pointer __i = __buf.begin();
2497 __i != __buf.end(); ++__i)
2498 __alloc_traits::deallocate(__a, *__i, __base::__block_size);
2499 throw;
2500 }
Howard Hinnant3b6579a2010-08-22 00:02:43 +00002501#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00002502 for (; __front_capacity > 0; --__front_capacity)
2503 {
2504 __buf.push_back(__base::__map_.front());
2505 __base::__map_.pop_front();
2506 }
2507 for (typename __base::__map_pointer __i = __base::__map_.end();
2508 __i != __base::__map_.begin();)
2509 __buf.push_front(*--__i);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002510 _VSTD::swap(__base::__map_.__first_, __buf.__first_);
2511 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
2512 _VSTD::swap(__base::__map_.__end_, __buf.__end_);
2513 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
Howard Hinnantc51e1022010-05-11 19:42:16 +00002514 __base::__start_ -= __ds;
2515 }
2516}
2517
2518template <class _Tp, class _Allocator>
2519void
2520deque<_Tp, _Allocator>::pop_front()
2521{
2522 allocator_type& __a = __base::__alloc();
Howard Hinnantdcb73a32013-06-23 21:17:24 +00002523 __alloc_traits::destroy(__a, __to_raw_pointer(*(__base::__map_.begin() +
2524 __base::__start_ / __base::__block_size) +
2525 __base::__start_ % __base::__block_size));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002526 --__base::size();
2527 if (++__base::__start_ >= 2 * __base::__block_size)
2528 {
2529 __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
2530 __base::__map_.pop_front();
2531 __base::__start_ -= __base::__block_size;
2532 }
2533}
2534
2535template <class _Tp, class _Allocator>
2536void
2537deque<_Tp, _Allocator>::pop_back()
2538{
2539 allocator_type& __a = __base::__alloc();
2540 size_type __p = __base::size() + __base::__start_ - 1;
Howard Hinnantdcb73a32013-06-23 21:17:24 +00002541 __alloc_traits::destroy(__a, __to_raw_pointer(*(__base::__map_.begin() +
2542 __p / __base::__block_size) +
2543 __p % __base::__block_size));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002544 --__base::size();
2545 if (__back_spare() >= 2 * __base::__block_size)
2546 {
2547 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
2548 __base::__map_.pop_back();
2549 }
2550}
2551
2552// move assign [__f, __l) to [__r, __r + (__l-__f)).
2553// If __vt points into [__f, __l), then subtract (__f - __r) from __vt.
2554template <class _Tp, class _Allocator>
2555typename deque<_Tp, _Allocator>::iterator
2556deque<_Tp, _Allocator>::__move_and_check(iterator __f, iterator __l, iterator __r,
2557 const_pointer& __vt)
2558{
2559 // as if
2560 // for (; __f != __l; ++__f, ++__r)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002561 // *__r = _VSTD::move(*__f);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002562 difference_type __n = __l - __f;
2563 while (__n > 0)
2564 {
2565 pointer __fb = __f.__ptr_;
2566 pointer __fe = *__f.__m_iter_ + __base::__block_size;
2567 difference_type __bs = __fe - __fb;
2568 if (__bs > __n)
2569 {
2570 __bs = __n;
2571 __fe = __fb + __bs;
2572 }
2573 if (__fb <= __vt && __vt < __fe)
Howard Hinnantdcb73a32013-06-23 21:17:24 +00002574 __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) -= __f - __r).__ptr_;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002575 __r = _VSTD::move(__fb, __fe, __r);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002576 __n -= __bs;
2577 __f += __bs;
2578 }
2579 return __r;
2580}
2581
2582// move assign [__f, __l) to [__r - (__l-__f), __r) backwards.
2583// If __vt points into [__f, __l), then add (__r - __l) to __vt.
2584template <class _Tp, class _Allocator>
2585typename deque<_Tp, _Allocator>::iterator
2586deque<_Tp, _Allocator>::__move_backward_and_check(iterator __f, iterator __l, iterator __r,
2587 const_pointer& __vt)
2588{
2589 // as if
2590 // while (__f != __l)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002591 // *--__r = _VSTD::move(*--__l);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002592 difference_type __n = __l - __f;
2593 while (__n > 0)
2594 {
2595 --__l;
2596 pointer __lb = *__l.__m_iter_;
2597 pointer __le = __l.__ptr_ + 1;
2598 difference_type __bs = __le - __lb;
2599 if (__bs > __n)
2600 {
2601 __bs = __n;
2602 __lb = __le - __bs;
2603 }
2604 if (__lb <= __vt && __vt < __le)
Howard Hinnantdcb73a32013-06-23 21:17:24 +00002605 __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) += __r - __l - 1).__ptr_;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002606 __r = _VSTD::move_backward(__lb, __le, __r);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002607 __n -= __bs;
2608 __l -= __bs - 1;
2609 }
2610 return __r;
2611}
2612
2613// move construct [__f, __l) to [__r, __r + (__l-__f)).
2614// If __vt points into [__f, __l), then add (__r - __f) to __vt.
2615template <class _Tp, class _Allocator>
2616void
2617deque<_Tp, _Allocator>::__move_construct_and_check(iterator __f, iterator __l,
2618 iterator __r, const_pointer& __vt)
2619{
2620 allocator_type& __a = __base::__alloc();
2621 // as if
2622 // for (; __f != __l; ++__r, ++__f, ++__base::size())
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002623 // __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__f));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002624 difference_type __n = __l - __f;
2625 while (__n > 0)
2626 {
2627 pointer __fb = __f.__ptr_;
2628 pointer __fe = *__f.__m_iter_ + __base::__block_size;
2629 difference_type __bs = __fe - __fb;
2630 if (__bs > __n)
2631 {
2632 __bs = __n;
2633 __fe = __fb + __bs;
2634 }
2635 if (__fb <= __vt && __vt < __fe)
Howard Hinnantdcb73a32013-06-23 21:17:24 +00002636 __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) += __r - __f).__ptr_;
Howard Hinnantc51e1022010-05-11 19:42:16 +00002637 for (; __fb != __fe; ++__fb, ++__r, ++__base::size())
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002638 __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__fb));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002639 __n -= __bs;
2640 __f += __bs;
2641 }
2642}
2643
2644// move construct [__f, __l) to [__r - (__l-__f), __r) backwards.
2645// If __vt points into [__f, __l), then subtract (__l - __r) from __vt.
2646template <class _Tp, class _Allocator>
2647void
2648deque<_Tp, _Allocator>::__move_construct_backward_and_check(iterator __f, iterator __l,
2649 iterator __r, const_pointer& __vt)
2650{
2651 allocator_type& __a = __base::__alloc();
2652 // as if
2653 // for (iterator __j = __l; __j != __f;)
2654 // {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002655 // __alloc_traitsconstruct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__j));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002656 // --__base::__start_;
2657 // ++__base::size();
2658 // }
2659 difference_type __n = __l - __f;
2660 while (__n > 0)
2661 {
2662 --__l;
2663 pointer __lb = *__l.__m_iter_;
2664 pointer __le = __l.__ptr_ + 1;
2665 difference_type __bs = __le - __lb;
2666 if (__bs > __n)
2667 {
2668 __bs = __n;
2669 __lb = __le - __bs;
2670 }
2671 if (__lb <= __vt && __vt < __le)
Howard Hinnantdcb73a32013-06-23 21:17:24 +00002672 __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) -= __l - __r + 1).__ptr_;
Howard Hinnantc51e1022010-05-11 19:42:16 +00002673 while (__le != __lb)
2674 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002675 __alloc_traits::construct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__le));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002676 --__base::__start_;
2677 ++__base::size();
2678 }
2679 __n -= __bs;
2680 __l -= __bs - 1;
2681 }
2682}
2683
2684template <class _Tp, class _Allocator>
2685typename deque<_Tp, _Allocator>::iterator
2686deque<_Tp, _Allocator>::erase(const_iterator __f)
2687{
2688 difference_type __n = 1;
2689 iterator __b = __base::begin();
2690 difference_type __pos = __f - __b;
2691 iterator __p = __b + __pos;
2692 allocator_type& __a = __base::__alloc();
Marshall Clowe7e39922015-06-05 22:34:19 +00002693 if (__pos <= (__base::size() - 1) / 2)
Howard Hinnantc51e1022010-05-11 19:42:16 +00002694 { // erase from front
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002695 _VSTD::move_backward(__b, __p, _VSTD::next(__p));
2696 __alloc_traits::destroy(__a, _VSTD::addressof(*__b));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002697 --__base::size();
2698 ++__base::__start_;
2699 if (__front_spare() >= 2 * __base::__block_size)
2700 {
2701 __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
2702 __base::__map_.pop_front();
2703 __base::__start_ -= __base::__block_size;
2704 }
2705 }
2706 else
2707 { // erase from back
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002708 iterator __i = _VSTD::move(_VSTD::next(__p), __base::end(), __p);
2709 __alloc_traits::destroy(__a, _VSTD::addressof(*__i));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002710 --__base::size();
2711 if (__back_spare() >= 2 * __base::__block_size)
2712 {
2713 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
2714 __base::__map_.pop_back();
2715 }
2716 }
2717 return __base::begin() + __pos;
2718}
2719
2720template <class _Tp, class _Allocator>
2721typename deque<_Tp, _Allocator>::iterator
2722deque<_Tp, _Allocator>::erase(const_iterator __f, const_iterator __l)
2723{
2724 difference_type __n = __l - __f;
2725 iterator __b = __base::begin();
2726 difference_type __pos = __f - __b;
2727 iterator __p = __b + __pos;
2728 if (__n > 0)
2729 {
2730 allocator_type& __a = __base::__alloc();
Marshall Clowe7e39922015-06-05 22:34:19 +00002731 if (__pos <= (__base::size() - __n) / 2)
Howard Hinnantc51e1022010-05-11 19:42:16 +00002732 { // erase from front
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002733 iterator __i = _VSTD::move_backward(__b, __p, __p + __n);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002734 for (; __b != __i; ++__b)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002735 __alloc_traits::destroy(__a, _VSTD::addressof(*__b));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002736 __base::size() -= __n;
2737 __base::__start_ += __n;
2738 while (__front_spare() >= 2 * __base::__block_size)
2739 {
2740 __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
2741 __base::__map_.pop_front();
2742 __base::__start_ -= __base::__block_size;
2743 }
2744 }
2745 else
2746 { // erase from back
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002747 iterator __i = _VSTD::move(__p + __n, __base::end(), __p);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002748 for (iterator __e = __base::end(); __i != __e; ++__i)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002749 __alloc_traits::destroy(__a, _VSTD::addressof(*__i));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002750 __base::size() -= __n;
2751 while (__back_spare() >= 2 * __base::__block_size)
2752 {
2753 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
2754 __base::__map_.pop_back();
2755 }
2756 }
2757 }
2758 return __base::begin() + __pos;
2759}
2760
2761template <class _Tp, class _Allocator>
2762void
2763deque<_Tp, _Allocator>::__erase_to_end(const_iterator __f)
2764{
2765 iterator __e = __base::end();
2766 difference_type __n = __e - __f;
2767 if (__n > 0)
2768 {
2769 allocator_type& __a = __base::__alloc();
2770 iterator __b = __base::begin();
2771 difference_type __pos = __f - __b;
2772 for (iterator __p = __b + __pos; __p != __e; ++__p)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002773 __alloc_traits::destroy(__a, _VSTD::addressof(*__p));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002774 __base::size() -= __n;
2775 while (__back_spare() >= 2 * __base::__block_size)
2776 {
2777 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
2778 __base::__map_.pop_back();
2779 }
2780 }
2781}
2782
2783template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00002784inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002785void
2786deque<_Tp, _Allocator>::swap(deque& __c)
Marshall Clow8982dcd2015-07-13 20:04:56 +00002787#if _LIBCPP_STD_VER >= 14
2788 _NOEXCEPT
2789#else
2790 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
2791 __is_nothrow_swappable<allocator_type>::value)
2792#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00002793{
2794 __base::swap(__c);
2795}
2796
2797template <class _Tp, class _Allocator>
Howard Hinnant874ad9a2010-09-21 21:28:23 +00002798inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002799void
Howard Hinnantda2df912011-06-02 16:10:22 +00002800deque<_Tp, _Allocator>::clear() _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00002801{
2802 __base::clear();
2803}
2804
2805template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00002806inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002807bool
2808operator==(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2809{
2810 const typename deque<_Tp, _Allocator>::size_type __sz = __x.size();
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002811 return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantc51e1022010-05-11 19:42:16 +00002812}
2813
2814template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00002815inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002816bool
2817operator!=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2818{
2819 return !(__x == __y);
2820}
2821
2822template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00002823inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002824bool
2825operator< (const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2826{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002827 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00002828}
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 return __y < __x;
2836}
2837
2838template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00002839inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002840bool
2841operator>=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2842{
2843 return !(__x < __y);
2844}
2845
2846template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00002847inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002848bool
2849operator<=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y)
2850{
2851 return !(__y < __x);
2852}
2853
2854template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00002855inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002856void
2857swap(deque<_Tp, _Allocator>& __x, deque<_Tp, _Allocator>& __y)
Howard Hinnantca2fc222011-06-02 20:00:14 +00002858 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantc51e1022010-05-11 19:42:16 +00002859{
2860 __x.swap(__y);
2861}
2862
2863_LIBCPP_END_NAMESPACE_STD
2864
2865#endif // _LIBCPP_DEQUE