stl_vector.h
1 
// Vector implementation * C++ *


2  
3 
// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,

4 
// 2011 Free Software Foundation, Inc.

5 
//

6 
// This file is part of the GNU ISO C++ Library. This library is free

7 
// software; you can redistribute it and/or modify it under the

8 
// terms of the GNU General Public License as published by the

9 
// Free Software Foundation; either version 3, or (at your option)

10 
// any later version.

11  
12 
// This library is distributed in the hope that it will be useful,

13 
// but WITHOUT ANY WARRANTY; without even the implied warranty of

14 
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

15 
// GNU General Public License for more details.

16  
17 
// Under Section 7 of GPL version 3, you are granted additional

18 
// permissions described in the GCC Runtime Library Exception, version

19 
// 3.1, as published by the Free Software Foundation.

20  
21 
// You should have received a copy of the GNU General Public License and

22 
// a copy of the GCC Runtime Library Exception along with this program;

23 
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see

24 
// <http://www.gnu.org/licenses/>.

25  
26 
/*

27 
*

28 
* Copyright (c) 1994

29 
* HewlettPackard Company

30 
*

31 
* Permission to use, copy, modify, distribute and sell this software

32 
* and its documentation for any purpose is hereby granted without fee,

33 
* provided that the above copyright notice appear in all copies and

34 
* that both that copyright notice and this permission notice appear

35 
* in supporting documentation. HewlettPackard Company makes no

36 
* representations about the suitability of this software for any

37 
* purpose. It is provided "as is" without express or implied warranty.

38 
*

39 
*

40 
* Copyright (c) 1996

41 
* Silicon Graphics Computer Systems, Inc.

42 
*

43 
* Permission to use, copy, modify, distribute and sell this software

44 
* and its documentation for any purpose is hereby granted without fee,

45 
* provided that the above copyright notice appear in all copies and

46 
* that both that copyright notice and this permission notice appear

47 
* in supporting documentation. Silicon Graphics makes no

48 
* representations about the suitability of this software for any

49 
* purpose. It is provided "as is" without express or implied warranty.

50 
*/

51  
52 
/** @file bits/stl_vector.h

53 
* This is an internal header file, included by other library headers.

54 
* Do not attempt to use it directly. @headername{vector}

55 
*/

56  
57 
#ifndef _STL_VECTOR_H

58 
#define _STL_VECTOR_H 1 
59  
60 
#include <bits/stl_iterator_base_funcs.h> 
61 
#include <bits/functexcept.h> 
62 
#include <bits/concept_check.h> 
63 
#include <initializer_list> 
64  
65 
namespace std _GLIBCXX_VISIBILITY(default)

