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