libstdc++
|
00001 // Vector implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001-2019 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /* 00026 * 00027 * Copyright (c) 1994 00028 * Hewlett-Packard Company 00029 * 00030 * Permission to use, copy, modify, distribute and sell this software 00031 * and its documentation for any purpose is hereby granted without fee, 00032 * provided that the above copyright notice appear in all copies and 00033 * that both that copyright notice and this permission notice appear 00034 * in supporting documentation. Hewlett-Packard Company makes no 00035 * representations about the suitability of this software for any 00036 * purpose. It is provided "as is" without express or implied warranty. 00037 * 00038 * 00039 * Copyright (c) 1996 00040 * Silicon Graphics Computer Systems, Inc. 00041 * 00042 * Permission to use, copy, modify, distribute and sell this software 00043 * and its documentation for any purpose is hereby granted without fee, 00044 * provided that the above copyright notice appear in all copies and 00045 * that both that copyright notice and this permission notice appear 00046 * in supporting documentation. Silicon Graphics makes no 00047 * representations about the suitability of this software for any 00048 * purpose. It is provided "as is" without express or implied warranty. 00049 */ 00050 00051 /** @file bits/stl_vector.h 00052 * This is an internal header file, included by other library headers. 00053 * Do not attempt to use it directly. @headername{vector} 00054 */ 00055 00056 #ifndef _STL_VECTOR_H 00057 #define _STL_VECTOR_H 1 00058 00059 #include <bits/stl_iterator_base_funcs.h> 00060 #include <bits/functexcept.h> 00061 #include <bits/concept_check.h> 00062 #if __cplusplus >= 201103L 00063 #include <initializer_list> 00064 #endif 00065 00066 #include <debug/assertions.h> 00067 00068 #if _GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR 00069 extern "C" void 00070 __sanitizer_annotate_contiguous_container(const void*, const void*, 00071 const void*, const void*); 00072 #endif 00073 00074 namespace std _GLIBCXX_VISIBILITY(default) 00075 { 00076 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00077 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 00078 00079 /// See bits/stl_deque.h's _Deque_base for an explanation. 00080 template<typename _Tp, typename _Alloc> 00081 struct _Vector_base 00082 { 00083 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template 00084 rebind<_Tp>::other _Tp_alloc_type; 00085 typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer 00086 pointer; 00087 00088 struct _Vector_impl_data 00089 { 00090 pointer _M_start; 00091 pointer _M_finish; 00092 pointer _M_end_of_storage; 00093 00094 _Vector_impl_data() _GLIBCXX_NOEXCEPT 00095 : _M_start(), _M_finish(), _M_end_of_storage() 00096 { } 00097 00098 #if __cplusplus >= 201103L 00099 _Vector_impl_data(_Vector_impl_data&& __x) noexcept 00100 : _M_start(__x._M_start), _M_finish(__x._M_finish), 00101 _M_end_of_storage(__x._M_end_of_storage) 00102 { __x._M_start = __x._M_finish = __x._M_end_of_storage = pointer(); } 00103 #endif 00104 00105 void 00106 _M_copy_data(_Vector_impl_data const& __x) _GLIBCXX_NOEXCEPT 00107 { 00108 _M_start = __x._M_start; 00109 _M_finish = __x._M_finish; 00110 _M_end_of_storage = __x._M_end_of_storage; 00111 } 00112 00113 void 00114 _M_swap_data(_Vector_impl_data& __x) _GLIBCXX_NOEXCEPT 00115 { 00116 // Do not use std::swap(_M_start, __x._M_start), etc as it loses 00117 // information used by TBAA. 00118 _Vector_impl_data __tmp; 00119 __tmp._M_copy_data(*this); 00120 _M_copy_data(__x); 00121 __x._M_copy_data(__tmp); 00122 } 00123 }; 00124 00125 struct _Vector_impl 00126 : public _Tp_alloc_type, public _Vector_impl_data 00127 { 00128 _Vector_impl() _GLIBCXX_NOEXCEPT_IF( 00129 is_nothrow_default_constructible<_Tp_alloc_type>::value) 00130 : _Tp_alloc_type() 00131 { } 00132 00133 _Vector_impl(_Tp_alloc_type const& __a) _GLIBCXX_NOEXCEPT 00134 : _Tp_alloc_type(__a) 00135 { } 00136 00137 #if __cplusplus >= 201103L 00138 // Not defaulted, to enforce noexcept(true) even when 00139 // !is_nothrow_move_constructible<_Tp_alloc_type>. 00140 _Vector_impl(_Vector_impl&& __x) noexcept 00141 : _Tp_alloc_type(std::move(__x)), _Vector_impl_data(std::move(__x)) 00142 { } 00143 00144 _Vector_impl(_Tp_alloc_type&& __a) noexcept 00145 : _Tp_alloc_type(std::move(__a)) 00146 { } 00147 00148 _Vector_impl(_Tp_alloc_type&& __a, _Vector_impl&& __rv) noexcept 00149 : _Tp_alloc_type(std::move(__a)), _Vector_impl_data(std::move(__rv)) 00150 { } 00151 #endif 00152 00153 #if _GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR 00154 template<typename = _Tp_alloc_type> 00155 struct _Asan 00156 { 00157 typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type> 00158 ::size_type size_type; 00159 00160 static void _S_shrink(_Vector_impl&, size_type) { } 00161 static void _S_on_dealloc(_Vector_impl&) { } 00162 00163 typedef _Vector_impl& _Reinit; 00164 00165 struct _Grow 00166 { 00167 _Grow(_Vector_impl&, size_type) { } 00168 void _M_grew(size_type) { } 00169 }; 00170 }; 00171 00172 // Enable ASan annotations for memory obtained from std::allocator. 00173 template<typename _Up> 00174 struct _Asan<allocator<_Up> > 00175 { 00176 typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type> 00177 ::size_type size_type; 00178 00179 // Adjust ASan annotation for [_M_start, _M_end_of_storage) to 00180 // mark end of valid region as __curr instead of __prev. 00181 static void 00182 _S_adjust(_Vector_impl& __impl, pointer __prev, pointer __curr) 00183 { 00184 __sanitizer_annotate_contiguous_container(__impl._M_start, 00185 __impl._M_end_of_storage, __prev, __curr); 00186 } 00187 00188 static void 00189 _S_grow(_Vector_impl& __impl, size_type __n) 00190 { _S_adjust(__impl, __impl._M_finish, __impl._M_finish + __n); } 00191 00192 static void 00193 _S_shrink(_Vector_impl& __impl, size_type __n) 00194 { _S_adjust(__impl, __impl._M_finish + __n, __impl._M_finish); } 00195 00196 static void 00197 _S_on_dealloc(_Vector_impl& __impl) 00198 { 00199 if (__impl._M_start) 00200 _S_adjust(__impl, __impl._M_finish, __impl._M_end_of_storage); 00201 } 00202 00203 // Used on reallocation to tell ASan unused capacity is invalid. 00204 struct _Reinit 00205 { 00206 explicit _Reinit(_Vector_impl& __impl) : _M_impl(__impl) 00207 { 00208 // Mark unused capacity as valid again before deallocating it. 00209 _S_on_dealloc(_M_impl); 00210 } 00211 00212 ~_Reinit() 00213 { 00214 // Mark unused capacity as invalid after reallocation. 00215 if (_M_impl._M_start) 00216 _S_adjust(_M_impl, _M_impl._M_end_of_storage, 00217 _M_impl._M_finish); 00218 } 00219 00220 _Vector_impl& _M_impl; 00221 00222 #if __cplusplus >= 201103L 00223 _Reinit(const _Reinit&) = delete; 00224 _Reinit& operator=(const _Reinit&) = delete; 00225 #endif 00226 }; 00227 00228 // Tell ASan when unused capacity is initialized to be valid. 00229 struct _Grow 00230 { 00231 _Grow(_Vector_impl& __impl, size_type __n) 00232 : _M_impl(__impl), _M_n(__n) 00233 { _S_grow(_M_impl, __n); } 00234 00235 ~_Grow() { if (_M_n) _S_shrink(_M_impl, _M_n); } 00236 00237 void _M_grew(size_type __n) { _M_n -= __n; } 00238 00239 #if __cplusplus >= 201103L 00240 _Grow(const _Grow&) = delete; 00241 _Grow& operator=(const _Grow&) = delete; 00242 #endif 00243 private: 00244 _Vector_impl& _M_impl; 00245 size_type _M_n; 00246 }; 00247 }; 00248 00249 #define _GLIBCXX_ASAN_ANNOTATE_REINIT \ 00250 typename _Base::_Vector_impl::template _Asan<>::_Reinit const \ 00251 __attribute__((__unused__)) __reinit_guard(this->_M_impl) 00252 #define _GLIBCXX_ASAN_ANNOTATE_GROW(n) \ 00253 typename _Base::_Vector_impl::template _Asan<>::_Grow \ 00254 __attribute__((__unused__)) __grow_guard(this->_M_impl, (n)) 00255 #define _GLIBCXX_ASAN_ANNOTATE_GREW(n) __grow_guard._M_grew(n) 00256 #define _GLIBCXX_ASAN_ANNOTATE_SHRINK(n) \ 00257 _Base::_Vector_impl::template _Asan<>::_S_shrink(this->_M_impl, n) 00258 #define _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC \ 00259 _Base::_Vector_impl::template _Asan<>::_S_on_dealloc(this->_M_impl) 00260 #else // ! (_GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR) 00261 #define _GLIBCXX_ASAN_ANNOTATE_REINIT 00262 #define _GLIBCXX_ASAN_ANNOTATE_GROW(n) 00263 #define _GLIBCXX_ASAN_ANNOTATE_GREW(n) 00264 #define _GLIBCXX_ASAN_ANNOTATE_SHRINK(n) 00265 #define _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC 00266 #endif // _GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR 00267 }; 00268 00269 public: 00270 typedef _Alloc allocator_type; 00271 00272 _Tp_alloc_type& 00273 _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT 00274 { return this->_M_impl; } 00275 00276 const _Tp_alloc_type& 00277 _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT 00278 { return this->_M_impl; } 00279 00280 allocator_type 00281 get_allocator() const _GLIBCXX_NOEXCEPT 00282 { return allocator_type(_M_get_Tp_allocator()); } 00283 00284 #if __cplusplus >= 201103L 00285 _Vector_base() = default; 00286 #else 00287 _Vector_base() { } 00288 #endif 00289 00290 _Vector_base(const allocator_type& __a) _GLIBCXX_NOEXCEPT 00291 : _M_impl(__a) { } 00292 00293 // Kept for ABI compatibility. 00294 #if !_GLIBCXX_INLINE_VERSION 00295 _Vector_base(size_t __n) 00296 : _M_impl() 00297 { _M_create_storage(__n); } 00298 #endif 00299 00300 _Vector_base(size_t __n, const allocator_type& __a) 00301 : _M_impl(__a) 00302 { _M_create_storage(__n); } 00303 00304 #if __cplusplus >= 201103L 00305 _Vector_base(_Vector_base&&) = default; 00306 00307 // Kept for ABI compatibility. 00308 # if !_GLIBCXX_INLINE_VERSION 00309 _Vector_base(_Tp_alloc_type&& __a) noexcept 00310 : _M_impl(std::move(__a)) { } 00311 00312 _Vector_base(_Vector_base&& __x, const allocator_type& __a) 00313 : _M_impl(__a) 00314 { 00315 if (__x.get_allocator() == __a) 00316 this->_M_impl._M_swap_data(__x._M_impl); 00317 else 00318 { 00319 size_t __n = __x._M_impl._M_finish - __x._M_impl._M_start; 00320 _M_create_storage(__n); 00321 } 00322 } 00323 # endif 00324 00325 _Vector_base(const allocator_type& __a, _Vector_base&& __x) 00326 : _M_impl(_Tp_alloc_type(__a), std::move(__x._M_impl)) 00327 { } 00328 #endif 00329 00330 ~_Vector_base() _GLIBCXX_NOEXCEPT 00331 { 00332 _M_deallocate(_M_impl._M_start, 00333 _M_impl._M_end_of_storage - _M_impl._M_start); 00334 } 00335 00336 public: 00337 _Vector_impl _M_impl; 00338 00339 pointer 00340 _M_allocate(size_t __n) 00341 { 00342 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr; 00343 return __n != 0 ? _Tr::allocate(_M_impl, __n) : pointer(); 00344 } 00345 00346 void 00347 _M_deallocate(pointer __p, size_t __n) 00348 { 00349 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr; 00350 if (__p) 00351 _Tr::deallocate(_M_impl, __p, __n); 00352 } 00353 00354 protected: 00355 void 00356 _M_create_storage(size_t __n) 00357 { 00358 this->_M_impl._M_start = this->_M_allocate(__n); 00359 this->_M_impl._M_finish = this->_M_impl._M_start; 00360 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 00361 } 00362 }; 00363 00364 /** 00365 * @brief A standard container which offers fixed time access to 00366 * individual elements in any order. 00367 * 00368 * @ingroup sequences 00369 * 00370 * @tparam _Tp Type of element. 00371 * @tparam _Alloc Allocator type, defaults to allocator<_Tp>. 00372 * 00373 * Meets the requirements of a <a href="tables.html#65">container</a>, a 00374 * <a href="tables.html#66">reversible container</a>, and a 00375 * <a href="tables.html#67">sequence</a>, including the 00376 * <a href="tables.html#68">optional sequence requirements</a> with the 00377 * %exception of @c push_front and @c pop_front. 00378 * 00379 * In some terminology a %vector can be described as a dynamic 00380 * C-style array, it offers fast and efficient access to individual 00381 * elements in any order and saves the user from worrying about 00382 * memory and size allocation. Subscripting ( @c [] ) access is 00383 * also provided as with C-style arrays. 00384 */ 00385 template<typename _Tp, typename _Alloc = std::allocator<_Tp> > 00386 class vector : protected _Vector_base<_Tp, _Alloc> 00387 { 00388 #ifdef _GLIBCXX_CONCEPT_CHECKS 00389 // Concept requirements. 00390 typedef typename _Alloc::value_type _Alloc_value_type; 00391 # if __cplusplus < 201103L 00392 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 00393 # endif 00394 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept) 00395 #endif 00396 00397 #if __cplusplus >= 201103L 00398 static_assert(is_same<typename remove_cv<_Tp>::type, _Tp>::value, 00399 "std::vector must have a non-const, non-volatile value_type"); 00400 # ifdef __STRICT_ANSI__ 00401 static_assert(is_same<typename _Alloc::value_type, _Tp>::value, 00402 "std::vector must have the same value_type as its allocator"); 00403 # endif 00404 #endif 00405 00406 typedef _Vector_base<_Tp, _Alloc> _Base; 00407 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; 00408 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Alloc_traits; 00409 00410 public: 00411 typedef _Tp value_type; 00412 typedef typename _Base::pointer pointer; 00413 typedef typename _Alloc_traits::const_pointer const_pointer; 00414 typedef typename _Alloc_traits::reference reference; 00415 typedef typename _Alloc_traits::const_reference const_reference; 00416 typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator; 00417 typedef __gnu_cxx::__normal_iterator<const_pointer, vector> 00418 const_iterator; 00419 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00420 typedef std::reverse_iterator<iterator> reverse_iterator; 00421 typedef size_t size_type; 00422 typedef ptrdiff_t difference_type; 00423 typedef _Alloc allocator_type; 00424 00425 private: 00426 #if __cplusplus >= 201103L 00427 static constexpr bool 00428 _S_nothrow_relocate(true_type) 00429 { 00430 return noexcept(std::__relocate_a(std::declval<pointer>(), 00431 std::declval<pointer>(), 00432 std::declval<pointer>(), 00433 std::declval<_Tp_alloc_type&>())); 00434 } 00435 00436 static constexpr bool 00437 _S_nothrow_relocate(false_type) 00438 { return false; } 00439 00440 static constexpr bool 00441 _S_use_relocate() 00442 { 00443 // Instantiating std::__relocate_a might cause an error outside the 00444 // immediate context (in __relocate_object_a's noexcept-specifier), 00445 // so only do it if we know the type can be move-inserted into *this. 00446 return _S_nothrow_relocate(__is_move_insertable<_Tp_alloc_type>{}); 00447 } 00448 00449 static pointer 00450 _S_do_relocate(pointer __first, pointer __last, pointer __result, 00451 _Tp_alloc_type& __alloc, true_type) noexcept 00452 { 00453 return std::__relocate_a(__first, __last, __result, __alloc); 00454 } 00455 00456 static pointer 00457 _S_do_relocate(pointer, pointer, pointer __result, 00458 _Tp_alloc_type&, false_type) noexcept 00459 { return __result; } 00460 00461 static pointer 00462 _S_relocate(pointer __first, pointer __last, pointer __result, 00463 _Tp_alloc_type& __alloc) noexcept 00464 { 00465 using __do_it = __bool_constant<_S_use_relocate()>; 00466 return _S_do_relocate(__first, __last, __result, __alloc, __do_it{}); 00467 } 00468 #endif // C++11 00469 00470 protected: 00471 using _Base::_M_allocate; 00472 using _Base::_M_deallocate; 00473 using _Base::_M_impl; 00474 using _Base::_M_get_Tp_allocator; 00475 00476 public: 00477 // [23.2.4.1] construct/copy/destroy 00478 // (assign() and get_allocator() are also listed in this section) 00479 00480 /** 00481 * @brief Creates a %vector with no elements. 00482 */ 00483 #if __cplusplus >= 201103L 00484 vector() = default; 00485 #else 00486 vector() { } 00487 #endif 00488 00489 /** 00490 * @brief Creates a %vector with no elements. 00491 * @param __a An allocator object. 00492 */ 00493 explicit 00494 vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT 00495 : _Base(__a) { } 00496 00497 #if __cplusplus >= 201103L 00498 /** 00499 * @brief Creates a %vector with default constructed elements. 00500 * @param __n The number of elements to initially create. 00501 * @param __a An allocator. 00502 * 00503 * This constructor fills the %vector with @a __n default 00504 * constructed elements. 00505 */ 00506 explicit 00507 vector(size_type __n, const allocator_type& __a = allocator_type()) 00508 : _Base(_S_check_init_len(__n, __a), __a) 00509 { _M_default_initialize(__n); } 00510 00511 /** 00512 * @brief Creates a %vector with copies of an exemplar element. 00513 * @param __n The number of elements to initially create. 00514 * @param __value An element to copy. 00515 * @param __a An allocator. 00516 * 00517 * This constructor fills the %vector with @a __n copies of @a __value. 00518 */ 00519 vector(size_type __n, const value_type& __value, 00520 const allocator_type& __a = allocator_type()) 00521 : _Base(_S_check_init_len(__n, __a), __a) 00522 { _M_fill_initialize(__n, __value); } 00523 #else 00524 /** 00525 * @brief Creates a %vector with copies of an exemplar element. 00526 * @param __n The number of elements to initially create. 00527 * @param __value An element to copy. 00528 * @param __a An allocator. 00529 * 00530 * This constructor fills the %vector with @a __n copies of @a __value. 00531 */ 00532 explicit 00533 vector(size_type __n, const value_type& __value = value_type(), 00534 const allocator_type& __a = allocator_type()) 00535 : _Base(_S_check_init_len(__n, __a), __a) 00536 { _M_fill_initialize(__n, __value); } 00537 #endif 00538 00539 /** 00540 * @brief %Vector copy constructor. 00541 * @param __x A %vector of identical element and allocator types. 00542 * 00543 * All the elements of @a __x are copied, but any unused capacity in 00544 * @a __x will not be copied 00545 * (i.e. capacity() == size() in the new %vector). 00546 * 00547 * The newly-created %vector uses a copy of the allocator object used 00548 * by @a __x (unless the allocator traits dictate a different object). 00549 */ 00550 vector(const vector& __x) 00551 : _Base(__x.size(), 00552 _Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator())) 00553 { 00554 this->_M_impl._M_finish = 00555 std::__uninitialized_copy_a(__x.begin(), __x.end(), 00556 this->_M_impl._M_start, 00557 _M_get_Tp_allocator()); 00558 } 00559 00560 #if __cplusplus >= 201103L 00561 /** 00562 * @brief %Vector move constructor. 00563 * 00564 * The newly-created %vector contains the exact contents of the 00565 * moved instance. 00566 * The contents of the moved instance are a valid, but unspecified 00567 * %vector. 00568 */ 00569 vector(vector&&) noexcept = default; 00570 00571 /// Copy constructor with alternative allocator 00572 vector(const vector& __x, const allocator_type& __a) 00573 : _Base(__x.size(), __a) 00574 { 00575 this->_M_impl._M_finish = 00576 std::__uninitialized_copy_a(__x.begin(), __x.end(), 00577 this->_M_impl._M_start, 00578 _M_get_Tp_allocator()); 00579 } 00580 00581 private: 00582 vector(vector&& __rv, const allocator_type& __m, true_type) noexcept 00583 : _Base(__m, std::move(__rv)) 00584 { } 00585 00586 vector(vector&& __rv, const allocator_type& __m, false_type) 00587 : _Base(__m) 00588 { 00589 if (__rv.get_allocator() == __m) 00590 this->_M_impl._M_swap_data(__rv._M_impl); 00591 else if (!__rv.empty()) 00592 { 00593 this->_M_create_storage(__rv.size()); 00594 this->_M_impl._M_finish = 00595 std::__uninitialized_move_a(__rv.begin(), __rv.end(), 00596 this->_M_impl._M_start, 00597 _M_get_Tp_allocator()); 00598 __rv.clear(); 00599 } 00600 } 00601 00602 public: 00603 /// Move constructor with alternative allocator 00604 vector(vector&& __rv, const allocator_type& __m) 00605 noexcept( noexcept( 00606 vector(std::declval<vector&&>(), std::declval<const allocator_type&>(), 00607 std::declval<typename _Alloc_traits::is_always_equal>())) ) 00608 : vector(std::move(__rv), __m, typename _Alloc_traits::is_always_equal{}) 00609 { } 00610 00611 /** 00612 * @brief Builds a %vector from an initializer list. 00613 * @param __l An initializer_list. 00614 * @param __a An allocator. 00615 * 00616 * Create a %vector consisting of copies of the elements in the 00617 * initializer_list @a __l. 00618 * 00619 * This will call the element type's copy constructor N times 00620 * (where N is @a __l.size()) and do no memory reallocation. 00621 */ 00622 vector(initializer_list<value_type> __l, 00623 const allocator_type& __a = allocator_type()) 00624 : _Base(__a) 00625 { 00626 _M_range_initialize(__l.begin(), __l.end(), 00627 random_access_iterator_tag()); 00628 } 00629 #endif 00630 00631 /** 00632 * @brief Builds a %vector from a range. 00633 * @param __first An input iterator. 00634 * @param __last An input iterator. 00635 * @param __a An allocator. 00636 * 00637 * Create a %vector consisting of copies of the elements from 00638 * [first,last). 00639 * 00640 * If the iterators are forward, bidirectional, or 00641 * random-access, then this will call the elements' copy 00642 * constructor N times (where N is distance(first,last)) and do 00643 * no memory reallocation. But if only input iterators are 00644 * used, then this will do at most 2N calls to the copy 00645 * constructor, and logN memory reallocations. 00646 */ 00647 #if __cplusplus >= 201103L 00648 template<typename _InputIterator, 00649 typename = std::_RequireInputIter<_InputIterator>> 00650 vector(_InputIterator __first, _InputIterator __last, 00651 const allocator_type& __a = allocator_type()) 00652 : _Base(__a) 00653 { 00654 _M_range_initialize(__first, __last, 00655 std::__iterator_category(__first)); 00656 } 00657 #else 00658 template<typename _InputIterator> 00659 vector(_InputIterator __first, _InputIterator __last, 00660 const allocator_type& __a = allocator_type()) 00661 : _Base(__a) 00662 { 00663 // Check whether it's an integral type. If so, it's not an iterator. 00664 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00665 _M_initialize_dispatch(__first, __last, _Integral()); 00666 } 00667 #endif 00668 00669 /** 00670 * The dtor only erases the elements, and note that if the 00671 * elements themselves are pointers, the pointed-to memory is 00672 * not touched in any way. Managing the pointer is the user's 00673 * responsibility. 00674 */ 00675 ~vector() _GLIBCXX_NOEXCEPT 00676 { 00677 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 00678 _M_get_Tp_allocator()); 00679 _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC; 00680 } 00681 00682 /** 00683 * @brief %Vector assignment operator. 00684 * @param __x A %vector of identical element and allocator types. 00685 * 00686 * All the elements of @a __x are copied, but any unused capacity in 00687 * @a __x will not be copied. 00688 * 00689 * Whether the allocator is copied depends on the allocator traits. 00690 */ 00691 vector& 00692 operator=(const vector& __x); 00693 00694 #if __cplusplus >= 201103L 00695 /** 00696 * @brief %Vector move assignment operator. 00697 * @param __x A %vector of identical element and allocator types. 00698 * 00699 * The contents of @a __x are moved into this %vector (without copying, 00700 * if the allocators permit it). 00701 * Afterwards @a __x is a valid, but unspecified %vector. 00702 * 00703 * Whether the allocator is moved depends on the allocator traits. 00704 */ 00705 vector& 00706 operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move()) 00707 { 00708 constexpr bool __move_storage = 00709 _Alloc_traits::_S_propagate_on_move_assign() 00710 || _Alloc_traits::_S_always_equal(); 00711 _M_move_assign(std::move(__x), __bool_constant<__move_storage>()); 00712 return *this; 00713 } 00714 00715 /** 00716 * @brief %Vector list assignment operator. 00717 * @param __l An initializer_list. 00718 * 00719 * This function fills a %vector with copies of the elements in the 00720 * initializer list @a __l. 00721 * 00722 * Note that the assignment completely changes the %vector and 00723 * that the resulting %vector's size is the same as the number 00724 * of elements assigned. 00725 */ 00726 vector& 00727 operator=(initializer_list<value_type> __l) 00728 { 00729 this->_M_assign_aux(__l.begin(), __l.end(), 00730 random_access_iterator_tag()); 00731 return *this; 00732 } 00733 #endif 00734 00735 /** 00736 * @brief Assigns a given value to a %vector. 00737 * @param __n Number of elements to be assigned. 00738 * @param __val Value to be assigned. 00739 * 00740 * This function fills a %vector with @a __n copies of the given 00741 * value. Note that the assignment completely changes the 00742 * %vector and that the resulting %vector's size is the same as 00743 * the number of elements assigned. 00744 */ 00745 void 00746 assign(size_type __n, const value_type& __val) 00747 { _M_fill_assign(__n, __val); } 00748 00749 /** 00750 * @brief Assigns a range to a %vector. 00751 * @param __first An input iterator. 00752 * @param __last An input iterator. 00753 * 00754 * This function fills a %vector with copies of the elements in the 00755 * range [__first,__last). 00756 * 00757 * Note that the assignment completely changes the %vector and 00758 * that the resulting %vector's size is the same as the number 00759 * of elements assigned. 00760 */ 00761 #if __cplusplus >= 201103L 00762 template<typename _InputIterator, 00763 typename = std::_RequireInputIter<_InputIterator>> 00764 void 00765 assign(_InputIterator __first, _InputIterator __last) 00766 { _M_assign_dispatch(__first, __last, __false_type()); } 00767 #else 00768 template<typename _InputIterator> 00769 void 00770 assign(_InputIterator __first, _InputIterator __last) 00771 { 00772 // Check whether it's an integral type. If so, it's not an iterator. 00773 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00774 _M_assign_dispatch(__first, __last, _Integral()); 00775 } 00776 #endif 00777 00778 #if __cplusplus >= 201103L 00779 /** 00780 * @brief Assigns an initializer list to a %vector. 00781 * @param __l An initializer_list. 00782 * 00783 * This function fills a %vector with copies of the elements in the 00784 * initializer list @a __l. 00785 * 00786 * Note that the assignment completely changes the %vector and 00787 * that the resulting %vector's size is the same as the number 00788 * of elements assigned. 00789 */ 00790 void 00791 assign(initializer_list<value_type> __l) 00792 { 00793 this->_M_assign_aux(__l.begin(), __l.end(), 00794 random_access_iterator_tag()); 00795 } 00796 #endif 00797 00798 /// Get a copy of the memory allocation object. 00799 using _Base::get_allocator; 00800 00801 // iterators 00802 /** 00803 * Returns a read/write iterator that points to the first 00804 * element in the %vector. Iteration is done in ordinary 00805 * element order. 00806 */ 00807 iterator 00808 begin() _GLIBCXX_NOEXCEPT 00809 { return iterator(this->_M_impl._M_start); } 00810 00811 /** 00812 * Returns a read-only (constant) iterator that points to the 00813 * first element in the %vector. Iteration is done in ordinary 00814 * element order. 00815 */ 00816 const_iterator 00817 begin() const _GLIBCXX_NOEXCEPT 00818 { return const_iterator(this->_M_impl._M_start); } 00819 00820 /** 00821 * Returns a read/write iterator that points one past the last 00822 * element in the %vector. Iteration is done in ordinary 00823 * element order. 00824 */ 00825 iterator 00826 end() _GLIBCXX_NOEXCEPT 00827 { return iterator(this->_M_impl._M_finish); } 00828 00829 /** 00830 * Returns a read-only (constant) iterator that points one past 00831 * the last element in the %vector. Iteration is done in 00832 * ordinary element order. 00833 */ 00834 const_iterator 00835 end() const _GLIBCXX_NOEXCEPT 00836 { return const_iterator(this->_M_impl._M_finish); } 00837 00838 /** 00839 * Returns a read/write reverse iterator that points to the 00840 * last element in the %vector. Iteration is done in reverse 00841 * element order. 00842 */ 00843 reverse_iterator 00844 rbegin() _GLIBCXX_NOEXCEPT 00845 { return reverse_iterator(end()); } 00846 00847 /** 00848 * Returns a read-only (constant) reverse iterator that points 00849 * to the last element in the %vector. Iteration is done in 00850 * reverse element order. 00851 */ 00852 const_reverse_iterator 00853 rbegin() const _GLIBCXX_NOEXCEPT 00854 { return const_reverse_iterator(end()); } 00855 00856 /** 00857 * Returns a read/write reverse iterator that points to one 00858 * before the first element in the %vector. Iteration is done 00859 * in reverse element order. 00860 */ 00861 reverse_iterator 00862 rend() _GLIBCXX_NOEXCEPT 00863 { return reverse_iterator(begin()); } 00864 00865 /** 00866 * Returns a read-only (constant) reverse iterator that points 00867 * to one before the first element in the %vector. Iteration 00868 * is done in reverse element order. 00869 */ 00870 const_reverse_iterator 00871 rend() const _GLIBCXX_NOEXCEPT 00872 { return const_reverse_iterator(begin()); } 00873 00874 #if __cplusplus >= 201103L 00875 /** 00876 * Returns a read-only (constant) iterator that points to the 00877 * first element in the %vector. Iteration is done in ordinary 00878 * element order. 00879 */ 00880 const_iterator 00881 cbegin() const noexcept 00882 { return const_iterator(this->_M_impl._M_start); } 00883 00884 /** 00885 * Returns a read-only (constant) iterator that points one past 00886 * the last element in the %vector. Iteration is done in 00887 * ordinary element order. 00888 */ 00889 const_iterator 00890 cend() const noexcept 00891 { return const_iterator(this->_M_impl._M_finish); } 00892 00893 /** 00894 * Returns a read-only (constant) reverse iterator that points 00895 * to the last element in the %vector. Iteration is done in 00896 * reverse element order. 00897 */ 00898 const_reverse_iterator 00899 crbegin() const noexcept 00900 { return const_reverse_iterator(end()); } 00901 00902 /** 00903 * Returns a read-only (constant) reverse iterator that points 00904 * to one before the first element in the %vector. Iteration 00905 * is done in reverse element order. 00906 */ 00907 const_reverse_iterator 00908 crend() const noexcept 00909 { return const_reverse_iterator(begin()); } 00910 #endif 00911 00912 // [23.2.4.2] capacity 00913 /** Returns the number of elements in the %vector. */ 00914 size_type 00915 size() const _GLIBCXX_NOEXCEPT 00916 { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); } 00917 00918 /** Returns the size() of the largest possible %vector. */ 00919 size_type 00920 max_size() const _GLIBCXX_NOEXCEPT 00921 { return _S_max_size(_M_get_Tp_allocator()); } 00922 00923 #if __cplusplus >= 201103L 00924 /** 00925 * @brief Resizes the %vector to the specified number of elements. 00926 * @param __new_size Number of elements the %vector should contain. 00927 * 00928 * This function will %resize the %vector to the specified 00929 * number of elements. If the number is smaller than the 00930 * %vector's current size the %vector is truncated, otherwise 00931 * default constructed elements are appended. 00932 */ 00933 void 00934 resize(size_type __new_size) 00935 { 00936 if (__new_size > size()) 00937 _M_default_append(__new_size - size()); 00938 else if (__new_size < size()) 00939 _M_erase_at_end(this->_M_impl._M_start + __new_size); 00940 } 00941 00942 /** 00943 * @brief Resizes the %vector to the specified number of elements. 00944 * @param __new_size Number of elements the %vector should contain. 00945 * @param __x Data with which new elements should be populated. 00946 * 00947 * This function will %resize the %vector to the specified 00948 * number of elements. If the number is smaller than the 00949 * %vector's current size the %vector is truncated, otherwise 00950 * the %vector is extended and new elements are populated with 00951 * given data. 00952 */ 00953 void 00954 resize(size_type __new_size, const value_type& __x) 00955 { 00956 if (__new_size > size()) 00957 _M_fill_insert(end(), __new_size - size(), __x); 00958 else if (__new_size < size()) 00959 _M_erase_at_end(this->_M_impl._M_start + __new_size); 00960 } 00961 #else 00962 /** 00963 * @brief Resizes the %vector to the specified number of elements. 00964 * @param __new_size Number of elements the %vector should contain. 00965 * @param __x Data with which new elements should be populated. 00966 * 00967 * This function will %resize the %vector to the specified 00968 * number of elements. If the number is smaller than the 00969 * %vector's current size the %vector is truncated, otherwise 00970 * the %vector is extended and new elements are populated with 00971 * given data. 00972 */ 00973 void 00974 resize(size_type __new_size, value_type __x = value_type()) 00975 { 00976 if (__new_size > size()) 00977 _M_fill_insert(end(), __new_size - size(), __x); 00978 else if (__new_size < size()) 00979 _M_erase_at_end(this->_M_impl._M_start + __new_size); 00980 } 00981 #endif 00982 00983 #if __cplusplus >= 201103L 00984 /** A non-binding request to reduce capacity() to size(). */ 00985 void 00986 shrink_to_fit() 00987 { _M_shrink_to_fit(); } 00988 #endif 00989 00990 /** 00991 * Returns the total number of elements that the %vector can 00992 * hold before needing to allocate more memory. 00993 */ 00994 size_type 00995 capacity() const _GLIBCXX_NOEXCEPT 00996 { return size_type(this->_M_impl._M_end_of_storage 00997 - this->_M_impl._M_start); } 00998 00999 /** 01000 * Returns true if the %vector is empty. (Thus begin() would 01001 * equal end().) 01002 */ 01003 _GLIBCXX_NODISCARD bool 01004 empty() const _GLIBCXX_NOEXCEPT 01005 { return begin() == end(); } 01006 01007 /** 01008 * @brief Attempt to preallocate enough memory for specified number of 01009 * elements. 01010 * @param __n Number of elements required. 01011 * @throw std::length_error If @a n exceeds @c max_size(). 01012 * 01013 * This function attempts to reserve enough memory for the 01014 * %vector to hold the specified number of elements. If the 01015 * number requested is more than max_size(), length_error is 01016 * thrown. 01017 * 01018 * The advantage of this function is that if optimal code is a 01019 * necessity and the user can determine the number of elements 01020 * that will be required, the user can reserve the memory in 01021 * %advance, and thus prevent a possible reallocation of memory 01022 * and copying of %vector data. 01023 */ 01024 void 01025 reserve(size_type __n); 01026 01027 // element access 01028 /** 01029 * @brief Subscript access to the data contained in the %vector. 01030 * @param __n The index of the element for which data should be 01031 * accessed. 01032 * @return Read/write reference to data. 01033 * 01034 * This operator allows for easy, array-style, data access. 01035 * Note that data access with this operator is unchecked and 01036 * out_of_range lookups are not defined. (For checked lookups 01037 * see at().) 01038 */ 01039 reference 01040 operator[](size_type __n) _GLIBCXX_NOEXCEPT 01041 { 01042 __glibcxx_requires_subscript(__n); 01043 return *(this->_M_impl._M_start + __n); 01044 } 01045 01046 /** 01047 * @brief Subscript access to the data contained in the %vector. 01048 * @param __n The index of the element for which data should be 01049 * accessed. 01050 * @return Read-only (constant) reference to data. 01051 * 01052 * This operator allows for easy, array-style, data access. 01053 * Note that data access with this operator is unchecked and 01054 * out_of_range lookups are not defined. (For checked lookups 01055 * see at().) 01056 */ 01057 const_reference 01058 operator[](size_type __n) const _GLIBCXX_NOEXCEPT 01059 { 01060 __glibcxx_requires_subscript(__n); 01061 return *(this->_M_impl._M_start + __n); 01062 } 01063 01064 protected: 01065 /// Safety check used only from at(). 01066 void 01067 _M_range_check(size_type __n) const 01068 { 01069 if (__n >= this->size()) 01070 __throw_out_of_range_fmt(__N("vector::_M_range_check: __n " 01071 "(which is %zu) >= this->size() " 01072 "(which is %zu)"), 01073 __n, this->size()); 01074 } 01075 01076 public: 01077 /** 01078 * @brief Provides access to the data contained in the %vector. 01079 * @param __n The index of the element for which data should be 01080 * accessed. 01081 * @return Read/write reference to data. 01082 * @throw std::out_of_range If @a __n is an invalid index. 01083 * 01084 * This function provides for safer data access. The parameter 01085 * is first checked that it is in the range of the vector. The 01086 * function throws out_of_range if the check fails. 01087 */ 01088 reference 01089 at(size_type __n) 01090 { 01091 _M_range_check(__n); 01092 return (*this)[__n]; 01093 } 01094 01095 /** 01096 * @brief Provides access to the data contained in the %vector. 01097 * @param __n The index of the element for which data should be 01098 * accessed. 01099 * @return Read-only (constant) reference to data. 01100 * @throw std::out_of_range If @a __n is an invalid index. 01101 * 01102 * This function provides for safer data access. The parameter 01103 * is first checked that it is in the range of the vector. The 01104 * function throws out_of_range if the check fails. 01105 */ 01106 const_reference 01107 at(size_type __n) const 01108 { 01109 _M_range_check(__n); 01110 return (*this)[__n]; 01111 } 01112 01113 /** 01114 * Returns a read/write reference to the data at the first 01115 * element of the %vector. 01116 */ 01117 reference 01118 front() _GLIBCXX_NOEXCEPT 01119 { 01120 __glibcxx_requires_nonempty(); 01121 return *begin(); 01122 } 01123 01124 /** 01125 * Returns a read-only (constant) reference to the data at the first 01126 * element of the %vector. 01127 */ 01128 const_reference 01129 front() const _GLIBCXX_NOEXCEPT 01130 { 01131 __glibcxx_requires_nonempty(); 01132 return *begin(); 01133 } 01134 01135 /** 01136 * Returns a read/write reference to the data at the last 01137 * element of the %vector. 01138 */ 01139 reference 01140 back() _GLIBCXX_NOEXCEPT 01141 { 01142 __glibcxx_requires_nonempty(); 01143 return *(end() - 1); 01144 } 01145 01146 /** 01147 * Returns a read-only (constant) reference to the data at the 01148 * last element of the %vector. 01149 */ 01150 const_reference 01151 back() const _GLIBCXX_NOEXCEPT 01152 { 01153 __glibcxx_requires_nonempty(); 01154 return *(end() - 1); 01155 } 01156 01157 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01158 // DR 464. Suggestion for new member functions in standard containers. 01159 // data access 01160 /** 01161 * Returns a pointer such that [data(), data() + size()) is a valid 01162 * range. For a non-empty %vector, data() == &front(). 01163 */ 01164 _Tp* 01165 data() _GLIBCXX_NOEXCEPT 01166 { return _M_data_ptr(this->_M_impl._M_start); } 01167 01168 const _Tp* 01169 data() const _GLIBCXX_NOEXCEPT 01170 { return _M_data_ptr(this->_M_impl._M_start); } 01171 01172 // [23.2.4.3] modifiers 01173 /** 01174 * @brief Add data to the end of the %vector. 01175 * @param __x Data to be added. 01176 * 01177 * This is a typical stack operation. The function creates an 01178 * element at the end of the %vector and assigns the given data 01179 * to it. Due to the nature of a %vector this operation can be 01180 * done in constant time if the %vector has preallocated space 01181 * available. 01182 */ 01183 void 01184 push_back(const value_type& __x) 01185 { 01186 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 01187 { 01188 _GLIBCXX_ASAN_ANNOTATE_GROW(1); 01189 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, 01190 __x); 01191 ++this->_M_impl._M_finish; 01192 _GLIBCXX_ASAN_ANNOTATE_GREW(1); 01193 } 01194 else 01195 _M_realloc_insert(end(), __x); 01196 } 01197 01198 #if __cplusplus >= 201103L 01199 void 01200 push_back(value_type&& __x) 01201 { emplace_back(std::move(__x)); } 01202 01203 template<typename... _Args> 01204 #if __cplusplus > 201402L 01205 reference 01206 #else 01207 void 01208 #endif 01209 emplace_back(_Args&&... __args); 01210 #endif 01211 01212 /** 01213 * @brief Removes last element. 01214 * 01215 * This is a typical stack operation. It shrinks the %vector by one. 01216 * 01217 * Note that no data is returned, and if the last element's 01218 * data is needed, it should be retrieved before pop_back() is 01219 * called. 01220 */ 01221 void 01222 pop_back() _GLIBCXX_NOEXCEPT 01223 { 01224 __glibcxx_requires_nonempty(); 01225 --this->_M_impl._M_finish; 01226 _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish); 01227 _GLIBCXX_ASAN_ANNOTATE_SHRINK(1); 01228 } 01229 01230 #if __cplusplus >= 201103L 01231 /** 01232 * @brief Inserts an object in %vector before specified iterator. 01233 * @param __position A const_iterator into the %vector. 01234 * @param __args Arguments. 01235 * @return An iterator that points to the inserted data. 01236 * 01237 * This function will insert an object of type T constructed 01238 * with T(std::forward<Args>(args)...) before the specified location. 01239 * Note that this kind of operation could be expensive for a %vector 01240 * and if it is frequently used the user should consider using 01241 * std::list. 01242 */ 01243 template<typename... _Args> 01244 iterator 01245 emplace(const_iterator __position, _Args&&... __args) 01246 { return _M_emplace_aux(__position, std::forward<_Args>(__args)...); } 01247 01248 /** 01249 * @brief Inserts given value into %vector before specified iterator. 01250 * @param __position A const_iterator into the %vector. 01251 * @param __x Data to be inserted. 01252 * @return An iterator that points to the inserted data. 01253 * 01254 * This function will insert a copy of the given value before 01255 * the specified location. Note that this kind of operation 01256 * could be expensive for a %vector and if it is frequently 01257 * used the user should consider using std::list. 01258 */ 01259 iterator 01260 insert(const_iterator __position, const value_type& __x); 01261 #else 01262 /** 01263 * @brief Inserts given value into %vector before specified iterator. 01264 * @param __position An iterator into the %vector. 01265 * @param __x Data to be inserted. 01266 * @return An iterator that points to the inserted data. 01267 * 01268 * This function will insert a copy of the given value before 01269 * the specified location. Note that this kind of operation 01270 * could be expensive for a %vector and if it is frequently 01271 * used the user should consider using std::list. 01272 */ 01273 iterator 01274 insert(iterator __position, const value_type& __x); 01275 #endif 01276 01277 #if __cplusplus >= 201103L 01278 /** 01279 * @brief Inserts given rvalue into %vector before specified iterator. 01280 * @param __position A const_iterator into the %vector. 01281 * @param __x Data to be inserted. 01282 * @return An iterator that points to the inserted data. 01283 * 01284 * This function will insert a copy of the given rvalue before 01285 * the specified location. Note that this kind of operation 01286 * could be expensive for a %vector and if it is frequently 01287 * used the user should consider using std::list. 01288 */ 01289 iterator 01290 insert(const_iterator __position, value_type&& __x) 01291 { return _M_insert_rval(__position, std::move(__x)); } 01292 01293 /** 01294 * @brief Inserts an initializer_list into the %vector. 01295 * @param __position An iterator into the %vector. 01296 * @param __l An initializer_list. 01297 * 01298 * This function will insert copies of the data in the 01299 * initializer_list @a l into the %vector before the location 01300 * specified by @a position. 01301 * 01302 * Note that this kind of operation could be expensive for a 01303 * %vector and if it is frequently used the user should 01304 * consider using std::list. 01305 */ 01306 iterator 01307 insert(const_iterator __position, initializer_list<value_type> __l) 01308 { 01309 auto __offset = __position - cbegin(); 01310 _M_range_insert(begin() + __offset, __l.begin(), __l.end(), 01311 std::random_access_iterator_tag()); 01312 return begin() + __offset; 01313 } 01314 #endif 01315 01316 #if __cplusplus >= 201103L 01317 /** 01318 * @brief Inserts a number of copies of given data into the %vector. 01319 * @param __position A const_iterator into the %vector. 01320 * @param __n Number of elements to be inserted. 01321 * @param __x Data to be inserted. 01322 * @return An iterator that points to the inserted data. 01323 * 01324 * This function will insert a specified number of copies of 01325 * the given data before the location specified by @a position. 01326 * 01327 * Note that this kind of operation could be expensive for a 01328 * %vector and if it is frequently used the user should 01329 * consider using std::list. 01330 */ 01331 iterator 01332 insert(const_iterator __position, size_type __n, const value_type& __x) 01333 { 01334 difference_type __offset = __position - cbegin(); 01335 _M_fill_insert(begin() + __offset, __n, __x); 01336 return begin() + __offset; 01337 } 01338 #else 01339 /** 01340 * @brief Inserts a number of copies of given data into the %vector. 01341 * @param __position An iterator into the %vector. 01342 * @param __n Number of elements to be inserted. 01343 * @param __x Data to be inserted. 01344 * 01345 * This function will insert a specified number of copies of 01346 * the given data before the location specified by @a position. 01347 * 01348 * Note that this kind of operation could be expensive for a 01349 * %vector and if it is frequently used the user should 01350 * consider using std::list. 01351 */ 01352 void 01353 insert(iterator __position, size_type __n, const value_type& __x) 01354 { _M_fill_insert(__position, __n, __x); } 01355 #endif 01356 01357 #if __cplusplus >= 201103L 01358 /** 01359 * @brief Inserts a range into the %vector. 01360 * @param __position A const_iterator into the %vector. 01361 * @param __first An input iterator. 01362 * @param __last An input iterator. 01363 * @return An iterator that points to the inserted data. 01364 * 01365 * This function will insert copies of the data in the range 01366 * [__first,__last) into the %vector before the location specified 01367 * by @a pos. 01368 * 01369 * Note that this kind of operation could be expensive for a 01370 * %vector and if it is frequently used the user should 01371 * consider using std::list. 01372 */ 01373 template<typename _InputIterator, 01374 typename = std::_RequireInputIter<_InputIterator>> 01375 iterator 01376 insert(const_iterator __position, _InputIterator __first, 01377 _InputIterator __last) 01378 { 01379 difference_type __offset = __position - cbegin(); 01380 _M_insert_dispatch(begin() + __offset, 01381 __first, __last, __false_type()); 01382 return begin() + __offset; 01383 } 01384 #else 01385 /** 01386 * @brief Inserts a range into the %vector. 01387 * @param __position An iterator into the %vector. 01388 * @param __first An input iterator. 01389 * @param __last An input iterator. 01390 * 01391 * This function will insert copies of the data in the range 01392 * [__first,__last) into the %vector before the location specified 01393 * by @a pos. 01394 * 01395 * Note that this kind of operation could be expensive for a 01396 * %vector and if it is frequently used the user should 01397 * consider using std::list. 01398 */ 01399 template<typename _InputIterator> 01400 void 01401 insert(iterator __position, _InputIterator __first, 01402 _InputIterator __last) 01403 { 01404 // Check whether it's an integral type. If so, it's not an iterator. 01405 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 01406 _M_insert_dispatch(__position, __first, __last, _Integral()); 01407 } 01408 #endif 01409 01410 /** 01411 * @brief Remove element at given position. 01412 * @param __position Iterator pointing to element to be erased. 01413 * @return An iterator pointing to the next element (or end()). 01414 * 01415 * This function will erase the element at the given position and thus 01416 * shorten the %vector by one. 01417 * 01418 * Note This operation could be expensive and if it is 01419 * frequently used the user should consider using std::list. 01420 * The user is also cautioned that this function only erases 01421 * the element, and that if the element is itself a pointer, 01422 * the pointed-to memory is not touched in any way. Managing 01423 * the pointer is the user's responsibility. 01424 */ 01425 iterator 01426 #if __cplusplus >= 201103L 01427 erase(const_iterator __position) 01428 { return _M_erase(begin() + (__position - cbegin())); } 01429 #else 01430 erase(iterator __position) 01431 { return _M_erase(__position); } 01432 #endif 01433 01434 /** 01435 * @brief Remove a range of elements. 01436 * @param __first Iterator pointing to the first element to be erased. 01437 * @param __last Iterator pointing to one past the last element to be 01438 * erased. 01439 * @return An iterator pointing to the element pointed to by @a __last 01440 * prior to erasing (or end()). 01441 * 01442 * This function will erase the elements in the range 01443 * [__first,__last) and shorten the %vector accordingly. 01444 * 01445 * Note This operation could be expensive and if it is 01446 * frequently used the user should consider using std::list. 01447 * The user is also cautioned that this function only erases 01448 * the elements, and that if the elements themselves are 01449 * pointers, the pointed-to memory is not touched in any way. 01450 * Managing the pointer is the user's responsibility. 01451 */ 01452 iterator 01453 #if __cplusplus >= 201103L 01454 erase(const_iterator __first, const_iterator __last) 01455 { 01456 const auto __beg = begin(); 01457 const auto __cbeg = cbegin(); 01458 return _M_erase(__beg + (__first - __cbeg), __beg + (__last - __cbeg)); 01459 } 01460 #else 01461 erase(iterator __first, iterator __last) 01462 { return _M_erase(__first, __last); } 01463 #endif 01464 01465 /** 01466 * @brief Swaps data with another %vector. 01467 * @param __x A %vector of the same element and allocator types. 01468 * 01469 * This exchanges the elements between two vectors in constant time. 01470 * (Three pointers, so it should be quite fast.) 01471 * Note that the global std::swap() function is specialized such that 01472 * std::swap(v1,v2) will feed to this function. 01473 * 01474 * Whether the allocators are swapped depends on the allocator traits. 01475 */ 01476 void 01477 swap(vector& __x) _GLIBCXX_NOEXCEPT 01478 { 01479 #if __cplusplus >= 201103L 01480 __glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value 01481 || _M_get_Tp_allocator() == __x._M_get_Tp_allocator()); 01482 #endif 01483 this->_M_impl._M_swap_data(__x._M_impl); 01484 _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(), 01485 __x._M_get_Tp_allocator()); 01486 } 01487 01488 /** 01489 * Erases all the elements. Note that this function only erases the 01490 * elements, and that if the elements themselves are pointers, the 01491 * pointed-to memory is not touched in any way. Managing the pointer is 01492 * the user's responsibility. 01493 */ 01494 void 01495 clear() _GLIBCXX_NOEXCEPT 01496 { _M_erase_at_end(this->_M_impl._M_start); } 01497 01498 protected: 01499 /** 01500 * Memory expansion handler. Uses the member allocation function to 01501 * obtain @a n bytes of memory, and then copies [first,last) into it. 01502 */ 01503 template<typename _ForwardIterator> 01504 pointer 01505 _M_allocate_and_copy(size_type __n, 01506 _ForwardIterator __first, _ForwardIterator __last) 01507 { 01508 pointer __result = this->_M_allocate(__n); 01509 __try 01510 { 01511 std::__uninitialized_copy_a(__first, __last, __result, 01512 _M_get_Tp_allocator()); 01513 return __result; 01514 } 01515 __catch(...) 01516 { 01517 _M_deallocate(__result, __n); 01518 __throw_exception_again; 01519 } 01520 } 01521 01522 01523 // Internal constructor functions follow. 01524 01525 // Called by the range constructor to implement [23.1.1]/9 01526 01527 #if __cplusplus < 201103L 01528 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01529 // 438. Ambiguity in the "do the right thing" clause 01530 template<typename _Integer> 01531 void 01532 _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type) 01533 { 01534 this->_M_impl._M_start = _M_allocate(_S_check_init_len( 01535 static_cast<size_type>(__n), _M_get_Tp_allocator())); 01536 this->_M_impl._M_end_of_storage = 01537 this->_M_impl._M_start + static_cast<size_type>(__n); 01538 _M_fill_initialize(static_cast<size_type>(__n), __value); 01539 } 01540 01541 // Called by the range constructor to implement [23.1.1]/9 01542 template<typename _InputIterator> 01543 void 01544 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 01545 __false_type) 01546 { 01547 _M_range_initialize(__first, __last, 01548 std::__iterator_category(__first)); 01549 } 01550 #endif 01551 01552 // Called by the second initialize_dispatch above 01553 template<typename _InputIterator> 01554 void 01555 _M_range_initialize(_InputIterator __first, _InputIterator __last, 01556 std::input_iterator_tag) 01557 { 01558 __try { 01559 for (; __first != __last; ++__first) 01560 #if __cplusplus >= 201103L 01561 emplace_back(*__first); 01562 #else 01563 push_back(*__first); 01564 #endif 01565 } __catch(...) { 01566 clear(); 01567 __throw_exception_again; 01568 } 01569 } 01570 01571 // Called by the second initialize_dispatch above 01572 template<typename _ForwardIterator> 01573 void 01574 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, 01575 std::forward_iterator_tag) 01576 { 01577 const size_type __n = std::distance(__first, __last); 01578 this->_M_impl._M_start 01579 = this->_M_allocate(_S_check_init_len(__n, _M_get_Tp_allocator())); 01580 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 01581 this->_M_impl._M_finish = 01582 std::__uninitialized_copy_a(__first, __last, 01583 this->_M_impl._M_start, 01584 _M_get_Tp_allocator()); 01585 } 01586 01587 // Called by the first initialize_dispatch above and by the 01588 // vector(n,value,a) constructor. 01589 void 01590 _M_fill_initialize(size_type __n, const value_type& __value) 01591 { 01592 this->_M_impl._M_finish = 01593 std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value, 01594 _M_get_Tp_allocator()); 01595 } 01596 01597 #if __cplusplus >= 201103L 01598 // Called by the vector(n) constructor. 01599 void 01600 _M_default_initialize(size_type __n) 01601 { 01602 this->_M_impl._M_finish = 01603 std::__uninitialized_default_n_a(this->_M_impl._M_start, __n, 01604 _M_get_Tp_allocator()); 01605 } 01606 #endif 01607 01608 // Internal assign functions follow. The *_aux functions do the actual 01609 // assignment work for the range versions. 01610 01611 // Called by the range assign to implement [23.1.1]/9 01612 01613 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01614 // 438. Ambiguity in the "do the right thing" clause 01615 template<typename _Integer> 01616 void 01617 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 01618 { _M_fill_assign(__n, __val); } 01619 01620 // Called by the range assign to implement [23.1.1]/9 01621 template<typename _InputIterator> 01622 void 01623 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 01624 __false_type) 01625 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } 01626 01627 // Called by the second assign_dispatch above 01628 template<typename _InputIterator> 01629 void 01630 _M_assign_aux(_InputIterator __first, _InputIterator __last, 01631 std::input_iterator_tag); 01632 01633 // Called by the second assign_dispatch above 01634 template<typename _ForwardIterator> 01635 void 01636 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 01637 std::forward_iterator_tag); 01638 01639 // Called by assign(n,t), and the range assign when it turns out 01640 // to be the same thing. 01641 void 01642 _M_fill_assign(size_type __n, const value_type& __val); 01643 01644 // Internal insert functions follow. 01645 01646 // Called by the range insert to implement [23.1.1]/9 01647 01648 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01649 // 438. Ambiguity in the "do the right thing" clause 01650 template<typename _Integer> 01651 void 01652 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val, 01653 __true_type) 01654 { _M_fill_insert(__pos, __n, __val); } 01655 01656 // Called by the range insert to implement [23.1.1]/9 01657 template<typename _InputIterator> 01658 void 01659 _M_insert_dispatch(iterator __pos, _InputIterator __first, 01660 _InputIterator __last, __false_type) 01661 { 01662 _M_range_insert(__pos, __first, __last, 01663 std::__iterator_category(__first)); 01664 } 01665 01666 // Called by the second insert_dispatch above 01667 template<typename _InputIterator> 01668 void 01669 _M_range_insert(iterator __pos, _InputIterator __first, 01670 _InputIterator __last, std::input_iterator_tag); 01671 01672 // Called by the second insert_dispatch above 01673 template<typename _ForwardIterator> 01674 void 01675 _M_range_insert(iterator __pos, _ForwardIterator __first, 01676 _ForwardIterator __last, std::forward_iterator_tag); 01677 01678 // Called by insert(p,n,x), and the range insert when it turns out to be 01679 // the same thing. 01680 void 01681 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x); 01682 01683 #if __cplusplus >= 201103L 01684 // Called by resize(n). 01685 void 01686 _M_default_append(size_type __n); 01687 01688 bool 01689 _M_shrink_to_fit(); 01690 #endif 01691 01692 #if __cplusplus < 201103L 01693 // Called by insert(p,x) 01694 void 01695 _M_insert_aux(iterator __position, const value_type& __x); 01696 01697 void 01698 _M_realloc_insert(iterator __position, const value_type& __x); 01699 #else 01700 // A value_type object constructed with _Alloc_traits::construct() 01701 // and destroyed with _Alloc_traits::destroy(). 01702 struct _Temporary_value 01703 { 01704 template<typename... _Args> 01705 explicit 01706 _Temporary_value(vector* __vec, _Args&&... __args) : _M_this(__vec) 01707 { 01708 _Alloc_traits::construct(_M_this->_M_impl, _M_ptr(), 01709 std::forward<_Args>(__args)...); 01710 } 01711 01712 ~_Temporary_value() 01713 { _Alloc_traits::destroy(_M_this->_M_impl, _M_ptr()); } 01714 01715 value_type& 01716 _M_val() { return *_M_ptr(); } 01717 01718 private: 01719 _Tp* 01720 _M_ptr() { return reinterpret_cast<_Tp*>(&__buf); } 01721 01722 vector* _M_this; 01723 typename aligned_storage<sizeof(_Tp), alignof(_Tp)>::type __buf; 01724 }; 01725 01726 // Called by insert(p,x) and other functions when insertion needs to 01727 // reallocate or move existing elements. _Arg is either _Tp& or _Tp. 01728 template<typename _Arg> 01729 void 01730 _M_insert_aux(iterator __position, _Arg&& __arg); 01731 01732 template<typename... _Args> 01733 void 01734 _M_realloc_insert(iterator __position, _Args&&... __args); 01735 01736 // Either move-construct at the end, or forward to _M_insert_aux. 01737 iterator 01738 _M_insert_rval(const_iterator __position, value_type&& __v); 01739 01740 // Try to emplace at the end, otherwise forward to _M_insert_aux. 01741 template<typename... _Args> 01742 iterator 01743 _M_emplace_aux(const_iterator __position, _Args&&... __args); 01744 01745 // Emplacing an rvalue of the correct type can use _M_insert_rval. 01746 iterator 01747 _M_emplace_aux(const_iterator __position, value_type&& __v) 01748 { return _M_insert_rval(__position, std::move(__v)); } 01749 #endif 01750 01751 // Called by _M_fill_insert, _M_insert_aux etc. 01752 size_type 01753 _M_check_len(size_type __n, const char* __s) const 01754 { 01755 if (max_size() - size() < __n) 01756 __throw_length_error(__N(__s)); 01757 01758 const size_type __len = size() + (std::max)(size(), __n); 01759 return (__len < size() || __len > max_size()) ? max_size() : __len; 01760 } 01761 01762 // Called by constructors to check initial size. 01763 static size_type 01764 _S_check_init_len(size_type __n, const allocator_type& __a) 01765 { 01766 if (__n > _S_max_size(_Tp_alloc_type(__a))) 01767 __throw_length_error( 01768 __N("cannot create std::vector larger than max_size()")); 01769 return __n; 01770 } 01771 01772 static size_type 01773 _S_max_size(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT 01774 { 01775 // std::distance(begin(), end()) cannot be greater than PTRDIFF_MAX, 01776 // and realistically we can't store more than PTRDIFF_MAX/sizeof(T) 01777 // (even if std::allocator_traits::max_size says we can). 01778 const size_t __diffmax 01779 = __gnu_cxx::__numeric_traits<ptrdiff_t>::__max / sizeof(_Tp); 01780 const size_t __allocmax = _Alloc_traits::max_size(__a); 01781 return (std::min)(__diffmax, __allocmax); 01782 } 01783 01784 // Internal erase functions follow. 01785 01786 // Called by erase(q1,q2), clear(), resize(), _M_fill_assign, 01787 // _M_assign_aux. 01788 void 01789 _M_erase_at_end(pointer __pos) _GLIBCXX_NOEXCEPT 01790 { 01791 if (size_type __n = this->_M_impl._M_finish - __pos) 01792 { 01793 std::_Destroy(__pos, this->_M_impl._M_finish, 01794 _M_get_Tp_allocator()); 01795 this->_M_impl._M_finish = __pos; 01796 _GLIBCXX_ASAN_ANNOTATE_SHRINK(__n); 01797 } 01798 } 01799 01800 iterator 01801 _M_erase(iterator __position); 01802 01803 iterator 01804 _M_erase(iterator __first, iterator __last); 01805 01806 #if __cplusplus >= 201103L 01807 private: 01808 // Constant-time move assignment when source object's memory can be 01809 // moved, either because the source's allocator will move too 01810 // or because the allocators are equal. 01811 void 01812 _M_move_assign(vector&& __x, true_type) noexcept 01813 { 01814 vector __tmp(get_allocator()); 01815 this->_M_impl._M_swap_data(__x._M_impl); 01816 __tmp._M_impl._M_swap_data(__x._M_impl); 01817 std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator()); 01818 } 01819 01820 // Do move assignment when it might not be possible to move source 01821 // object's memory, resulting in a linear-time operation. 01822 void 01823 _M_move_assign(vector&& __x, false_type) 01824 { 01825 if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator()) 01826 _M_move_assign(std::move(__x), true_type()); 01827 else 01828 { 01829 // The rvalue's allocator cannot be moved and is not equal, 01830 // so we need to individually move each element. 01831 this->assign(std::__make_move_if_noexcept_iterator(__x.begin()), 01832 std::__make_move_if_noexcept_iterator(__x.end())); 01833 __x.clear(); 01834 } 01835 } 01836 #endif 01837 01838 template<typename _Up> 01839 _Up* 01840 _M_data_ptr(_Up* __ptr) const _GLIBCXX_NOEXCEPT 01841 { return __ptr; } 01842 01843 #if __cplusplus >= 201103L 01844 template<typename _Ptr> 01845 typename std::pointer_traits<_Ptr>::element_type* 01846 _M_data_ptr(_Ptr __ptr) const 01847 { return empty() ? nullptr : std::__to_address(__ptr); } 01848 #else 01849 template<typename _Up> 01850 _Up* 01851 _M_data_ptr(_Up* __ptr) _GLIBCXX_NOEXCEPT 01852 { return __ptr; } 01853 01854 template<typename _Ptr> 01855 value_type* 01856 _M_data_ptr(_Ptr __ptr) 01857 { return empty() ? (value_type*)0 : __ptr.operator->(); } 01858 01859 template<typename _Ptr> 01860 const value_type* 01861 _M_data_ptr(_Ptr __ptr) const 01862 { return empty() ? (const value_type*)0 : __ptr.operator->(); } 01863 #endif 01864 }; 01865 01866 #if __cpp_deduction_guides >= 201606 01867 template<typename _InputIterator, typename _ValT 01868 = typename iterator_traits<_InputIterator>::value_type, 01869 typename _Allocator = allocator<_ValT>, 01870 typename = _RequireInputIter<_InputIterator>, 01871 typename = _RequireAllocator<_Allocator>> 01872 vector(_InputIterator, _InputIterator, _Allocator = _Allocator()) 01873 -> vector<_ValT, _Allocator>; 01874 #endif 01875 01876 /** 01877 * @brief Vector equality comparison. 01878 * @param __x A %vector. 01879 * @param __y A %vector of the same type as @a __x. 01880 * @return True iff the size and elements of the vectors are equal. 01881 * 01882 * This is an equivalence relation. It is linear in the size of the 01883 * vectors. Vectors are considered equivalent if their sizes are equal, 01884 * and if corresponding elements compare equal. 01885 */ 01886 template<typename _Tp, typename _Alloc> 01887 inline bool 01888 operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 01889 { return (__x.size() == __y.size() 01890 && std::equal(__x.begin(), __x.end(), __y.begin())); } 01891 01892 /** 01893 * @brief Vector ordering relation. 01894 * @param __x A %vector. 01895 * @param __y A %vector of the same type as @a __x. 01896 * @return True iff @a __x is lexicographically less than @a __y. 01897 * 01898 * This is a total ordering relation. It is linear in the size of the 01899 * vectors. The elements must be comparable with @c <. 01900 * 01901 * See std::lexicographical_compare() for how the determination is made. 01902 */ 01903 template<typename _Tp, typename _Alloc> 01904 inline bool 01905 operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 01906 { return std::lexicographical_compare(__x.begin(), __x.end(), 01907 __y.begin(), __y.end()); } 01908 01909 /// Based on operator== 01910 template<typename _Tp, typename _Alloc> 01911 inline bool 01912 operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 01913 { return !(__x == __y); } 01914 01915 /// Based on operator< 01916 template<typename _Tp, typename _Alloc> 01917 inline bool 01918 operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 01919 { return __y < __x; } 01920 01921 /// Based on operator< 01922 template<typename _Tp, typename _Alloc> 01923 inline bool 01924 operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 01925 { return !(__y < __x); } 01926 01927 /// Based on operator< 01928 template<typename _Tp, typename _Alloc> 01929 inline bool 01930 operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 01931 { return !(__x < __y); } 01932 01933 /// See std::vector::swap(). 01934 template<typename _Tp, typename _Alloc> 01935 inline void 01936 swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y) 01937 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y))) 01938 { __x.swap(__y); } 01939 01940 _GLIBCXX_END_NAMESPACE_CONTAINER 01941 01942 #if __cplusplus >= 201703L 01943 namespace __detail::__variant 01944 { 01945 template<typename> struct _Never_valueless_alt; // see <variant> 01946 01947 // Provide the strong exception-safety guarantee when emplacing a 01948 // vector into a variant, but only if move assignment cannot throw. 01949 template<typename _Tp, typename _Alloc> 01950 struct _Never_valueless_alt<_GLIBCXX_STD_C::vector<_Tp, _Alloc>> 01951 : std::is_nothrow_move_assignable<_GLIBCXX_STD_C::vector<_Tp, _Alloc>> 01952 { }; 01953 } // namespace __detail::__variant 01954 #endif // C++17 01955 01956 _GLIBCXX_END_NAMESPACE_VERSION 01957 } // namespace std 01958 01959 #endif /* _STL_VECTOR_H */