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