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 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 * 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 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 newly-created %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 newly-created %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 * random-access, 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 pointed-to 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 read-only (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 read-only (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 read-only (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 read-only (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 read-only (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 read-only (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 read-only (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 read-only (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 non-binding 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, array-style, 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 non-zero. 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 Read-only (constant) reference to data. 756 * 757 * This operator allows for easy, array-style, 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 non-zero. 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 Read-only (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 read-only (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 read-only (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 non-empty %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 pointed-to 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 pointed-to 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 * pointed-to 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 */ 1399