66 
{ 
67 
_GLIBCXX_BEGIN_NAMESPACE_CONTAINER 
68  
69 
/// See bits/stl_deque.h's _Deque_base for an explanation.

70 
template<typename _Tp, typename _Alloc> 
71 
struct _Vector_base

72 
{ 
73 
typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;

74  
75 
struct _Vector_impl

76 
: public _Tp_alloc_type 
77 
{ 
78 
typename _Tp_alloc_type::pointer _M_start; 
79 
typename _Tp_alloc_type::pointer _M_finish; 
80 
typename _Tp_alloc_type::pointer _M_end_of_storage; 
81  
82 
_Vector_impl() 
83 
: _Tp_alloc_type(), _M_start(0), _M_finish(0), _M_end_of_storage(0) 
84 
{ } 
85  
86 
_Vector_impl(_Tp_alloc_type const& __a)

87 
: _Tp_alloc_type(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0) 
88 
{ } 
89 
}; 
90 

91 
public:

92 
typedef _Alloc allocator_type;

93  
94 
_Tp_alloc_type& 
95 
_M_get_Tp_allocator() 
96 
{ return *static_cast<_Tp_alloc_type*>(&this>_M_impl); }

97  
98 
const _Tp_alloc_type&

99 
_M_get_Tp_allocator() const

100 
{ return *static_cast<const _Tp_alloc_type*>(&this>_M_impl); } 
101  
102 
allocator_type 
103 
get_allocator() const

104 
{ return allocator_type(_M_get_Tp_allocator()); }

105  
106 
_Vector_base() 
107 
: _M_impl() { } 
108  
109 
_Vector_base(const allocator_type& __a)

110 
: _M_impl(__a) { } 
111  
112 
_Vector_base(size_t __n) 
113 
: _M_impl() 
114 
{ 
115 
this>_M_impl._M_start = this>_M_allocate(__n); 
116 
this>_M_impl._M_finish = this>_M_impl._M_start; 
117 
this>_M_impl._M_end_of_storage = this>_M_impl._M_start + __n; 
118 
} 
119  
120 
_Vector_base(size_t __n, const allocator_type& __a)

121 
: _M_impl(__a) 
122 
{ 
123 
this>_M_impl._M_start = this>_M_allocate(__n); 
124 
this>_M_impl._M_finish = this>_M_impl._M_start; 
125 
this>_M_impl._M_end_of_storage = this>_M_impl._M_start + __n; 
126 
} 
127  
128 
#ifdef __GXX_EXPERIMENTAL_CXX0X__

129 
_Vector_base(_Vector_base&& __x) 
130 
: _M_impl(__x._M_get_Tp_allocator()) 
131 
{ 
132 
this>_M_impl._M_start = __x._M_impl._M_start; 
133 
this>_M_impl._M_finish = __x._M_impl._M_finish; 
134 
this>_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage; 
135 
__x._M_impl._M_start = 0;

136 
__x._M_impl._M_finish = 0;

137 
__x._M_impl._M_end_of_storage = 0;

138 
} 
139 
#endif

140  
141 
~_Vector_base() 
142 
{ _M_deallocate(this>_M_impl._M_start, this>_M_impl._M_end_of_storage 
143 
 this>_M_impl._M_start); } 
144  
145 
public:

146 
_Vector_impl _M_impl; 
147  
148 
typename _Tp_alloc_type::pointer 
149 
_M_allocate(size_t __n) 
150 
{ return __n != 0 ? _M_impl.allocate(__n) : 0; } 
151  
152 
void

153 
_M_deallocate(typename _Tp_alloc_type::pointer __p, size_t __n) 
154 
{ 
155 
if (__p)

156 
_M_impl.deallocate(__p, __n); 
157 
} 
158 
}; 
159  
160  
161 
/**

162 
* @brief A standard container which offers fixed time access to

163 
* individual elements in any order.

164 
*

165 
* @ingroup sequences

166 
*

167 
* Meets the requirements of a <a href="tables.html#65">container</a>, a

168 
* <a href="tables.html#66">reversible container</a>, and a

169 
* <a href="tables.html#67">sequence</a>, including the

170 
* <a href="tables.html#68">optional sequence requirements</a> with the

171 
* %exception of @c push_front and @c pop_front.

172 
*

173 
* In some terminology a %vector can be described as a dynamic

174 
* Cstyle array, it offers fast and efficient access to individual

175 
* elements in any order and saves the user from worrying about

176 
* memory and size allocation. Subscripting ( @c [] ) access is

177 
* also provided as with Cstyle arrays.

178 
*/

179 
template<typename _Tp, typename _Alloc = std::allocator<_Tp> > 
180 
class vector : protected _Vector_base<_Tp, _Alloc> 
181 
{ 
182 
// Concept requirements.

183 
typedef typename _Alloc::value_type _Alloc_value_type;

184 
__glibcxx_class_requires(_Tp, _SGIAssignableConcept) 
185 
__glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept) 
186 

187 
typedef _Vector_base<_Tp, _Alloc> _Base;

188 
typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;

189  
190 
public:

191 
typedef _Tp value_type;

192 
typedef typename _Tp_alloc_type::pointer pointer;

193 
typedef typename _Tp_alloc_type::const_pointer const_pointer;

194 
typedef typename _Tp_alloc_type::reference reference;

195 
typedef typename _Tp_alloc_type::const_reference const_reference;

196 
typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;

197 
typedef __gnu_cxx::__normal_iterator<const_pointer, vector>

198 
const_iterator; 
199 
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

200 
typedef std::reverse_iterator<iterator> reverse_iterator;

201 
typedef size_t size_type;

202 
typedef ptrdiff_t difference_type;

203 
typedef _Alloc allocator_type;

204  
205 
protected:

206 
using _Base::_M_allocate; 
207 
using _Base::_M_deallocate; 
208 
using _Base::_M_impl; 
209 
using _Base::_M_get_Tp_allocator; 
210  
211 
bool _M_is_valid() const 
212 
{ 
213 
return (this>_M_impl._M_end_of_storage == 0 
214 
&& this>_M_impl._M_start == 0

215 
&& this>_M_impl._M_finish == 0)

216 
 (this>_M_impl._M_start <= this>_M_impl._M_finish 
217 
&& this>_M_impl._M_finish <= this>_M_impl._M_end_of_storage 
218 
&& this>_M_impl._M_start < this>_M_impl._M_end_of_storage); 
219 
} 
220  
221 
public:

222 
// [23.2.4.1] construct/copy/destroy

223 
// (assign() and get_allocator() are also listed in this section)

224 
/**

225 
* @brief Default constructor creates no elements.

226 
*/

227 
vector() 
228 
: _Base() { } 
229  
230 
/**

231 
* @brief Creates a %vector with no elements.

232 
* @param a An allocator object.

233 
*/

234 
explicit 
235 
vector(const allocator_type& __a)

236 
: _Base(__a) { } 
237  
238 
#ifdef __GXX_EXPERIMENTAL_CXX0X__

239 
/**

240 
* @brief Creates a %vector with default constructed elements.

241 
* @param n The number of elements to initially create.

242 
*

243 
* This constructor fills the %vector with @a n default

244 
* constructed elements.

245 
*/

246 
explicit 
247 
vector(size_type __n) 
248 
: _Base(__n) 
249 
{ _M_default_initialize(__n); } 
250  
251 
/**

252 
* @brief Creates a %vector with copies of an exemplar element.

253 
* @param n The number of elements to initially create.

254 
* @param value An element to copy.

255 
* @param a An allocator.

256 
*

257 
* This constructor fills the %vector with @a n copies of @a value.

258 
*/

259 
vector(size_type __n, const value_type& __value,

260 
const allocator_type& __a = allocator_type())

261 
: _Base(__n, __a) 
262 
{ _M_fill_initialize(__n, __value); } 
263 
#else

264 
/**

265 
* @brief Creates a %vector with copies of an exemplar element.

266 
* @param n The number of elements to initially create.

267 
* @param value An element to copy.

268 
* @param a An allocator.

269 
*

270 
* This constructor fills the %vector with @a n copies of @a value.

271 
*/

272 
explicit 
273 
vector(size_type __n, const value_type& __value = value_type(),

274 
const allocator_type& __a = allocator_type())

275 
: _Base(__n, __a) 
276 
{ _M_fill_initialize(__n, __value); } 
277 
#endif

278  
279 
/**

280 
* @brief %Vector copy constructor.

281 
* @param x A %vector of identical element and allocator types.

282 
*

283 
* The newlycreated %vector uses a copy of the allocation

284 
* object used by @a x. All the elements of @a x are copied,

285 
* but any extra memory in

286 
* @a x (for fast expansion) will not be copied.

287 
*/

288 
vector(const vector& __x)

289 
: _Base(__x.size(), __x._M_get_Tp_allocator()) 
290 
{ this>_M_impl._M_finish = 
291 
std::__uninitialized_copy_a(__x.begin(), __x.end(), 
292 
this>_M_impl._M_start, 
293 
_M_get_Tp_allocator()); 
294 
} 
295  
296 
#ifdef __GXX_EXPERIMENTAL_CXX0X__

297 
/**

298 
* @brief %Vector move constructor.

299 
* @param x A %vector of identical element and allocator types.

300 
*

301 
* The newlycreated %vector contains the exact contents of @a x.

302 
* The contents of @a x are a valid, but unspecified %vector.

303 
*/

304 
vector(vector&& __x) 
305 
: _Base(std::move(__x)) { } 
306  
307 
/**

308 
* @brief Builds a %vector from an initializer list.

309 
* @param l An initializer_list.

310 
* @param a An allocator.

311 
*

312 
* Create a %vector consisting of copies of the elements in the

313 
* initializer_list @a l.

314 
*

315 
* This will call the element type's copy constructor N times

316 
* (where N is @a l.size()) and do no memory reallocation.

317 
*/

318 
vector(initializer_list<value_type> __l, 
319 
const allocator_type& __a = allocator_type())

320 
: _Base(__a) 
321 
{ 
322 
_M_range_initialize(__l.begin(), __l.end(), 
323 
random_access_iterator_tag()); 
324 
} 
325 
#endif

326  
327 
/**

328 
* @brief Builds a %vector from a range.

329 
* @param first An input iterator.

330 
* @param last An input iterator.

331 
* @param a An allocator.

332 
*

333 
* Create a %vector consisting of copies of the elements from

334 
* [first,last).

335 
*

336 
* If the iterators are forward, bidirectional, or

337 
* randomaccess, then this will call the elements' copy

338 
* constructor N times (where N is distance(first,last)) and do

339 
* no memory reallocation. But if only input iterators are

340 
* used, then this will do at most 2N calls to the copy

341 
* constructor, and logN memory reallocations.

342 
*/

343 
template<typename _InputIterator> 
344 
vector(_InputIterator __first, _InputIterator __last, 
345 
const allocator_type& __a = allocator_type())

346 
: _Base(__a) 
347 
{ 
348 
// Check whether it's an integral type. If so, it's not an iterator.

349 
typedef typename std::__is_integer<_InputIterator>::__type _Integral;

350 
_M_initialize_dispatch(__first, __last, _Integral()); 
351 
} 
352  
353 
/**

354 
* The dtor only erases the elements, and note that if the

355 
* elements themselves are pointers, the pointedto memory is

356 
* not touched in any way. Managing the pointer is the user's

357 
* responsibility.

358 
*/

359 
~vector() 
360 
{ std::_Destroy(this>_M_impl._M_start, this>_M_impl._M_finish, 
361 
_M_get_Tp_allocator()); } 
362  
363 
/**

364 
* @brief %Vector assignment operator.

365 
* @param x A %vector of identical element and allocator types.

366 
*

367 
* All the elements of @a x are copied, but any extra memory in

368 
* @a x (for fast expansion) will not be copied. Unlike the

369 
* copy constructor, the allocator object is not copied.

370 
*/

371 
vector& 
372 
operator=(const vector& __x);

373  
374 
#ifdef __GXX_EXPERIMENTAL_CXX0X__

375 
/**

376 
* @brief %Vector move assignment operator.

377 
* @param x A %vector of identical element and allocator types.

378 
*

379 
* The contents of @a x are moved into this %vector (without copying).

380 
* @a x is a valid, but unspecified %vector.

381 
*/

382 
vector& 
383 
operator=(vector&& __x) 
384 
{ 
385 
// NB: DR 1204.

386 
// NB: DR 675.

387 
this>clear(); 
388 
this>swap(__x); 
389 
return *this;

390 
} 
391  
392 
/**

393 
* @brief %Vector list assignment operator.

394 
* @param l An initializer_list.

395 
*

396 
* This function fills a %vector with copies of the elements in the

397 
* initializer list @a l.

398 
*

399 
* Note that the assignment completely changes the %vector and

400 
* that the resulting %vector's size is the same as the number

401 
* of elements assigned. Old data may be lost.

402 
*/

403 
vector& 
404 
operator=(initializer_list<value_type> __l) 
405 
{ 
406 
this>assign(__l.begin(), __l.end()); 
407 
return *this;

408 
} 
409 
#endif

410  
411 
/**

412 
* @brief Assigns a given value to a %vector.

413 
* @param n Number of elements to be assigned.

414 
* @param val Value to be assigned.

415 
*

416 
* This function fills a %vector with @a n copies of the given

417 
* value. Note that the assignment completely changes the

418 
* %vector and that the resulting %vector's size is the same as

419 
* the number of elements assigned. Old data may be lost.

420 
*/

421 
void

422 
assign(size_type __n, const value_type& __val)

423 
{ _M_fill_assign(__n, __val); } 
424  
425 
/**

426 
* @brief Assigns a range to a %vector.

427 
* @param first An input iterator.

428 
* @param last An input iterator.

429 
*

430 
* This function fills a %vector with copies of the elements in the

431 
* range [first,last).

432 
*

433 
* Note that the assignment completely changes the %vector and

434 
* that the resulting %vector's size is the same as the number

435 
* of elements assigned. Old data may be lost.

436 
*/

437 
template<typename _InputIterator> 
438 
void

439 
assign(_InputIterator __first, _InputIterator __last) 
440 
{ 
441 
// Check whether it's an integral type. If so, it's not an iterator.

442 
typedef typename std::__is_integer<_InputIterator>::__type _Integral;

443 
_M_assign_dispatch(__first, __last, _Integral()); 
444 
} 
445  
446 
#ifdef __GXX_EXPERIMENTAL_CXX0X__

447 
/**

448 
* @brief Assigns an initializer list to a %vector.

449 
* @param l An initializer_list.

450 
*

451 
* This function fills a %vector with copies of the elements in the

452 
* initializer list @a l.

453 
*

454 
* Note that the assignment completely changes the %vector and

455 
* that the resulting %vector's size is the same as the number

456 
* of elements assigned. Old data may be lost.

457 
*/

458 
void

459 
assign(initializer_list<value_type> __l) 
460 
{ this>assign(__l.begin(), __l.end()); } 
461 
#endif

462  
463 
/// Get a copy of the memory allocation object.

464 
using _Base::get_allocator; 
465  
466 
// iterators

467 
/**

468 
* Returns a read/write iterator that points to the first

469 
* element in the %vector. Iteration is done in ordinary

470 
* element order.

471 
*/

472 
iterator 
473 
begin() 
474 
{ 
475 
#if __google_stl_debug_dangling_vector

476 
if (!this>_M_is_valid())

477 
__throw_logic_error("begin() on corrupt (dangling?) vector");

478 
#endif

479 
return iterator(this>_M_impl._M_start);

480 
} 
481  
482 
/**

483 
* Returns a readonly (constant) iterator that points to the

484 
* first element in the %vector. Iteration is done in ordinary

485 
* element order.

486 
*/

487 
const_iterator 
488 
begin() const

489 
{ 
490 
#if __google_stl_debug_dangling_vector

491 
if (!this>_M_is_valid())

492 
__throw_logic_error("begin() on corrupt (dangling?) vector");

493 
#endif

494 
return const_iterator(this>_M_impl._M_start);

495 
} 
496  
497 
/**

498 
* Returns a read/write iterator that points one past the last

499 
* element in the %vector. Iteration is done in ordinary

500 
* element order.

501 
*/

502 
iterator 
503 
end() 
504 
{ 
505 
#if __google_stl_debug_dangling_vector

506 
if (!this>_M_is_valid())

507 
__throw_logic_error("end() on corrupt (dangling?) vector");

508 
#endif

509 
return iterator(this>_M_impl._M_finish);

510 
} 
511  
512 
/**

513 
* Returns a readonly (constant) iterator that points one past

514 
* the last element in the %vector. Iteration is done in

515 
* ordinary element order.

516 
*/

517 
const_iterator 
518 
end() const

519 
{ 
520 
#if __google_stl_debug_dangling_vector

521 
if (!this>_M_is_valid())

522 
__throw_logic_error("end() on corrupt (dangling?) vector");

523 
#endif

524 
return const_iterator(this>_M_impl._M_finish);

525 
} 
526  
527 
/**

528 
* Returns a read/write reverse iterator that points to the

529 
* last element in the %vector. Iteration is done in reverse

530 
* element order.

531 
*/

532 
reverse_iterator 
533 
rbegin() 
534 
{ return reverse_iterator(end()); }

535  
536 
/**

537 
* Returns a readonly (constant) reverse iterator that points

538 
* to the last element in the %vector. Iteration is done in

539 
* reverse element order.

540 
*/

541 
const_reverse_iterator 
542 
rbegin() const

543 
{ return const_reverse_iterator(end()); }

544  
545 
/**

546 
* Returns a read/write reverse iterator that points to one

547 
* before the first element in the %vector. Iteration is done

548 
* in reverse element order.

549 
*/

550 
reverse_iterator 
551 
rend() 
552 
{ return reverse_iterator(begin()); }

553  
554 
/**

555 
* Returns a readonly (constant) reverse iterator that points

556 
* to one before the first element in the %vector. Iteration

557 
* is done in reverse element order.

558 
*/

559 
const_reverse_iterator 
560 
rend() const

561 
{ return const_reverse_iterator(begin()); }

562  
563 
#ifdef __GXX_EXPERIMENTAL_CXX0X__

564 
/**

565 
* Returns a readonly (constant) iterator that points to the

566 
* first element in the %vector. Iteration is done in ordinary

567 
* element order.

568 
*/

569 
const_iterator 
570 
cbegin() const

571 
{ return const_iterator(this>_M_impl._M_start); }

572  
573 
/**

574 
* Returns a readonly (constant) iterator that points one past

575 
* the last element in the %vector. Iteration is done in

576 
* ordinary element order.

577 
*/

578 
const_iterator 
579 
cend() const

580 
{ return const_iterator(this>_M_impl._M_finish); }

581  
582 
/**

583 
* Returns a readonly (constant) reverse iterator that points

584 
* to the last element in the %vector. Iteration is done in

585 
* reverse element order.

586 
*/

587 
const_reverse_iterator 
588 
crbegin() const

589 
{ return const_reverse_iterator(end()); }

590  
591 
/**

592 
* Returns a readonly (constant) reverse iterator that points

593 
* to one before the first element in the %vector. Iteration

594 
* is done in reverse element order.

595 
*/

596 
const_reverse_iterator 
597 
crend() const

598 
{ return const_reverse_iterator(begin()); }

599 
#endif

600  
601 
// [23.2.4.2] capacity

602 
/** Returns the number of elements in the %vector. */

603 
size_type 
604 
size() const

605 
{ 
606 
#if __google_stl_debug_dangling_vector

607 
if (!this>_M_is_valid())

608 
__throw_logic_error("size() on corrupt (dangling?) vector");

609 
#endif

610 
return size_type(this>_M_impl._M_finish  this>_M_impl._M_start);

611 
} 
612  
613 
/** Returns the size() of the largest possible %vector. */

614 
size_type 
615 
max_size() const

616 
{ return _M_get_Tp_allocator().max_size(); }

617  
618 
#ifdef __GXX_EXPERIMENTAL_CXX0X__

619 
/**

620 
* @brief Resizes the %vector to the specified number of elements.

621 
* @param new_size Number of elements the %vector should contain.

622 
*

623 
* This function will %resize the %vector to the specified

624 
* number of elements. If the number is smaller than the

625 
* %vector's current size the %vector is truncated, otherwise

626 
* default constructed elements are appended.

627 
*/

628 
void

629 
resize(size_type __new_size) 
630 
{ 
631 
if (__new_size > size())

632 
_M_default_append(__new_size  size()); 
633 
else if (__new_size < size()) 
634 
_M_erase_at_end(this>_M_impl._M_start + __new_size); 
635 
} 
636  
637 
/**

638 
* @brief Resizes the %vector to the specified number of elements.

639 
* @param new_size Number of elements the %vector should contain.

640 
* @param x Data with which new elements should be populated.

641 
*

642 
* This function will %resize the %vector to the specified

643 
* number of elements. If the number is smaller than the

644 
* %vector's current size the %vector is truncated, otherwise

645 
* the %vector is extended and new elements are populated with

646 
* given data.

647 
*/

648 
void

649 
resize(size_type __new_size, const value_type& __x)

650 
{ 
651 
if (__new_size > size())

652 
insert(end(), __new_size  size(), __x); 
653 
else if (__new_size < size()) 
654 
_M_erase_at_end(this>_M_impl._M_start + __new_size); 
655 
} 
656 
#else

657 
/**

658 
* @brief Resizes the %vector to the specified number of elements.

659 
* @param new_size Number of elements the %vector should contain.

660 
* @param x Data with which new elements should be populated.

661 
*

662 
* This function will %resize the %vector to the specified

663 
* number of elements. If the number is smaller than the

664 
* %vector's current size the %vector is truncated, otherwise

665 
* the %vector is extended and new elements are populated with

666 
* given data.

667 
*/

668 
void

669 
resize(size_type __new_size, value_type __x = value_type()) 
670 
{ 
671 
if (__new_size > size())

672 
insert(end(), __new_size  size(), __x); 
673 
else if (__new_size < size()) 
674 
_M_erase_at_end(this>_M_impl._M_start + __new_size); 
675 
} 
676 
#endif

677  
678 
#ifdef __GXX_EXPERIMENTAL_CXX0X__

679 
/** A nonbinding request to reduce capacity() to size(). */

680 
void

681 
shrink_to_fit() 
682 
{ std::__shrink_to_fit<vector>::_S_do_it(*this); } 
683 
#endif

684  
685 
/**

686 
* Returns the total number of elements that the %vector can

687 
* hold before needing to allocate more memory.

688 
*/

689 
size_type 
690 
capacity() const

691 
{ 
692 
#if __google_stl_debug_dangling_vector

693 
if (!this>_M_is_valid())

694 
__throw_logic_error("capacity() on corrupt (dangling?) vector");

695 
#endif

696 
return size_type(this>_M_impl._M_end_of_storage

697 
 this>_M_impl._M_start); } 
698  
699 
/**

700 
* Returns true if the %vector is empty. (Thus begin() would

701 
* equal end().)

702 
*/

703 
bool

704 
empty() const

705 
{ return begin() == end(); }

706  
707 
/**

708 
* @brief Attempt to preallocate enough memory for specified number of

709 
* elements.

710 
* @param n Number of elements required.

711 
* @throw std::length_error If @a n exceeds @c max_size().

712 
*

713 
* This function attempts to reserve enough memory for the

714 
* %vector to hold the specified number of elements. If the

715 
* number requested is more than max_size(), length_error is

716 
* thrown.

717 
*

718 
* The advantage of this function is that if optimal code is a

719 
* necessity and the user can determine the number of elements

720 
* that will be required, the user can reserve the memory in

721 
* %advance, and thus prevent a possible reallocation of memory

722 
* and copying of %vector data.

723 
*/

724 
void

725 
reserve(size_type __n); 
726  
727 
// element access

728 
/**

729 
* @brief Subscript access to the data contained in the %vector.

730 
* @param n The index of the element for which data should be

731 
* accessed.

732 
* @return Read/write reference to data.

733 
*

734 
* This operator allows for easy, arraystyle, data access.

735 
* Note that data access with this operator is unchecked and

736 
* out_of_range lookups are not defined. (For checked lookups

737 
* see at().)

738 
*

739 
* Local modification: range checks are performed if

740 
* __google_stl_debug_vector is defined to nonzero.

741 
*/

742 
reference 
743 
operator[](size_type __n) 
744 
{ 
745 
#if __google_stl_debug_vector

746 
_M_range_check(__n); 
747 
#endif

748 
return *(this>_M_impl._M_start + __n);

749 
} 
750  
751 
/**

752 
* @brief Subscript access to the data contained in the %vector.

753 
* @param n The index of the element for which data should be

754 
* accessed.

755 
* @return Readonly (constant) reference to data.

756 
*

757 
* This operator allows for easy, arraystyle, data access.

758 
* Note that data access with this operator is unchecked and

759 
* out_of_range lookups are not defined. (For checked lookups

760 
* see at().)

761 
*

762 
* Local modification: range checks are performed if

763 
* __google_stl_debug_vector is defined to nonzero.

764 
*/

765 
const_reference 
766 
operator[](size_type __n) const

767 
{ 
768 
#if __google_stl_debug_vector

769 
_M_range_check(__n); 
770 
#endif

771 
return *(this>_M_impl._M_start + __n);

772 
} 
773  
774 
protected:

775 
/// Safety check used only from at().

776 
void

777 
_M_range_check(size_type __n) const

778 
{ 
779 
if (__n >= this>size())

780 
__throw_out_of_range(__N("vector::_M_range_check"));

781 
} 
782  
783 
public:

784 
/**

785 
* @brief Provides access to the data contained in the %vector.

786 
* @param n The index of the element for which data should be

787 
* accessed.

788 
* @return Read/write reference to data.

789 
* @throw std::out_of_range If @a n is an invalid index.

790 
*

791 
* This function provides for safer data access. The parameter

792 
* is first checked that it is in the range of the vector. The

793 
* function throws out_of_range if the check fails.

794 
*/

795 
reference 
796 
at(size_type __n) 
797 
{ 
798 
_M_range_check(__n); 
799 
return (*this)[__n];

800 
} 
801  
802 
/**

803 
* @brief Provides access to the data contained in the %vector.

804 
* @param n The index of the element for which data should be

805 
* accessed.

806 
* @return Readonly (constant) reference to data.

807 
* @throw std::out_of_range If @a n is an invalid index.

808 
*

809 
* This function provides for safer data access. The parameter

810 
* is first checked that it is in the range of the vector. The

811 
* function throws out_of_range if the check fails.

812 
*/

813 
const_reference 
814 
at(size_type __n) const

815 
{ 
816 
_M_range_check(__n); 
817 
return (*this)[__n];

818 
} 
819  
820 
/**

821 
* Returns a read/write reference to the data at the first

822 
* element of the %vector.

823 
*/

824 
reference 
825 
front() 
826 
{ return *begin(); }

827  
828 
/**

829 
* Returns a readonly (constant) reference to the data at the first

830 
* element of the %vector.

831 
*/

832 
const_reference 
833 
front() const

834 
{ return *begin(); }

835  
836 
/**

837 
* Returns a read/write reference to the data at the last

838 
* element of the %vector.

839 
*/

840 
reference 
841 
back() 
842 
{ return *(end()  1); } 
843 

844 
/**

845 
* Returns a readonly (constant) reference to the data at the

846 
* last element of the %vector.

847 
*/

848 
const_reference 
849 
back() const

850 
{ return *(end()  1); } 
851  
852 
// _GLIBCXX_RESOLVE_LIB_DEFECTS

853 
// DR 464. Suggestion for new member functions in standard containers.

854 
// data access

855 
/**

856 
* Returns a pointer such that [data(), data() + size()) is a valid

857 
* range. For a nonempty %vector, data() == &front().

858 
*/

859 
#ifdef __GXX_EXPERIMENTAL_CXX0X__

860 
_Tp* 
861 
#else

862 
pointer 
863 
#endif

864 
data() 
865 
{ return std::__addressof(front()); }

866  
867 
#ifdef __GXX_EXPERIMENTAL_CXX0X__

868 
const _Tp*

869 
#else

870 
const_pointer 
871 
#endif

872 
data() const

873 
{ return std::__addressof(front()); }

874  
875 
// [23.2.4.3] modifiers

876 
/**

877 
* @brief Add data to the end of the %vector.

878 
* @param x Data to be added.

879 
*

880 
* This is a typical stack operation. The function creates an

881 
* element at the end of the %vector and assigns the given data

882 
* to it. Due to the nature of a %vector this operation can be

883 
* done in constant time if the %vector has preallocated space

884 
* available.

885 
*/

886 
void

887 
push_back(const value_type& __x)

888 
{ 
889 
if (this>_M_impl._M_finish != this>_M_impl._M_end_of_storage)

890 
{ 
891 
this>_M_impl.construct(this>_M_impl._M_finish, __x); 
892 
++this>_M_impl._M_finish; 
893 
} 
894 
else

895 
_M_insert_aux(end(), __x); 
896 
} 
897  
898 
#ifdef __GXX_EXPERIMENTAL_CXX0X__

899 
void

900 
push_back(value_type&& __x) 
901 
{ emplace_back(std::move(__x)); } 
902  
903 
template<typename... _Args> 
904 
void

905 
emplace_back(_Args&&... __args); 
906 
#endif

907  
908 
/**

909 
* @brief Removes last element.

910 
*

911 
* This is a typical stack operation. It shrinks the %vector by one.

912 
*

913 
* Note that no data is returned, and if the last element's

914 
* data is needed, it should be retrieved before pop_back() is

915 
* called.

916 
*/

917 
void

918 
pop_back() 
919 
{ 
920 
this>_M_impl._M_finish; 
921 
this>_M_impl.destroy(this>_M_impl._M_finish); 
922 
} 
923  
924 
#ifdef __GXX_EXPERIMENTAL_CXX0X__

925 
/**

926 
* @brief Inserts an object in %vector before specified iterator.

927 
* @param position An iterator into the %vector.

928 
* @param args Arguments.

929 
* @return An iterator that points to the inserted data.

930 
*

931 
* This function will insert an object of type T constructed

932 
* with T(std::forward<Args>(args)...) before the specified location.

933 
* Note that this kind of operation could be expensive for a %vector

934 
* and if it is frequently used the user should consider using

935 
* std::list.

936 
*/

937 
template<typename... _Args> 
938 
iterator 
939 
emplace(iterator __position, _Args&&... __args); 
940 
#endif

941  
942 
/**

943 
* @brief Inserts given value into %vector before specified iterator.

944 
* @param position An iterator into the %vector.

945 
* @param x Data to be inserted.

946 
* @return An iterator that points to the inserted data.

947 
*

948 
* This function will insert a copy of the given value before

949 
* the specified location. Note that this kind of operation

950 
* could be expensive for a %vector and if it is frequently

951 
* used the user should consider using std::list.

952 
*/

953 
iterator 
954 
insert(iterator __position, const value_type& __x);

955  
956 
#ifdef __GXX_EXPERIMENTAL_CXX0X__

957 
/**

958 
* @brief Inserts given rvalue into %vector before specified iterator.

959 
* @param position An iterator into the %vector.

960 
* @param x Data to be inserted.

961 
* @return An iterator that points to the inserted data.

962 
*

963 
* This function will insert a copy of the given rvalue before

964 
* the specified location. Note that this kind of operation

965 
* could be expensive for a %vector and if it is frequently

966 
* used the user should consider using std::list.

967 
*/

968 
iterator 
969 
insert(iterator __position, value_type&& __x) 
970 
{ return emplace(__position, std::move(__x)); }

971  
972 
/**

973 
* @brief Inserts an initializer_list into the %vector.

974 
* @param position An iterator into the %vector.

975 
* @param l An initializer_list.

976 
*

977 
* This function will insert copies of the data in the

978 
* initializer_list @a l into the %vector before the location

979 
* specified by @a position.

980 
*

981 
* Note that this kind of operation could be expensive for a

982 
* %vector and if it is frequently used the user should

983 
* consider using std::list.

984 
*/

985 
void

986 
insert(iterator __position, initializer_list<value_type> __l) 
987 
{ this>insert(__position, __l.begin(), __l.end()); } 
988 
#endif

989  
990 
/**

991 
* @brief Inserts a number of copies of given data into the %vector.

992 
* @param position An iterator into the %vector.

993 
* @param n Number of elements to be inserted.

994 
* @param x Data to be inserted.

995 
*

996 
* This function will insert a specified number of copies of

997 
* the given data before the location specified by @a position.

998 
*

999 
* Note that this kind of operation could be expensive for a

1000 
* %vector and if it is frequently used the user should

1001 
* consider using std::list.

1002 
*/

1003 
void

1004 
insert(iterator __position, size_type __n, const value_type& __x)

1005 
{ _M_fill_insert(__position, __n, __x); } 
1006  
1007 
/**

1008 
* @brief Inserts a range into the %vector.

1009 
* @param position An iterator into the %vector.

1010 
* @param first An input iterator.

1011 
* @param last An input iterator.

1012 
*

1013 
* This function will insert copies of the data in the range

1014 
* [first,last) into the %vector before the location specified

1015 
* by @a pos.

1016 
*

1017 
* Note that this kind of operation could be expensive for a

1018 
* %vector and if it is frequently used the user should

1019 
* consider using std::list.

1020 
*/

1021 
template<typename _InputIterator> 
1022 
void

1023 
insert(iterator __position, _InputIterator __first, 
1024 
_InputIterator __last) 
1025 
{ 
1026 
// Check whether it's an integral type. If so, it's not an iterator.

1027 
typedef typename std::__is_integer<_InputIterator>::__type _Integral;

1028 
_M_insert_dispatch(__position, __first, __last, _Integral()); 
1029 
} 
1030  
1031 
/**

1032 
* @brief Remove element at given position.

1033 
* @param position Iterator pointing to element to be erased.

1034 
* @return An iterator pointing to the next element (or end()).

1035 
*

1036 
* This function will erase the element at the given position and thus

1037 
* shorten the %vector by one.

1038 
*

1039 
* Note This operation could be expensive and if it is

1040 
* frequently used the user should consider using std::list.

1041 
* The user is also cautioned that this function only erases

1042 
* the element, and that if the element is itself a pointer,

1043 
* the pointedto memory is not touched in any way. Managing

1044 
* the pointer is the user's responsibility.

1045 
*/

1046 
iterator 
1047 
erase(iterator __position); 
1048  
1049 
/**

1050 
* @brief Remove a range of elements.

1051 
* @param first Iterator pointing to the first element to be erased.

1052 
* @param last Iterator pointing to one past the last element to be

1053 
* erased.

1054 
* @return An iterator pointing to the element pointed to by @a last

1055 
* prior to erasing (or end()).

1056 
*

1057 
* This function will erase the elements in the range [first,last) and

1058 
* shorten the %vector accordingly.

1059 
*

1060 
* Note This operation could be expensive and if it is

1061 
* frequently used the user should consider using std::list.

1062 
* The user is also cautioned that this function only erases

1063 
* the elements, and that if the elements themselves are

1064 
* pointers, the pointedto memory is not touched in any way.

1065 
* Managing the pointer is the user's responsibility.

1066 
*/

1067 
iterator 
1068 
erase(iterator __first, iterator __last); 
1069  
1070 
/**

1071 
* @brief Swaps data with another %vector.

1072 
* @param x A %vector of the same element and allocator types.

1073 
*

1074 
* This exchanges the elements between two vectors in constant time.

1075 
* (Three pointers, so it should be quite fast.)

1076 
* Note that the global std::swap() function is specialized such that

1077 
* std::swap(v1,v2) will feed to this function.

1078 
*/

1079 
void

1080 
swap(vector& __x) 
1081 
{ 
1082 
#if __google_stl_debug_dangling_vector

1083 
if (!this>_M_is_valid()  !__x._M_is_valid())

1084 
__throw_logic_error("swap() on corrupt (dangling?) vector");

1085 
#endif

1086 
std::swap(this>_M_impl._M_start, __x._M_impl._M_start); 
1087 
std::swap(this>_M_impl._M_finish, __x._M_impl._M_finish); 
1088 
std::swap(this>_M_impl._M_end_of_storage, 
1089 
__x._M_impl._M_end_of_storage); 
1090  
1091 
// _GLIBCXX_RESOLVE_LIB_DEFECTS

1092 
// 431. Swapping containers with unequal allocators.

1093 
std::__alloc_swap<_Tp_alloc_type>::_S_do_it(_M_get_Tp_allocator(), 
1094 
__x._M_get_Tp_allocator()); 
1095 
} 
1096  
1097 
/**

1098 
* Erases all the elements. Note that this function only erases the

1099 
* elements, and that if the elements themselves are pointers, the

1100 
* pointedto memory is not touched in any way. Managing the pointer is

1101 
* the user's responsibility.

1102 
*/

1103 
void

1104 
clear() 
1105 
{ 
1106 
#if __google_stl_debug_dangling_vector

1107 
if (!this>_M_is_valid())

1108 
__throw_logic_error("clear() on corrupt (dangling?) vector");

1109 
#endif

1110 
_M_erase_at_end(this>_M_impl._M_start); 
1111 
} 
1112  
1113 
protected:

1114 
/**

1115 
* Memory expansion handler. Uses the member allocation function to

1116 
* obtain @a n bytes of memory, and then copies [first,last) into it.

1117 
*/

1118 
template<typename _ForwardIterator> 
1119 
pointer 
1120 
_M_allocate_and_copy(size_type __n, 
1121 
_ForwardIterator __first, _ForwardIterator __last) 
1122 
{ 
1123 
pointer __result = this>_M_allocate(__n); 
1124 
__try 
1125 
{ 
1126 
std::__uninitialized_copy_a(__first, __last, __result, 
1127 
_M_get_Tp_allocator()); 
1128 
return __result;

1129 
} 
1130 
__catch(...) 
1131 
{ 
1132 
_M_deallocate(__result, __n); 
1133 
__throw_exception_again; 
1134 
} 
1135 
} 
1136  
1137  
1138 
// Internal constructor functions follow.

1139  
1140 
// Called by the range constructor to implement [23.1.1]/9

1141  
1142 
// _GLIBCXX_RESOLVE_LIB_DEFECTS

1143 
// 438. Ambiguity in the "do the right thing" clause

1144 
template<typename _Integer> 
1145 
void

1146 
_M_initialize_dispatch(_Integer __n, _Integer __value, __true_type) 
1147 
{ 
1148 
this>_M_impl._M_start = _M_allocate(static_cast<size_type>(__n)); 
1149 
this>_M_impl._M_end_of_storage = 
1150 
this>_M_impl._M_start + static_cast<size_type>(__n); 
1151 
_M_fill_initialize(static_cast<size_type>(__n), __value); 
1152 
} 
1153  
1154 
// Called by the range constructor to implement [23.1.1]/9

1155 
template<typename _InputIterator> 
1156 
void

1157 
_M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 
1158 
__false_type) 
1159 
{ 
1160 
typedef typename std::iterator_traits<_InputIterator>::

1161 
iterator_category _IterCategory; 
1162 
_M_range_initialize(__first, __last, _IterCategory()); 
1163 
} 
1164  
1165 
// Called by the second initialize_dispatch above

