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 * Hewlett-Packard 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. Hewlett-Packard 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 65namespace 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 * C-style 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 C-style 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 public: 212 // [23.2.4.1] construct/copy/destroy 213 // (assign() and get_allocator() are also listed in this section) 214 /** 215 * @brief Default constructor creates no elements. 216 */ 217 vector() 218 : _Base() { } 219 220 /** 221 * @brief Creates a %vector with no elements. 222 * @param a An allocator object. 223 */ 224 explicit 225 vector(const allocator_type& __a) 226 : _Base(__a) { } 227 228#ifdef __GXX_EXPERIMENTAL_CXX0X__ 229 /** 230 * @brief Creates a %vector with default constructed elements. 231 * @param n The number of elements to initially create. 232 * 233 * This constructor fills the %vector with @a n default 234 * constructed elements. 235 */ 236 explicit 237 vector(size_type __n) 238 : _Base(__n) 239 { _M_default_initialize(__n); } 240 241 /** 242 * @brief Creates a %vector with copies of an exemplar element. 243 * @param n The number of elements to initially create. 244 * @param value An element to copy. 245 * @param a An allocator. 246 * 247 * This constructor fills the %vector with @a n copies of @a value. 248 */ 249 vector(size_type __n, const value_type& __value, 250 const allocator_type& __a = allocator_type()) 251 : _Base(__n, __a) 252 { _M_fill_initialize(__n, __value); } 253#else 254 /** 255 * @brief Creates a %vector with copies of an exemplar element. 256 * @param n The number of elements to initially create. 257 * @param value An element to copy. 258 * @param a An allocator. 259 * 260 * This constructor fills the %vector with @a n copies of @a value. 261 */ 262 explicit 263 vector(size_type __n, const value_type& __value = value_type(), 264 const allocator_type& __a = allocator_type()) 265 : _Base(__n, __a) 266 { _M_fill_initialize(__n, __value); } 267#endif 268 269 /** 270 * @brief %Vector copy constructor. 271 * @param x A %vector of identical element and allocator types. 272 * 273 * The newly-created %vector uses a copy of the allocation 274 * object used by @a x. All the elements of @a x are copied, 275 * but any extra memory in 276 * @a x (for fast expansion) will not be copied. 277 */ 278 vector(const vector& __x) 279 : _Base(__x.size(), __x._M_get_Tp_allocator()) 280 { this->_M_impl._M_finish = 281 std::__uninitialized_copy_a(__x.begin(), __x.end(), 282 this->_M_impl._M_start, 283 _M_get_Tp_allocator()); 284 } 285 286#ifdef __GXX_EXPERIMENTAL_CXX0X__ 287 /** 288 * @brief %Vector move constructor. 289 * @param x A %vector of identical element and allocator types. 290 * 291 * The newly-created %vector contains the exact contents of @a x. 292 * The contents of @a x are a valid, but unspecified %vector. 293 */ 294 vector(vector&& __x) 295 : _Base(std::move(__x)) { } 296 297 /** 298 * @brief Builds a %vector from an initializer list. 299 * @param l An initializer_list. 300 * @param a An allocator. 301 * 302 * Create a %vector consisting of copies of the elements in the 303 * initializer_list @a l. 304 * 305 * This will call the element type's copy constructor N times 306 * (where N is @a l.size()) and do no memory reallocation. 307 */ 308 vector(initializer_list<value_type> __l, 309 const allocator_type& __a = allocator_type()) 310 : _Base(__a) 311 { 312 _M_range_initialize(__l.begin(), __l.end(), 313 random_access_iterator_tag()); 314 } 315#endif 316 317 /** 318 * @brief Builds a %vector from a range. 319 * @param first An input iterator. 320 * @param last An input iterator. 321 * @param a An allocator. 322 * 323 * Create a %vector consisting of copies of the elements from 324 * [first,last). 325 * 326 * If the iterators are forward, bidirectional, or 327 * random-access, then this will call the elements' copy 328 * constructor N times (where N is distance(first,last)) and do 329 * no memory reallocation. But if only input iterators are 330 * used, then this will do at most 2N calls to the copy 331 * constructor, and logN memory reallocations. 332 */ 333 template<typename _InputIterator> 334 vector(_InputIterator __first, _InputIterator __last, 335 const allocator_type& __a = allocator_type()) 336 : _Base(__a) 337 { 338 // Check whether it's an integral type. If so, it's not an iterator. 339 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 340 _M_initialize_dispatch(__first, __last, _Integral()); 341 } 342 343 /** 344 * The dtor only erases the elements, and note that if the 345 * elements themselves are pointers, the pointed-to memory is 346 * not touched in any way. Managing the pointer is the user's 347 * responsibility. 348 */ 349 ~vector() 350 { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 351 _M_get_Tp_allocator()); } 352 353 /** 354 * @brief %Vector assignment operator. 355 * @param x A %vector of identical element and allocator types. 356 * 357 * All the elements of @a x are copied, but any extra memory in 358 * @a x (for fast expansion) will not be copied. Unlike the 359 * copy constructor, the allocator object is not copied. 360 */ 361 vector& 362 operator=(const vector& __x); 363 364#ifdef __GXX_EXPERIMENTAL_CXX0X__ 365 /** 366 * @brief %Vector move assignment operator. 367 * @param x A %vector of identical element and allocator types. 368 * 369 * The contents of @a x are moved into this %vector (without copying). 370 * @a x is a valid, but unspecified %vector. 371 */ 372 vector& 373 operator=(vector&& __x) 374 { 375 // NB: DR 1204. 376 // NB: DR 675. 377 this->clear(); 378 this->swap(__x); 379 return *this; 380 } 381 382 /** 383 * @brief %Vector list assignment operator. 384 * @param l An initializer_list. 385 * 386 * This function fills a %vector with copies of the elements in the 387 * initializer list @a l. 388 * 389 * Note that the assignment completely changes the %vector and 390 * that the resulting %vector's size is the same as the number 391 * of elements assigned. Old data may be lost. 392 */ 393 vector& 394 operator=(initializer_list<value_type> __l) 395 { 396 this->assign(__l.begin(), __l.end()); 397 return *this; 398 } 399#endif 400 401 /** 402 * @brief Assigns a given value to a %vector. 403 * @param n Number of elements to be assigned. 404 * @param val Value to be assigned. 405 * 406 * This function fills a %vector with @a n copies of the given 407 * value. Note that the assignment completely changes the 408 * %vector and that the resulting %vector's size is the same as 409 * the number of elements assigned. Old data may be lost. 410 */ 411 void 412 assign(size_type __n, const value_type& __val) 413 { _M_fill_assign(__n, __val); } 414 415 /** 416 * @brief Assigns a range to a %vector. 417 * @param first An input iterator. 418 * @param last An input iterator. 419 * 420 * This function fills a %vector with copies of the elements in the 421 * range [first,last). 422 * 423 * Note that the assignment completely changes the %vector and 424 * that the resulting %vector's size is the same as the number 425 * of elements assigned. Old data may be lost. 426 */ 427 template<typename _InputIterator> 428 void 429 assign(_InputIterator __first, _InputIterator __last) 430 { 431 // Check whether it's an integral type. If so, it's not an iterator. 432 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 433 _M_assign_dispatch(__first, __last, _Integral()); 434 } 435 436#ifdef __GXX_EXPERIMENTAL_CXX0X__ 437 /** 438 * @brief Assigns an initializer list to a %vector. 439 * @param l An initializer_list. 440 * 441 * This function fills a %vector with copies of the elements in the 442 * initializer list @a l. 443 * 444 * Note that the assignment completely changes the %vector and 445 * that the resulting %vector's size is the same as the number 446 * of elements assigned. Old data may be lost. 447 */ 448 void 449 assign(initializer_list<value_type> __l) 450 { this->assign(__l.begin(), __l.end()); } 451#endif 452 453 /// Get a copy of the memory allocation object. 454 using _Base::get_allocator; 455 456 // iterators 457 /** 458 * Returns a read/write iterator that points to the first 459 * element in the %vector. Iteration is done in ordinary 460 * element order. 461 */ 462 iterator 463 begin() 464 { return iterator(this->_M_impl._M_start); } 465 466 /** 467 * Returns a read-only (constant) iterator that points to the 468 * first element in the %vector. Iteration is done in ordinary 469 * element order. 470 */ 471 const_iterator 472 begin() const 473 { return const_iterator(this->_M_impl._M_start); } 474 475 /** 476 * Returns a read/write iterator that points one past the last 477 * element in the %vector. Iteration is done in ordinary 478 * element order. 479 */ 480 iterator 481 end() 482 { return iterator(this->_M_impl._M_finish); } 483 484 /** 485 * Returns a read-only (constant) iterator that points one past 486 * the last element in the %vector. Iteration is done in 487 * ordinary element order. 488 */ 489 const_iterator 490 end() const 491 { return const_iterator(this->_M_impl._M_finish); } 492 493 /** 494 * Returns a read/write reverse iterator that points to the 495 * last element in the %vector. Iteration is done in reverse 496 * element order. 497 */ 498 reverse_iterator 499 rbegin() 500 { return reverse_iterator(end()); } 501 502 /** 503 * Returns a read-only (constant) reverse iterator that points 504 * to the last element in the %vector. Iteration is done in 505 * reverse element order. 506 */ 507 const_reverse_iterator 508 rbegin() const 509 { return const_reverse_iterator(end()); } 510 511 /** 512 * Returns a read/write reverse iterator that points to one 513 * before the first element in the %vector. Iteration is done 514 * in reverse element order. 515 */ 516 reverse_iterator 517 rend() 518 { return reverse_iterator(begin()); } 519 520 /** 521 * Returns a read-only (constant) reverse iterator that points 522 * to one before the first element in the %vector. Iteration 523 * is done in reverse element order. 524 */ 525 const_reverse_iterator 526 rend() const 527 { return const_reverse_iterator(begin()); } 528 529#ifdef __GXX_EXPERIMENTAL_CXX0X__ 530 /** 531 * Returns a read-only (constant) iterator that points to the 532 * first element in the %vector. Iteration is done in ordinary 533 * element order. 534 */ 535 const_iterator 536 cbegin() const 537 { return const_iterator(this->_M_impl._M_start); } 538 539 /** 540 * Returns a read-only (constant) iterator that points one past 541 * the last element in the %vector. Iteration is done in 542 * ordinary element order. 543 */ 544 const_iterator 545 cend() const 546 { return const_iterator(this->_M_impl._M_finish); } 547 548 /** 549 * Returns a read-only (constant) reverse iterator that points 550 * to the last element in the %vector. Iteration is done in 551 * reverse element order. 552 */ 553 const_reverse_iterator 554 crbegin() const 555 { return const_reverse_iterator(end()); } 556 557 /** 558 * Returns a read-only (constant) reverse iterator that points 559 * to one before the first element in the %vector. Iteration 560 * is done in reverse element order. 561 */ 562 const_reverse_iterator 563 crend() const 564 { return const_reverse_iterator(begin()); } 565#endif 566 567 // [23.2.4.2] capacity 568 /** Returns the number of elements in the %vector. */ 569 size_type 570 size() const 571 { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); } 572 573 /** Returns the size() of the largest possible %vector. */ 574 size_type 575 max_size() const 576 { return _M_get_Tp_allocator().max_size(); } 577 578#ifdef __GXX_EXPERIMENTAL_CXX0X__ 579 /** 580 * @brief Resizes the %vector to the specified number of elements. 581 * @param new_size Number of elements the %vector should contain. 582 * 583 * This function will %resize the %vector to the specified 584 * number of elements. If the number is smaller than the 585 * %vector's current size the %vector is truncated, otherwise 586 * default constructed elements are appended. 587 */ 588 void 589 resize(size_type __new_size) 590 { 591 if (__new_size > size()) 592 _M_default_append(__new_size - size()); 593 else if (__new_size < size()) 594 _M_erase_at_end(this->_M_impl._M_start + __new_size); 595 } 596 597 /** 598 * @brief Resizes the %vector to the specified number of elements. 599 * @param new_size Number of elements the %vector should contain. 600 * @param x Data with which new elements should be populated. 601 * 602 * This function will %resize the %vector to the specified 603 * number of elements. If the number is smaller than the 604 * %vector's current size the %vector is truncated, otherwise 605 * the %vector is extended and new elements are populated with 606 * given data. 607 */ 608 void 609 resize(size_type __new_size, const value_type& __x) 610 { 611 if (__new_size > size()) 612 insert(end(), __new_size - size(), __x); 613 else if (__new_size < size()) 614 _M_erase_at_end(this->_M_impl._M_start + __new_size); 615 } 616#else 617 /** 618 * @brief Resizes the %vector to the specified number of elements. 619 * @param new_size Number of elements the %vector should contain. 620 * @param x Data with which new elements should be populated. 621 * 622 * This function will %resize the %vector to the specified 623 * number of elements. If the number is smaller than the 624 * %vector's current size the %vector is truncated, otherwise 625 * the %vector is extended and new elements are populated with 626 * given data. 627 */ 628 void 629 resize(size_type __new_size, value_type __x = value_type()) 630 { 631 if (__new_size > size()) 632 insert(end(), __new_size - size(), __x); 633 else if (__new_size < size()) 634 _M_erase_at_end(this->_M_impl._M_start + __new_size); 635 } 636#endif 637 638#ifdef __GXX_EXPERIMENTAL_CXX0X__ 639 /** A non-binding request to reduce capacity() to size(). */ 640 void 641 shrink_to_fit() 642 { std::__shrink_to_fit<vector>::_S_do_it(*this); } 643#endif 644 645 /** 646 * Returns the total number of elements that the %vector can 647 * hold before needing to allocate more memory. 648 */ 649 size_type 650 capacity() const 651 { return size_type(this->_M_impl._M_end_of_storage 652 - this->_M_impl._M_start); } 653 654 /** 655 * Returns true if the %vector is empty. (Thus begin() would 656 * equal end().) 657 */ 658 bool 659 empty() const 660 { return begin() == end(); } 661 662 /** 663 * @brief Attempt to preallocate enough memory for specified number of 664 * elements. 665 * @param n Number of elements required. 666 * @throw std::length_error If @a n exceeds @c max_size(). 667 * 668 * This function attempts to reserve enough memory for the 669 * %vector to hold the specified number of elements. If the 670 * number requested is more than max_size(), length_error is 671 * thrown. 672 * 673 * The advantage of this function is that if optimal code is a 674 * necessity and the user can determine the number of elements 675 * that will be required, the user can reserve the memory in 676 * %advance, and thus prevent a possible reallocation of memory 677 * and copying of %vector data. 678 */ 679 void 680 reserve(size_type __n); 681 682 // element access 683 /** 684 * @brief Subscript access to the data contained in the %vector. 685 * @param n The index of the element for which data should be 686 * accessed. 687 * @return Read/write reference to data. 688 * 689 * This operator allows for easy, array-style, data access. 690 * Note that data access with this operator is unchecked and 691 * out_of_range lookups are not defined. (For checked lookups 692 * see at().) 693 */ 694 reference 695 operator[](size_type __n) 696 { return *(this->_M_impl._M_start + __n); } 697 698 /** 699 * @brief Subscript access to the data contained in the %vector. 700 * @param n The index of the element for which data should be 701 * accessed. 702 * @return Read-only (constant) reference to data. 703 * 704 * This operator allows for easy, array-style, data access. 705 * Note that data access with this operator is unchecked and 706 * out_of_range lookups are not defined. (For checked lookups 707 * see at().) 708 */ 709 const_reference 710 operator[](size_type __n) const 711 { return *(this->_M_impl._M_start + __n); } 712 713 protected: 714 /// Safety check used only from at(). 715 void 716 _M_range_check(size_type __n) const 717 { 718 if (__n >= this->size()) 719 __throw_out_of_range(__N("vector::_M_range_check")); 720 } 721 722 public: 723 /** 724 * @brief Provides access to the data contained in the %vector. 725 * @param n The index of the element for which data should be 726 * accessed. 727 * @return Read/write reference to data. 728 * @throw std::out_of_range If @a n is an invalid index. 729 * 730 * This function provides for safer data access. The parameter 731 * is first checked that it is in the range of the vector. The 732 * function throws out_of_range if the check fails. 733 */ 734 reference 735 at(size_type __n) 736 { 737 _M_range_check(__n); 738 return (*this)[__n]; 739 } 740 741 /** 742 * @brief Provides access to the data contained in the %vector. 743 * @param n The index of the element for which data should be 744 * accessed. 745 * @return Read-only (constant) reference to data. 746 * @throw std::out_of_range If @a n is an invalid index. 747 * 748 * This function provides for safer data access. The parameter 749 * is first checked that it is in the range of the vector. The 750 * function throws out_of_range if the check fails. 751 */ 752 const_reference 753 at(size_type __n) const 754 { 755 _M_range_check(__n); 756 return (*this)[__n]; 757 } 758 759 /** 760 * Returns a read/write reference to the data at the first 761 * element of the %vector. 762 */ 763 reference 764 front() 765 { return *begin(); } 766 767 /** 768 * Returns a read-only (constant) reference to the data at the first 769 * element of the %vector. 770 */ 771 const_reference 772 front() const 773 { return *begin(); } 774 775 /** 776 * Returns a read/write reference to the data at the last 777 * element of the %vector. 778 */ 779 reference 780 back() 781 { return *(end() - 1); } 782 783 /** 784 * Returns a read-only (constant) reference to the data at the 785 * last element of the %vector. 786 */ 787 const_reference 788 back() const 789 { return *(end() - 1); } 790 791 // _GLIBCXX_RESOLVE_LIB_DEFECTS 792 // DR 464. Suggestion for new member functions in standard containers. 793 // data access 794 /** 795 * Returns a pointer such that [data(), data() + size()) is a valid 796 * range. For a non-empty %vector, data() == &front(). 797 */ 798#ifdef __GXX_EXPERIMENTAL_CXX0X__ 799 _Tp* 800#else 801 pointer 802#endif 803 data() 804 { return std::__addressof(front()); } 805 806#ifdef __GXX_EXPERIMENTAL_CXX0X__ 807 const _Tp* 808#else 809 const_pointer 810#endif 811 data() const 812 { return std::__addressof(front()); } 813 814 // [23.2.4.3] modifiers 815 /** 816 * @brief Add data to the end of the %vector. 817 * @param x Data to be added. 818 * 819 * This is a typical stack operation. The function creates an 820 * element at the end of the %vector and assigns the given data 821 * to it. Due to the nature of a %vector this operation can be 822 * done in constant time if the %vector has preallocated space 823 * available. 824 */ 825 void 826 push_back(const value_type& __x) 827 { 828 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 829 { 830 this->_M_impl.construct(this->_M_impl._M_finish, __x); 831 ++this->_M_impl._M_finish; 832 } 833 else 834 _M_insert_aux(end(), __x); 835 } 836 837#ifdef __GXX_EXPERIMENTAL_CXX0X__ 838 void 839 push_back(value_type&& __x) 840 { emplace_back(std::move(__x)); } 841 842 template<typename... _Args> 843 void 844 emplace_back(_Args&&... __args); 845#endif 846 847 /** 848 * @brief Removes last element. 849 * 850 * This is a typical stack operation. It shrinks the %vector by one. 851 * 852 * Note that no data is returned, and if the last element's 853 * data is needed, it should be retrieved before pop_back() is 854 * called. 855 */ 856 void 857 pop_back() 858 { 859 --this->_M_impl._M_finish; 860 this->_M_impl.destroy(this->_M_impl._M_finish); 861 } 862 863#ifdef __GXX_EXPERIMENTAL_CXX0X__ 864 /** 865 * @brief Inserts an object in %vector before specified iterator. 866 * @param position An iterator into the %vector. 867 * @param args Arguments. 868 * @return An iterator that points to the inserted data. 869 * 870 * This function will insert an object of type T constructed 871 * with T(std::forward<Args>(args)...) before the specified location. 872 * Note that this kind of operation could be expensive for a %vector 873 * and if it is frequently used the user should consider using 874 * std::list. 875 */ 876 template<typename... _Args> 877 iterator 878 emplace(iterator __position, _Args&&... __args); 879#endif 880 881 /** 882 * @brief Inserts given value into %vector before specified iterator. 883 * @param position An iterator into the %vector. 884 * @param x Data to be inserted. 885 * @return An iterator that points to the inserted data. 886 * 887 * This function will insert a copy of the given value before 888 * the specified location. Note that this kind of operation 889 * could be expensive for a %vector and if it is frequently 890 * used the user should consider using std::list. 891 */ 892 iterator 893 insert(iterator __position, const value_type& __x); 894 895#ifdef __GXX_EXPERIMENTAL_CXX0X__ 896 /** 897 * @brief Inserts given rvalue into %vector before specified iterator. 898 * @param position An iterator into the %vector. 899 * @param x Data to be inserted. 900 * @return An iterator that points to the inserted data. 901 * 902 * This function will insert a copy of the given rvalue before 903 * the specified location. Note that this kind of operation 904 * could be expensive for a %vector and if it is frequently 905 * used the user should consider using std::list. 906 */ 907 iterator 908 insert(iterator __position, value_type&& __x) 909 { return emplace(__position, std::move(__x)); } 910 911 /** 912 * @brief Inserts an initializer_list into the %vector. 913 * @param position An iterator into the %vector. 914 * @param l An initializer_list. 915 * 916 * This function will insert copies of the data in the 917 * initializer_list @a l into the %vector before the location 918 * specified by @a position. 919 * 920 * Note that this kind of operation could be expensive for a 921 * %vector and if it is frequently used the user should 922 * consider using std::list. 923 */ 924 void 925 insert(iterator __position, initializer_list<value_type> __l) 926 { this->insert(__position, __l.begin(), __l.end()); } 927#endif 928 929 /** 930 * @brief Inserts a number of copies of given data into the %vector. 931 * @param position An iterator into the %vector. 932 * @param n Number of elements to be inserted. 933 * @param x Data to be inserted. 934 * 935 * This function will insert a specified number of copies of 936 * the given data before the location specified by @a position. 937 * 938 * Note that this kind of operation could be expensive for a 939 * %vector and if it is frequently used the user should 940 * consider using std::list. 941 */ 942 void 943 insert(iterator __position, size_type __n, const value_type& __x) 944 { _M_fill_insert(__position, __n, __x); } 945 946 /** 947 * @brief Inserts a range into the %vector. 948 * @param position An iterator into the %vector. 949 * @param first An input iterator. 950 * @param last An input iterator. 951 * 952 * This function will insert copies of the data in the range 953 * [first,last) into the %vector before the location specified 954 * by @a pos. 955 * 956 * Note that this kind of operation could be expensive for a 957 * %vector and if it is frequently used the user should 958 * consider using std::list. 959 */ 960 template<typename _InputIterator> 961 void 962 insert(iterator __position, _InputIterator __first, 963 _InputIterator __last) 964 { 965 // Check whether it's an integral type. If so, it's not an iterator. 966 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 967 _M_insert_dispatch(__position, __first, __last, _Integral()); 968 } 969 970 /** 971 * @brief Remove element at given position. 972 * @param position Iterator pointing to element to be erased. 973 * @return An iterator pointing to the next element (or end()). 974 * 975 * This function will erase the element at the given position and thus 976 * shorten the %vector by one. 977 * 978 * Note This operation could be expensive and if it is 979 * frequently used the user should consider using std::list. 980 * The user is also cautioned that this function only erases 981 * the element, and that if the element is itself a pointer, 982 * the pointed-to memory is not touched in any way. Managing 983 * the pointer is the user's responsibility. 984 */ 985 iterator 986 erase(iterator __position); 987 988 /** 989 * @brief Remove a range of elements. 990 * @param first Iterator pointing to the first element to be erased. 991 * @param last Iterator pointing to one past the last element to be 992 * erased. 993 * @return An iterator pointing to the element pointed to by @a last 994 * prior to erasing (or end()). 995 * 996 * This function will erase the elements in the range [first,last) and 997 * shorten the %vector accordingly. 998 * 999 * Note This operation could be expensive and if it is 1000 * frequently used the user should consider using std::list. 1001 * The user is also cautioned that this function only erases 1002 * the elements, and that if the elements themselves are 1003 * pointers, the pointed-to memory is not touched in any way. 1004 * Managing the pointer is the user's responsibility. 1005 */ 1006 iterator 1007 erase(iterator __first, iterator __last); 1008 1009 /** 1010 * @brief Swaps data with another %vector. 1011 * @param x A %vector of the same element and allocator types. 1012 * 1013 * This exchanges the elements between two vectors in constant time. 1014 * (Three pointers, so it should be quite fast.) 1015 * Note that the global std::swap() function is specialized such that 1016 * std::swap(v1,v2) will feed to this function. 1017 */ 1018 void 1019 swap(vector& __x) 1020 { 1021 std::swap(this->_M_impl._M_start, __x._M_impl._M_start); 1022 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); 1023 std::swap(this->_M_impl._M_end_of_storage, 1024 __x._M_impl._M_end_of_storage); 1025 1026 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1027 // 431. Swapping containers with unequal allocators. 1028 std::__alloc_swap<_Tp_alloc_type>::_S_do_it(_M_get_Tp_allocator(), 1029 __x._M_get_Tp_allocator()); 1030 } 1031 1032 /** 1033 * Erases all the elements. Note that this function only erases the 1034 * elements, and that if the elements themselves are pointers, the 1035 * pointed-to memory is not touched in any way. Managing the pointer is 1036 * the user's responsibility. 1037 */ 1038 void 1039 clear() 1040 { _M_erase_at_end(this->_M_impl._M_start); } 1041 1042 protected: 1043 /** 1044 * Memory expansion handler. Uses the member allocation function to 1045 * obtain @a n bytes of memory, and then copies [first,last) into it. 1046 */ 1047 template<typename _ForwardIterator> 1048 pointer 1049 _M_allocate_and_copy(size_type __n, 1050 _ForwardIterator __first, _ForwardIterator __last) 1051 { 1052 pointer __result = this->_M_allocate(__n); 1053 __try 1054 { 1055 std::__uninitialized_copy_a(__first, __last, __result, 1056 _M_get_Tp_allocator()); 1057 return __result; 1058 } 1059 __catch(...) 1060 { 1061 _M_deallocate(__result, __n); 1062 __throw_exception_again; 1063 } 1064 } 1065 1066 1067 // Internal constructor functions follow. 1068 1069 // Called by the range constructor to implement [23.1.1]/9 1070 1071 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1072 // 438. Ambiguity in the "do the right thing" clause 1073 template<typename _Integer> 1074 void 1075 _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type) 1076 { 1077 this->_M_impl._M_start = _M_allocate(static_cast<size_type>(__n)); 1078 this->_M_impl._M_end_of_storage = 1079 this->_M_impl._M_start + static_cast<size_type>(__n); 1080 _M_fill_initialize(static_cast<size_type>(__n), __value); 1081 } 1082 1083 // Called by the range constructor to implement [23.1.1]/9 1084 template<typename _InputIterator> 1085 void 1086 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 1087 __false_type) 1088 { 1089 typedef typename std::iterator_traits<_InputIterator>:: 1090 iterator_category _IterCategory; 1091 _M_range_initialize(__first, __last, _IterCategory()); 1092 } 1093 1094 // Called by the second initialize_dispatch above 1095 template<typename _InputIterator> 1096 void 1097 _M_range_initialize(_InputIterator __first, 1098 _InputIterator __last, std::input_iterator_tag) 1099 { 1100 for (; __first != __last; ++__first) 1101 push_back(*__first); 1102 } 1103 1104 // Called by the second initialize_dispatch above 1105 template<typename _ForwardIterator> 1106 void 1107 _M_range_initialize(_ForwardIterator __first, 1108 _ForwardIterator __last, std::forward_iterator_tag) 1109 { 1110 const size_type __n = std::distance(__first, __last); 1111 this->_M_impl._M_start = this->_M_allocate(__n); 1112 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 1113 this->_M_impl._M_finish = 1114 std::__uninitialized_copy_a(__first, __last, 1115 this->_M_impl._M_start, 1116 _M_get_Tp_allocator()); 1117 } 1118 1119 // Called by the first initialize_dispatch above and by the 1120 // vector(n,value,a) constructor. 1121 void 1122 _M_fill_initialize(size_type __n, const value_type& __value) 1123 { 1124 std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value, 1125 _M_get_Tp_allocator()); 1126 this->_M_impl._M_finish = this->_M_impl._M_end_of_storage; 1127 } 1128 1129#ifdef __GXX_EXPERIMENTAL_CXX0X__ 1130 // Called by the vector(n) constructor. 1131 void 1132 _M_default_initialize(size_type __n) 1133 { 1134 std::__uninitialized_default_n_a(this->_M_impl._M_start, __n, 1135 _M_get_Tp_allocator()); 1136 this->_M_impl._M_finish = this->_M_impl._M_end_of_storage; 1137 } 1138#endif 1139 1140 // Internal assign functions follow. The *_aux functions do the actual 1141 // assignment work for the range versions. 1142 1143 // Called by the range assign to implement [23.1.1]/9 1144 1145 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1146 // 438. Ambiguity in the "do the right thing" clause 1147 template<typename _Integer> 1148 void 1149 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 1150 { _M_fill_assign(__n, __val); } 1151 1152 // Called by the range assign to implement [23.1.1]/9 1153 template<typename _InputIterator> 1154 void 1155 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 1156 __false_type) 1157 { 1158 typedef typename std::iterator_traits<_InputIterator>:: 1159 iterator_category _IterCategory; 1160 _M_assign_aux(__first, __last, _IterCategory()); 1161 } 1162 1163 // Called by the second assign_dispatch above 1164 template<typename _InputIterator> 1165 void 1166 _M_assign_aux(_InputIterator __first, _InputIterator __last, 1167 std::input_iterator_tag); 1168 1169 // Called by the second assign_dispatch above 1170 template<typename _ForwardIterator> 1171 void 1172 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 1173 std::forward_iterator_tag); 1174 1175 // Called by assign(n,t), and the range assign when it turns out 1176 // to be the same thing. 1177 void 1178 _M_fill_assign(size_type __n, const value_type& __val); 1179 1180 1181 // Internal insert functions follow. 1182 1183 // Called by the range insert to implement [23.1.1]/9 1184 1185 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1186 // 438. Ambiguity in the "do the right thing" clause 1187 template<typename _Integer> 1188 void 1189 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val, 1190 __true_type) 1191 { _M_fill_insert(__pos, __n, __val); } 1192 1193 // Called by the range insert to implement [23.1.1]/9 1194 template<typename _InputIterator> 1195 void 1196 _M_insert_dispatch(iterator __pos, _InputIterator __first, 1197 _InputIterator __last, __false_type) 1198 { 1199 typedef typename std::iterator_traits<_InputIterator>:: 1200 iterator_category _IterCategory; 1201 _M_range_insert(__pos, __first, __last, _IterCategory()); 1202 } 1203 1204 // Called by the second insert_dispatch above 1205 template<typename _InputIterator> 1206 void 1207 _M_range_insert(iterator __pos, _InputIterator __first, 1208 _InputIterator __last, std::input_iterator_tag); 1209 1210 // Called by the second insert_dispatch above 1211 template<typename _ForwardIterator> 1212 void 1213 _M_range_insert(iterator __pos, _ForwardIterator __first, 1214 _ForwardIterator __last, std::forward_iterator_tag); 1215 1216 // Called by insert(p,n,x), and the range insert when it turns out to be 1217 // the same thing. 1218 void 1219 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x); 1220 1221#ifdef __GXX_EXPERIMENTAL_CXX0X__ 1222 // Called by resize(n). 1223 void 1224 _M_default_append(size_type __n); 1225#endif 1226 1227 // Called by insert(p,x) 1228#ifndef __GXX_EXPERIMENTAL_CXX0X__ 1229 void 1230 _M_insert_aux(iterator __position, const value_type& __x); 1231#else 1232 template<typename... _Args> 1233 void 1234 _M_insert_aux(iterator __position, _Args&&... __args); 1235#endif 1236 1237 // Called by the latter. 1238 size_type 1239 _M_check_len(size_type __n, const char* __s) const 1240 { 1241 if (max_size() - size() < __n) 1242 __throw_length_error(__N(__s)); 1243 1244 const size_type __len = size() + std::max(size(), __n); 1245 return (__len < size() || __len > max_size()) ? max_size() : __len; 1246 } 1247 1248 // Internal erase functions follow. 1249 1250 // Called by erase(q1,q2), clear(), resize(), _M_fill_assign, 1251 // _M_assign_aux. 1252 void 1253 _M_erase_at_end(pointer __pos) 1254 { 1255 std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator()); 1256 this->_M_impl._M_finish = __pos; 1257 } 1258 }; 1259 1260 1261 /** 1262 * @brief Vector equality comparison. 1263 * @param x A %vector. 1264 * @param y A %vector of the same type as @a x. 1265 * @return True iff the size and elements of the vectors are equal. 1266 * 1267 * This is an equivalence relation. It is linear in the size of the 1268 * vectors. Vectors are considered equivalent if their sizes are equal, 1269 * and if corresponding elements compare equal. 1270 */ 1271 template<typename _Tp, typename _Alloc> 1272 inline bool 1273 operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 1274 { return (__x.size() == __y.size() 1275 && std::equal(__x.begin(), __x.end(), __y.begin())); } 1276 1277 /** 1278 * @brief Vector ordering relation. 1279 * @param x A %vector. 1280 * @param y A %vector of the same type as @a x. 1281 * @return True iff @a x is lexicographically less than @a y. 1282 * 1283 * This is a total ordering relation. It is linear in the size of the 1284 * vectors. The elements must be comparable with @c <. 1285 * 1286 * See std::lexicographical_compare() for how the determination is made. 1287 */ 1288 template<typename _Tp, typename _Alloc> 1289 inline bool 1290 operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 1291 { return std::lexicographical_compare(__x.begin(), __x.end(), 1292 __y.begin(), __y.end()); } 1293 1294 /// Based on operator== 1295 template<typename _Tp, typename _Alloc> 1296 inline bool 1297 operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 1298 { return !(__x == __y); } 1299 1300 /// Based on operator< 1301 template<typename _Tp, typename _Alloc> 1302 inline bool 1303 operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 1304 { return __y < __x; } 1305 1306 /// Based on operator< 1307 template<typename _Tp, typename _Alloc> 1308 inline bool 1309 operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 1310 { return !(__y < __x); } 1311 1312 /// Based on operator< 1313 template<typename _Tp, typename _Alloc> 1314 inline bool 1315 operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 1316 { return !(__x < __y); } 1317 1318 /// See std::vector::swap(). 1319 template<typename _Tp, typename _Alloc> 1320 inline void 1321 swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y) 1322 { __x.swap(__y); } 1323 1324_GLIBCXX_END_NAMESPACE_CONTAINER 1325} // namespace std 1326 1327#endif /* _STL_VECTOR_H */ 1328