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