1166 
template<typename _InputIterator> 
1167 
void

1168 
_M_range_initialize(_InputIterator __first, 
1169 
_InputIterator __last, std::input_iterator_tag) 
1170 
{ 
1171 
for (; __first != __last; ++__first)

1172 
push_back(*__first); 
1173 
} 
1174  
1175 
// Called by the second initialize_dispatch above

1176 
template<typename _ForwardIterator> 
1177 
void

1178 
_M_range_initialize(_ForwardIterator __first, 
1179 
_ForwardIterator __last, std::forward_iterator_tag) 
1180 
{ 
1181 
const size_type __n = std::distance(__first, __last);

1182 
this>_M_impl._M_start = this>_M_allocate(__n); 
1183 
this>_M_impl._M_end_of_storage = this>_M_impl._M_start + __n; 
1184 
this>_M_impl._M_finish = 
1185 
std::__uninitialized_copy_a(__first, __last, 
1186 
this>_M_impl._M_start, 
1187 
_M_get_Tp_allocator()); 
1188 
} 
1189  
1190 
// Called by the first initialize_dispatch above and by the

1191 
// vector(n,value,a) constructor.

1192 
void

1193 
_M_fill_initialize(size_type __n, const value_type& __value)

1194 
{ 
1195 
std::__uninitialized_fill_n_a(this>_M_impl._M_start, __n, __value, 
1196 
_M_get_Tp_allocator()); 
1197 
this>_M_impl._M_finish = this>_M_impl._M_end_of_storage; 
1198 
} 
1199  
1200 
#ifdef __GXX_EXPERIMENTAL_CXX0X__

