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