API tools faq
paste
Guest User

Untitled

a guest
Apr 20th, 2018
57
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 106.79 KB | None | 0 0
raw download clone embed print report
  1. // -*- C++ -*-
  2. //===------------------------------ vector --------------------------------===//
  3. //
  4. // The LLVM Compiler Infrastructure
  5. //
  6. // This file is dual licensed under the MIT and the University of Illinois Open
  7. // Source Licenses. See LICENSE.TXT for details.
  8. //
  9. //===----------------------------------------------------------------------===//
  10.  
  11. #ifndef _LIBCPP_VECTOR
  12. #define _LIBCPP_VECTOR
  13.  
  14. /*
  15. vector synopsis
  16.  
  17. namespace std
  18. {
  19.  
  20. template <class T, class Allocator = allocator<T> >
  21. class vector
  22. {
  23. public:
  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. vector()
  38. noexcept(is_nothrow_default_constructible<allocator_type>::value);
  39. explicit vector(const allocator_type&);
  40. explicit vector(size_type n);
  41. explicit vector(size_type n, const allocator_type&); // C++14
  42. vector(size_type n, const value_type& value, const allocator_type& = allocator_type());
  43. template <class InputIterator>
  44. vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type());
  45. vector(const vector& x);
  46. vector(vector&& x)
  47. noexcept(is_nothrow_move_constructible<allocator_type>::value);
  48. vector(initializer_list<value_type> il);
  49. vector(initializer_list<value_type> il, const allocator_type& a);
  50. ~vector();
  51. vector& operator=(const vector& x);
  52. vector& operator=(vector&& x)
  53. noexcept(
  54. allocator_type::propagate_on_container_move_assignment::value ||
  55. allocator_type::is_always_equal::value); // C++17
  56. vector& operator=(initializer_list<value_type> il);
  57. template <class InputIterator>
  58. void assign(InputIterator first, InputIterator last);
  59. void assign(size_type n, const value_type& u);
  60. void assign(initializer_list<value_type> il);
  61.  
  62. allocator_type get_allocator() const noexcept;
  63.  
  64. iterator begin() noexcept;
  65. const_iterator begin() const noexcept;
  66. iterator end() noexcept;
  67. const_iterator end() const noexcept;
  68.  
  69. reverse_iterator rbegin() noexcept;
  70. const_reverse_iterator rbegin() const noexcept;
  71. reverse_iterator rend() noexcept;
  72. const_reverse_iterator rend() const noexcept;
  73.  
  74. const_iterator cbegin() const noexcept;
  75. const_iterator cend() const noexcept;
  76. const_reverse_iterator crbegin() const noexcept;
  77. const_reverse_iterator crend() const noexcept;
  78.  
  79. size_type size() const noexcept;
  80. size_type max_size() const noexcept;
  81. size_type capacity() const noexcept;
  82. bool empty() const noexcept;
  83. void reserve(size_type n);
  84. void shrink_to_fit() noexcept;
  85.  
  86. reference operator[](size_type n);
  87. const_reference operator[](size_type n) const;
  88. reference at(size_type n);
  89. const_reference at(size_type n) const;
  90.  
  91. reference front();
  92. const_reference front() const;
  93. reference back();
  94. const_reference back() const;
  95.  
  96. value_type* data() noexcept;
  97. const value_type* data() const noexcept;
  98.  
  99. void push_back(const value_type& x);
  100. void push_back(value_type&& x);
  101. template <class... Args>
  102. reference emplace_back(Args&&... args); // reference in C++17
  103. void pop_back();
  104.  
  105. template <class... Args> iterator emplace(const_iterator position, Args&&... args);
  106. iterator insert(const_iterator position, const value_type& x);
  107. iterator insert(const_iterator position, value_type&& x);
  108. iterator insert(const_iterator position, size_type n, const value_type& x);
  109. template <class InputIterator>
  110. iterator insert(const_iterator position, InputIterator first, InputIterator last);
  111. iterator insert(const_iterator position, initializer_list<value_type> il);
  112.  
  113. iterator erase(const_iterator position);
  114. iterator erase(const_iterator first, const_iterator last);
  115.  
  116. void clear() noexcept;
  117.  
  118. void resize(size_type sz);
  119. void resize(size_type sz, const value_type& c);
  120.  
  121. void swap(vector&)
  122. noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value ||
  123. allocator_traits<allocator_type>::is_always_equal::value); // C++17
  124.  
  125. bool __invariants() const;
  126. };
  127.  
  128. template <class Allocator = allocator<T> >
  129. class vector<bool, Allocator>
  130. {
  131. public:
  132. typedef bool value_type;
  133. typedef Allocator allocator_type;
  134. typedef implementation-defined iterator;
  135. typedef implementation-defined const_iterator;
  136. typedef typename allocator_type::size_type size_type;
  137. typedef typename allocator_type::difference_type difference_type;
  138. typedef iterator pointer;
  139. typedef const_iterator const_pointer;
  140. typedef std::reverse_iterator<iterator> reverse_iterator;
  141. typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  142.  
  143. class reference
  144. {
  145. public:
  146. reference(const reference&) noexcept;
  147. operator bool() const noexcept;
  148. reference& operator=(const bool x) noexcept;
  149. reference& operator=(const reference& x) noexcept;
  150. iterator operator&() const noexcept;
  151. void flip() noexcept;
  152. };
  153.  
  154. class const_reference
  155. {
  156. public:
  157. const_reference(const reference&) noexcept;
  158. operator bool() const noexcept;
  159. const_iterator operator&() const noexcept;
  160. };
  161.  
  162. vector()
  163. noexcept(is_nothrow_default_constructible<allocator_type>::value);
  164. explicit vector(const allocator_type&);
  165. explicit vector(size_type n, const allocator_type& a = allocator_type()); // C++14
  166. vector(size_type n, const value_type& value, const allocator_type& = allocator_type());
  167. template <class InputIterator>
  168. vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type());
  169. vector(const vector& x);
  170. vector(vector&& x)
  171. noexcept(is_nothrow_move_constructible<allocator_type>::value);
  172. vector(initializer_list<value_type> il);
  173. vector(initializer_list<value_type> il, const allocator_type& a);
  174. ~vector();
  175. vector& operator=(const vector& x);
  176. vector& operator=(vector&& x)
  177. noexcept(
  178. allocator_type::propagate_on_container_move_assignment::value ||
  179. allocator_type::is_always_equal::value); // C++17
  180. vector& operator=(initializer_list<value_type> il);
  181. template <class InputIterator>
  182. void assign(InputIterator first, InputIterator last);
  183. void assign(size_type n, const value_type& u);
  184. void assign(initializer_list<value_type> il);
  185.  
  186. allocator_type get_allocator() const noexcept;
  187.  
  188. iterator begin() noexcept;
  189. const_iterator begin() const noexcept;
  190. iterator end() noexcept;
  191. const_iterator end() const noexcept;
  192.  
  193. reverse_iterator rbegin() noexcept;
  194. const_reverse_iterator rbegin() const noexcept;
  195. reverse_iterator rend() noexcept;
  196. const_reverse_iterator rend() const noexcept;
  197.  
  198. const_iterator cbegin() const noexcept;
  199. const_iterator cend() const noexcept;
  200. const_reverse_iterator crbegin() const noexcept;
  201. const_reverse_iterator crend() const noexcept;
  202.  
  203. size_type size() const noexcept;
  204. size_type max_size() const noexcept;
  205. size_type capacity() const noexcept;
  206. bool empty() const noexcept;
  207. void reserve(size_type n);
  208. void shrink_to_fit() noexcept;
  209.  
  210. reference operator[](size_type n);
  211. const_reference operator[](size_type n) const;
  212. reference at(size_type n);
  213. const_reference at(size_type n) const;
  214.  
  215. reference front();
  216. const_reference front() const;
  217. reference back();
  218. const_reference back() const;
  219.  
  220. void push_back(const value_type& x);
  221. template <class... Args> reference emplace_back(Args&&... args); // C++14; reference in C++17
  222. void pop_back();
  223.  
  224. template <class... Args> iterator emplace(const_iterator position, Args&&... args); // C++14
  225. iterator insert(const_iterator position, const value_type& x);
  226. iterator insert(const_iterator position, size_type n, const value_type& x);
  227. template <class InputIterator>
  228. iterator insert(const_iterator position, InputIterator first, InputIterator last);
  229. iterator insert(const_iterator position, initializer_list<value_type> il);
  230.  
  231. iterator erase(const_iterator position);
  232. iterator erase(const_iterator first, const_iterator last);
  233.  
  234. void clear() noexcept;
  235.  
  236. void resize(size_type sz);
  237. void resize(size_type sz, value_type x);
  238.  
  239. void swap(vector&)
  240. noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value ||
  241. allocator_traits<allocator_type>::is_always_equal::value); // C++17
  242. void flip() noexcept;
  243.  
  244. bool __invariants() const;
  245. };
  246.  
  247. template <class Allocator> struct hash<std::vector<bool, Allocator>>;
  248.  
  249. template <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
  250. template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
  251. template <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
  252. template <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
  253. template <class T, class Allocator> bool operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
  254. template <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
  255.  
  256. template <class T, class Allocator>
  257. void swap(vector<T,Allocator>& x, vector<T,Allocator>& y)
  258. noexcept(noexcept(x.swap(y)));
  259.  
  260. } // std
  261.  
  262. */
  263.  
  264. #include <__config>
  265. #include <iosfwd> // for forward declaration of vector
  266. #include <__bit_reference>
  267. #include <type_traits>
  268. #include <climits>
  269. #include <limits>
  270. #include <initializer_list>
  271. #include <memory>
  272. #include <stdexcept>
  273. #include <algorithm>
  274. #include <cstring>
  275. #include <__split_buffer>
  276. #include <__functional_base>
  277.  
  278. #include <__debug>
  279.  
  280. #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  281. #pragma GCC system_header
  282. #endif
  283.  
  284. _LIBCPP_PUSH_MACROS
  285. #include <__undef_macros>
  286.  
  287.  
  288. _LIBCPP_BEGIN_NAMESPACE_STD
  289.  
  290. template <bool>
  291. class __vector_base_common
  292. {
  293. protected:
  294. _LIBCPP_ALWAYS_INLINE __vector_base_common() {}
  295. _LIBCPP_NORETURN void __throw_length_error() const;
  296. _LIBCPP_NORETURN void __throw_out_of_range() const;
  297. };
  298.  
  299. template <bool __b>
  300. void
  301. __vector_base_common<__b>::__throw_length_error() const
  302. {
  303. _VSTD::__throw_length_error("vector");
  304. }
  305.  
  306. template <bool __b>
  307. void
  308. __vector_base_common<__b>::__throw_out_of_range() const
  309. {
  310. _VSTD::__throw_out_of_range("vector");
  311. }
  312.  
  313. _LIBCPP_EXTERN_TEMPLATE(class _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS __vector_base_common<true>)
  314.  
  315. template <class _Tp, class _Allocator>
  316. class __vector_base
  317. : protected __vector_base_common<true>
  318. {
  319. protected:
  320. typedef _Tp value_type;
  321. typedef _Allocator allocator_type;
  322. typedef allocator_traits<allocator_type> __alloc_traits;
  323. typedef value_type& reference;
  324. typedef const value_type& const_reference;
  325. typedef typename __alloc_traits::size_type size_type;
  326. typedef typename __alloc_traits::difference_type difference_type;
  327. typedef typename __alloc_traits::pointer pointer;
  328. typedef typename __alloc_traits::const_pointer const_pointer;
  329. typedef pointer iterator;
  330. typedef const_pointer const_iterator;
  331.  
  332. pointer __begin_;
  333. pointer __end_;
  334. __compressed_pair<pointer, allocator_type> __end_cap_;
  335.  
  336. _LIBCPP_INLINE_VISIBILITY
  337. allocator_type& __alloc() _NOEXCEPT
  338. {return __end_cap_.second();}
  339. _LIBCPP_INLINE_VISIBILITY
  340. const allocator_type& __alloc() const _NOEXCEPT
  341. {return __end_cap_.second();}
  342. _LIBCPP_INLINE_VISIBILITY
  343. pointer& __end_cap() _NOEXCEPT
  344. {return __end_cap_.first();}
  345. _LIBCPP_INLINE_VISIBILITY
  346. const pointer& __end_cap() const _NOEXCEPT
  347. {return __end_cap_.first();}
  348.  
  349. _LIBCPP_INLINE_VISIBILITY
  350. __vector_base()
  351. _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
  352. _LIBCPP_INLINE_VISIBILITY __vector_base(const allocator_type& __a);
  353. ~__vector_base();
  354.  
  355. _LIBCPP_INLINE_VISIBILITY
  356. void clear() _NOEXCEPT {__destruct_at_end(__begin_);}
  357. _LIBCPP_INLINE_VISIBILITY
  358. size_type capacity() const _NOEXCEPT
  359. {return static_cast<size_type>(__end_cap() - __begin_);}
  360.  
  361. _LIBCPP_INLINE_VISIBILITY
  362. void __destruct_at_end(pointer __new_last) _NOEXCEPT;
  363.  
  364. _LIBCPP_INLINE_VISIBILITY
  365. void __copy_assign_alloc(const __vector_base& __c)
  366. {__copy_assign_alloc(__c, integral_constant<bool,
  367. __alloc_traits::propagate_on_container_copy_assignment::value>());}
  368.  
  369. _LIBCPP_INLINE_VISIBILITY
  370. void __move_assign_alloc(__vector_base& __c)
  371. _NOEXCEPT_(
  372. !__alloc_traits::propagate_on_container_move_assignment::value ||
  373. is_nothrow_move_assignable<allocator_type>::value)
  374. {__move_assign_alloc(__c, integral_constant<bool,
  375. __alloc_traits::propagate_on_container_move_assignment::value>());}
  376. private:
  377. _LIBCPP_INLINE_VISIBILITY
  378. void __copy_assign_alloc(const __vector_base& __c, true_type)
  379. {
  380. if (__alloc() != __c.__alloc())
  381. {
  382. clear();
  383. __alloc_traits::deallocate(__alloc(), __begin_, capacity());
  384. __begin_ = __end_ = __end_cap() = nullptr;
  385. }
  386. __alloc() = __c.__alloc();
  387. }
  388.  
  389. _LIBCPP_INLINE_VISIBILITY
  390. void __copy_assign_alloc(const __vector_base&, false_type)
  391. {}
  392.  
  393. _LIBCPP_INLINE_VISIBILITY
  394. void __move_assign_alloc(__vector_base& __c, true_type)
  395. _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
  396. {
  397. __alloc() = _VSTD::move(__c.__alloc());
  398. }
  399.  
  400. _LIBCPP_INLINE_VISIBILITY
  401. void __move_assign_alloc(__vector_base&, false_type)
  402. _NOEXCEPT
  403. {}
  404. };
  405.  
  406. template <class _Tp, class _Allocator>
  407. inline _LIBCPP_INLINE_VISIBILITY
  408. void
  409. __vector_base<_Tp, _Allocator>::__destruct_at_end(pointer __new_last) _NOEXCEPT
  410. {
  411. pointer __soon_to_be_end = __end_;
  412. while (__new_last != __soon_to_be_end)
  413. __alloc_traits::destroy(__alloc(), _VSTD::__to_raw_pointer(--__soon_to_be_end));
  414. __end_ = __new_last;
  415. }
  416.  
  417. template <class _Tp, class _Allocator>
  418. inline _LIBCPP_INLINE_VISIBILITY
  419. __vector_base<_Tp, _Allocator>::__vector_base()
  420. _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
  421. : __begin_(nullptr),
  422. __end_(nullptr),
  423. __end_cap_(nullptr)
  424. {
  425. }
  426.  
  427. template <class _Tp, class _Allocator>
  428. inline _LIBCPP_INLINE_VISIBILITY
  429. __vector_base<_Tp, _Allocator>::__vector_base(const allocator_type& __a)
  430. : __begin_(nullptr),
  431. __end_(nullptr),
  432. __end_cap_(nullptr, __a)
  433. {
  434. }
  435.  
  436. template <class _Tp, class _Allocator>
  437. __vector_base<_Tp, _Allocator>::~__vector_base()
  438. {
  439. if (__begin_ != nullptr)
  440. {
  441. clear();
  442. __alloc_traits::deallocate(__alloc(), __begin_, capacity());
  443. }
  444. }
  445.  
  446. template <class _Tp, class _Allocator /* = allocator<_Tp> */>
  447. class _LIBCPP_TEMPLATE_VIS vector
  448. : private __vector_base<_Tp, _Allocator>
  449. {
  450. private:
  451. typedef __vector_base<_Tp, _Allocator> __base;
  452. typedef allocator<_Tp> __default_allocator_type;
  453. public:
  454. typedef vector __self;
  455. typedef _Tp value_type;
  456. typedef _Allocator allocator_type;
  457. typedef typename __base::__alloc_traits __alloc_traits;
  458. typedef typename __base::reference reference;
  459. typedef typename __base::const_reference const_reference;
  460. typedef typename __base::size_type size_type;
  461. typedef typename __base::difference_type difference_type;
  462. typedef typename __base::pointer pointer;
  463. typedef typename __base::const_pointer const_pointer;
  464. typedef __wrap_iter<pointer> iterator;
  465. typedef __wrap_iter<const_pointer> const_iterator;
  466. typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
  467. typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
  468.  
  469. static_assert((is_same<typename allocator_type::value_type, value_type>::value),
  470. "Allocator::value_type must be same type as value_type");
  471.  
  472. _LIBCPP_INLINE_VISIBILITY
  473. vector() _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
  474. {
  475. #if _LIBCPP_DEBUG_LEVEL >= 2
  476. __get_db()->__insert_c(this);
  477. #endif
  478. }
  479. _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a)
  480. #if _LIBCPP_STD_VER <= 14
  481. _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
  482. #else
  483. _NOEXCEPT
  484. #endif
  485. : __base(__a)
  486. {
  487. #if _LIBCPP_DEBUG_LEVEL >= 2
  488. __get_db()->__insert_c(this);
  489. #endif
  490. }
  491. explicit vector(size_type __n);
  492. #if _LIBCPP_STD_VER > 11
  493. explicit vector(size_type __n, const allocator_type& __a);
  494. #endif
  495. vector(size_type __n, const_reference __x);
  496. vector(size_type __n, const_reference __x, const allocator_type& __a);
  497. template <class _InputIterator>
  498. vector(_InputIterator __first,
  499. typename enable_if<__is_input_iterator <_InputIterator>::value &&
  500. !__is_forward_iterator<_InputIterator>::value &&
  501. is_constructible<
  502. value_type,
  503. typename iterator_traits<_InputIterator>::reference>::value,
  504. _InputIterator>::type __last);
  505. template <class _InputIterator>
  506. vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
  507. typename enable_if<__is_input_iterator <_InputIterator>::value &&
  508. !__is_forward_iterator<_InputIterator>::value &&
  509. is_constructible<
  510. value_type,
  511. typename iterator_traits<_InputIterator>::reference>::value>::type* = 0);
  512. template <class _ForwardIterator>
  513. vector(_ForwardIterator __first,
  514. typename enable_if<__is_forward_iterator<_ForwardIterator>::value &&
  515. is_constructible<
  516. value_type,
  517. typename iterator_traits<_ForwardIterator>::reference>::value,
  518. _ForwardIterator>::type __last);
  519. template <class _ForwardIterator>
  520. vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
  521. typename enable_if<__is_forward_iterator<_ForwardIterator>::value &&
  522. is_constructible<
  523. value_type,
  524. typename iterator_traits<_ForwardIterator>::reference>::value>::type* = 0);
  525.  
  526. #if _LIBCPP_DEBUG_LEVEL >= 2
  527. _LIBCPP_INLINE_VISIBILITY
  528. ~vector()
  529. {
  530. __get_db()->__erase_c(this);
  531. }
  532. #endif
  533.  
  534. vector(const vector& __x);
  535. vector(const vector& __x, const allocator_type& __a);
  536. _LIBCPP_INLINE_VISIBILITY
  537. vector& operator=(const vector& __x);
  538.  
  539. #ifndef _LIBCPP_CXX03_LANG
  540. _LIBCPP_INLINE_VISIBILITY
  541. vector(initializer_list<value_type> __il);
  542.  
  543. _LIBCPP_INLINE_VISIBILITY
  544. vector(initializer_list<value_type> __il, const allocator_type& __a);
  545.  
  546. _LIBCPP_INLINE_VISIBILITY
  547. vector(vector&& __x)
  548. #if _LIBCPP_STD_VER > 14
  549. _NOEXCEPT;
  550. #else
  551. _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
  552. #endif
  553.  
  554. _LIBCPP_INLINE_VISIBILITY
  555. vector(vector&& __x, const allocator_type& __a);
  556. _LIBCPP_INLINE_VISIBILITY
  557. vector& operator=(vector&& __x)
  558. _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value));
  559.  
  560. _LIBCPP_INLINE_VISIBILITY
  561. vector& operator=(initializer_list<value_type> __il)
  562. {assign(__il.begin(), __il.end()); return *this;}
  563.  
  564. #endif // !_LIBCPP_CXX03_LANG
  565.  
  566. template <class _InputIterator>
  567. typename enable_if
  568. <
  569. __is_input_iterator <_InputIterator>::value &&
  570. !__is_forward_iterator<_InputIterator>::value &&
  571. is_constructible<
  572. value_type,
  573. typename iterator_traits<_InputIterator>::reference>::value,
  574. void
  575. >::type
  576. assign(_InputIterator __first, _InputIterator __last);
  577. template <class _ForwardIterator>
  578. typename enable_if
  579. <
  580. __is_forward_iterator<_ForwardIterator>::value &&
  581. is_constructible<
  582. value_type,
  583. typename iterator_traits<_ForwardIterator>::reference>::value,
  584. void
  585. >::type
  586. assign(_ForwardIterator __first, _ForwardIterator __last);
  587.  
  588. void assign(size_type __n, const_reference __u);
  589.  
  590. #ifndef _LIBCPP_CXX03_LANG
  591. _LIBCPP_INLINE_VISIBILITY
  592. void assign(initializer_list<value_type> __il)
  593. {assign(__il.begin(), __il.end());}
  594. #endif
  595.  
  596. _LIBCPP_INLINE_VISIBILITY
  597. allocator_type get_allocator() const _NOEXCEPT
  598. {return this->__alloc();}
  599.  
  600. _LIBCPP_INLINE_VISIBILITY iterator begin() _NOEXCEPT;
  601. _LIBCPP_INLINE_VISIBILITY const_iterator begin() const _NOEXCEPT;
  602. _LIBCPP_INLINE_VISIBILITY iterator end() _NOEXCEPT;
  603. _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT;
  604.  
  605. _LIBCPP_INLINE_VISIBILITY
  606. reverse_iterator rbegin() _NOEXCEPT
  607. {return reverse_iterator(end());}
  608. _LIBCPP_INLINE_VISIBILITY
  609. const_reverse_iterator rbegin() const _NOEXCEPT
  610. {return const_reverse_iterator(end());}
  611. _LIBCPP_INLINE_VISIBILITY
  612. reverse_iterator rend() _NOEXCEPT
  613. {return reverse_iterator(begin());}
  614. _LIBCPP_INLINE_VISIBILITY
  615. const_reverse_iterator rend() const _NOEXCEPT
  616. {return const_reverse_iterator(begin());}
  617.  
  618. _LIBCPP_INLINE_VISIBILITY
  619. const_iterator cbegin() const _NOEXCEPT
  620. {return begin();}
  621. _LIBCPP_INLINE_VISIBILITY
  622. const_iterator cend() const _NOEXCEPT
  623. {return end();}
  624. _LIBCPP_INLINE_VISIBILITY
  625. const_reverse_iterator crbegin() const _NOEXCEPT
  626. {return rbegin();}
  627. _LIBCPP_INLINE_VISIBILITY
  628. const_reverse_iterator crend() const _NOEXCEPT
  629. {return rend();}
  630.  
  631. _LIBCPP_INLINE_VISIBILITY
  632. size_type size() const _NOEXCEPT
  633. {return static_cast<size_type>(this->__end_ - this->__begin_);}
  634. _LIBCPP_INLINE_VISIBILITY
  635. size_type capacity() const _NOEXCEPT
  636. {return __base::capacity();}
  637. _LIBCPP_INLINE_VISIBILITY
  638. bool empty() const _NOEXCEPT
  639. {return this->__begin_ == this->__end_;}
  640. size_type max_size() const _NOEXCEPT;
  641. void reserve(size_type __n);
  642. void shrink_to_fit() _NOEXCEPT;
  643.  
  644. _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n);
  645. _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const;
  646. reference at(size_type __n);
  647. const_reference at(size_type __n) const;
  648.  
  649. _LIBCPP_INLINE_VISIBILITY reference front()
  650. {
  651. _LIBCPP_ASSERT(!empty(), "front() called for empty vector");
  652. return *this->__begin_;
  653. }
  654. _LIBCPP_INLINE_VISIBILITY const_reference front() const
  655. {
  656. _LIBCPP_ASSERT(!empty(), "front() called for empty vector");
  657. return *this->__begin_;
  658. }
  659. _LIBCPP_INLINE_VISIBILITY reference back()
  660. {
  661. _LIBCPP_ASSERT(!empty(), "back() called for empty vector");
  662. return *(this->__end_ - 1);
  663. }
  664. _LIBCPP_INLINE_VISIBILITY const_reference back() const
  665. {
  666. _LIBCPP_ASSERT(!empty(), "back() called for empty vector");
  667. return *(this->__end_ - 1);
  668. }
  669.  
  670. _LIBCPP_INLINE_VISIBILITY
  671. value_type* data() _NOEXCEPT
  672. {return _VSTD::__to_raw_pointer(this->__begin_);}
  673. _LIBCPP_INLINE_VISIBILITY
  674. const value_type* data() const _NOEXCEPT
  675. {return _VSTD::__to_raw_pointer(this->__begin_);}
  676.  
  677. _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x);
  678.  
  679. #ifndef _LIBCPP_CXX03_LANG
  680. _LIBCPP_INLINE_VISIBILITY void push_back(value_type&& __x);
  681.  
  682. template <class... _Args>
  683. _LIBCPP_INLINE_VISIBILITY
  684. #if _LIBCPP_STD_VER > 14
  685. reference emplace_back(_Args&&... __args);
  686. #else
  687. void emplace_back(_Args&&... __args);
  688. #endif
  689. #endif // !_LIBCPP_CXX03_LANG
  690.  
  691. _LIBCPP_INLINE_VISIBILITY
  692. void pop_back();
  693.  
  694. iterator insert(const_iterator __position, const_reference __x);
  695.  
  696. #ifndef _LIBCPP_CXX03_LANG
  697. iterator insert(const_iterator __position, value_type&& __x);
  698. template <class... _Args>
  699. iterator emplace(const_iterator __position, _Args&&... __args);
  700. #endif // !_LIBCPP_CXX03_LANG
  701.  
  702. iterator insert(const_iterator __position, size_type __n, const_reference __x);
  703. template <class _InputIterator>
  704. typename enable_if
  705. <
  706. __is_input_iterator <_InputIterator>::value &&
  707. !__is_forward_iterator<_InputIterator>::value &&
  708. is_constructible<
  709. value_type,
  710. typename iterator_traits<_InputIterator>::reference>::value,
  711. iterator
  712. >::type
  713. insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
  714. template <class _ForwardIterator>
  715. typename enable_if
  716. <
  717. __is_forward_iterator<_ForwardIterator>::value &&
  718. is_constructible<
  719. value_type,
  720. typename iterator_traits<_ForwardIterator>::reference>::value,
  721. iterator
  722. >::type
  723. insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
  724.  
  725. #ifndef _LIBCPP_CXX03_LANG
  726. _LIBCPP_INLINE_VISIBILITY
  727. iterator insert(const_iterator __position, initializer_list<value_type> __il)
  728. {return insert(__position, __il.begin(), __il.end());}
  729. #endif
  730.  
  731. _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position);
  732. iterator erase(const_iterator __first, const_iterator __last);
  733.  
  734. _LIBCPP_INLINE_VISIBILITY
  735. void clear() _NOEXCEPT
  736. {
  737. size_type __old_size = size();
  738. __base::clear();
  739. __annotate_shrink(__old_size);
  740. __invalidate_all_iterators();
  741. }
  742.  
  743. void resize(size_type __sz);
  744. void resize(size_type __sz, const_reference __x);
  745.  
  746. void swap(vector&)
  747. #if _LIBCPP_STD_VER >= 14
  748. _NOEXCEPT_DEBUG;
  749. #else
  750. _NOEXCEPT_DEBUG_(!__alloc_traits::propagate_on_container_swap::value ||
  751. __is_nothrow_swappable<allocator_type>::value);
  752. #endif
  753.  
  754. bool __invariants() const;
  755.  
  756. #if _LIBCPP_DEBUG_LEVEL >= 2
  757.  
  758. bool __dereferenceable(const const_iterator* __i) const;
  759. bool __decrementable(const const_iterator* __i) const;
  760. bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
  761. bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
  762.  
  763. #endif // _LIBCPP_DEBUG_LEVEL >= 2
  764.  
  765. private:
  766. _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
  767. _LIBCPP_INLINE_VISIBILITY void __invalidate_iterators_past(pointer __new_last);
  768. void allocate(size_type __n);
  769. void deallocate() _NOEXCEPT;
  770. _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const;
  771. void __construct_at_end(size_type __n);
  772. _LIBCPP_INLINE_VISIBILITY
  773. void __construct_at_end(size_type __n, const_reference __x);
  774. template <class _ForwardIterator>
  775. typename enable_if
  776. <
  777. __is_forward_iterator<_ForwardIterator>::value,
  778. void
  779. >::type
  780. __construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n);
  781. void __append(size_type __n);
  782. void __append(size_type __n, const_reference __x);
  783. _LIBCPP_INLINE_VISIBILITY
  784. iterator __make_iter(pointer __p) _NOEXCEPT;
  785. _LIBCPP_INLINE_VISIBILITY
  786. const_iterator __make_iter(const_pointer __p) const _NOEXCEPT;
  787. void __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v);
  788. pointer __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p);
  789. void __move_range(pointer __from_s, pointer __from_e, pointer __to);
  790. void __move_assign(vector& __c, true_type)
  791. _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
  792. void __move_assign(vector& __c, false_type)
  793. _NOEXCEPT_(__alloc_traits::is_always_equal::value);
  794. _LIBCPP_INLINE_VISIBILITY
  795. void __destruct_at_end(pointer __new_last) _NOEXCEPT
  796. {
  797. __invalidate_iterators_past(__new_last);
  798. size_type __old_size = size();
  799. __base::__destruct_at_end(__new_last);
  800. __annotate_shrink(__old_size);
  801. }
  802.  
  803. #ifndef _LIBCPP_CXX03_LANG
  804. template <class _Up> void __push_back_slow_path(_Up&& __x);
  805.  
  806. template <class... _Args>
  807. void __emplace_back_slow_path(_Args&&... __args);
  808. #else
  809. template <class _Up> void __push_back_slow_path(_Up& __x);
  810. #endif
  811.  
  812. // The following functions are no-ops outside of AddressSanitizer mode.
  813. // We call annotatations only for the default Allocator because other allocators
  814. // may not meet the AddressSanitizer alignment constraints.
  815. // See the documentation for __sanitizer_annotate_contiguous_container for more details.
  816. #ifndef _LIBCPP_HAS_NO_ASAN
  817. void __annotate_contiguous_container(const void *__beg, const void *__end,
  818. const void *__old_mid,
  819. const void *__new_mid) const
  820. {
  821.  
  822. if (__beg && is_same<allocator_type, __default_allocator_type>::value)
  823. __sanitizer_annotate_contiguous_container(__beg, __end, __old_mid, __new_mid);
  824. }
  825. #else
  826. _LIBCPP_INLINE_VISIBILITY
  827. void __annotate_contiguous_container(const void*, const void*, const void*,
  828. const void*) const {}
  829. #endif
  830. _LIBCPP_INLINE_VISIBILITY
  831. void __annotate_new(size_type __current_size) const {
  832. __annotate_contiguous_container(data(), data() + capacity(),
  833. data() + capacity(), data() + __current_size);
  834. }
  835.  
  836. _LIBCPP_INLINE_VISIBILITY
  837. void __annotate_delete() const {
  838. __annotate_contiguous_container(data(), data() + capacity(),
  839. data() + size(), data() + capacity());
  840. }
  841.  
  842. _LIBCPP_INLINE_VISIBILITY
  843. void __annotate_increase(size_type __n) const
  844. {
  845. __annotate_contiguous_container(data(), data() + capacity(),
  846. data() + size(), data() + size() + __n);
  847. }
  848.  
  849. _LIBCPP_INLINE_VISIBILITY
  850. void __annotate_shrink(size_type __old_size) const
  851. {
  852. __annotate_contiguous_container(data(), data() + capacity(),
  853. data() + __old_size, data() + size());
  854. }
  855. #ifndef _LIBCPP_HAS_NO_ASAN
  856. // The annotation for size increase should happen before the actual increase,
  857. // but if an exception is thrown after that the annotation has to be undone.
  858. struct __RAII_IncreaseAnnotator {
  859. __RAII_IncreaseAnnotator(const vector &__v, size_type __n = 1)
  860. : __commit(false), __v(__v), __old_size(__v.size() + __n) {
  861. __v.__annotate_increase(__n);
  862. }
  863. void __done() { __commit = true; }
  864. ~__RAII_IncreaseAnnotator() {
  865. if (__commit) return;
  866. __v.__annotate_shrink(__old_size);
  867. }
  868. bool __commit;
  869. const vector &__v;
  870. size_type __old_size;
  871. };
  872. #else
  873. struct __RAII_IncreaseAnnotator {
  874. _LIBCPP_INLINE_VISIBILITY
  875. __RAII_IncreaseAnnotator(const vector &, size_type = 1) {}
  876. _LIBCPP_INLINE_VISIBILITY void __done() {}
  877. };
  878. #endif
  879.  
  880. };
  881.  
  882. template <class _Tp, class _Allocator>
  883. void
  884. vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v)
  885. {
  886. __annotate_delete();
  887. __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, this->__end_, __v.__begin_);
  888. _VSTD::swap(this->__begin_, __v.__begin_);
  889. _VSTD::swap(this->__end_, __v.__end_);
  890. _VSTD::swap(this->__end_cap(), __v.__end_cap());
  891. __v.__first_ = __v.__begin_;
  892. __annotate_new(size());
  893. __invalidate_all_iterators();
  894. }
  895.  
  896. template <class _Tp, class _Allocator>
  897. typename vector<_Tp, _Allocator>::pointer
  898. vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p)
  899. {
  900. __annotate_delete();
  901. pointer __r = __v.__begin_;
  902. __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, __p, __v.__begin_);
  903. __alloc_traits::__construct_forward(this->__alloc(), __p, this->__end_, __v.__end_);
  904. _VSTD::swap(this->__begin_, __v.__begin_);
  905. _VSTD::swap(this->__end_, __v.__end_);
  906. _VSTD::swap(this->__end_cap(), __v.__end_cap());
  907. __v.__first_ = __v.__begin_;
  908. __annotate_new(size());
  909. __invalidate_all_iterators();
  910. return __r;
  911. }
  912.  
  913. // Allocate space for __n objects
  914. // throws length_error if __n > max_size()
  915. // throws (probably bad_alloc) if memory run out
  916. // Precondition: __begin_ == __end_ == __end_cap() == 0
  917. // Precondition: __n > 0
  918. // Postcondition: capacity() == __n
  919. // Postcondition: size() == 0
  920. template <class _Tp, class _Allocator>
  921. void
  922. vector<_Tp, _Allocator>::allocate(size_type __n)
  923. {
  924. if (__n > max_size())
  925. this->__throw_length_error();
  926. this->__begin_ = this->__end_ = __alloc_traits::allocate(this->__alloc(), __n);
  927. this->__end_cap() = this->__begin_ + __n;
  928. __annotate_new(0);
  929. }
  930.  
  931. template <class _Tp, class _Allocator>
  932. void
  933. vector<_Tp, _Allocator>::deallocate() _NOEXCEPT
  934. {
  935. if (this->__begin_ != nullptr)
  936. {
  937. clear();
  938. __alloc_traits::deallocate(this->__alloc(), this->__begin_, capacity());
  939. this->__begin_ = this->__end_ = this->__end_cap() = nullptr;
  940. }
  941. }
  942.  
  943. template <class _Tp, class _Allocator>
  944. typename vector<_Tp, _Allocator>::size_type
  945. vector<_Tp, _Allocator>::max_size() const _NOEXCEPT
  946. {
  947. return _VSTD::min<size_type>(__alloc_traits::max_size(this->__alloc()),
  948. numeric_limits<difference_type>::max());
  949. }
  950.  
  951. // Precondition: __new_size > capacity()
  952. template <class _Tp, class _Allocator>
  953. inline _LIBCPP_INLINE_VISIBILITY
  954. typename vector<_Tp, _Allocator>::size_type
  955. vector<_Tp, _Allocator>::__recommend(size_type __new_size) const
  956. {
  957. const size_type __ms = max_size();
  958. if (__new_size > __ms)
  959. this->__throw_length_error();
  960. const size_type __cap = capacity();
  961. if (__cap >= __ms / 2)
  962. return __ms;
  963. return _VSTD::max<size_type>(2*__cap, __new_size);
  964. }
  965.  
  966. // Default constructs __n objects starting at __end_
  967. // throws if construction throws
  968. // Precondition: __n > 0
  969. // Precondition: size() + __n <= capacity()
  970. // Postcondition: size() == size() + __n
  971. template <class _Tp, class _Allocator>
  972. void
  973. vector<_Tp, _Allocator>::__construct_at_end(size_type __n)
  974. {
  975. allocator_type& __a = this->__alloc();
  976. do
  977. {
  978. __RAII_IncreaseAnnotator __annotator(*this);
  979. __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_));
  980. ++this->__end_;
  981. --__n;
  982. __annotator.__done();
  983. } while (__n > 0);
  984. }
  985.  
  986. // Copy constructs __n objects starting at __end_ from __x
  987. // throws if construction throws
  988. // Precondition: __n > 0
  989. // Precondition: size() + __n <= capacity()
  990. // Postcondition: size() == old size() + __n
  991. // Postcondition: [i] == __x for all i in [size() - __n, __n)
  992. template <class _Tp, class _Allocator>
  993. inline
  994. void
  995. vector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x)
  996. {
  997. allocator_type& __a = this->__alloc();
  998. do
  999. {
  1000. __RAII_IncreaseAnnotator __annotator(*this);
  1001. __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), __x);
  1002. ++this->__end_;
  1003. --__n;
  1004. __annotator.__done();
  1005. } while (__n > 0);
  1006. }
  1007.  
  1008. template <class _Tp, class _Allocator>
  1009. template <class _ForwardIterator>
  1010. typename enable_if
  1011. <
  1012. __is_forward_iterator<_ForwardIterator>::value,
  1013. void
  1014. >::type
  1015. vector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n)
  1016. {
  1017. allocator_type& __a = this->__alloc();
  1018. __RAII_IncreaseAnnotator __annotator(*this, __n);
  1019. __alloc_traits::__construct_range_forward(__a, __first, __last, this->__end_);
  1020. __annotator.__done();
  1021. }
  1022.  
  1023. // Default constructs __n objects starting at __end_
  1024. // throws if construction throws
  1025. // Postcondition: size() == size() + __n
  1026. // Exception safety: strong.
  1027. template <class _Tp, class _Allocator>
  1028. void
  1029. vector<_Tp, _Allocator>::__append(size_type __n)
  1030. {
  1031. if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)
  1032. this->__construct_at_end(__n);
  1033. else
  1034. {
  1035. allocator_type& __a = this->__alloc();
  1036. __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
  1037. __v.__construct_at_end(__n);
  1038. __swap_out_circular_buffer(__v);
  1039. }
  1040. }
  1041.  
  1042. // Default constructs __n objects starting at __end_
  1043. // throws if construction throws
  1044. // Postcondition: size() == size() + __n
  1045. // Exception safety: strong.
  1046. template <class _Tp, class _Allocator>
  1047. void
  1048. vector<_Tp, _Allocator>::__append(size_type __n, const_reference __x)
  1049. {
  1050. if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)
  1051. this->__construct_at_end(__n, __x);
  1052. else
  1053. {
  1054. allocator_type& __a = this->__alloc();
  1055. __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
  1056. __v.__construct_at_end(__n, __x);
  1057. __swap_out_circular_buffer(__v);
  1058. }
  1059. }
  1060.  
  1061. template <class _Tp, class _Allocator>
  1062. vector<_Tp, _Allocator>::vector(size_type __n)
  1063. {
  1064. #if _LIBCPP_DEBUG_LEVEL >= 2
  1065. __get_db()->__insert_c(this);
  1066. #endif
  1067. if (__n > 0)
  1068. {
  1069. allocate(__n);
  1070. __construct_at_end(__n);
  1071. }
  1072. }
  1073.  
  1074. #if _LIBCPP_STD_VER > 11
  1075. template <class _Tp, class _Allocator>
  1076. vector<_Tp, _Allocator>::vector(size_type __n, const allocator_type& __a)
  1077. : __base(__a)
  1078. {
  1079. #if _LIBCPP_DEBUG_LEVEL >= 2
  1080. __get_db()->__insert_c(this);
  1081. #endif
  1082. if (__n > 0)
  1083. {
  1084. allocate(__n);
  1085. __construct_at_end(__n);
  1086. }
  1087. }
  1088. #endif
  1089.  
  1090. template <class _Tp, class _Allocator>
  1091. vector<_Tp, _Allocator>::vector(size_type __n, const_reference __x)
  1092. {
  1093. #if _LIBCPP_DEBUG_LEVEL >= 2
  1094. __get_db()->__insert_c(this);
  1095. #endif
  1096. if (__n > 0)
  1097. {
  1098. allocate(__n);
  1099. __construct_at_end(__n, __x);
  1100. }
  1101. }
  1102.  
  1103. template <class _Tp, class _Allocator>
  1104. vector<_Tp, _Allocator>::vector(size_type __n, const_reference __x, const allocator_type& __a)
  1105. : __base(__a)
  1106. {
  1107. #if _LIBCPP_DEBUG_LEVEL >= 2
  1108. __get_db()->__insert_c(this);
  1109. #endif
  1110. if (__n > 0)
  1111. {
  1112. allocate(__n);
  1113. __construct_at_end(__n, __x);
  1114. }
  1115. }
  1116.  
  1117. template <class _Tp, class _Allocator>
  1118. template <class _InputIterator>
  1119. vector<_Tp, _Allocator>::vector(_InputIterator __first,
  1120. typename enable_if<__is_input_iterator <_InputIterator>::value &&
  1121. !__is_forward_iterator<_InputIterator>::value &&
  1122. is_constructible<
  1123. value_type,
  1124. typename iterator_traits<_InputIterator>::reference>::value,
  1125. _InputIterator>::type __last)
  1126. {
  1127. #if _LIBCPP_DEBUG_LEVEL >= 2
  1128. __get_db()->__insert_c(this);
  1129. #endif
  1130. for (; __first != __last; ++__first)
  1131. push_back(*__first);
  1132. }
  1133.  
  1134. template <class _Tp, class _Allocator>
  1135. template <class _InputIterator>
  1136. vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
  1137. typename enable_if<__is_input_iterator <_InputIterator>::value &&
  1138. !__is_forward_iterator<_InputIterator>::value &&
  1139. is_constructible<
  1140. value_type,
  1141. typename iterator_traits<_InputIterator>::reference>::value>::type*)
  1142. : __base(__a)
  1143. {
  1144. #if _LIBCPP_DEBUG_LEVEL >= 2
  1145. __get_db()->__insert_c(this);
  1146. #endif
  1147. for (; __first != __last; ++__first)
  1148. push_back(*__first);
  1149. }
  1150.  
  1151. template <class _Tp, class _Allocator>
  1152. template <class _ForwardIterator>
  1153. vector<_Tp, _Allocator>::vector(_ForwardIterator __first,
  1154. typename enable_if<__is_forward_iterator<_ForwardIterator>::value &&
  1155. is_constructible<
  1156. value_type,
  1157. typename iterator_traits<_ForwardIterator>::reference>::value,
  1158. _ForwardIterator>::type __last)
  1159. {
  1160. #if _LIBCPP_DEBUG_LEVEL >= 2
  1161. __get_db()->__insert_c(this);
  1162. #endif
  1163. size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
  1164. if (__n > 0)
  1165. {
  1166. allocate(__n);
  1167. __construct_at_end(__first, __last, __n);
  1168. }
  1169. }
  1170.  
  1171. template <class _Tp, class _Allocator>
  1172. template <class _ForwardIterator>
  1173. vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
  1174. typename enable_if<__is_forward_iterator<_ForwardIterator>::value &&
  1175. is_constructible<
  1176. value_type,
  1177. typename iterator_traits<_ForwardIterator>::reference>::value>::type*)
  1178. : __base(__a)
  1179. {
  1180. #if _LIBCPP_DEBUG_LEVEL >= 2
  1181. __get_db()->__insert_c(this);
  1182. #endif
  1183. size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
  1184. if (__n > 0)
  1185. {
  1186. allocate(__n);
  1187. __construct_at_end(__first, __last, __n);
  1188. }
  1189. }
  1190.  
  1191. template <class _Tp, class _Allocator>
  1192. vector<_Tp, _Allocator>::vector(const vector& __x)
  1193. : __base(__alloc_traits::select_on_container_copy_construction(__x.__alloc()))
  1194. {
  1195. #if _LIBCPP_DEBUG_LEVEL >= 2
  1196. __get_db()->__insert_c(this);
  1197. #endif
  1198. size_type __n = __x.size();
  1199. if (__n > 0)
  1200. {
  1201. allocate(__n);
  1202. __construct_at_end(__x.__begin_, __x.__end_, __n);
  1203. }
  1204. }
  1205.  
  1206. template <class _Tp, class _Allocator>
  1207. vector<_Tp, _Allocator>::vector(const vector& __x, const allocator_type& __a)
  1208. : __base(__a)
  1209. {
  1210. #if _LIBCPP_DEBUG_LEVEL >= 2
  1211. __get_db()->__insert_c(this);
  1212. #endif
  1213. size_type __n = __x.size();
  1214. if (__n > 0)
  1215. {
  1216. allocate(__n);
  1217. __construct_at_end(__x.__begin_, __x.__end_, __n);
  1218. }
  1219. }
  1220.  
  1221. #ifndef _LIBCPP_CXX03_LANG
  1222.  
  1223. template <class _Tp, class _Allocator>
  1224. inline _LIBCPP_INLINE_VISIBILITY
  1225. vector<_Tp, _Allocator>::vector(vector&& __x)
  1226. #if _LIBCPP_STD_VER > 14
  1227. _NOEXCEPT
  1228. #else
  1229. _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
  1230. #endif
  1231. : __base(_VSTD::move(__x.__alloc()))
  1232. {
  1233. #if _LIBCPP_DEBUG_LEVEL >= 2
  1234. __get_db()->__insert_c(this);
  1235. __get_db()->swap(this, &__x);
  1236. #endif
  1237. this->__begin_ = __x.__begin_;
  1238. this->__end_ = __x.__end_;
  1239. this->__end_cap() = __x.__end_cap();
  1240. __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
  1241. }
  1242.  
  1243. template <class _Tp, class _Allocator>
  1244. inline _LIBCPP_INLINE_VISIBILITY
  1245. vector<_Tp, _Allocator>::vector(vector&& __x, const allocator_type& __a)
  1246. : __base(__a)
  1247. {
  1248. #if _LIBCPP_DEBUG_LEVEL >= 2
  1249. __get_db()->__insert_c(this);
  1250. #endif
  1251. if (__a == __x.__alloc())
  1252. {
  1253. this->__begin_ = __x.__begin_;
  1254. this->__end_ = __x.__end_;
  1255. this->__end_cap() = __x.__end_cap();
  1256. __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
  1257. #if _LIBCPP_DEBUG_LEVEL >= 2
  1258. __get_db()->swap(this, &__x);
  1259. #endif
  1260. }
  1261. else
  1262. {
  1263. typedef move_iterator<iterator> _Ip;
  1264. assign(_Ip(__x.begin()), _Ip(__x.end()));
  1265. }
  1266. }
  1267.  
  1268. template <class _Tp, class _Allocator>
  1269. inline _LIBCPP_INLINE_VISIBILITY
  1270. vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il)
  1271. {
  1272. #if _LIBCPP_DEBUG_LEVEL >= 2
  1273. __get_db()->__insert_c(this);
  1274. #endif
  1275. if (__il.size() > 0)
  1276. {
  1277. allocate(__il.size());
  1278. __construct_at_end(__il.begin(), __il.end(), __il.size());
  1279. }
  1280. }
  1281.  
  1282. template <class _Tp, class _Allocator>
  1283. inline _LIBCPP_INLINE_VISIBILITY
  1284. vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
  1285. : __base(__a)
  1286. {
  1287. #if _LIBCPP_DEBUG_LEVEL >= 2
  1288. __get_db()->__insert_c(this);
  1289. #endif
  1290. if (__il.size() > 0)
  1291. {
  1292. allocate(__il.size());
  1293. __construct_at_end(__il.begin(), __il.end(), __il.size());
  1294. }
  1295. }
  1296.  
  1297. template <class _Tp, class _Allocator>
  1298. inline _LIBCPP_INLINE_VISIBILITY
  1299. vector<_Tp, _Allocator>&
  1300. vector<_Tp, _Allocator>::operator=(vector&& __x)
  1301. _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value))
  1302. {
  1303. __move_assign(__x, integral_constant<bool,
  1304. __alloc_traits::propagate_on_container_move_assignment::value>());
  1305. return *this;
  1306. }
  1307.  
  1308. template <class _Tp, class _Allocator>
  1309. void
  1310. vector<_Tp, _Allocator>::__move_assign(vector& __c, false_type)
  1311. _NOEXCEPT_(__alloc_traits::is_always_equal::value)
  1312. {
  1313. if (__base::__alloc() != __c.__alloc())
  1314. {
  1315. typedef move_iterator<iterator> _Ip;
  1316. assign(_Ip(__c.begin()), _Ip(__c.end()));
  1317. }
  1318. else
  1319. __move_assign(__c, true_type());
  1320. }
  1321.  
  1322. template <class _Tp, class _Allocator>
  1323. void
  1324. vector<_Tp, _Allocator>::__move_assign(vector& __c, true_type)
  1325. _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
  1326. {
  1327. deallocate();
  1328. __base::__move_assign_alloc(__c); // this can throw
  1329. this->__begin_ = __c.__begin_;
  1330. this->__end_ = __c.__end_;
  1331. this->__end_cap() = __c.__end_cap();
  1332. __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr;
  1333. #if _LIBCPP_DEBUG_LEVEL >= 2
  1334. __get_db()->swap(this, &__c);
  1335. #endif
  1336. }
  1337.  
  1338. #endif // !_LIBCPP_CXX03_LANG
  1339.  
  1340. template <class _Tp, class _Allocator>
  1341. inline _LIBCPP_INLINE_VISIBILITY
  1342. vector<_Tp, _Allocator>&
  1343. vector<_Tp, _Allocator>::operator=(const vector& __x)
  1344. {
  1345. if (this != &__x)
  1346. {
  1347. __base::__copy_assign_alloc(__x);
  1348. assign(__x.__begin_, __x.__end_);
  1349. }
  1350. return *this;
  1351. }
  1352.  
  1353. template <class _Tp, class _Allocator>
  1354. template <class _InputIterator>
  1355. typename enable_if
  1356. <
  1357. __is_input_iterator <_InputIterator>::value &&
  1358. !__is_forward_iterator<_InputIterator>::value &&
  1359. is_constructible<
  1360. _Tp,
  1361. typename iterator_traits<_InputIterator>::reference>::value,
  1362. void
  1363. >::type
  1364. vector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
  1365. {
  1366. clear();
  1367. for (; __first != __last; ++__first)
  1368. push_back(*__first);
  1369. }
  1370.  
  1371. template <class _Tp, class _Allocator>
  1372. template <class _ForwardIterator>
  1373. typename enable_if
  1374. <
  1375. __is_forward_iterator<_ForwardIterator>::value &&
  1376. is_constructible<
  1377. _Tp,
  1378. typename iterator_traits<_ForwardIterator>::reference>::value,
  1379. void
  1380. >::type
  1381. vector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
  1382. {
  1383. size_type __new_size = static_cast<size_type>(_VSTD::distance(__first, __last));
  1384. if (__new_size <= capacity())
  1385. {
  1386. _ForwardIterator __mid = __last;
  1387. bool __growing = false;
  1388. if (__new_size > size())
  1389. {
  1390. __growing = true;
  1391. __mid = __first;
  1392. _VSTD::advance(__mid, size());
  1393. }
  1394. pointer __m = _VSTD::copy(__first, __mid, this->__begin_);
  1395. if (__growing)
  1396. __construct_at_end(__mid, __last, __new_size - size());
  1397. else
  1398. this->__destruct_at_end(__m);
  1399. }
  1400. else
  1401. {
  1402. deallocate();
  1403. allocate(__recommend(__new_size));
  1404. __construct_at_end(__first, __last, __new_size);
  1405. }
  1406. __invalidate_all_iterators();
  1407. }
  1408.  
  1409. template <class _Tp, class _Allocator>
  1410. void
  1411. vector<_Tp, _Allocator>::assign(size_type __n, const_reference __u)
  1412. {
  1413. if (__n <= capacity())
  1414. {
  1415. size_type __s = size();
  1416. _VSTD::fill_n(this->__begin_, _VSTD::min(__n, __s), __u);
  1417. if (__n > __s)
  1418. __construct_at_end(__n - __s, __u);
  1419. else
  1420. this->__destruct_at_end(this->__begin_ + __n);
  1421. }
  1422. else
  1423. {
  1424. deallocate();
  1425. allocate(__recommend(static_cast<size_type>(__n)));
  1426. __construct_at_end(__n, __u);
  1427. }
  1428. __invalidate_all_iterators();
  1429. }
  1430.  
  1431. template <class _Tp, class _Allocator>
  1432. inline _LIBCPP_INLINE_VISIBILITY
  1433. typename vector<_Tp, _Allocator>::iterator
  1434. vector<_Tp, _Allocator>::__make_iter(pointer __p) _NOEXCEPT
  1435. {
  1436. #if _LIBCPP_DEBUG_LEVEL >= 2
  1437. return iterator(this, __p);
  1438. #else
  1439. return iterator(__p);
  1440. #endif
  1441. }
  1442.  
  1443. template <class _Tp, class _Allocator>
  1444. inline _LIBCPP_INLINE_VISIBILITY
  1445. typename vector<_Tp, _Allocator>::const_iterator
  1446. vector<_Tp, _Allocator>::__make_iter(const_pointer __p) const _NOEXCEPT
  1447. {
  1448. #if _LIBCPP_DEBUG_LEVEL >= 2
  1449. return const_iterator(this, __p);
  1450. #else
  1451. return const_iterator(__p);
  1452. #endif
  1453. }
  1454.  
  1455. template <class _Tp, class _Allocator>
  1456. inline _LIBCPP_INLINE_VISIBILITY
  1457. typename vector<_Tp, _Allocator>::iterator
  1458. vector<_Tp, _Allocator>::begin() _NOEXCEPT
  1459. {
  1460. return __make_iter(this->__begin_);
  1461. }
  1462.  
  1463. template <class _Tp, class _Allocator>
  1464. inline _LIBCPP_INLINE_VISIBILITY
  1465. typename vector<_Tp, _Allocator>::const_iterator
  1466. vector<_Tp, _Allocator>::begin() const _NOEXCEPT
  1467. {
  1468. return __make_iter(this->__begin_);
  1469. }
  1470.  
  1471. template <class _Tp, class _Allocator>
  1472. inline _LIBCPP_INLINE_VISIBILITY
  1473. typename vector<_Tp, _Allocator>::iterator
  1474. vector<_Tp, _Allocator>::end() _NOEXCEPT
  1475. {
  1476. return __make_iter(this->__end_);
  1477. }
  1478.  
  1479. template <class _Tp, class _Allocator>
  1480. inline _LIBCPP_INLINE_VISIBILITY
  1481. typename vector<_Tp, _Allocator>::const_iterator
  1482. vector<_Tp, _Allocator>::end() const _NOEXCEPT
  1483. {
  1484. return __make_iter(this->__end_);
  1485. }
  1486.  
  1487. template <class _Tp, class _Allocator>
  1488. inline _LIBCPP_INLINE_VISIBILITY
  1489. typename vector<_Tp, _Allocator>::reference
  1490. vector<_Tp, _Allocator>::operator[](size_type __n)
  1491. {
  1492. _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds");
  1493. return this->__begin_[__n];
  1494. }
  1495.  
  1496. template <class _Tp, class _Allocator>
  1497. inline _LIBCPP_INLINE_VISIBILITY
  1498. typename vector<_Tp, _Allocator>::const_reference
  1499. vector<_Tp, _Allocator>::operator[](size_type __n) const
  1500. {
  1501. _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds");
  1502. return this->__begin_[__n];
  1503. }
  1504.  
  1505. template <class _Tp, class _Allocator>
  1506. typename vector<_Tp, _Allocator>::reference
  1507. vector<_Tp, _Allocator>::at(size_type __n)
  1508. {
  1509. if (__n >= size())
  1510. this->__throw_out_of_range();
  1511. return this->__begin_[__n];
  1512. }
  1513.  
  1514. template <class _Tp, class _Allocator>
  1515. typename vector<_Tp, _Allocator>::const_reference
  1516. vector<_Tp, _Allocator>::at(size_type __n) const
  1517. {
  1518. if (__n >= size())
  1519. this->__throw_out_of_range();
  1520. return this->__begin_[__n];
  1521. }
  1522.  
  1523. template <class _Tp, class _Allocator>
  1524. void
  1525. vector<_Tp, _Allocator>::reserve(size_type __n)
  1526. {
  1527. if (__n > capacity())
  1528. {
  1529. allocator_type& __a = this->__alloc();
  1530. __split_buffer<value_type, allocator_type&> __v(__n, size(), __a);
  1531. __swap_out_circular_buffer(__v);
  1532. }
  1533. }
  1534.  
  1535. template <class _Tp, class _Allocator>
  1536. void
  1537. vector<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
  1538. {
  1539. if (capacity() > size())
  1540. {
  1541. #ifndef _LIBCPP_NO_EXCEPTIONS
  1542. try
  1543. {
  1544. #endif // _LIBCPP_NO_EXCEPTIONS
  1545. allocator_type& __a = this->__alloc();
  1546. __split_buffer<value_type, allocator_type&> __v(size(), size(), __a);
  1547. __swap_out_circular_buffer(__v);
  1548. #ifndef _LIBCPP_NO_EXCEPTIONS
  1549. }
  1550. catch (...)
  1551. {
  1552. }
  1553. #endif // _LIBCPP_NO_EXCEPTIONS
  1554. }
  1555. }
  1556.  
  1557. template <class _Tp, class _Allocator>
  1558. template <class _Up>
  1559. void
  1560. #ifndef _LIBCPP_CXX03_LANG
  1561. vector<_Tp, _Allocator>::__push_back_slow_path(_Up&& __x)
  1562. #else
  1563. vector<_Tp, _Allocator>::__push_back_slow_path(_Up& __x)
  1564. #endif
  1565. {
  1566. allocator_type& __a = this->__alloc();
  1567. __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
  1568. // __v.push_back(_VSTD::forward<_Up>(__x));
  1569. __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__v.__end_), _VSTD::forward<_Up>(__x));
  1570. __v.__end_++;
  1571. __swap_out_circular_buffer(__v);
  1572. }
  1573.  
  1574. template <class _Tp, class _Allocator>
  1575. inline _LIBCPP_INLINE_VISIBILITY
  1576. void
  1577. vector<_Tp, _Allocator>::push_back(const_reference __x)
  1578. {
  1579. if (this->__end_ != this->__end_cap())
  1580. {
  1581. __RAII_IncreaseAnnotator __annotator(*this);
  1582. __alloc_traits::construct(this->__alloc(),
  1583. _VSTD::__to_raw_pointer(this->__end_), __x);
  1584. __annotator.__done();
  1585. ++this->__end_;
  1586. }
  1587. else
  1588. __push_back_slow_path(__x);
  1589. }
  1590.  
  1591. #ifndef _LIBCPP_CXX03_LANG
  1592.  
  1593. template <class _Tp, class _Allocator>
  1594. inline _LIBCPP_INLINE_VISIBILITY
  1595. void
  1596. vector<_Tp, _Allocator>::push_back(value_type&& __x)
  1597. {
  1598. if (this->__end_ < this->__end_cap())
  1599. {
  1600. __RAII_IncreaseAnnotator __annotator(*this);
  1601. __alloc_traits::construct(this->__alloc(),
  1602. _VSTD::__to_raw_pointer(this->__end_),
  1603. _VSTD::move(__x));
  1604. __annotator.__done();
  1605. ++this->__end_;
  1606. }
  1607. else
  1608. __push_back_slow_path(_VSTD::move(__x));
  1609. }
  1610.  
  1611. template <class _Tp, class _Allocator>
  1612. template <class... _Args>
  1613. void
  1614. vector<_Tp, _Allocator>::__emplace_back_slow_path(_Args&&... __args)
  1615. {
  1616. allocator_type& __a = this->__alloc();
  1617. __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
  1618. // __v.emplace_back(_VSTD::forward<_Args>(__args)...);
  1619. __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__v.__end_), _VSTD::forward<_Args>(__args)...);
  1620. __v.__end_++;
  1621. __swap_out_circular_buffer(__v);
  1622. }
  1623.  
  1624. template <class _Tp, class _Allocator>
  1625. template <class... _Args>
  1626. inline
  1627. #if _LIBCPP_STD_VER > 14
  1628. typename vector<_Tp, _Allocator>::reference
  1629. #else
  1630. void
  1631. #endif
  1632. vector<_Tp, _Allocator>::emplace_back(_Args&&... __args)
  1633. {
  1634. if (this->__end_ < this->__end_cap())
  1635. {
  1636. __RAII_IncreaseAnnotator __annotator(*this);
  1637. __alloc_traits::construct(this->__alloc(),
  1638. _VSTD::__to_raw_pointer(this->__end_),
  1639. _VSTD::forward<_Args>(__args)...);
  1640. __annotator.__done();
  1641. ++this->__end_;
  1642. }
  1643. else
  1644. __emplace_back_slow_path(_VSTD::forward<_Args>(__args)...);
  1645. #if _LIBCPP_STD_VER > 14
  1646. return this->back();
  1647. #endif
  1648. }
  1649.  
  1650. #endif // !_LIBCPP_CXX03_LANG
  1651.  
  1652. template <class _Tp, class _Allocator>
  1653. inline
  1654. void
  1655. vector<_Tp, _Allocator>::pop_back()
  1656. {
  1657. _LIBCPP_ASSERT(!empty(), "vector::pop_back called for empty vector");
  1658. this->__destruct_at_end(this->__end_ - 1);
  1659. }
  1660.  
  1661. template <class _Tp, class _Allocator>
  1662. inline _LIBCPP_INLINE_VISIBILITY
  1663. typename vector<_Tp, _Allocator>::iterator
  1664. vector<_Tp, _Allocator>::erase(const_iterator __position)
  1665. {
  1666. #if _LIBCPP_DEBUG_LEVEL >= 2
  1667. _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
  1668. "vector::erase(iterator) called with an iterator not"
  1669. " referring to this vector");
  1670. #endif
  1671. _LIBCPP_ASSERT(__position != end(),
  1672. "vector::erase(iterator) called with a non-dereferenceable iterator");
  1673. difference_type __ps = __position - cbegin();
  1674. pointer __p = this->__begin_ + __ps;
  1675. this->__destruct_at_end(_VSTD::move(__p + 1, this->__end_, __p));
  1676. this->__invalidate_iterators_past(__p-1);
  1677. iterator __r = __make_iter(__p);
  1678. return __r;
  1679. }
  1680.  
  1681. template <class _Tp, class _Allocator>
  1682. typename vector<_Tp, _Allocator>::iterator
  1683. vector<_Tp, _Allocator>::erase(const_iterator __first, const_iterator __last)
  1684. {
  1685. #if _LIBCPP_DEBUG_LEVEL >= 2
  1686. _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this,
  1687. "vector::erase(iterator, iterator) called with an iterator not"
  1688. " referring to this vector");
  1689. _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__last) == this,
  1690. "vector::erase(iterator, iterator) called with an iterator not"
  1691. " referring to this vector");
  1692. #endif
  1693. _LIBCPP_ASSERT(__first <= __last, "vector::erase(first, last) called with invalid range");
  1694. pointer __p = this->__begin_ + (__first - begin());
  1695. if (__first != __last) {
  1696. this->__destruct_at_end(_VSTD::move(__p + (__last - __first), this->__end_, __p));
  1697. this->__invalidate_iterators_past(__p - 1);
  1698. }
  1699. iterator __r = __make_iter(__p);
  1700. return __r;
  1701. }
  1702.  
  1703. template <class _Tp, class _Allocator>
  1704. void
  1705. vector<_Tp, _Allocator>::__move_range(pointer __from_s, pointer __from_e, pointer __to)
  1706. {
  1707. pointer __old_last = this->__end_;
  1708. difference_type __n = __old_last - __to;
  1709. for (pointer __i = __from_s + __n; __i < __from_e; ++__i, ++this->__end_)
  1710. __alloc_traits::construct(this->__alloc(),
  1711. _VSTD::__to_raw_pointer(this->__end_),
  1712. _VSTD::move(*__i));
  1713. _VSTD::move_backward(__from_s, __from_s + __n, __old_last);
  1714. }
  1715.  
  1716. template <class _Tp, class _Allocator>
  1717. typename vector<_Tp, _Allocator>::iterator
  1718. vector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x)
  1719. {
  1720. #if _LIBCPP_DEBUG_LEVEL >= 2
  1721. _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
  1722. "vector::insert(iterator, x) called with an iterator not"
  1723. " referring to this vector");
  1724. #endif
  1725. pointer __p = this->__begin_ + (__position - begin());
  1726. if (this->__end_ < this->__end_cap())
  1727. {
  1728. __RAII_IncreaseAnnotator __annotator(*this);
  1729. if (__p == this->__end_)
  1730. {
  1731. __alloc_traits::construct(this->__alloc(),
  1732. _VSTD::__to_raw_pointer(this->__end_), __x);
  1733. ++this->__end_;
  1734. }
  1735. else
  1736. {
  1737. __move_range(__p, this->__end_, __p + 1);
  1738. const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
  1739. if (__p <= __xr && __xr < this->__end_)
  1740. ++__xr;
  1741. *__p = *__xr;
  1742. }
  1743. __annotator.__done();
  1744. }
  1745. else
  1746. {
  1747. allocator_type& __a = this->__alloc();
  1748. __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
  1749. __v.push_back(__x);
  1750. __p = __swap_out_circular_buffer(__v, __p);
  1751. }
  1752. return __make_iter(__p);
  1753. }
  1754.  
  1755. #ifndef _LIBCPP_CXX03_LANG
  1756.  
  1757. template <class _Tp, class _Allocator>
  1758. typename vector<_Tp, _Allocator>::iterator
  1759. vector<_Tp, _Allocator>::insert(const_iterator __position, value_type&& __x)
  1760. {
  1761. #if _LIBCPP_DEBUG_LEVEL >= 2
  1762. _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
  1763. "vector::insert(iterator, x) called with an iterator not"
  1764. " referring to this vector");
  1765. #endif
  1766. pointer __p = this->__begin_ + (__position - begin());
  1767. if (this->__end_ < this->__end_cap())
  1768. {
  1769. __RAII_IncreaseAnnotator __annotator(*this);
  1770. if (__p == this->__end_)
  1771. {
  1772. __alloc_traits::construct(this->__alloc(),
  1773. _VSTD::__to_raw_pointer(this->__end_),
  1774. _VSTD::move(__x));
  1775. ++this->__end_;
  1776. }
  1777. else
  1778. {
  1779. __move_range(__p, this->__end_, __p + 1);
  1780. *__p = _VSTD::move(__x);
  1781. }
  1782. __annotator.__done();
  1783. }
  1784. else
  1785. {
  1786. allocator_type& __a = this->__alloc();
  1787. __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
  1788. __v.push_back(_VSTD::move(__x));
  1789. __p = __swap_out_circular_buffer(__v, __p);
  1790. }
  1791. return __make_iter(__p);
  1792. }
  1793.  
  1794. template <class _Tp, class _Allocator>
  1795. template <class... _Args>
  1796. typename vector<_Tp, _Allocator>::iterator
  1797. vector<_Tp, _Allocator>::emplace(const_iterator __position, _Args&&... __args)
  1798. {
  1799. #if _LIBCPP_DEBUG_LEVEL >= 2
  1800. _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
  1801. "vector::emplace(iterator, x) called with an iterator not"
  1802. " referring to this vector");
  1803. #endif
  1804. pointer __p = this->__begin_ + (__position - begin());
  1805. if (this->__end_ < this->__end_cap())
  1806. {
  1807. __RAII_IncreaseAnnotator __annotator(*this);
  1808. if (__p == this->__end_)
  1809. {
  1810. __alloc_traits::construct(this->__alloc(),
  1811. _VSTD::__to_raw_pointer(this->__end_),
  1812. _VSTD::forward<_Args>(__args)...);
  1813. ++this->__end_;
  1814. }
  1815. else
  1816. {
  1817. __temp_value<value_type, _Allocator> __tmp(this->__alloc(), _VSTD::forward<_Args>(__args)...);
  1818. __move_range(__p, this->__end_, __p + 1);
  1819. *__p = _VSTD::move(__tmp.get());
  1820. }
  1821. __annotator.__done();
  1822. }
  1823. else
  1824. {
  1825. allocator_type& __a = this->__alloc();
  1826. __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
  1827. __v.emplace_back(_VSTD::forward<_Args>(__args)...);
  1828. __p = __swap_out_circular_buffer(__v, __p);
  1829. }
  1830. return __make_iter(__p);
  1831. }
  1832.  
  1833. #endif // !_LIBCPP_CXX03_LANG
  1834.  
  1835. template <class _Tp, class _Allocator>
  1836. typename vector<_Tp, _Allocator>::iterator
  1837. vector<_Tp, _Allocator>::insert(const_iterator __position, size_type __n, const_reference __x)
  1838. {
  1839. #if _LIBCPP_DEBUG_LEVEL >= 2
  1840. _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
  1841. "vector::insert(iterator, n, x) called with an iterator not"
  1842. " referring to this vector");
  1843. #endif
  1844. pointer __p = this->__begin_ + (__position - begin());
  1845. if (__n > 0)
  1846. {
  1847. if (__n <= static_cast<size_type>(this->__end_cap() - this->__end_))
  1848. {
  1849. size_type __old_n = __n;
  1850. pointer __old_last = this->__end_;
  1851. if (__n > static_cast<size_type>(this->__end_ - __p))
  1852. {
  1853. size_type __cx = __n - (this->__end_ - __p);
  1854. __construct_at_end(__cx, __x);
  1855. __n -= __cx;
  1856. }
  1857. if (__n > 0)
  1858. {
  1859. __RAII_IncreaseAnnotator __annotator(*this, __n);
  1860. __move_range(__p, __old_last, __p + __old_n);
  1861. __annotator.__done();
  1862. const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
  1863. if (__p <= __xr && __xr < this->__end_)
  1864. __xr += __old_n;
  1865. _VSTD::fill_n(__p, __n, *__xr);
  1866. }
  1867. }
  1868. else
  1869. {
  1870. allocator_type& __a = this->__alloc();
  1871. __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
  1872. __v.__construct_at_end(__n, __x);
  1873. __p = __swap_out_circular_buffer(__v, __p);
  1874. }
  1875. }
  1876. return __make_iter(__p);
  1877. }
  1878.  
  1879. template <class _Tp, class _Allocator>
  1880. template <class _InputIterator>
  1881. typename enable_if
  1882. <
  1883. __is_input_iterator <_InputIterator>::value &&
  1884. !__is_forward_iterator<_InputIterator>::value &&
  1885. is_constructible<
  1886. _Tp,
  1887. typename iterator_traits<_InputIterator>::reference>::value,
  1888. typename vector<_Tp, _Allocator>::iterator
  1889. >::type
  1890. vector<_Tp, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
  1891. {
  1892. #if _LIBCPP_DEBUG_LEVEL >= 2
  1893. _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
  1894. "vector::insert(iterator, range) called with an iterator not"
  1895. " referring to this vector");
  1896. #endif
  1897. difference_type __off = __position - begin();
  1898. pointer __p = this->__begin_ + __off;
  1899. allocator_type& __a = this->__alloc();
  1900. pointer __old_last = this->__end_;
  1901. for (; this->__end_ != this->__end_cap() && __first != __last; ++__first)
  1902. {
  1903. __RAII_IncreaseAnnotator __annotator(*this);
  1904. __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_),
  1905. *__first);
  1906. ++this->__end_;
  1907. __annotator.__done();
  1908. }
  1909. __split_buffer<value_type, allocator_type&> __v(__a);
  1910. if (__first != __last)
  1911. {
  1912. #ifndef _LIBCPP_NO_EXCEPTIONS
  1913. try
  1914. {
  1915. #endif // _LIBCPP_NO_EXCEPTIONS
  1916. __v.__construct_at_end(__first, __last);
  1917. difference_type __old_size = __old_last - this->__begin_;
  1918. difference_type __old_p = __p - this->__begin_;
  1919. reserve(__recommend(size() + __v.size()));
  1920. __p = this->__begin_ + __old_p;
  1921. __old_last = this->__begin_ + __old_size;
  1922. #ifndef _LIBCPP_NO_EXCEPTIONS
  1923. }
  1924. catch (...)
  1925. {
  1926. erase(__make_iter(__old_last), end());
  1927. throw;
  1928. }
  1929. #endif // _LIBCPP_NO_EXCEPTIONS
  1930. }
  1931. __p = _VSTD::rotate(__p, __old_last, this->__end_);
  1932. insert(__make_iter(__p), make_move_iterator(__v.begin()),
  1933. make_move_iterator(__v.end()));
  1934. return begin() + __off;
  1935. }
  1936.  
  1937. template <class _Tp, class _Allocator>
  1938. template <class _ForwardIterator>
  1939. typename enable_if
  1940. <
  1941. __is_forward_iterator<_ForwardIterator>::value &&
  1942. is_constructible<
  1943. _Tp,
  1944. typename iterator_traits<_ForwardIterator>::reference>::value,
  1945. typename vector<_Tp, _Allocator>::iterator
  1946. >::type
  1947. vector<_Tp, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last)
  1948. {
  1949. #if _LIBCPP_DEBUG_LEVEL >= 2
  1950. _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
  1951. "vector::insert(iterator, range) called with an iterator not"
  1952. " referring to this vector");
  1953. #endif
  1954. pointer __p = this->__begin_ + (__position - begin());
  1955. difference_type __n = _VSTD::distance(__first, __last);
  1956. if (__n > 0)
  1957. {
  1958. if (__n <= this->__end_cap() - this->__end_)
  1959. {
  1960. size_type __old_n = __n;
  1961. pointer __old_last = this->__end_;
  1962. _ForwardIterator __m = __last;
  1963. difference_type __dx = this->__end_ - __p;
  1964. if (__n > __dx)
  1965. {
  1966. __m = __first;
  1967. difference_type __diff = this->__end_ - __p;
  1968. _VSTD::advance(__m, __diff);
  1969. __construct_at_end(__m, __last, __n - __diff);
  1970. __n = __dx;
  1971. }
  1972. if (__n > 0)
  1973. {
  1974. __RAII_IncreaseAnnotator __annotator(*this, __n);
  1975. __move_range(__p, __old_last, __p + __old_n);
  1976. __annotator.__done();
  1977. _VSTD::copy(__first, __m, __p);
  1978. }
  1979. }
  1980. else
  1981. {
  1982. allocator_type& __a = this->__alloc();
  1983. __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
  1984. __v.__construct_at_end(__first, __last);
  1985. __p = __swap_out_circular_buffer(__v, __p);
  1986. }
  1987. }
  1988. return __make_iter(__p);
  1989. }
  1990.  
  1991. template <class _Tp, class _Allocator>
  1992. void
  1993. vector<_Tp, _Allocator>::resize(size_type __sz)
  1994. {
  1995. size_type __cs = size();
  1996. if (__cs < __sz)
  1997. this->__append(__sz - __cs);
  1998. else if (__cs > __sz)
  1999. this->__destruct_at_end(this->__begin_ + __sz);
  2000. }
  2001.  
  2002. template <class _Tp, class _Allocator>
  2003. void
  2004. vector<_Tp, _Allocator>::resize(size_type __sz, const_reference __x)
  2005. {
  2006. size_type __cs = size();
  2007. if (__cs < __sz)
  2008. this->__append(__sz - __cs, __x);
  2009. else if (__cs > __sz)
  2010. this->__destruct_at_end(this->__begin_ + __sz);
  2011. }
  2012.  
  2013. template <class _Tp, class _Allocator>
  2014. void
  2015. vector<_Tp, _Allocator>::swap(vector& __x)
  2016. #if _LIBCPP_STD_VER >= 14
  2017. _NOEXCEPT_DEBUG
  2018. #else
  2019. _NOEXCEPT_DEBUG_(!__alloc_traits::propagate_on_container_swap::value ||
  2020. __is_nothrow_swappable<allocator_type>::value)
  2021. #endif
  2022. {
  2023. _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value ||
  2024. this->__alloc() == __x.__alloc(),
  2025. "vector::swap: Either propagate_on_container_swap must be true"
  2026. " or the allocators must compare equal");
  2027. _VSTD::swap(this->__begin_, __x.__begin_);
  2028. _VSTD::swap(this->__end_, __x.__end_);
  2029. _VSTD::swap(this->__end_cap(), __x.__end_cap());
  2030. __swap_allocator(this->__alloc(), __x.__alloc(),
  2031. integral_constant<bool,__alloc_traits::propagate_on_container_swap::value>());
  2032. #if _LIBCPP_DEBUG_LEVEL >= 2
  2033. __get_db()->swap(this, &__x);
  2034. #endif // _LIBCPP_DEBUG_LEVEL >= 2
  2035. }
  2036.  
  2037. template <class _Tp, class _Allocator>
  2038. bool
  2039. vector<_Tp, _Allocator>::__invariants() const
  2040. {
  2041. if (this->__begin_ == nullptr)
  2042. {
  2043. if (this->__end_ != nullptr || this->__end_cap() != nullptr)
  2044. return false;
  2045. }
  2046. else
  2047. {
  2048. if (this->__begin_ > this->__end_)
  2049. return false;
  2050. if (this->__begin_ == this->__end_cap())
  2051. return false;
  2052. if (this->__end_ > this->__end_cap())
  2053. return false;
  2054. }
  2055. return true;
  2056. }
  2057.  
  2058. #if _LIBCPP_DEBUG_LEVEL >= 2
  2059.  
  2060. template <class _Tp, class _Allocator>
  2061. bool
  2062. vector<_Tp, _Allocator>::__dereferenceable(const const_iterator* __i) const
  2063. {
  2064. return this->__begin_ <= __i->base() && __i->base() < this->__end_;
  2065. }
  2066.  
  2067. template <class _Tp, class _Allocator>
  2068. bool
  2069. vector<_Tp, _Allocator>::__decrementable(const const_iterator* __i) const
  2070. {
  2071. return this->__begin_ < __i->base() && __i->base() <= this->__end_;
  2072. }
  2073.  
  2074. template <class _Tp, class _Allocator>
  2075. bool
  2076. vector<_Tp, _Allocator>::__addable(const const_iterator* __i, ptrdiff_t __n) const
  2077. {
  2078. const_pointer __p = __i->base() + __n;
  2079. return this->__begin_ <= __p && __p <= this->__end_;
  2080. }
  2081.  
  2082. template <class _Tp, class _Allocator>
  2083. bool
  2084. vector<_Tp, _Allocator>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const
  2085. {
  2086. const_pointer __p = __i->base() + __n;
  2087. return this->__begin_ <= __p && __p < this->__end_;
  2088. }
  2089.  
  2090. #endif // _LIBCPP_DEBUG_LEVEL >= 2
  2091.  
  2092. template <class _Tp, class _Allocator>
  2093. inline _LIBCPP_INLINE_VISIBILITY
  2094. void
  2095. vector<_Tp, _Allocator>::__invalidate_all_iterators()
  2096. {
  2097. #if _LIBCPP_DEBUG_LEVEL >= 2
  2098. __get_db()->__invalidate_all(this);
  2099. #endif // _LIBCPP_DEBUG_LEVEL >= 2
  2100. }
  2101.  
  2102.  
  2103. template <class _Tp, class _Allocator>
  2104. inline _LIBCPP_INLINE_VISIBILITY
  2105. void
  2106. vector<_Tp, _Allocator>::__invalidate_iterators_past(pointer __new_last) {
  2107. #if _LIBCPP_DEBUG_LEVEL >= 2
  2108. __c_node* __c = __get_db()->__find_c_and_lock(this);
  2109. for (__i_node** __p = __c->end_; __p != __c->beg_; ) {
  2110. --__p;
  2111. const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
  2112. if (__i->base() > __new_last) {
  2113. (*__p)->__c_ = nullptr;
  2114. if (--__c->end_ != __p)
  2115. memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
  2116. }
  2117. }
  2118. __get_db()->unlock();
  2119. #else
  2120. ((void)__new_last);
  2121. #endif
  2122. }
  2123.  
  2124. // vector<bool>
  2125.  
  2126. template <class _Allocator> class vector<bool, _Allocator>;
  2127.  
  2128. template <class _Allocator> struct hash<vector<bool, _Allocator> >;
  2129.  
  2130. template <class _Allocator>
  2131. struct __has_storage_type<vector<bool, _Allocator> >
  2132. {
  2133. static const bool value = true;
  2134. };
  2135.  
  2136. template <class _Allocator>
  2137. class _LIBCPP_TEMPLATE_VIS vector<bool, _Allocator>
  2138. : private __vector_base_common<true>
  2139. {
  2140. public:
  2141. typedef vector __self;
  2142. typedef bool value_type;
  2143. typedef _Allocator allocator_type;
  2144. typedef allocator_traits<allocator_type> __alloc_traits;
  2145. typedef typename __alloc_traits::size_type size_type;
  2146. typedef typename __alloc_traits::difference_type difference_type;
  2147. typedef size_type __storage_type;
  2148. typedef __bit_iterator<vector, false> pointer;
  2149. typedef __bit_iterator<vector, true> const_pointer;
  2150. typedef pointer iterator;
  2151. typedef const_pointer const_iterator;
  2152. typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
  2153. typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
  2154.  
  2155. private:
  2156. typedef typename __rebind_alloc_helper<__alloc_traits, __storage_type>::type __storage_allocator;
  2157. typedef allocator_traits<__storage_allocator> __storage_traits;
  2158. typedef typename __storage_traits::pointer __storage_pointer;
  2159. typedef typename __storage_traits::const_pointer __const_storage_pointer;
  2160.  
  2161. __storage_pointer __begin_;
  2162. size_type __size_;
  2163. __compressed_pair<size_type, __storage_allocator> __cap_alloc_;
  2164. public:
  2165. typedef __bit_reference<vector> reference;
  2166. typedef __bit_const_reference<vector> const_reference;
  2167. private:
  2168. _LIBCPP_INLINE_VISIBILITY
  2169. size_type& __cap() _NOEXCEPT
  2170. {return __cap_alloc_.first();}
  2171. _LIBCPP_INLINE_VISIBILITY
  2172. const size_type& __cap() const _NOEXCEPT
  2173. {return __cap_alloc_.first();}
  2174. _LIBCPP_INLINE_VISIBILITY
  2175. __storage_allocator& __alloc() _NOEXCEPT
  2176. {return __cap_alloc_.second();}
  2177. _LIBCPP_INLINE_VISIBILITY
  2178. const __storage_allocator& __alloc() const _NOEXCEPT
  2179. {return __cap_alloc_.second();}
  2180.  
  2181. static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);
  2182.  
  2183. _LIBCPP_INLINE_VISIBILITY
  2184. static size_type __internal_cap_to_external(size_type __n) _NOEXCEPT
  2185. {return __n * __bits_per_word;}
  2186. _LIBCPP_INLINE_VISIBILITY
  2187. static size_type __external_cap_to_internal(size_type __n) _NOEXCEPT
  2188. {return (__n - 1) / __bits_per_word + 1;}
  2189.  
  2190. public:
  2191. _LIBCPP_INLINE_VISIBILITY
  2192. vector() _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
  2193.  
  2194. _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a)
  2195. #if _LIBCPP_STD_VER <= 14
  2196. _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value);
  2197. #else
  2198. _NOEXCEPT;
  2199. #endif
  2200. ~vector();
  2201. explicit vector(size_type __n);
  2202. #if _LIBCPP_STD_VER > 11
  2203. explicit vector(size_type __n, const allocator_type& __a);
  2204. #endif
  2205. vector(size_type __n, const value_type& __v);
  2206. vector(size_type __n, const value_type& __v, const allocator_type& __a);
  2207. template <class _InputIterator>
  2208. vector(_InputIterator __first, _InputIterator __last,
  2209. typename enable_if<__is_input_iterator <_InputIterator>::value &&
  2210. !__is_forward_iterator<_InputIterator>::value>::type* = 0);
  2211. template <class _InputIterator>
  2212. vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
  2213. typename enable_if<__is_input_iterator <_InputIterator>::value &&
  2214. !__is_forward_iterator<_InputIterator>::value>::type* = 0);
  2215. template <class _ForwardIterator>
  2216. vector(_ForwardIterator __first, _ForwardIterator __last,
  2217. typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0);
  2218. template <class _ForwardIterator>
  2219. vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
  2220. typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0);
  2221.  
  2222. vector(const vector& __v);
  2223. vector(const vector& __v, const allocator_type& __a);
  2224. vector& operator=(const vector& __v);
  2225.  
  2226. #ifndef _LIBCPP_CXX03_LANG
  2227. vector(initializer_list<value_type> __il);
  2228. vector(initializer_list<value_type> __il, const allocator_type& __a);
  2229.  
  2230. _LIBCPP_INLINE_VISIBILITY
  2231. vector(vector&& __v)
  2232. #if _LIBCPP_STD_VER > 14
  2233. _NOEXCEPT;
  2234. #else
  2235. _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
  2236. #endif
  2237. vector(vector&& __v, const allocator_type& __a);
  2238. _LIBCPP_INLINE_VISIBILITY
  2239. vector& operator=(vector&& __v)
  2240. _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value));
  2241.  
  2242. _LIBCPP_INLINE_VISIBILITY
  2243. vector& operator=(initializer_list<value_type> __il)
  2244. {assign(__il.begin(), __il.end()); return *this;}
  2245.  
  2246. #endif // !_LIBCPP_CXX03_LANG
  2247.  
  2248. template <class _InputIterator>
  2249. typename enable_if
  2250. <
  2251. __is_input_iterator<_InputIterator>::value &&
  2252. !__is_forward_iterator<_InputIterator>::value,
  2253. void
  2254. >::type
  2255. assign(_InputIterator __first, _InputIterator __last);
  2256. template <class _ForwardIterator>
  2257. typename enable_if
  2258. <
  2259. __is_forward_iterator<_ForwardIterator>::value,
  2260. void
  2261. >::type
  2262. assign(_ForwardIterator __first, _ForwardIterator __last);
  2263.  
  2264. void assign(size_type __n, const value_type& __x);
  2265.  
  2266. #ifndef _LIBCPP_CXX03_LANG
  2267. _LIBCPP_INLINE_VISIBILITY
  2268. void assign(initializer_list<value_type> __il)
  2269. {assign(__il.begin(), __il.end());}
  2270. #endif
  2271.  
  2272. _LIBCPP_INLINE_VISIBILITY allocator_type get_allocator() const _NOEXCEPT
  2273. {return allocator_type(this->__alloc());}
  2274.  
  2275. size_type max_size() const _NOEXCEPT;
  2276. _LIBCPP_INLINE_VISIBILITY
  2277. size_type capacity() const _NOEXCEPT
  2278. {return __internal_cap_to_external(__cap());}
  2279. _LIBCPP_INLINE_VISIBILITY
  2280. size_type size() const _NOEXCEPT
  2281. {return __size_;}
  2282. _LIBCPP_INLINE_VISIBILITY
  2283. bool empty() const _NOEXCEPT
  2284. {return __size_ == 0;}
  2285. void reserve(size_type __n);
  2286. void shrink_to_fit() _NOEXCEPT;
  2287.  
  2288. _LIBCPP_INLINE_VISIBILITY
  2289. iterator begin() _NOEXCEPT
  2290. {return __make_iter(0);}
  2291. _LIBCPP_INLINE_VISIBILITY
  2292. const_iterator begin() const _NOEXCEPT
  2293. {return __make_iter(0);}
  2294. _LIBCPP_INLINE_VISIBILITY
  2295. iterator end() _NOEXCEPT
  2296. {return __make_iter(__size_);}
  2297. _LIBCPP_INLINE_VISIBILITY
  2298. const_iterator end() const _NOEXCEPT
  2299. {return __make_iter(__size_);}
  2300.  
  2301. _LIBCPP_INLINE_VISIBILITY
  2302. reverse_iterator rbegin() _NOEXCEPT
  2303. {return reverse_iterator(end());}
  2304. _LIBCPP_INLINE_VISIBILITY
  2305. const_reverse_iterator rbegin() const _NOEXCEPT
  2306. {return const_reverse_iterator(end());}
  2307. _LIBCPP_INLINE_VISIBILITY
  2308. reverse_iterator rend() _NOEXCEPT
  2309. {return reverse_iterator(begin());}
  2310. _LIBCPP_INLINE_VISIBILITY
  2311. const_reverse_iterator rend() const _NOEXCEPT
  2312. {return const_reverse_iterator(begin());}
  2313.  
  2314. _LIBCPP_INLINE_VISIBILITY
  2315. const_iterator cbegin() const _NOEXCEPT
  2316. {return __make_iter(0);}
  2317. _LIBCPP_INLINE_VISIBILITY
  2318. const_iterator cend() const _NOEXCEPT
  2319. {return __make_iter(__size_);}
  2320. _LIBCPP_INLINE_VISIBILITY
  2321. const_reverse_iterator crbegin() const _NOEXCEPT
  2322. {return rbegin();}
  2323. _LIBCPP_INLINE_VISIBILITY
  2324. const_reverse_iterator crend() const _NOEXCEPT
  2325. {return rend();}
  2326.  
  2327. _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n) {return __make_ref(__n);}
  2328. _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const {return __make_ref(__n);}
  2329. reference at(size_type __n);
  2330. const_reference at(size_type __n) const;
  2331.  
  2332. _LIBCPP_INLINE_VISIBILITY reference front() {return __make_ref(0);}
  2333. _LIBCPP_INLINE_VISIBILITY const_reference front() const {return __make_ref(0);}
  2334. _LIBCPP_INLINE_VISIBILITY reference back() {return __make_ref(__size_ - 1);}
  2335. _LIBCPP_INLINE_VISIBILITY const_reference back() const {return __make_ref(__size_ - 1);}
  2336.  
  2337. void push_back(const value_type& __x);
  2338. #if _LIBCPP_STD_VER > 11
  2339. template <class... _Args>
  2340. #if _LIBCPP_STD_VER > 14
  2341. _LIBCPP_INLINE_VISIBILITY reference emplace_back(_Args&&... __args)
  2342. #else
  2343. _LIBCPP_INLINE_VISIBILITY void emplace_back(_Args&&... __args)
  2344. #endif
  2345. {
  2346. push_back ( value_type ( _VSTD::forward<_Args>(__args)... ));
  2347. #if _LIBCPP_STD_VER > 14
  2348. return this->back();
  2349. #endif
  2350. }
  2351. #endif
  2352.  
  2353. _LIBCPP_INLINE_VISIBILITY void pop_back() {--__size_;}
  2354.  
  2355. #if _LIBCPP_STD_VER > 11
  2356. template <class... _Args>
  2357. _LIBCPP_INLINE_VISIBILITY iterator emplace(const_iterator position, _Args&&... __args)
  2358. { return insert ( position, value_type ( _VSTD::forward<_Args>(__args)... )); }
  2359. #endif
  2360.  
  2361. iterator insert(const_iterator __position, const value_type& __x);
  2362. iterator insert(const_iterator __position, size_type __n, const value_type& __x);
  2363. iterator insert(const_iterator __position, size_type __n, const_reference __x);
  2364. template <class _InputIterator>
  2365. typename enable_if
  2366. <
  2367. __is_input_iterator <_InputIterator>::value &&
  2368. !__is_forward_iterator<_InputIterator>::value,
  2369. iterator
  2370. >::type
  2371. insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
  2372. template <class _ForwardIterator>
  2373. typename enable_if
  2374. <
  2375. __is_forward_iterator<_ForwardIterator>::value,
  2376. iterator
  2377. >::type
  2378. insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
  2379.  
  2380. #ifndef _LIBCPP_CXX03_LANG
  2381. _LIBCPP_INLINE_VISIBILITY
  2382. iterator insert(const_iterator __position, initializer_list<value_type> __il)
  2383. {return insert(__position, __il.begin(), __il.end());}
  2384. #endif
  2385.  
  2386. _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position);
  2387. iterator erase(const_iterator __first, const_iterator __last);
  2388.  
  2389. _LIBCPP_INLINE_VISIBILITY
  2390. void clear() _NOEXCEPT {__size_ = 0;}
  2391.  
  2392. void swap(vector&)
  2393. #if _LIBCPP_STD_VER >= 14
  2394. _NOEXCEPT;
  2395. #else
  2396. _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
  2397. __is_nothrow_swappable<allocator_type>::value);
  2398. #endif
  2399. static void swap(reference __x, reference __y) _NOEXCEPT { _VSTD::swap(__x, __y); }
  2400.  
  2401. void resize(size_type __sz, value_type __x = false);
  2402. void flip() _NOEXCEPT;
  2403.  
  2404. bool __invariants() const;
  2405.  
  2406. private:
  2407. _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
  2408. void allocate(size_type __n);
  2409. void deallocate() _NOEXCEPT;
  2410. _LIBCPP_INLINE_VISIBILITY
  2411. static size_type __align_it(size_type __new_size) _NOEXCEPT
  2412. {return __new_size + (__bits_per_word-1) & ~((size_type)__bits_per_word-1);};
  2413. _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const;
  2414. _LIBCPP_INLINE_VISIBILITY void __construct_at_end(size_type __n, bool __x);
  2415. template <class _ForwardIterator>
  2416. typename enable_if
  2417. <
  2418. __is_forward_iterator<_ForwardIterator>::value,
  2419. void
  2420. >::type
  2421. __construct_at_end(_ForwardIterator __first, _ForwardIterator __last);
  2422. void __append(size_type __n, const_reference __x);
  2423. _LIBCPP_INLINE_VISIBILITY
  2424. reference __make_ref(size_type __pos) _NOEXCEPT
  2425. {return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
  2426. _LIBCPP_INLINE_VISIBILITY
  2427. const_reference __make_ref(size_type __pos) const _NOEXCEPT
  2428. {return const_reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
  2429. _LIBCPP_INLINE_VISIBILITY
  2430. iterator __make_iter(size_type __pos) _NOEXCEPT
  2431. {return iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
  2432. _LIBCPP_INLINE_VISIBILITY
  2433. const_iterator __make_iter(size_type __pos) const _NOEXCEPT
  2434. {return const_iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
  2435. _LIBCPP_INLINE_VISIBILITY
  2436. iterator __const_iterator_cast(const_iterator __p) _NOEXCEPT
  2437. {return begin() + (__p - cbegin());}
  2438.  
  2439. _LIBCPP_INLINE_VISIBILITY
  2440. void __copy_assign_alloc(const vector& __v)
  2441. {__copy_assign_alloc(__v, integral_constant<bool,
  2442. __storage_traits::propagate_on_container_copy_assignment::value>());}
  2443. _LIBCPP_INLINE_VISIBILITY
  2444. void __copy_assign_alloc(const vector& __c, true_type)
  2445. {
  2446. if (__alloc() != __c.__alloc())
  2447. deallocate();
  2448. __alloc() = __c.__alloc();
  2449. }
  2450.  
  2451. _LIBCPP_INLINE_VISIBILITY
  2452. void __copy_assign_alloc(const vector&, false_type)
  2453. {}
  2454.  
  2455. void __move_assign(vector& __c, false_type);
  2456. void __move_assign(vector& __c, true_type)
  2457. _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
  2458. _LIBCPP_INLINE_VISIBILITY
  2459. void __move_assign_alloc(vector& __c)
  2460. _NOEXCEPT_(
  2461. !__storage_traits::propagate_on_container_move_assignment::value ||
  2462. is_nothrow_move_assignable<allocator_type>::value)
  2463. {__move_assign_alloc(__c, integral_constant<bool,
  2464. __storage_traits::propagate_on_container_move_assignment::value>());}
  2465. _LIBCPP_INLINE_VISIBILITY
  2466. void __move_assign_alloc(vector& __c, true_type)
  2467. _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
  2468. {
  2469. __alloc() = _VSTD::move(__c.__alloc());
  2470. }
  2471.  
  2472. _LIBCPP_INLINE_VISIBILITY
  2473. void __move_assign_alloc(vector&, false_type)
  2474. _NOEXCEPT
  2475. {}
  2476.  
  2477. size_t __hash_code() const _NOEXCEPT;
  2478.  
  2479. friend class __bit_reference<vector>;
  2480. friend class __bit_const_reference<vector>;
  2481. friend class __bit_iterator<vector, false>;
  2482. friend class __bit_iterator<vector, true>;
  2483. friend struct __bit_array<vector>;
  2484. friend struct _LIBCPP_TEMPLATE_VIS hash<vector>;
  2485. };
  2486.  
  2487. template <class _Allocator>
  2488. inline _LIBCPP_INLINE_VISIBILITY
  2489. void
  2490. vector<bool, _Allocator>::__invalidate_all_iterators()
  2491. {
  2492. }
  2493.  
  2494. // Allocate space for __n objects
  2495. // throws length_error if __n > max_size()
  2496. // throws (probably bad_alloc) if memory run out
  2497. // Precondition: __begin_ == __end_ == __cap() == 0
  2498. // Precondition: __n > 0
  2499. // Postcondition: capacity() == __n
  2500. // Postcondition: size() == 0
  2501. template <class _Allocator>
  2502. void
  2503. vector<bool, _Allocator>::allocate(size_type __n)
  2504. {
  2505. if (__n > max_size())
  2506. this->__throw_length_error();
  2507. __n = __external_cap_to_internal(__n);
  2508. this->__begin_ = __storage_traits::allocate(this->__alloc(), __n);
  2509. this->__size_ = 0;
  2510. this->__cap() = __n;
  2511. }
  2512.  
  2513. template <class _Allocator>
  2514. void
  2515. vector<bool, _Allocator>::deallocate() _NOEXCEPT
  2516. {
  2517. if (this->__begin_ != nullptr)
  2518. {
  2519. __storage_traits::deallocate(this->__alloc(), this->__begin_, __cap());
  2520. __invalidate_all_iterators();
  2521. this->__begin_ = nullptr;
  2522. this->__size_ = this->__cap() = 0;
  2523. }
  2524. }
  2525.  
  2526. template <class _Allocator>
  2527. typename vector<bool, _Allocator>::size_type
  2528. vector<bool, _Allocator>::max_size() const _NOEXCEPT
  2529. {
  2530. size_type __amax = __storage_traits::max_size(__alloc());
  2531. size_type __nmax = numeric_limits<size_type>::max() / 2; // end() >= begin(), always
  2532. if (__nmax / __bits_per_word <= __amax)
  2533. return __nmax;
  2534. return __internal_cap_to_external(__amax);
  2535. }
  2536.  
  2537. // Precondition: __new_size > capacity()
  2538. template <class _Allocator>
  2539. inline _LIBCPP_INLINE_VISIBILITY
  2540. typename vector<bool, _Allocator>::size_type
  2541. vector<bool, _Allocator>::__recommend(size_type __new_size) const
  2542. {
  2543. const size_type __ms = max_size();
  2544. if (__new_size > __ms)
  2545. this->__throw_length_error();
  2546. const size_type __cap = capacity();
  2547. if (__cap >= __ms / 2)
  2548. return __ms;
  2549. return _VSTD::max(2*__cap, __align_it(__new_size));
  2550. }
  2551.  
  2552. // Default constructs __n objects starting at __end_
  2553. // Precondition: __n > 0
  2554. // Precondition: size() + __n <= capacity()
  2555. // Postcondition: size() == size() + __n
  2556. template <class _Allocator>
  2557. inline _LIBCPP_INLINE_VISIBILITY
  2558. void
  2559. vector<bool, _Allocator>::__construct_at_end(size_type __n, bool __x)
  2560. {
  2561. size_type __old_size = this->__size_;
  2562. this->__size_ += __n;
  2563. _VSTD::fill_n(__make_iter(__old_size), __n, __x);
  2564. }
  2565.  
  2566. template <class _Allocator>
  2567. template <class _ForwardIterator>
  2568. typename enable_if
  2569. <
  2570. __is_forward_iterator<_ForwardIterator>::value,
  2571. void
  2572. >::type
  2573. vector<bool, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last)
  2574. {
  2575. size_type __old_size = this->__size_;
  2576. this->__size_ += _VSTD::distance(__first, __last);
  2577. _VSTD::copy(__first, __last, __make_iter(__old_size));
  2578. }
  2579.  
  2580. template <class _Allocator>
  2581. inline _LIBCPP_INLINE_VISIBILITY
  2582. vector<bool, _Allocator>::vector()
  2583. _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
  2584. : __begin_(nullptr),
  2585. __size_(0),
  2586. __cap_alloc_(0)
  2587. {
  2588. }
  2589.  
  2590. template <class _Allocator>
  2591. inline _LIBCPP_INLINE_VISIBILITY
  2592. vector<bool, _Allocator>::vector(const allocator_type& __a)
  2593. #if _LIBCPP_STD_VER <= 14
  2594. _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
  2595. #else
  2596. _NOEXCEPT
  2597. #endif
  2598. : __begin_(nullptr),
  2599. __size_(0),
  2600. __cap_alloc_(0, static_cast<__storage_allocator>(__a))
  2601. {
  2602. }
  2603.  
  2604. template <class _Allocator>
  2605. vector<bool, _Allocator>::vector(size_type __n)
  2606. : __begin_(nullptr),
  2607. __size_(0),
  2608. __cap_alloc_(0)
  2609. {
  2610. if (__n > 0)
  2611. {
  2612. allocate(__n);
  2613. __construct_at_end(__n, false);
  2614. }
  2615. }
  2616.  
  2617. #if _LIBCPP_STD_VER > 11
  2618. template <class _Allocator>
  2619. vector<bool, _Allocator>::vector(size_type __n, const allocator_type& __a)
  2620. : __begin_(nullptr),
  2621. __size_(0),
  2622. __cap_alloc_(0, static_cast<__storage_allocator>(__a))
  2623. {
  2624. if (__n > 0)
  2625. {
  2626. allocate(__n);
  2627. __construct_at_end(__n, false);
  2628. }
  2629. }
  2630. #endif
  2631.  
  2632. template <class _Allocator>
  2633. vector<bool, _Allocator>::vector(size_type __n, const value_type& __x)
  2634. : __begin_(nullptr),
  2635. __size_(0),
  2636. __cap_alloc_(0)
  2637. {
  2638. if (__n > 0)
  2639. {
  2640. allocate(__n);
  2641. __construct_at_end(__n, __x);
  2642. }
  2643. }
  2644.  
  2645. template <class _Allocator>
  2646. vector<bool, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a)
  2647. : __begin_(nullptr),
  2648. __size_(0),
  2649. __cap_alloc_(0, static_cast<__storage_allocator>(__a))
  2650. {
  2651. if (__n > 0)
  2652. {
  2653. allocate(__n);
  2654. __construct_at_end(__n, __x);
  2655. }
  2656. }
  2657.  
  2658. template <class _Allocator>
  2659. template <class _InputIterator>
  2660. vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last,
  2661. typename enable_if<__is_input_iterator <_InputIterator>::value &&
  2662. !__is_forward_iterator<_InputIterator>::value>::type*)
  2663. : __begin_(nullptr),
  2664. __size_(0),
  2665. __cap_alloc_(0)
  2666. {
  2667. #ifndef _LIBCPP_NO_EXCEPTIONS
  2668. try
  2669. {
  2670. #endif // _LIBCPP_NO_EXCEPTIONS
  2671. for (; __first != __last; ++__first)
  2672. push_back(*__first);
  2673. #ifndef _LIBCPP_NO_EXCEPTIONS
  2674. }
  2675. catch (...)
  2676. {
  2677. if (__begin_ != nullptr)
  2678. __storage_traits::deallocate(__alloc(), __begin_, __cap());
  2679. __invalidate_all_iterators();
  2680. throw;
  2681. }
  2682. #endif // _LIBCPP_NO_EXCEPTIONS
  2683. }
  2684.  
  2685. template <class _Allocator>
  2686. template <class _InputIterator>
  2687. vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
  2688. typename enable_if<__is_input_iterator <_InputIterator>::value &&
  2689. !__is_forward_iterator<_InputIterator>::value>::type*)
  2690. : __begin_(nullptr),
  2691. __size_(0),
  2692. __cap_alloc_(0, static_cast<__storage_allocator>(__a))
  2693. {
  2694. #ifndef _LIBCPP_NO_EXCEPTIONS
  2695. try
  2696. {
  2697. #endif // _LIBCPP_NO_EXCEPTIONS
  2698. for (; __first != __last; ++__first)
  2699. push_back(*__first);
  2700. #ifndef _LIBCPP_NO_EXCEPTIONS
  2701. }
  2702. catch (...)
  2703. {
  2704. if (__begin_ != nullptr)
  2705. __storage_traits::deallocate(__alloc(), __begin_, __cap());
  2706. __invalidate_all_iterators();
  2707. throw;
  2708. }
  2709. #endif // _LIBCPP_NO_EXCEPTIONS
  2710. }
  2711.  
  2712. template <class _Allocator>
  2713. template <class _ForwardIterator>
  2714. vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last,
  2715. typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*)
  2716. : __begin_(nullptr),
  2717. __size_(0),
  2718. __cap_alloc_(0)
  2719. {
  2720. size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
  2721. if (__n > 0)
  2722. {
  2723. allocate(__n);
  2724. __construct_at_end(__first, __last);
  2725. }
  2726. }
  2727.  
  2728. template <class _Allocator>
  2729. template <class _ForwardIterator>
  2730. vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
  2731. typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*)
  2732. : __begin_(nullptr),
  2733. __size_(0),
  2734. __cap_alloc_(0, static_cast<__storage_allocator>(__a))
  2735. {
  2736. size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
  2737. if (__n > 0)
  2738. {
  2739. allocate(__n);
  2740. __construct_at_end(__first, __last);
  2741. }
  2742. }
  2743.  
  2744. #ifndef _LIBCPP_CXX03_LANG
  2745.  
  2746. template <class _Allocator>
  2747. vector<bool, _Allocator>::vector(initializer_list<value_type> __il)
  2748. : __begin_(nullptr),
  2749. __size_(0),
  2750. __cap_alloc_(0)
  2751. {
  2752. size_type __n = static_cast<size_type>(__il.size());
  2753. if (__n > 0)
  2754. {
  2755. allocate(__n);
  2756. __construct_at_end(__il.begin(), __il.end());
  2757. }
  2758. }
  2759.  
  2760. template <class _Allocator>
  2761. vector<bool, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
  2762. : __begin_(nullptr),
  2763. __size_(0),
  2764. __cap_alloc_(0, static_cast<__storage_allocator>(__a))
  2765. {
  2766. size_type __n = static_cast<size_type>(__il.size());
  2767. if (__n > 0)
  2768. {
  2769. allocate(__n);
  2770. __construct_at_end(__il.begin(), __il.end());
  2771. }
  2772. }
  2773.  
  2774. #endif // _LIBCPP_CXX03_LANG
  2775.  
  2776. template <class _Allocator>
  2777. vector<bool, _Allocator>::~vector()
  2778. {
  2779. if (__begin_ != nullptr)
  2780. __storage_traits::deallocate(__alloc(), __begin_, __cap());
  2781. __invalidate_all_iterators();
  2782. }
  2783.  
  2784. template <class _Allocator>
  2785. vector<bool, _Allocator>::vector(const vector& __v)
  2786. : __begin_(nullptr),
  2787. __size_(0),
  2788. __cap_alloc_(0, __storage_traits::select_on_container_copy_construction(__v.__alloc()))
  2789. {
  2790. if (__v.size() > 0)
  2791. {
  2792. allocate(__v.size());
  2793. __construct_at_end(__v.begin(), __v.end());
  2794. }
  2795. }
  2796.  
  2797. template <class _Allocator>
  2798. vector<bool, _Allocator>::vector(const vector& __v, const allocator_type& __a)
  2799. : __begin_(nullptr),
  2800. __size_(0),
  2801. __cap_alloc_(0, __a)
  2802. {
  2803. if (__v.size() > 0)
  2804. {
  2805. allocate(__v.size());
  2806. __construct_at_end(__v.begin(), __v.end());
  2807. }
  2808. }
  2809.  
  2810. template <class _Allocator>
  2811. vector<bool, _Allocator>&
  2812. vector<bool, _Allocator>::operator=(const vector& __v)
  2813. {
  2814. if (this != &__v)
  2815. {
  2816. __copy_assign_alloc(__v);
  2817. if (__v.__size_)
  2818. {
  2819. if (__v.__size_ > capacity())
  2820. {
  2821. deallocate();
  2822. allocate(__v.__size_);
  2823. }
  2824. _VSTD::copy(__v.__begin_, __v.__begin_ + __external_cap_to_internal(__v.__size_), __begin_);
  2825. }
  2826. __size_ = __v.__size_;
  2827. }
  2828. return *this;
  2829. }
  2830.  
  2831. #ifndef _LIBCPP_CXX03_LANG
  2832.  
  2833. template <class _Allocator>
  2834. inline _LIBCPP_INLINE_VISIBILITY
  2835. vector<bool, _Allocator>::vector(vector&& __v)
  2836. #if _LIBCPP_STD_VER > 14
  2837. _NOEXCEPT
  2838. #else
  2839. _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
  2840. #endif
  2841. : __begin_(__v.__begin_),
  2842. __size_(__v.__size_),
  2843. __cap_alloc_(__v.__cap_alloc_)
  2844. {
  2845. __v.__begin_ = nullptr;
  2846. __v.__size_ = 0;
  2847. __v.__cap() = 0;
  2848. }
  2849.  
  2850. template <class _Allocator>
  2851. vector<bool, _Allocator>::vector(vector&& __v, const allocator_type& __a)
  2852. : __begin_(nullptr),
  2853. __size_(0),
  2854. __cap_alloc_(0, __a)
  2855. {
  2856. if (__a == allocator_type(__v.__alloc()))
  2857. {
  2858. this->__begin_ = __v.__begin_;
  2859. this->__size_ = __v.__size_;
  2860. this->__cap() = __v.__cap();
  2861. __v.__begin_ = nullptr;
  2862. __v.__cap() = __v.__size_ = 0;
  2863. }
  2864. else if (__v.size() > 0)
  2865. {
  2866. allocate(__v.size());
  2867. __construct_at_end(__v.begin(), __v.end());
  2868. }
  2869. }
  2870.  
  2871. template <class _Allocator>
  2872. inline _LIBCPP_INLINE_VISIBILITY
  2873. vector<bool, _Allocator>&
  2874. vector<bool, _Allocator>::operator=(vector&& __v)
  2875. _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value))
  2876. {
  2877. __move_assign(__v, integral_constant<bool,
  2878. __storage_traits::propagate_on_container_move_assignment::value>());
  2879. return *this;
  2880. }
  2881.  
  2882. template <class _Allocator>
  2883. void
  2884. vector<bool, _Allocator>::__move_assign(vector& __c, false_type)
  2885. {
  2886. if (__alloc() != __c.__alloc())
  2887. assign(__c.begin(), __c.end());
  2888. else
  2889. __move_assign(__c, true_type());
  2890. }
  2891.  
  2892. template <class _Allocator>
  2893. void
  2894. vector<bool, _Allocator>::__move_assign(vector& __c, true_type)
  2895. _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
  2896. {
  2897. deallocate();
  2898. __move_assign_alloc(__c);
  2899. this->__begin_ = __c.__begin_;
  2900. this->__size_ = __c.__size_;
  2901. this->__cap() = __c.__cap();
  2902. __c.__begin_ = nullptr;
  2903. __c.__cap() = __c.__size_ = 0;
  2904. }
  2905.  
  2906. #endif // !_LIBCPP_CXX03_LANG
  2907.  
  2908. template <class _Allocator>
  2909. void
  2910. vector<bool, _Allocator>::assign(size_type __n, const value_type& __x)
  2911. {
  2912. __size_ = 0;
  2913. if (__n > 0)
  2914. {
  2915. size_type __c = capacity();
  2916. if (__n <= __c)
  2917. __size_ = __n;
  2918. else
  2919. {
  2920. vector __v(__alloc());
  2921. __v.reserve(__recommend(__n));
  2922. __v.__size_ = __n;
  2923. swap(__v);
  2924. }
  2925. _VSTD::fill_n(begin(), __n, __x);
  2926. }
  2927. __invalidate_all_iterators();
  2928. }
  2929.  
  2930. template <class _Allocator>
  2931. template <class _InputIterator>
  2932. typename enable_if
  2933. <
  2934. __is_input_iterator<_InputIterator>::value &&
  2935. !__is_forward_iterator<_InputIterator>::value,
  2936. void
  2937. >::type
  2938. vector<bool, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
  2939. {
  2940. clear();
  2941. for (; __first != __last; ++__first)
  2942. push_back(*__first);
  2943. }
  2944.  
  2945. template <class _Allocator>
  2946. template <class _ForwardIterator>
  2947. typename enable_if
  2948. <
  2949. __is_forward_iterator<_ForwardIterator>::value,
  2950. void
  2951. >::type
  2952. vector<bool, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
  2953. {
  2954. clear();
  2955. difference_type __ns = _VSTD::distance(__first, __last);
  2956. _LIBCPP_ASSERT(__ns >= 0, "invalid range specified");
  2957. const size_t __n = static_cast<size_type>(__ns);
  2958. if (__n)
  2959. {
  2960. if (__n > capacity())
  2961. {
  2962. deallocate();
  2963. allocate(__n);
  2964. }
  2965. __construct_at_end(__first, __last);
  2966. }
  2967. }
  2968.  
  2969. template <class _Allocator>
  2970. void
  2971. vector<bool, _Allocator>::reserve(size_type __n)
  2972. {
  2973. if (__n > capacity())
  2974. {
  2975. vector __v(this->__alloc());
  2976. __v.allocate(__n);
  2977. __v.__construct_at_end(this->begin(), this->end());
  2978. swap(__v);
  2979. __invalidate_all_iterators();
  2980. }
  2981. }
  2982.  
  2983. template <class _Allocator>
  2984. void
  2985. vector<bool, _Allocator>::shrink_to_fit() _NOEXCEPT
  2986. {
  2987. if (__external_cap_to_internal(size()) > __cap())
  2988. {
  2989. #ifndef _LIBCPP_NO_EXCEPTIONS
  2990. try
  2991. {
  2992. #endif // _LIBCPP_NO_EXCEPTIONS
  2993. vector(*this, allocator_type(__alloc())).swap(*this);
  2994. #ifndef _LIBCPP_NO_EXCEPTIONS
  2995. }
  2996. catch (...)
  2997. {
  2998. }
  2999. #endif // _LIBCPP_NO_EXCEPTIONS
  3000. }
  3001. }
  3002.  
  3003. template <class _Allocator>
  3004. typename vector<bool, _Allocator>::reference
  3005. vector<bool, _Allocator>::at(size_type __n)
  3006. {
  3007. if (__n >= size())
  3008. this->__throw_out_of_range();
  3009. return (*this)[__n];
  3010. }
  3011.  
  3012. template <class _Allocator>
  3013. typename vector<bool, _Allocator>::const_reference
  3014. vector<bool, _Allocator>::at(size_type __n) const
  3015. {
  3016. if (__n >= size())
  3017. this->__throw_out_of_range();
  3018. return (*this)[__n];
  3019. }
  3020.  
  3021. template <class _Allocator>
  3022. void
  3023. vector<bool, _Allocator>::push_back(const value_type& __x)
  3024. {
  3025. if (this->__size_ == this->capacity())
  3026. reserve(__recommend(this->__size_ + 1));
  3027. ++this->__size_;
  3028. back() = __x;
  3029. }
  3030.  
  3031. template <class _Allocator>
  3032. typename vector<bool, _Allocator>::iterator
  3033. vector<bool, _Allocator>::insert(const_iterator __position, const value_type& __x)
  3034. {
  3035. iterator __r;
  3036. if (size() < capacity())
  3037. {
  3038. const_iterator __old_end = end();
  3039. ++__size_;
  3040. _VSTD::copy_backward(__position, __old_end, end());
  3041. __r = __const_iterator_cast(__position);
  3042. }
  3043. else
  3044. {
  3045. vector __v(__alloc());
  3046. __v.reserve(__recommend(__size_ + 1));
  3047. __v.__size_ = __size_ + 1;
  3048. __r = _VSTD::copy(cbegin(), __position, __v.begin());
  3049. _VSTD::copy_backward(__position, cend(), __v.end());
  3050. swap(__v);
  3051. }
  3052. *__r = __x;
  3053. return __r;
  3054. }
  3055.  
  3056. template <class _Allocator>
  3057. typename vector<bool, _Allocator>::iterator
  3058. vector<bool, _Allocator>::insert(const_iterator __position, size_type __n, const value_type& __x)
  3059. {
  3060. iterator __r;
  3061. size_type __c = capacity();
  3062. if (__n <= __c && size() <= __c - __n)
  3063. {
  3064. const_iterator __old_end = end();
  3065. __size_ += __n;
  3066. _VSTD::copy_backward(__position, __old_end, end());
  3067. __r = __const_iterator_cast(__position);
  3068. }
  3069. else
  3070. {
  3071. vector __v(__alloc());
  3072. __v.reserve(__recommend(__size_ + __n));
  3073. __v.__size_ = __size_ + __n;
  3074. __r = _VSTD::copy(cbegin(), __position, __v.begin());
  3075. _VSTD::copy_backward(__position, cend(), __v.end());
  3076. swap(__v);
  3077. }
  3078. _VSTD::fill_n(__r, __n, __x);
  3079. return __r;
  3080. }
  3081.  
  3082. template <class _Allocator>
  3083. template <class _InputIterator>
  3084. typename enable_if
  3085. <
  3086. __is_input_iterator <_InputIterator>::value &&
  3087. !__is_forward_iterator<_InputIterator>::value,
  3088. typename vector<bool, _Allocator>::iterator
  3089. >::type
  3090. vector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
  3091. {
  3092. difference_type __off = __position - begin();
  3093. iterator __p = __const_iterator_cast(__position);
  3094. iterator __old_end = end();
  3095. for (; size() != capacity() && __first != __last; ++__first)
  3096. {
  3097. ++this->__size_;
  3098. back() = *__first;
  3099. }
  3100. vector __v(__alloc());
  3101. if (__first != __last)
  3102. {
  3103. #ifndef _LIBCPP_NO_EXCEPTIONS
  3104. try
  3105. {
  3106. #endif // _LIBCPP_NO_EXCEPTIONS
  3107. __v.assign(__first, __last);
  3108. difference_type __old_size = static_cast<difference_type>(__old_end - begin());
  3109. difference_type __old_p = __p - begin();
  3110. reserve(__recommend(size() + __v.size()));
  3111. __p = begin() + __old_p;
  3112. __old_end = begin() + __old_size;
  3113. #ifndef _LIBCPP_NO_EXCEPTIONS
  3114. }
  3115. catch (...)
  3116. {
  3117. erase(__old_end, end());
  3118. throw;
  3119. }
  3120. #endif // _LIBCPP_NO_EXCEPTIONS
  3121. }
  3122. __p = _VSTD::rotate(__p, __old_end, end());
  3123. insert(__p, __v.begin(), __v.end());
  3124. return begin() + __off;
  3125. }
  3126.  
  3127. template <class _Allocator>
  3128. template <class _ForwardIterator>
  3129. typename enable_if
  3130. <
  3131. __is_forward_iterator<_ForwardIterator>::value,
  3132. typename vector<bool, _Allocator>::iterator
  3133. >::type
  3134. vector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last)
  3135. {
  3136. const difference_type __n_signed = _VSTD::distance(__first, __last);
  3137. _LIBCPP_ASSERT(__n_signed >= 0, "invalid range specified");
  3138. const size_type __n = static_cast<size_type>(__n_signed);
  3139. iterator __r;
  3140. size_type __c = capacity();
  3141. if (__n <= __c && size() <= __c - __n)
  3142. {
  3143. const_iterator __old_end = end();
  3144. __size_ += __n;
  3145. _VSTD::copy_backward(__position, __old_end, end());
  3146. __r = __const_iterator_cast(__position);
  3147. }
  3148. else
  3149. {
  3150. vector __v(__alloc());
  3151. __v.reserve(__recommend(__size_ + __n));
  3152. __v.__size_ = __size_ + __n;
  3153. __r = _VSTD::copy(cbegin(), __position, __v.begin());
  3154. _VSTD::copy_backward(__position, cend(), __v.end());
  3155. swap(__v);
  3156. }
  3157. _VSTD::copy(__first, __last, __r);
  3158. return __r;
  3159. }
  3160.  
  3161. template <class _Allocator>
  3162. inline _LIBCPP_INLINE_VISIBILITY
  3163. typename vector<bool, _Allocator>::iterator
  3164. vector<bool, _Allocator>::erase(const_iterator __position)
  3165. {
  3166. iterator __r = __const_iterator_cast(__position);
  3167. _VSTD::copy(__position + 1, this->cend(), __r);
  3168. --__size_;
  3169. return __r;
  3170. }
  3171.  
  3172. template <class _Allocator>
  3173. typename vector<bool, _Allocator>::iterator
  3174. vector<bool, _Allocator>::erase(const_iterator __first, const_iterator __last)
  3175. {
  3176. iterator __r = __const_iterator_cast(__first);
  3177. difference_type __d = __last - __first;
  3178. _VSTD::copy(__last, this->cend(), __r);
  3179. __size_ -= __d;
  3180. return __r;
  3181. }
  3182.  
  3183. template <class _Allocator>
  3184. void
  3185. vector<bool, _Allocator>::swap(vector& __x)
  3186. #if _LIBCPP_STD_VER >= 14
  3187. _NOEXCEPT
  3188. #else
  3189. _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
  3190. __is_nothrow_swappable<allocator_type>::value)
  3191. #endif
  3192. {
  3193. _VSTD::swap(this->__begin_, __x.__begin_);
  3194. _VSTD::swap(this->__size_, __x.__size_);
  3195. _VSTD::swap(this->__cap(), __x.__cap());
  3196. __swap_allocator(this->__alloc(), __x.__alloc(),
  3197. integral_constant<bool, __alloc_traits::propagate_on_container_swap::value>());
  3198. }
  3199.  
  3200. template <class _Allocator>
  3201. void
  3202. vector<bool, _Allocator>::resize(size_type __sz, value_type __x)
  3203. {
  3204. size_type __cs = size();
  3205. if (__cs < __sz)
  3206. {
  3207. iterator __r;
  3208. size_type __c = capacity();
  3209. size_type __n = __sz - __cs;
  3210. if (__n <= __c && __cs <= __c - __n)
  3211. {
  3212. __r = end();
  3213. __size_ += __n;
  3214. }
  3215. else
  3216. {
  3217. vector __v(__alloc());
  3218. __v.reserve(__recommend(__size_ + __n));
  3219. __v.__size_ = __size_ + __n;
  3220. __r = _VSTD::copy(cbegin(), cend(), __v.begin());
  3221. swap(__v);
  3222. }
  3223. _VSTD::fill_n(__r, __n, __x);
  3224. }
  3225. else
  3226. __size_ = __sz;
  3227. }
  3228.  
  3229. template <class _Allocator>
  3230. void
  3231. vector<bool, _Allocator>::flip() _NOEXCEPT
  3232. {
  3233. // do middle whole words
  3234. size_type __n = __size_;
  3235. __storage_pointer __p = __begin_;
  3236. for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
  3237. *__p = ~*__p;
  3238. // do last partial word
  3239. if (__n > 0)
  3240. {
  3241. __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
  3242. __storage_type __b = *__p & __m;
  3243. *__p &= ~__m;
  3244. *__p |= ~__b & __m;
  3245. }
  3246. }
  3247.  
  3248. template <class _Allocator>
  3249. bool
  3250. vector<bool, _Allocator>::__invariants() const
  3251. {
  3252. if (this->__begin_ == nullptr)
  3253. {
  3254. if (this->__size_ != 0 || this->__cap() != 0)
  3255. return false;
  3256. }
  3257. else
  3258. {
  3259. if (this->__cap() == 0)
  3260. return false;
  3261. if (this->__size_ > this->capacity())
  3262. return false;
  3263. }
  3264. return true;
  3265. }
  3266.  
  3267. template <class _Allocator>
  3268. size_t
  3269. vector<bool, _Allocator>::__hash_code() const _NOEXCEPT
  3270. {
  3271. size_t __h = 0;
  3272. // do middle whole words
  3273. size_type __n = __size_;
  3274. __storage_pointer __p = __begin_;
  3275. for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
  3276. __h ^= *__p;
  3277. // do last partial word
  3278. if (__n > 0)
  3279. {
  3280. const __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
  3281. __h ^= *__p & __m;
  3282. }
  3283. return __h;
  3284. }
  3285.  
  3286. template <class _Allocator>
  3287. struct _LIBCPP_TEMPLATE_VIS hash<vector<bool, _Allocator> >
  3288. : public unary_function<vector<bool, _Allocator>, size_t>
  3289. {
  3290. _LIBCPP_INLINE_VISIBILITY
  3291. size_t operator()(const vector<bool, _Allocator>& __vec) const _NOEXCEPT
  3292. {return __vec.__hash_code();}
  3293. };
  3294.  
  3295. template <class _Tp, class _Allocator>
  3296. inline _LIBCPP_INLINE_VISIBILITY
  3297. bool
  3298. operator==(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
  3299. {
  3300. const typename vector<_Tp, _Allocator>::size_type __sz = __x.size();
  3301. return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
  3302. }
  3303.  
  3304. template <class _Tp, class _Allocator>
  3305. inline _LIBCPP_INLINE_VISIBILITY
  3306. bool
  3307. operator!=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
  3308. {
  3309. return !(__x == __y);
  3310. }
  3311.  
  3312. template <class _Tp, class _Allocator>
  3313. inline _LIBCPP_INLINE_VISIBILITY
  3314. bool
  3315. operator< (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
  3316. {
  3317. return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
  3318. }
  3319.  
  3320. template <class _Tp, class _Allocator>
  3321. inline _LIBCPP_INLINE_VISIBILITY
  3322. bool
  3323. operator> (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
  3324. {
  3325. return __y < __x;
  3326. }
  3327.  
  3328. template <class _Tp, class _Allocator>
  3329. inline _LIBCPP_INLINE_VISIBILITY
  3330. bool
  3331. operator>=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
  3332. {
  3333. return !(__x < __y);
  3334. }
  3335.  
  3336. template <class _Tp, class _Allocator>
  3337. inline _LIBCPP_INLINE_VISIBILITY
  3338. bool
  3339. operator<=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
  3340. {
  3341. return !(__y < __x);
  3342. }
  3343.  
  3344. template <class _Tp, class _Allocator>
  3345. inline _LIBCPP_INLINE_VISIBILITY
  3346. void
  3347. swap(vector<_Tp, _Allocator>& __x, vector<_Tp, _Allocator>& __y)
  3348. _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
  3349. {
  3350. __x.swap(__y);
  3351. }
  3352.  
  3353. _LIBCPP_END_NAMESPACE_STD
  3354.  
  3355. _LIBCPP_POP_MACROS
  3356.  
  3357. #endif // _LIBCPP_VECTOR
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!