1201 
// Called by the vector(n) constructor.

1202 
void

1203 
_M_default_initialize(size_type __n) 
1204 
{ 
1205 
std::__uninitialized_default_n_a(this>_M_impl._M_start, __n, 
1206 
_M_get_Tp_allocator()); 
1207 
this>_M_impl._M_finish = this>_M_impl._M_end_of_storage; 
1208 
} 
1209 
#endif

1210  
1211 
// Internal assign functions follow. The *_aux functions do the actual

1212 
// assignment work for the range versions.

1213  
1214 
// Called by the range assign to implement [23.1.1]/9

1215  
1216 
// _GLIBCXX_RESOLVE_LIB_DEFECTS

1217 
// 438. Ambiguity in the "do the right thing" clause

1218 
template<typename _Integer> 
1219 
void

1220 
_M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 
1221 
{ _M_fill_assign(__n, __val); } 
1222  
1223 
// Called by the range assign to implement [23.1.1]/9

1224 
template<typename _InputIterator> 
1225 
void

1226 
_M_assign_dispatch(_InputIterator __first, _InputIterator __last, 
1227 
__false_type) 
1228 
{ 
1229 
typedef typename std::iterator_traits<_InputIterator>::

1230 
iterator_category _IterCategory; 
1231 
_M_assign_aux(__first, __last, _IterCategory()); 
1232 
} 
1233  
1234 
// Called by the second assign_dispatch above

