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