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 * @a __x is a valid, but unspecified %vector. 00424 */ 00425 vector& 00426 operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move()) 00427 { 00428 if (_Alloc_traits::_S_propagate_on_move_assign()) 00429 { 00430 // We're moving the rvalue's allocator so can move the data too. 00431 const vector __tmp(std::move(*this)); // discard existing data 00432 this->_M_impl._M_swap_data(__x._M_impl); 00433 std::__alloc_on_move(_M_get_Tp_allocator(), 00434 __x._M_get_Tp_allocator()); 00435 } 00436 else if (_Alloc_traits::_S_always_equal() 00437 || __x._M_get_Tp_allocator() == this->_M_get_Tp_allocator()) 00438 { 00439 // The rvalue's allocator can free our storage and vice versa, 00440 // so can swap the data storage after destroying our contents. 00441 this->clear(); 00442 this->_M_impl._M_swap_data(__x._M_impl); 00443 } 00444 else 00445 { 00446 // The rvalue's allocator cannot be moved, or is not equal, 00447 // so we need to individually move each element. 00448 this->assign(std::__make_move_if_noexcept_iterator(__x.begin()), 00449 std::__make_move_if_noexcept_iterator(__x.end())); 00450 __x.clear(); 00451 } 00452 return *this; 00453 } 00454 00455 /** 00456 * @brief %Vector list assignment operator. 00457 * @param __l An initializer_list. 00458 * 00459 * This function fills a %vector with copies of the elements in the 00460 * initializer list @a __l. 00461 * 00462 * Note that the assignment completely changes the %vector and 00463 * that the resulting %vector's size is the same as the number 00464 * of elements assigned. Old data may be lost. 00465 */ 00466 vector& 00467 operator=(initializer_list<value_type> __l) 00468 { 00469 this->assign(__l.begin(), __l.end()); 00470 return *this; 00471 } 00472 #endif 00473 00474 /** 00475 * @brief Assigns a given value to a %vector. 00476 * @param __n Number of elements to be assigned. 00477 * @param __val Value to be assigned. 00478 * 00479 * This function fills a %vector with @a __n copies of the given 00480 * value. Note that the assignment completely changes the 00481 * %vector and that the resulting %vector's size is the same as 00482 * the number of elements assigned. Old data may be lost. 00483 */ 00484 void 00485 assign(size_type __n, const value_type& __val) 00486 { _M_fill_assign(__n, __val); } 00487 00488 /** 00489 * @brief Assigns a range to a %vector. 00490 * @param __first An input iterator. 00491 * @param __last An input iterator. 00492 * 00493 * This function fills a %vector with copies of the elements in the 00494 * range [__first,__last). 00495 * 00496 * Note that the assignment completely changes the %vector and 00497 * that the resulting %vector's size is the same as the number 00498 * of elements assigned. Old data may be lost. 00499 */ 00500 template<typename _InputIterator> 00501 void 00502 assign(_InputIterator __first, _InputIterator __last) 00503 { 00504 // Check whether it's an integral type. If so, it's not an iterator. 00505 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00506 _M_assign_dispatch(__first, __last, _Integral()); 00507 } 00508 00509 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00510 /** 00511 * @brief Assigns an initializer list to a %vector. 00512 * @param __l An initializer_list. 00513 * 00514 * This function fills a %vector with copies of the elements in the 00515 * initializer list @a __l. 00516 * 00517 * Note that the assignment completely changes the %vector and 00518 * that the resulting %vector's size is the same as the number 00519 * of elements assigned. Old data may be lost. 00520 */ 00521 void 00522 assign(initializer_list<value_type> __l) 00523 { this->assign(__l.begin(), __l.end()); } 00524 #endif 00525 00526 /// Get a copy of the memory allocation object. 00527 using _Base::get_allocator; 00528 00529 // iterators 00530 /** 00531 * Returns a read/write iterator that points to the first 00532 * element in the %vector. Iteration is done in ordinary 00533 * element order. 00534 */ 00535 iterator 00536 begin() _GLIBCXX_NOEXCEPT 00537 { return iterator(this->_M_impl._M_start); } 00538 00539 /** 00540 * Returns a read-only (constant) iterator that points to the 00541 * first element in the %vector. Iteration is done in ordinary 00542 * element order. 00543 */ 00544 const_iterator 00545 begin() const _GLIBCXX_NOEXCEPT 00546 { return const_iterator(this->_M_impl._M_start); } 00547 00548 /** 00549 * Returns a read/write iterator that points one past the last 00550 * element in the %vector. Iteration is done in ordinary 00551 * element order. 00552 */ 00553 iterator 00554 end() _GLIBCXX_NOEXCEPT 00555 { return iterator(this->_M_impl._M_finish); } 00556 00557 /** 00558 * Returns a read-only (constant) iterator that points one past 00559 * the last element in the %vector. Iteration is done in 00560 * ordinary element order. 00561 */ 00562 const_iterator 00563 end() const _GLIBCXX_NOEXCEPT 00564 { return const_iterator(this->_M_impl._M_finish); } 00565 00566 /** 00567 * Returns a read/write reverse iterator that points to the 00568 * last element in the %vector. Iteration is done in reverse 00569 * element order. 00570 */ 00571 reverse_iterator 00572 rbegin() _GLIBCXX_NOEXCEPT 00573 { return reverse_iterator(end()); } 00574 00575 /** 00576 * Returns a read-only (constant) reverse iterator that points 00577 * to the last element in the %vector. Iteration is done in 00578 * reverse element order. 00579 */ 00580 const_reverse_iterator 00581 rbegin() const _GLIBCXX_NOEXCEPT 00582 { return const_reverse_iterator(end()); } 00583 00584 /** 00585 * Returns a read/write reverse iterator that points to one 00586 * before the first element in the %vector. Iteration is done 00587 * in reverse element order. 00588 */ 00589 reverse_iterator 00590 rend() _GLIBCXX_NOEXCEPT 00591 { return reverse_iterator(begin()); } 00592 00593 /** 00594 * Returns a read-only (constant) reverse iterator that points 00595 * to one before the first element in the %vector. Iteration 00596 * is done in reverse element order. 00597 */ 00598 const_reverse_iterator 00599 rend() const _GLIBCXX_NOEXCEPT 00600 { return const_reverse_iterator(begin()); } 00601 00602 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00603 /** 00604 * Returns a read-only (constant) iterator that points to the 00605 * first element in the %vector. Iteration is done in ordinary 00606 * element order. 00607 */ 00608 const_iterator 00609 cbegin() const noexcept 00610 { return const_iterator(this->_M_impl._M_start); } 00611 00612 /** 00613 * Returns a read-only (constant) iterator that points one past 00614 * the last element in the %vector. Iteration is done in 00615 * ordinary element order. 00616 */ 00617 const_iterator 00618 cend() const noexcept 00619 { return const_iterator(this->_M_impl._M_finish); } 00620 00621 /** 00622 * Returns a read-only (constant) reverse iterator that points 00623 * to the last element in the %vector. Iteration is done in 00624 * reverse element order. 00625 */ 00626 const_reverse_iterator 00627 crbegin() const noexcept 00628 { return const_reverse_iterator(end()); } 00629 00630 /** 00631 * Returns a read-only (constant) reverse iterator that points 00632 * to one before the first element in the %vector. Iteration 00633 * is done in reverse element order. 00634 */ 00635 const_reverse_iterator 00636 crend() const noexcept 00637 { return const_reverse_iterator(begin()); } 00638 #endif 00639 00640 // [23.2.4.2] capacity 00641 /** Returns the number of elements in the %vector. */ 00642 size_type 00643 size() const _GLIBCXX_NOEXCEPT 00644 { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); } 00645 00646 /** Returns the size() of the largest possible %vector. */ 00647 size_type 00648 max_size() const _GLIBCXX_NOEXCEPT 00649 { return _Alloc_traits::max_size(_M_get_Tp_allocator()); } 00650 00651 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00652 /** 00653 * @brief Resizes the %vector to the specified number of elements. 00654 * @param __new_size Number of elements the %vector should contain. 00655 * 00656 * This function will %resize the %vector to the specified 00657 * number of elements. If the number is smaller than the 00658 * %vector's current size the %vector is truncated, otherwise 00659 * default constructed elements are appended. 00660 */ 00661 void 00662 resize(size_type __new_size) 00663 { 00664 if (__new_size > size()) 00665 _M_default_append(__new_size - size()); 00666 else if (__new_size < size()) 00667 _M_erase_at_end(this->_M_impl._M_start + __new_size); 00668 } 00669 00670 /** 00671 * @brief Resizes the %vector to the specified number of elements. 00672 * @param __new_size Number of elements the %vector should contain. 00673 * @param __x Data with which new elements should be populated. 00674 * 00675 * This function will %resize the %vector to the specified 00676 * number of elements. If the number is smaller than the 00677 * %vector's current size the %vector is truncated, otherwise 00678 * the %vector is extended and new elements are populated with 00679 * given data. 00680 */ 00681 void 00682 resize(size_type __new_size, const value_type& __x) 00683 { 00684 if (__new_size > size()) 00685 insert(end(), __new_size - size(), __x); 00686 else if (__new_size < size()) 00687 _M_erase_at_end(this->_M_impl._M_start + __new_size); 00688 } 00689 #else 00690 /** 00691 * @brief Resizes the %vector to the specified number of elements. 00692 * @param __new_size Number of elements the %vector should contain. 00693 * @param __x Data with which new elements should be populated. 00694 * 00695 * This function will %resize the %vector to the specified 00696 * number of elements. If the number is smaller than the 00697 * %vector's current size the %vector is truncated, otherwise 00698 * the %vector is extended and new elements are populated with 00699 * given data. 00700 */ 00701 void 00702 resize(size_type __new_size, value_type __x = value_type()) 00703 { 00704 if (__new_size > size()) 00705 insert(end(), __new_size - size(), __x); 00706 else if (__new_size < size()) 00707 _M_erase_at_end(this->_M_impl._M_start + __new_size); 00708 } 00709 #endif 00710 00711 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00712 /** A non-binding request to reduce capacity() to size(). */ 00713 void 00714 shrink_to_fit() 00715 { _M_shrink_to_fit(); } 00716 #endif 00717 00718 /** 00719 * Returns the total number of elements that the %vector can 00720 * hold before needing to allocate more memory. 00721 */ 00722 size_type 00723 capacity() const _GLIBCXX_NOEXCEPT 00724 { return size_type(this->_M_impl._M_end_of_storage 00725 - this->_M_impl._M_start); } 00726 00727 /** 00728 * Returns true if the %vector is empty. (Thus begin() would 00729 * equal end().) 00730 */ 00731 bool 00732 empty() const _GLIBCXX_NOEXCEPT 00733 { return begin() == end(); } 00734 00735 /** 00736 * @brief Attempt to preallocate enough memory for specified number of 00737 * elements. 00738 * @param __n Number of elements required. 00739 * @throw std::length_error If @a n exceeds @c max_size(). 00740 * 00741 * This function attempts to reserve enough memory for the 00742 * %vector to hold the specified number of elements. If the 00743 * number requested is more than max_size(), length_error is 00744 * thrown. 00745 * 00746 * The advantage of this function is that if optimal code is a 00747 * necessity and the user can determine the number of elements 00748 * that will be required, the user can reserve the memory in 00749 * %advance, and thus prevent a possible reallocation of memory 00750 * and copying of %vector data. 00751 */ 00752 void 00753 reserve(size_type __n); 00754 00755 // element access 00756 /** 00757 * @brief Subscript access to the data contained in the %vector. 00758 * @param __n The index of the element for which data should be 00759 * accessed. 00760 * @return Read/write reference to data. 00761 * 00762 * This operator allows for easy, array-style, data access. 00763 * Note that data access with this operator is unchecked and 00764 * out_of_range lookups are not defined. (For checked lookups 00765 * see at().) 00766 */ 00767 reference 00768 operator[](size_type __n) 00769 { return *(this->_M_impl._M_start + __n); } 00770 00771 /** 00772 * @brief Subscript access to the data contained in the %vector. 00773 * @param __n The index of the element for which data should be 00774 * accessed. 00775 * @return Read-only (constant) reference to data. 00776 * 00777 * This operator allows for easy, array-style, data access. 00778 * Note that data access with this operator is unchecked and 00779 * out_of_range lookups are not defined. (For checked lookups 00780 * see at().) 00781 */ 00782 const_reference 00783 operator[](size_type __n) const 00784 { return *(this->_M_impl._M_start + __n); } 00785 00786 protected: 00787 /// Safety check used only from at(). 00788 void 00789 _M_range_check(size_type __n) const 00790 { 00791 if (__n >= this->size()) 00792 __throw_out_of_range(__N("vector::_M_range_check")); 00793 } 00794 00795 public: 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/write 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 reference 00808 at(size_type __n) 00809 { 00810 _M_range_check(__n); 00811 return (*this)[__n]; 00812 } 00813 00814 /** 00815 * @brief Provides access to the data contained in the %vector. 00816 * @param __n The index of the element for which data should be 00817 * accessed. 00818 * @return Read-only (constant) reference to data. 00819 * @throw std::out_of_range If @a __n is an invalid index. 00820 * 00821 * This function provides for safer data access. The parameter 00822 * is first checked that it is in the range of the vector. The 00823 * function throws out_of_range if the check fails. 00824 */ 00825 const_reference 00826 at(size_type __n) const 00827 { 00828 _M_range_check(__n); 00829 return (*this)[__n]; 00830 } 00831 00832 /** 00833 * Returns a read/write reference to the data at the first 00834 * element of the %vector. 00835 */ 00836 reference 00837 front() 00838 { return *begin(); } 00839 00840 /** 00841 * Returns a read-only (constant) reference to the data at the first 00842 * element of the %vector. 00843 */ 00844 const_reference 00845 front() const 00846 { return *begin(); } 00847 00848 /** 00849 * Returns a read/write reference to the data at the last 00850 * element of the %vector. 00851 */ 00852 reference 00853 back() 00854 { return *(end() - 1); } 00855 00856 /** 00857 * Returns a read-only (constant) reference to the data at the 00858 * last element of the %vector. 00859 */ 00860 const_reference 00861 back() const 00862 { return *(end() - 1); } 00863 00864 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00865 // DR 464. Suggestion for new member functions in standard containers. 00866 // data access 00867 /** 00868 * Returns a pointer such that [data(), data() + size()) is a valid 00869 * range. For a non-empty %vector, data() == &front(). 00870 */ 00871 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00872 _Tp* 00873 #else 00874 pointer 00875 #endif 00876 data() _GLIBCXX_NOEXCEPT 00877 { return std::__addressof(front()); } 00878 00879 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00880 const _Tp* 00881 #else 00882 const_pointer 00883 #endif 00884 data() const _GLIBCXX_NOEXCEPT 00885 { return std::__addressof(front()); } 00886 00887 // [23.2.4.3] modifiers 00888 /** 00889 * @brief Add data to the end of the %vector. 00890 * @param __x Data to be added. 00891 * 00892 * This is a typical stack operation. The function creates an 00893 * element at the end of the %vector and assigns the given data 00894 * to it. Due to the nature of a %vector this operation can be 00895 * done in constant time if the %vector has preallocated space 00896 * available. 00897 */ 00898 void 00899 push_back(const value_type& __x) 00900 { 00901 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 00902 { 00903 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, 00904 __x); 00905 ++this->_M_impl._M_finish; 00906 } 00907 else 00908 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00909 _M_emplace_back_aux(__x); 00910 #else 00911 _M_insert_aux(end(), __x); 00912 #endif 00913 } 00914 00915 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00916 void 00917 push_back(value_type&& __x) 00918 { emplace_back(std::move(__x)); } 00919 00920 template<typename... _Args> 00921 void 00922 emplace_back(_Args&&... __args); 00923 #endif 00924 00925 /** 00926 * @brief Removes last element. 00927 * 00928 * This is a typical stack operation. It shrinks the %vector by one. 00929 * 00930 * Note that no data is returned, and if the last element's 00931 * data is needed, it should be retrieved before pop_back() is 00932 * called. 00933 */ 00934 void 00935 pop_back() 00936 { 00937 --this->_M_impl._M_finish; 00938 _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish); 00939 } 00940 00941 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00942 /** 00943 * @brief Inserts an object in %vector before specified iterator. 00944 * @param __position An iterator into the %vector. 00945 * @param __args Arguments. 00946 * @return An iterator that points to the inserted data. 00947 * 00948 * This function will insert an object of type T constructed 00949 * with T(std::forward<Args>(args)...) before the specified location. 00950 * Note that this kind of operation could be expensive for a %vector 00951 * and if it is frequently used the user should consider using 00952 * std::list. 00953 */ 00954 template<typename... _Args> 00955 iterator 00956 emplace(iterator __position, _Args&&... __args); 00957 #endif 00958 00959 /** 00960 * @brief Inserts given value into %vector before specified iterator. 00961 * @param __position An iterator into the %vector. 00962 * @param __x Data to be inserted. 00963 * @return An iterator that points to the inserted data. 00964 * 00965 * This function will insert a copy of the given value before 00966 * the specified location. Note that this kind of operation 00967 * could be expensive for a %vector and if it is frequently 00968 * used the user should consider using std::list. 00969 */ 00970 iterator 00971 insert(iterator __position, const value_type& __x); 00972 00973 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00974 /** 00975 * @brief Inserts given rvalue into %vector before specified iterator. 00976 * @param __position An iterator into the %vector. 00977 * @param __x Data to be inserted. 00978 * @return An iterator that points to the inserted data. 00979 * 00980 * This function will insert a copy of the given rvalue before 00981 * the specified location. Note that this kind of operation 00982 * could be expensive for a %vector and if it is frequently 00983 * used the user should consider using std::list. 00984 */ 00985 iterator 00986 insert(iterator __position, value_type&& __x) 00987 { return emplace(__position, std::move(__x)); } 00988 00989 /** 00990 * @brief Inserts an initializer_list into the %vector. 00991 * @param __position An iterator into the %vector. 00992 * @param __l An initializer_list. 00993 * 00994 * This function will insert copies of the data in the 00995 * initializer_list @a l into the %vector before the location 00996 * 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, initializer_list<value_type> __l) 01004 { this->insert(__position, __l.begin(), __l.end()); } 01005 #endif 01006 01007 /** 01008 * @brief Inserts a number of copies of given data into the %vector. 01009 * @param __position An iterator into the %vector. 01010 * @param __n Number of elements to be inserted. 01011 * @param __x Data to be inserted. 01012 * 01013 * This function will insert a specified number of copies of 01014 * the given data before the location specified by @a position. 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 void 01021 insert(iterator __position, size_type __n, const value_type& __x) 01022 { _M_fill_insert(__position, __n, __x); } 01023 01024 /** 01025 * @brief Inserts a range into the %vector. 01026 * @param __position An iterator into the %vector. 01027 * @param __first An input iterator. 01028 * @param __last An input iterator. 01029 * 01030 * This function will insert copies of the data in the range 01031 * [__first,__last) into the %vector before the location specified 01032 * by @a pos. 01033 * 01034 * Note that this kind of operation could be expensive for a 01035 * %vector and if it is frequently used the user should 01036 * consider using std::list. 01037 */ 01038 template<typename _InputIterator> 01039 void 01040 insert(iterator __position, _InputIterator __first, 01041 _InputIterator __last) 01042 { 01043 // Check whether it's an integral type. If so, it's not an iterator. 01044 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 01045 _M_insert_dispatch(__position, __first, __last, _Integral()); 01046 } 01047 01048 /** 01049 * @brief Remove element at given position. 01050 * @param __position Iterator pointing to element to be erased. 01051 * @return An iterator pointing to the next element (or end()). 01052 * 01053 * This function will erase the element at the given position and thus 01054 * shorten the %vector by one. 01055 * 01056 * Note This operation could be expensive and if it is 01057 * frequently used the user should consider using std::list. 01058 * The user is also cautioned that this function only erases 01059 * the element, and that if the element is itself a pointer, 01060 * the pointed-to memory is not touched in any way. Managing 01061 * the pointer is the user's responsibility. 01062 */ 01063 iterator 01064 erase(iterator __position); 01065 01066 /** 01067 * @brief Remove a range of elements. 01068 * @param __first Iterator pointing to the first element to be erased. 01069 * @param __last Iterator pointing to one past the last element to be 01070 * erased. 01071 * @return An iterator pointing to the element pointed to by @a __last 01072 * prior to erasing (or end()). 01073 * 01074 * This function will erase the elements in the range 01075 * [__first,__last) and shorten the %vector accordingly. 01076 * 01077 * Note This operation could be expensive and if it is 01078 * frequently used the user should consider using std::list. 01079 * The user is also cautioned that this function only erases 01080 * the elements, and that if the elements themselves are 01081 * pointers, the pointed-to memory is not touched in any way. 01082 * Managing the pointer is the user's responsibility. 01083 */ 01084 iterator 01085 erase(iterator __first, iterator __last); 01086 01087 /** 01088 * @brief Swaps data with another %vector. 01089 * @param __x A %vector of the same element and allocator types. 01090 * 01091 * This exchanges the elements between two vectors in constant time. 01092 * (Three pointers, so it should be quite fast.) 01093 * Note that the global std::swap() function is specialized such that 01094 * std::swap(v1,v2) will feed to this function. 01095 */ 01096 void 01097 swap(vector& __x) 01098 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01099 noexcept(_Alloc_traits::_S_nothrow_swap()) 01100 #endif 01101 { 01102 this->_M_impl._M_swap_data(__x._M_impl); 01103 _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(), 01104 __x._M_get_Tp_allocator()); 01105 } 01106 01107 /** 01108 * Erases all the elements. Note that this function only erases the 01109 * elements, and that if the elements themselves are pointers, the 01110 * pointed-to memory is not touched in any way. Managing the pointer is 01111 * the user's responsibility. 01112 */ 01113 void 01114 clear() _GLIBCXX_NOEXCEPT 01115 { _M_erase_at_end(this->_M_impl._M_start); } 01116 01117 protected: 01118 /** 01119 * Memory expansion handler. Uses the member allocation function to 01120 * obtain @a n bytes of memory, and then copies [first,last) into it. 01121 */ 01122 template<typename _ForwardIterator> 01123 pointer 01124 _M_allocate_and_copy(size_type __n, 01125 _ForwardIterator __first, _ForwardIterator __last) 01126 { 01127 pointer __result = this->_M_allocate(__n); 01128 __try 01129 { 01130 std::__uninitialized_copy_a(__first, __last, __result, 01131 _M_get_Tp_allocator()); 01132 return __result; 01133 } 01134 __catch(...) 01135 { 01136 _M_deallocate(__result, __n); 01137 __throw_exception_again; 01138 } 01139 } 01140 01141 01142 // Internal constructor functions follow. 01143 01144 // Called by the range constructor to implement [23.1.1]/9 01145 01146 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01147 // 438. Ambiguity in the "do the right thing" clause 01148 template<typename _Integer> 01149 void 01150 _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type) 01151 { 01152 this->_M_impl._M_start = _M_allocate(static_cast<size_type>(__n)); 01153 this->_M_impl._M_end_of_storage = 01154 this->_M_impl._M_start + static_cast<size_type>(__n); 01155 _M_fill_initialize(static_cast<size_type>(__n), __value); 01156 } 01157 01158 // Called by the range constructor to implement [23.1.1]/9 01159 template<typename _InputIterator> 01160 void 01161 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 01162 __false_type) 01163 { 01164 typedef typename std::iterator_traits<_InputIterator>:: 01165 iterator_category _IterCategory; 01166 _M_range_initialize(__first, __last, _IterCategory()); 01167 } 01168 01169 // Called by the second initialize_dispatch above 01170 template<typename _InputIterator> 01171 void 01172 _M_range_initialize(_InputIterator __first, 01173 _InputIterator __last, std::input_iterator_tag) 01174 { 01175 for (; __first != __last; ++__first) 01176 push_back(*__first); 01177 } 01178 01179 // Called by the second initialize_dispatch above 01180 template<typename _ForwardIterator> 01181 void 01182 _M_range_initialize(_ForwardIterator __first, 01183 _ForwardIterator __last, std::forward_iterator_tag) 01184 { 01185 const size_type __n = std::distance(__first, __last); 01186 this->_M_impl._M_start = this->_M_allocate(__n); 01187 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 01188 this->_M_impl._M_finish = 01189 std::__uninitialized_copy_a(__first, __last, 01190 this->_M_impl._M_start, 01191 _M_get_Tp_allocator()); 01192 } 01193 01194 // Called by the first initialize_dispatch above and by the 01195 // vector(n,value,a) constructor. 01196 void 01197 _M_fill_initialize(size_type __n, const value_type& __value) 01198 { 01199 std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value, 01200 _M_get_Tp_allocator()); 01201 this->_M_impl._M_finish = this->_M_impl._M_end_of_storage; 01202 } 01203 01204 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01205 // Called by the vector(n) constructor. 01206 void 01207 _M_default_initialize(size_type __n) 01208 { 01209 std::__uninitialized_default_n_a(this->_M_impl._M_start, __n, 01210 _M_get_Tp_allocator()); 01211 this->_M_impl._M_finish = this->_M_impl._M_end_of_storage; 01212 } 01213 #endif 01214 01215 // Internal assign functions follow. The *_aux functions do the actual 01216 // assignment work for the range versions. 01217 01218 // Called by the range assign to implement [23.1.1]/9 01219 01220 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01221 // 438. Ambiguity in the "do the right thing" clause 01222 template<typename _Integer> 01223 void 01224 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 01225 { _M_fill_assign(__n, __val); } 01226 01227 // Called by the range assign to implement [23.1.1]/9 01228 template<typename _InputIterator> 01229 void 01230 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 01231 __false_type) 01232 { 01233 typedef typename std::iterator_traits<_InputIterator>:: 01234 iterator_category _IterCategory; 01235 _M_assign_aux(__first, __last, _IterCategory()); 01236 } 01237 01238 // Called by the second assign_dispatch above 01239 template<typename _InputIterator> 01240 void 01241 _M_assign_aux(_InputIterator __first, _InputIterator __last, 01242 std::input_iterator_tag); 01243 01244 // Called by the second assign_dispatch above 01245 template<typename _ForwardIterator> 01246 void 01247 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 01248 std::forward_iterator_tag); 01249 01250 // Called by assign(n,t), and the range assign when it turns out 01251 // to be the same thing. 01252 void 01253 _M_fill_assign(size_type __n, const value_type& __val); 01254 01255 01256 // Internal insert functions follow. 01257 01258 // Called by the range insert to implement [23.1.1]/9 01259 01260 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01261 // 438. Ambiguity in the "do the right thing" clause 01262 template<typename _Integer> 01263 void 01264 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val, 01265 __true_type) 01266 { _M_fill_insert(__pos, __n, __val); } 01267 01268 // Called by the range insert to implement [23.1.1]/9 01269 template<typename _InputIterator> 01270 void 01271 _M_insert_dispatch(iterator __pos, _InputIterator __first, 01272 _InputIterator __last, __false_type) 01273 { 01274 typedef typename std::iterator_traits<_InputIterator>:: 01275 iterator_category _IterCategory; 01276 _M_range_insert(__pos, __first, __last, _IterCategory()); 01277 } 01278 01279 // Called by the second insert_dispatch above 01280 template<typename _InputIterator> 01281 void 01282 _M_range_insert(iterator __pos, _InputIterator __first, 01283 _InputIterator __last, std::input_iterator_tag); 01284 01285 // Called by the second insert_dispatch above 01286 template<typename _ForwardIterator> 01287 void 01288 _M_range_insert(iterator __pos, _ForwardIterator __first, 01289 _ForwardIterator __last, std::forward_iterator_tag); 01290 01291 // Called by insert(p,n,x), and the range insert when it turns out to be 01292 // the same thing. 01293 void 01294 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x); 01295 01296 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01297 // Called by resize(n). 01298 void 01299 _M_default_append(size_type __n); 01300 01301 bool 01302 _M_shrink_to_fit(); 01303 #endif 01304 01305 // Called by insert(p,x) 01306 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 01307 void 01308 _M_insert_aux(iterator __position, const value_type& __x); 01309 #else 01310 template<typename... _Args> 01311 void 01312 _M_insert_aux(iterator __position, _Args&&... __args); 01313 01314 template<typename... _Args> 01315 void 01316 _M_emplace_back_aux(_Args&&... __args); 01317 #endif 01318 01319 // Called by the latter. 01320 size_type 01321 _M_check_len(size_type __n, const char* __s) const 01322 { 01323 if (max_size() - size() < __n) 01324 __throw_length_error(__N(__s)); 01325 01326 const size_type __len = size() + std::max(size(), __n); 01327 return (__len < size() || __len > max_size()) ? max_size() : __len; 01328 } 01329 01330 // Internal erase functions follow. 01331 01332 // Called by erase(q1,q2), clear(), resize(), _M_fill_assign, 01333 // _M_assign_aux. 01334 void 01335 _M_erase_at_end(pointer __pos) 01336 { 01337 std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator()); 01338 this->_M_impl._M_finish = __pos; 01339 } 01340 }; 01341 01342 01343 /** 01344 * @brief Vector equality comparison. 01345 * @param __x A %vector. 01346 * @param __y A %vector of the same type as @a __x. 01347 * @return True iff the size and elements of the vectors are equal. 01348 * 01349 * This is an equivalence relation. It is linear in the size of the 01350 * vectors. Vectors are considered equivalent if their sizes are equal, 01351 * and if corresponding elements compare equal. 01352 */ 01353 template<typename _Tp, typename _Alloc> 01354 inline bool 01355 operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 01356 { return (__x.size() == __y.size() 01357 && std::equal(__x.begin(), __x.end(), __y.begin())); } 01358 01359 /** 01360 * @brief Vector ordering relation. 01361 * @param __x A %vector. 01362 * @param __y A %vector of the same type as @a __x. 01363 * @return True iff @a __x is lexicographically less than @a __y. 01364 * 01365 * This is a total ordering relation. It is linear in the size of the 01366 * vectors. The elements must be comparable with @c <. 01367 * 01368 * See std::lexicographical_compare() for how the determination is made. 01369 */ 01370 template<typename _Tp, typename _Alloc> 01371 inline bool 01372 operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 01373 { return std::lexicographical_compare(__x.begin(), __x.end(), 01374 __y.begin(), __y.end()); } 01375 01376 /// Based on operator== 01377 template<typename _Tp, typename _Alloc> 01378 inline bool 01379 operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 01380 { return !(__x == __y); } 01381 01382 /// Based on operator< 01383 template<typename _Tp, typename _Alloc> 01384 inline bool 01385 operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 01386 { return __y < __x; } 01387 01388 /// Based on operator< 01389 template<typename _Tp, typename _Alloc> 01390 inline bool 01391 operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 01392 { return !(__y < __x); } 01393 01394 /// Based on operator< 01395 template<typename _Tp, typename _Alloc> 01396 inline bool 01397 operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 01398 { return !(__x < __y); } 01399 01400 /// See std::vector::swap(). 01401 template<typename _Tp, typename _Alloc> 01402 inline void 01403 swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y) 01404 { __x.swap(__y); } 01405 01406 _GLIBCXX_END_NAMESPACE_CONTAINER 01407 } // namespace std 01408 01409 #endif /* _STL_VECTOR_H */