1235 
template<typename _InputIterator> 
1236 
void

1237 
_M_assign_aux(_InputIterator __first, _InputIterator __last, 
1238 
std::input_iterator_tag); 
1239  
1240 
// Called by the second assign_dispatch above

1241 
template<typename _ForwardIterator> 
1242 
void

1243 
_M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 
1244 
std::forward_iterator_tag); 
1245  
1246 
// Called by assign(n,t), and the range assign when it turns out

1247 
// to be the same thing.

1248 
void

1249 
_M_fill_assign(size_type __n, const value_type& __val);

1250  
1251  
1252 
// Internal insert functions follow.

1253  
1254 
// Called by the range insert to implement [23.1.1]/9

1255  
1256 
// _GLIBCXX_RESOLVE_LIB_DEFECTS

1257 
// 438. Ambiguity in the "do the right thing" clause

1258 
template<typename _Integer> 
1259 
void

1260 
_M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val, 
1261 
__true_type) 
1262 
{ _M_fill_insert(__pos, __n, __val); } 
1263  
1264 
// Called by the range insert to implement [23.1.1]/9

1265 
template<typename _InputIterator> 
1266 
void

1267 
_M_insert_dispatch(iterator __pos, _InputIterator __first, 
1268 
_InputIterator __last, __false_type) 
1269 
{ 
1270 
typedef typename std::iterator_traits<_InputIterator>::

1271 
iterator_category _IterCategory; 
1272 
_M_range_insert(__pos, __first, __last, _IterCategory()); 
1273 
} 
1274  
1275 
// Called by the second insert_dispatch above

