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