1276 
template<typename _InputIterator> 
1277 
void

1278 
_M_range_insert(iterator __pos, _InputIterator __first, 
1279 
_InputIterator __last, std::input_iterator_tag); 
1280  
1281 
// Called by the second insert_dispatch above

1282 
template<typename _ForwardIterator> 
1283 
void

1284 
_M_range_insert(iterator __pos, _ForwardIterator __first, 
1285 
_ForwardIterator __last, std::forward_iterator_tag); 
1286  
1287 
// Called by insert(p,n,x), and the range insert when it turns out to be

1288 
// the same thing.

1289 
void

1290 
_M_fill_insert(iterator __pos, size_type __n, const value_type& __x);

1291  
1292 
#ifdef __GXX_EXPERIMENTAL_CXX0X__

1293 
// Called by resize(n).

1294 
void

1295 
_M_default_append(size_type __n); 
1296 
#endif

1297  
1298 
// Called by insert(p,x)

1299 
#ifndef __GXX_EXPERIMENTAL_CXX0X__

1300 
void

1301 
_M_insert_aux(iterator __position, const value_type& __x);

1302 
#else

1303 
template<typename... _Args> 
1304 
void

1305 
_M_insert_aux(iterator __position, _Args&&... __args); 
1306 
#endif

1307  
1308 
// Called by the latter.

1309 
size_type 
1310 
_M_check_len(size_type __n, const char* __s) const 
1311 
{ 
1312 
if (max_size()  size() < __n)

1313 
__throw_length_error(__N(__s)); 
1314  
1315 
const size_type __len = size() + std::max(size(), __n);

1316 
return (__len < size()  __len > max_size()) ? max_size() : __len;

1317 
} 
1318  
1319 
// Internal erase functions follow.

1320  
1321 
// Called by erase(q1,q2), clear(), resize(), _M_fill_assign,

1322 
// _M_assign_aux.

1323 
void

1324 
_M_erase_at_end(pointer __pos) 
1325 
{ 
1326 
std::_Destroy(__pos, this>_M_impl._M_finish, _M_get_Tp_allocator()); 
1327 
this>_M_impl._M_finish = __pos; 
1328 
} 
1329 
}; 
1330  
1331  
1332 
/**

1333 
* @brief Vector equality comparison.

1334 
* @param x A %vector.

1335 
* @param y A %vector of the same type as @a x.

1336 
* @return True iff the size and elements of the vectors are equal.

1337 
*

1338 
* This is an equivalence relation. It is linear in the size of the

1339 
* vectors. Vectors are considered equivalent if their sizes are equal,

1340 
* and if corresponding elements compare equal.

1341 
*/

1342 
template<typename _Tp, typename _Alloc> 
1343 
inline bool 
1344 
operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 
1345 
{ return (__x.size() == __y.size()

1346 
&& std::equal(__x.begin(), __x.end(), __y.begin())); } 
1347  
1348 
/**

1349 
* @brief Vector ordering relation.

1350 
* @param x A %vector.

1351 
* @param y A %vector of the same type as @a x.

1352 
* @return True iff @a x is lexicographically less than @a y.

1353 
*

1354 
* This is a total ordering relation. It is linear in the size of the

1355 
* vectors. The elements must be comparable with @c <.

1356 
*

1357 
* See std::lexicographical_compare() for how the determination is made.

1358 
*/

1359 
template<typename _Tp, typename _Alloc> 
1360 
inline bool 
1361 
operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 
1362 
{ return std::lexicographical_compare(__x.begin(), __x.end(),

1363 
__y.begin(), __y.end()); } 
1364  
1365 
/// Based on operator==

1366 
template<typename _Tp, typename _Alloc> 
1367 
inline bool 
1368 
operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 
1369 
{ return !(__x == __y); }

1370  
1371 
/// Based on operator<

1372 
template<typename _Tp, typename _Alloc> 
1373 
inline bool 
1374 
operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 
1375 
{ return __y < __x; }

1376  
1377 
/// Based on operator<

1378 
template<typename _Tp, typename _Alloc> 
1379 
inline bool 
1380 
operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 
1381 
{ return !(__y < __x); }

1382  
1383 
/// Based on operator<

1384 
template<typename _Tp, typename _Alloc> 
1385 
inline bool 
1386 
operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 
1387 
{ return !(__x < __y); }

1388  
1389 
/// See std::vector::swap().

1390 
template<typename _Tp, typename _Alloc> 
1391 
inline void 
1392 
swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y) 
1393 
{ __x.swap(__y); } 
1394  
1395 
_GLIBCXX_END_NAMESPACE_CONTAINER 
1396 
} // namespace std

1397  
1398 
#endif /* _STL_VECTOR_H */ 