1 // Vector implementation -*- C++ -*- 2 3 // Copyright (C) 2001-2017 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /* 26 * 27 * Copyright (c) 1994 28 * Hewlett-Packard Company 29 * 30 * Permission to use, copy, modify, distribute and sell this software 31 * and its documentation for any purpose is hereby granted without fee, 32 * provided that the above copyright notice appear in all copies and 33 * that both that copyright notice and this permission notice appear 34 * in supporting documentation. Hewlett-Packard Company makes no 35 * representations about the suitability of this software for any 36 * purpose. It is provided "as is" without express or implied warranty. 37 * 38 * 39 * Copyright (c) 1996 40 * Silicon Graphics Computer Systems, Inc. 41 * 42 * Permission to use, copy, modify, distribute and sell this software 43 * and its documentation for any purpose is hereby granted without fee, 44 * provided that the above copyright notice appear in all copies and 45 * that both that copyright notice and this permission notice appear 46 * in supporting documentation. Silicon Graphics makes no 47 * representations about the suitability of this software for any 48 * purpose. It is provided "as is" without express or implied warranty. 49 */ 50 51 /** @file bits/stl_vector.h 52 * This is an internal header file, included by other library headers. 53 * Do not attempt to use it directly. @headername{vector} 54 */ 55 56 #ifndef _STL_VECTOR_H 57 #define _STL_VECTOR_H 1 58 59 #include <bits/stl_iterator_base_funcs.h> 60 #include <bits/functexcept.h> 61 #include <bits/concept_check.h> 62 #if __cplusplus >= 201103L 63 #include <initializer_list> 64 #endif 65 66 #include <debug/assertions.h> 67 68 namespace std _GLIBCXX_VISIBILITY(default) 69 { 70 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 71 72 /// See bits/stl_deque.h's _Deque_base for an explanation. 73 template<typename _Tp, typename _Alloc> 74 struct _Vector_base 75 { 76 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template 77 rebind<_Tp>::other _Tp_alloc_type; 78 typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer 79 pointer; 80 81 struct _Vector_impl 82 : public _Tp_alloc_type 83 { 84 pointer _M_start; 85 pointer _M_finish; 86 pointer _M_end_of_storage; 87 88 _Vector_impl() 89 : _Tp_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage() 90 { } 91 92 _Vector_impl(_Tp_alloc_type const& __a) _GLIBCXX_NOEXCEPT 93 : _Tp_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage() 94 { } 95 96 #if __cplusplus >= 201103L 97 _Vector_impl(_Tp_alloc_type&& __a) noexcept 98 : _Tp_alloc_type(std::move(__a)), 99 _M_start(), _M_finish(), _M_end_of_storage() 100 { } 101 #endif 102 103 void _M_swap_data(_Vector_impl& __x) _GLIBCXX_NOEXCEPT 104 { 105 std::swap(_M_start, __x._M_start); 106 std::swap(_M_finish, __x._M_finish); 107 std::swap(_M_end_of_storage, __x._M_end_of_storage); 108 } 109 }; 110 111 public: 112 typedef _Alloc allocator_type; 113 114 _Tp_alloc_type& 115 _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT 116 { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); } 117 118 const _Tp_alloc_type& 119 _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT 120 { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); } 121 122 allocator_type 123 get_allocator() const _GLIBCXX_NOEXCEPT 124 { return allocator_type(_M_get_Tp_allocator()); } 125 126 _Vector_base() 127 : _M_impl() { } 128 129 _Vector_base(const allocator_type& __a) _GLIBCXX_NOEXCEPT 130 : _M_impl(__a) { } 131 132 _Vector_base(size_t __n) 133 : _M_impl() 134 { _M_create_storage(__n); } 135 136 _Vector_base(size_t __n, const allocator_type& __a) 137 : _M_impl(__a) 138 { _M_create_storage(__n); } 139 140 #if __cplusplus >= 201103L 141 _Vector_base(_Tp_alloc_type&& __a) noexcept 142 : _M_impl(std::move(__a)) { } 143 144 _Vector_base(_Vector_base&& __x) noexcept 145 : _M_impl(std::move(__x._M_get_Tp_allocator())) 146 { this->_M_impl._M_swap_data(__x._M_impl); } 147 148 _Vector_base(_Vector_base&& __x, const allocator_type& __a) 149 : _M_impl(__a) 150 { 151 if (__x.get_allocator() == __a) 152 this->_M_impl._M_swap_data(__x._M_impl); 153 else 154 { 155 size_t __n = __x._M_impl._M_finish - __x._M_impl._M_start; 156 _M_create_storage(__n); 157 } 158 } 159 #endif 160 161 ~_Vector_base() _GLIBCXX_NOEXCEPT 162 { _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage 163 - this->_M_impl._M_start); } 164 165 public: 166 _Vector_impl _M_impl; 167 168 pointer 169 _M_allocate(size_t __n) 170 { 171 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr; 172 return __n != 0 ? _Tr::allocate(_M_impl, __n) : pointer(); 173 } 174 175 void 176 _M_deallocate(pointer __p, size_t __n) 177 { 178 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr; 179 if (__p) 180 _Tr::deallocate(_M_impl, __p, __n); 181 } 182 183 private: 184 void 185 _M_create_storage(size_t __n) 186 { 187 this->_M_impl._M_start = this->_M_allocate(__n); 188 this->_M_impl._M_finish = this->_M_impl._M_start; 189 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 190 } 191 }; 192 193 194 /** 195 * @brief A standard container which offers fixed time access to 196 * individual elements in any order. 197 * 198 * @ingroup sequences 199 * 200 * @tparam _Tp Type of element. 201 * @tparam _Alloc Allocator type, defaults to allocator<_Tp>. 202 * 203 * Meets the requirements of a <a href="tables.html#65">container</a>, a 204 * <a href="tables.html#66">reversible container</a>, and a 205 * <a href="tables.html#67">sequence</a>, including the 206 * <a href="tables.html#68">optional sequence requirements</a> with the 207 * %exception of @c push_front and @c pop_front. 208 * 209 * In some terminology a %vector can be described as a dynamic 210 * C-style array, it offers fast and efficient access to individual 211 * elements in any order and saves the user from worrying about 212 * memory and size allocation. Subscripting ( @c [] ) access is 213 * also provided as with C-style arrays. 214 */ 215 template<typename _Tp, typename _Alloc = std::allocator<_Tp> > 216 class vector : protected _Vector_base<_Tp, _Alloc> 217 { 218 #ifdef _GLIBCXX_CONCEPT_CHECKS 219 // Concept requirements. 220 typedef typename _Alloc::value_type _Alloc_value_type; 221 # if __cplusplus < 201103L 222 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 223 # endif 224 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept) 225 #endif 226 227 typedef _Vector_base<_Tp, _Alloc> _Base; 228 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; 229 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Alloc_traits; 230 231 public: 232 typedef _Tp value_type; 233 typedef typename _Base::pointer pointer; 234 typedef typename _Alloc_traits::const_pointer const_pointer; 235 typedef typename _Alloc_traits::reference reference; 236 typedef typename _Alloc_traits::const_reference const_reference; 237 typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator; 238 typedef __gnu_cxx::__normal_iterator<const_pointer, vector> 239 const_iterator; 240 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 241 typedef std::reverse_iterator<iterator> reverse_iterator; 242 typedef size_t size_type; 243 typedef ptrdiff_t difference_type; 244 typedef _Alloc allocator_type; 245 246 protected: 247 using _Base::_M_allocate; 248 using _Base::_M_deallocate; 249 using _Base::_M_impl; 250 using _Base::_M_get_Tp_allocator; 251 252 public: 253 // [23.2.4.1] construct/copy/destroy 254 // (assign() and get_allocator() are also listed in this section) 255 256 /** 257 * @brief Creates a %vector with no elements. 258 */ 259 vector() 260 #if __cplusplus >= 201103L 261 noexcept(is_nothrow_default_constructible<_Alloc>::value) 262 #endif 263 : _Base() { } 264 265 /** 266 * @brief Creates a %vector with no elements. 267 * @param __a An allocator object. 268 */ 269 explicit 270 vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT 271 : _Base(__a) { } 272 273 #if __cplusplus >= 201103L 274 /** 275 * @brief Creates a %vector with default constructed elements. 276 * @param __n The number of elements to initially create. 277 * @param __a An allocator. 278 * 279 * This constructor fills the %vector with @a __n default 280 * constructed elements. 281 */ 282 explicit 283 vector(size_type __n, const allocator_type& __a = allocator_type()) 284 : _Base(__n, __a) 285 { _M_default_initialize(__n); } 286 287 /** 288 * @brief Creates a %vector with copies of an exemplar element. 289 * @param __n The number of elements to initially create. 290 * @param __value An element to copy. 291 * @param __a An allocator. 292 * 293 * This constructor fills the %vector with @a __n copies of @a __value. 294 */ 295 vector(size_type __n, const value_type& __value, 296 const allocator_type& __a = allocator_type()) 297 : _Base(__n, __a) 298 { _M_fill_initialize(__n, __value); } 299 #else 300 /** 301 * @brief Creates a %vector with copies of an exemplar element. 302 * @param __n The number of elements to initially create. 303 * @param __value An element to copy. 304 * @param __a An allocator. 305 * 306 * This constructor fills the %vector with @a __n copies of @a __value. 307 */ 308 explicit 309 vector(size_type __n, const value_type& __value = value_type(), 310 const allocator_type& __a = allocator_type()) 311 : _Base(__n, __a) 312 { _M_fill_initialize(__n, __value); } 313 #endif 314 315 /** 316 * @brief %Vector copy constructor. 317 * @param __x A %vector of identical element and allocator types. 318 * 319 * All the elements of @a __x are copied, but any unused capacity in 320 * @a __x will not be copied 321 * (i.e. capacity() == size() in the new %vector). 322 * 323 * The newly-created %vector uses a copy of the allocator object used 324 * by @a __x (unless the allocator traits dictate a different object). 325 */ 326 vector(const vector& __x) 327 : _Base(__x.size(), 328 _Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator())) 329 { 330 this->_M_impl._M_finish = 331 std::__uninitialized_copy_a(__x.begin(), __x.end(), 332 this->_M_impl._M_start, 333 _M_get_Tp_allocator()); 334 } 335 336 #if __cplusplus >= 201103L 337 /** 338 * @brief %Vector move constructor. 339 * @param __x A %vector of identical element and allocator types. 340 * 341 * The newly-created %vector contains the exact contents of @a __x. 342 * The contents of @a __x are a valid, but unspecified %vector. 343 */ 344 vector(vector&& __x) noexcept 345 : _Base(std::move(__x)) { } 346 347 /// Copy constructor with alternative allocator 348 vector(const vector& __x, const allocator_type& __a) 349 : _Base(__x.size(), __a) 350 { 351 this->_M_impl._M_finish = 352 std::__uninitialized_copy_a(__x.begin(), __x.end(), 353 this->_M_impl._M_start, 354 _M_get_Tp_allocator()); 355 } 356 357 /// Move constructor with alternative allocator 358 vector(vector&& __rv, const allocator_type& __m) 359 noexcept(_Alloc_traits::_S_always_equal()) 360 : _Base(std::move(__rv), __m) 361 { 362 if (__rv.get_allocator() != __m) 363 { 364 this->_M_impl._M_finish = 365 std::__uninitialized_move_a(__rv.begin(), __rv.end(), 366 this->_M_impl._M_start, 367 _M_get_Tp_allocator()); 368 __rv.clear(); 369 } 370 } 371 372 /** 373 * @brief Builds a %vector from an initializer list. 374 * @param __l An initializer_list. 375 * @param __a An allocator. 376 * 377 * Create a %vector consisting of copies of the elements in the 378 * initializer_list @a __l. 379 * 380 * This will call the element type's copy constructor N times 381 * (where N is @a __l.size()) and do no memory reallocation. 382 */ 383 vector(initializer_list<value_type> __l, 384 const allocator_type& __a = allocator_type()) 385 : _Base(__a) 386 { 387 _M_range_initialize(__l.begin(), __l.end(), 388 random_access_iterator_tag()); 389 } 390 #endif 391 392 /** 393 * @brief Builds a %vector from a range. 394 * @param __first An input iterator. 395 * @param __last An input iterator. 396 * @param __a An allocator. 397 * 398 * Create a %vector consisting of copies of the elements from 399 * [first,last). 400 * 401 * If the iterators are forward, bidirectional, or 402 * random-access, then this will call the elements' copy 403 * constructor N times (where N is distance(first,last)) and do 404 * no memory reallocation. But if only input iterators are 405 * used, then this will do at most 2N calls to the copy 406 * constructor, and logN memory reallocations. 407 */ 408 #if __cplusplus >= 201103L 409 template<typename _InputIterator, 410 typename = std::_RequireInputIter<_InputIterator>> 411 vector(_InputIterator __first, _InputIterator __last, 412 const allocator_type& __a = allocator_type()) 413 : _Base(__a) 414 { _M_initialize_dispatch(__first, __last, __false_type()); } 415 #else 416 template<typename _InputIterator> 417 vector(_InputIterator __first, _InputIterator __last, 418 const allocator_type& __a = allocator_type()) 419 : _Base(__a) 420 { 421 // Check whether it's an integral type. If so, it's not an iterator. 422 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 423 _M_initialize_dispatch(__first, __last, _Integral()); 424 } 425 #endif 426 427 /** 428 * The dtor only erases the elements, and note that if the 429 * elements themselves are pointers, the pointed-to memory is 430 * not touched in any way. Managing the pointer is the user's 431 * responsibility. 432 */ 433 ~vector() _GLIBCXX_NOEXCEPT 434 { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 435 _M_get_Tp_allocator()); } 436 437 /** 438 * @brief %Vector assignment operator. 439 * @param __x A %vector of identical element and allocator types. 440 * 441 * All the elements of @a __x are copied, but any unused capacity in 442 * @a __x will not be copied. 443 * 444 * Whether the allocator is copied depends on the allocator traits. 445 */ 446 vector& 447 operator=(const vector& __x); 448 449 #if __cplusplus >= 201103L 450 /** 451 * @brief %Vector move assignment operator. 452 * @param __x A %vector of identical element and allocator types. 453 * 454 * The contents of @a __x are moved into this %vector (without copying, 455 * if the allocators permit it). 456 * Afterwards @a __x is a valid, but unspecified %vector. 457 * 458 * Whether the allocator is moved depends on the allocator traits. 459 */ 460 vector& 461 operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move()) 462 { 463 constexpr bool __move_storage = 464 _Alloc_traits::_S_propagate_on_move_assign() 465 || _Alloc_traits::_S_always_equal(); 466 _M_move_assign(std::move(__x), __bool_constant<__move_storage>()); 467 return *this; 468 } 469 470 /** 471 * @brief %Vector list assignment operator. 472 * @param __l An initializer_list. 473 * 474 * This function fills a %vector with copies of the elements in the 475 * initializer list @a __l. 476 * 477 * Note that the assignment completely changes the %vector and 478 * that the resulting %vector's size is the same as the number 479 * of elements assigned. 480 */ 481 vector& 482 operator=(initializer_list<value_type> __l) 483 { 484 this->_M_assign_aux(__l.begin(), __l.end(), 485 random_access_iterator_tag()); 486 return *this; 487 } 488 #endif 489 490 /** 491 * @brief Assigns a given value to a %vector. 492 * @param __n Number of elements to be assigned. 493 * @param __val Value to be assigned. 494 * 495 * This function fills a %vector with @a __n copies of the given 496 * value. Note that the assignment completely changes the 497 * %vector and that the resulting %vector's size is the same as 498 * the number of elements assigned. 499 */ 500 void 501 assign(size_type __n, const value_type& __val) 502 { _M_fill_assign(__n, __val); } 503 504 /** 505 * @brief Assigns a range to a %vector. 506 * @param __first An input iterator. 507 * @param __last An input iterator. 508 * 509 * This function fills a %vector with copies of the elements in the 510 * range [__first,__last). 511 * 512 * Note that the assignment completely changes the %vector and 513 * that the resulting %vector's size is the same as the number 514 * of elements assigned. 515 */ 516 #if __cplusplus >= 201103L 517 template<typename _InputIterator, 518 typename = std::_RequireInputIter<_InputIterator>> 519 void 520 assign(_InputIterator __first, _InputIterator __last) 521 { _M_assign_dispatch(__first, __last, __false_type()); } 522 #else 523 template<typename _InputIterator> 524 void 525 assign(_InputIterator __first, _InputIterator __last) 526 { 527 // Check whether it's an integral type. If so, it's not an iterator. 528 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 529 _M_assign_dispatch(__first, __last, _Integral()); 530 } 531 #endif 532 533 #if __cplusplus >= 201103L 534 /** 535 * @brief Assigns an initializer list to a %vector. 536 * @param __l An initializer_list. 537 * 538 * This function fills a %vector with copies of the elements in the 539 * initializer list @a __l. 540 * 541 * Note that the assignment completely changes the %vector and 542 * that the resulting %vector's size is the same as the number 543 * of elements assigned. 544 */ 545 void 546 assign(initializer_list<value_type> __l) 547 { 548 this->_M_assign_aux(__l.begin(), __l.end(), 549 random_access_iterator_tag()); 550 } 551 #endif 552 553 /// Get a copy of the memory allocation object. 554 using _Base::get_allocator; 555 556 // iterators 557 /** 558 * Returns a read/write iterator that points to the first 559 * element in the %vector. Iteration is done in ordinary 560 * element order. 561 */ 562 iterator 563 begin() _GLIBCXX_NOEXCEPT 564 { return iterator(this->_M_impl._M_start); } 565 566 /** 567 * Returns a read-only (constant) iterator that points to the 568 * first element in the %vector. Iteration is done in ordinary 569 * element order. 570 */ 571 const_iterator 572 begin() const _GLIBCXX_NOEXCEPT 573 { return const_iterator(this->_M_impl._M_start); } 574 575 /** 576 * Returns a read/write iterator that points one past the last 577 * element in the %vector. Iteration is done in ordinary 578 * element order. 579 */ 580 iterator 581 end() _GLIBCXX_NOEXCEPT 582 { return iterator(this->_M_impl._M_finish); } 583 584 /** 585 * Returns a read-only (constant) iterator that points one past 586 * the last element in the %vector. Iteration is done in 587 * ordinary element order. 588 */ 589 const_iterator 590 end() const _GLIBCXX_NOEXCEPT 591 { return const_iterator(this->_M_impl._M_finish); } 592 593 /** 594 * Returns a read/write reverse iterator that points to the 595 * last element in the %vector. Iteration is done in reverse 596 * element order. 597 */ 598 reverse_iterator 599 rbegin() _GLIBCXX_NOEXCEPT 600 { return reverse_iterator(end()); } 601 602 /** 603 * Returns a read-only (constant) reverse iterator that points 604 * to the last element in the %vector. Iteration is done in 605 * reverse element order. 606 */ 607 const_reverse_iterator 608 rbegin() const _GLIBCXX_NOEXCEPT 609 { return const_reverse_iterator(end()); } 610 611 /** 612 * Returns a read/write reverse iterator that points to one 613 * before the first element in the %vector. Iteration is done 614 * in reverse element order. 615 */ 616 reverse_iterator 617 rend() _GLIBCXX_NOEXCEPT 618 { return reverse_iterator(begin()); } 619 620 /** 621 * Returns a read-only (constant) reverse iterator that points 622 * to one before the first element in the %vector. Iteration 623 * is done in reverse element order. 624 */ 625 const_reverse_iterator 626 rend() const _GLIBCXX_NOEXCEPT 627 { return const_reverse_iterator(begin()); } 628 629 #if __cplusplus >= 201103L 630 /** 631 * Returns a read-only (constant) iterator that points to the 632 * first element in the %vector. Iteration is done in ordinary 633 * element order. 634 */ 635 const_iterator 636 cbegin() const noexcept 637 { return const_iterator(this->_M_impl._M_start); } 638 639 /** 640 * Returns a read-only (constant) iterator that points one past 641 * the last element in the %vector. Iteration is done in 642 * ordinary element order. 643 */ 644 const_iterator 645 cend() const noexcept 646 { return const_iterator(this->_M_impl._M_finish); } 647 648 /** 649 * Returns a read-only (constant) reverse iterator that points 650 * to the last element in the %vector. Iteration is done in 651 * reverse element order. 652 */ 653 const_reverse_iterator 654 crbegin() const noexcept 655 { return const_reverse_iterator(end()); } 656 657 /** 658 * Returns a read-only (constant) reverse iterator that points 659 * to one before the first element in the %vector. Iteration 660 * is done in reverse element order. 661 */ 662 const_reverse_iterator 663 crend() const noexcept 664 { return const_reverse_iterator(begin()); } 665 #endif 666 667 // [23.2.4.2] capacity 668 /** Returns the number of elements in the %vector. */ 669 size_type 670 size() const _GLIBCXX_NOEXCEPT 671 { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); } 672 673 /** Returns the size() of the largest possible %vector. */ 674 size_type 675 max_size() const _GLIBCXX_NOEXCEPT 676 { return _Alloc_traits::max_size(_M_get_Tp_allocator()); } 677 678 #if __cplusplus >= 201103L 679 /** 680 * @brief Resizes the %vector to the specified number of elements. 681 * @param __new_size Number of elements the %vector should contain. 682 * 683 * This function will %resize the %vector to the specified 684 * number of elements. If the number is smaller than the 685 * %vector's current size the %vector is truncated, otherwise 686 * default constructed elements are appended. 687 */ 688 void 689 resize(size_type __new_size) 690 { 691 if (__new_size > size()) 692 _M_default_append(__new_size - size()); 693 else if (__new_size < size()) 694 _M_erase_at_end(this->_M_impl._M_start + __new_size); 695 } 696 697 /** 698 * @brief Resizes the %vector to the specified number of elements. 699 * @param __new_size Number of elements the %vector should contain. 700 * @param __x Data with which new elements should be populated. 701 * 702 * This function will %resize the %vector to the specified 703 * number of elements. If the number is smaller than the 704 * %vector's current size the %vector is truncated, otherwise 705 * the %vector is extended and new elements are populated with 706 * given data. 707 */ 708 void 709 resize(size_type __new_size, const value_type& __x) 710 { 711 if (__new_size > size()) 712 _M_fill_insert(end(), __new_size - size(), __x); 713 else if (__new_size < size()) 714 _M_erase_at_end(this->_M_impl._M_start + __new_size); 715 } 716 #else 717 /** 718 * @brief Resizes the %vector to the specified number of elements. 719 * @param __new_size Number of elements the %vector should contain. 720 * @param __x Data with which new elements should be populated. 721 * 722 * This function will %resize the %vector to the specified 723 * number of elements. If the number is smaller than the 724 * %vector's current size the %vector is truncated, otherwise 725 * the %vector is extended and new elements are populated with 726 * given data. 727 */ 728 void 729 resize(size_type __new_size, value_type __x = value_type()) 730 { 731 if (__new_size > size()) 732 _M_fill_insert(end(), __new_size - size(), __x); 733 else if (__new_size < size()) 734 _M_erase_at_end(this->_M_impl._M_start + __new_size); 735 } 736 #endif 737 738 #if __cplusplus >= 201103L 739 /** A non-binding request to reduce capacity() to size(). */ 740 void 741 shrink_to_fit() 742 { _M_shrink_to_fit(); } 743 #endif 744 745 /** 746 * Returns the total number of elements that the %vector can 747 * hold before needing to allocate more memory. 748 */ 749 size_type 750 capacity() const _GLIBCXX_NOEXCEPT 751 { return size_type(this->_M_impl._M_end_of_storage 752 - this->_M_impl._M_start); } 753 754 /** 755 * Returns true if the %vector is empty. (Thus begin() would 756 * equal end().) 757 */ 758 bool 759 empty() const _GLIBCXX_NOEXCEPT 760 { return begin() == end(); } 761 762 /** 763 * @brief Attempt to preallocate enough memory for specified number of 764 * elements. 765 * @param __n Number of elements required. 766 * @throw std::length_error If @a n exceeds @c max_size(). 767 * 768 * This function attempts to reserve enough memory for the 769 * %vector to hold the specified number of elements. If the 770 * number requested is more than max_size(), length_error is 771 * thrown. 772 * 773 * The advantage of this function is that if optimal code is a 774 * necessity and the user can determine the number of elements 775 * that will be required, the user can reserve the memory in 776 * %advance, and thus prevent a possible reallocation of memory 777 * and copying of %vector data. 778 */ 779 void 780 reserve(size_type __n); 781 782 // element access 783 /** 784 * @brief Subscript access to the data contained in the %vector. 785 * @param __n The index of the element for which data should be 786 * accessed. 787 * @return Read/write reference to data. 788 * 789 * This operator allows for easy, array-style, data access. 790 * Note that data access with this operator is unchecked and 791 * out_of_range lookups are not defined. (For checked lookups 792 * see at().) 793 */ 794 reference 795 operator[](size_type __n) _GLIBCXX_NOEXCEPT 796 { 797 __glibcxx_requires_subscript(__n); 798 return *(this->_M_impl._M_start + __n); 799 } 800 801 /** 802 * @brief Subscript access to the data contained in the %vector. 803 * @param __n The index of the element for which data should be 804 * accessed. 805 * @return Read-only (constant) reference to data. 806 * 807 * This operator allows for easy, array-style, data access. 808 * Note that data access with this operator is unchecked and 809 * out_of_range lookups are not defined. (For checked lookups 810 * see at().) 811 */ 812 const_reference 813 operator[](size_type __n) const _GLIBCXX_NOEXCEPT 814 { 815 __glibcxx_requires_subscript(__n); 816 return *(this->_M_impl._M_start + __n); 817 } 818 819 protected: 820 /// Safety check used only from at(). 821 void 822 _M_range_check(size_type __n) const 823 { 824 if (__n >= this->size()) 825 __throw_out_of_range_fmt(__N("vector::_M_range_check: __n " 826 "(which is %zu) >= this->size() " 827 "(which is %zu)"), 828 __n, this->size()); 829 } 830 831 public: 832 /** 833 * @brief Provides access to the data contained in the %vector. 834 * @param __n The index of the element for which data should be 835 * accessed. 836 * @return Read/write reference to data. 837 * @throw std::out_of_range If @a __n is an invalid index. 838 * 839 * This function provides for safer data access. The parameter 840 * is first checked that it is in the range of the vector. The 841 * function throws out_of_range if the check fails. 842 */ 843 reference 844 at(size_type __n) 845 { 846 _M_range_check(__n); 847 return (*this)[__n]; 848 } 849 850 /** 851 * @brief Provides access to the data contained in the %vector. 852 * @param __n The index of the element for which data should be 853 * accessed. 854 * @return Read-only (constant) reference to data. 855 * @throw std::out_of_range If @a __n is an invalid index. 856 * 857 * This function provides for safer data access. The parameter 858 * is first checked that it is in the range of the vector. The 859 * function throws out_of_range if the check fails. 860 */ 861 const_reference 862 at(size_type __n) const 863 { 864 _M_range_check(__n); 865 return (*this)[__n]; 866 } 867 868 /** 869 * Returns a read/write reference to the data at the first 870 * element of the %vector. 871 */ 872 reference 873 front() _GLIBCXX_NOEXCEPT 874 { 875 __glibcxx_requires_nonempty(); 876 return *begin(); 877 } 878 879 /** 880 * Returns a read-only (constant) reference to the data at the first 881 * element of the %vector. 882 */ 883 const_reference 884 front() const _GLIBCXX_NOEXCEPT 885 { 886 __glibcxx_requires_nonempty(); 887 return *begin(); 888 } 889 890 /** 891 * Returns a read/write reference to the data at the last 892 * element of the %vector. 893 */ 894 reference 895 back() _GLIBCXX_NOEXCEPT 896 { 897 __glibcxx_requires_nonempty(); 898 return *(end() - 1); 899 } 900 901 /** 902 * Returns a read-only (constant) reference to the data at the 903 * last element of the %vector. 904 */ 905 const_reference 906 back() const _GLIBCXX_NOEXCEPT 907 { 908 __glibcxx_requires_nonempty(); 909 return *(end() - 1); 910 } 911 912 // _GLIBCXX_RESOLVE_LIB_DEFECTS 913 // DR 464. Suggestion for new member functions in standard containers. 914 // data access 915 /** 916 * Returns a pointer such that [data(), data() + size()) is a valid 917 * range. For a non-empty %vector, data() == &front(). 918 */ 919 _Tp* 920 data() _GLIBCXX_NOEXCEPT 921 { return _M_data_ptr(this->_M_impl._M_start); } 922 923 const _Tp* 924 data() const _GLIBCXX_NOEXCEPT 925 { return _M_data_ptr(this->_M_impl._M_start); } 926 927 // [23.2.4.3] modifiers 928 /** 929 * @brief Add data to the end of the %vector. 930 * @param __x Data to be added. 931 * 932 * This is a typical stack operation. The function creates an 933 * element at the end of the %vector and assigns the given data 934 * to it. Due to the nature of a %vector this operation can be 935 * done in constant time if the %vector has preallocated space 936 * available. 937 */ 938 void 939 push_back(const value_type& __x) 940 { 941 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 942 { 943 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, 944 __x); 945 ++this->_M_impl._M_finish; 946 } 947 else 948 _M_realloc_insert(end(), __x); 949 } 950 951 #if __cplusplus >= 201103L 952 void 953 push_back(value_type&& __x) 954 { emplace_back(std::move(__x)); } 955 956 template<typename... _Args> 957 #if __cplusplus > 201402L 958 reference 959 #else 960 void 961 #endif 962 emplace_back(_Args&&... __args); 963 #endif 964 965 /** 966 * @brief Removes last element. 967 * 968 * This is a typical stack operation. It shrinks the %vector by one. 969 * 970 * Note that no data is returned, and if the last element's 971 * data is needed, it should be retrieved before pop_back() is 972 * called. 973 */ 974 void 975 pop_back() _GLIBCXX_NOEXCEPT 976 { 977 __glibcxx_requires_nonempty(); 978 --this->_M_impl._M_finish; 979 _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish); 980 } 981 982 #if __cplusplus >= 201103L 983 /** 984 * @brief Inserts an object in %vector before specified iterator. 985 * @param __position A const_iterator into the %vector. 986 * @param __args Arguments. 987 * @return An iterator that points to the inserted data. 988 * 989 * This function will insert an object of type T constructed 990 * with T(std::forward<Args>(args)...) before the specified location. 991 * Note that this kind of operation could be expensive for a %vector 992 * and if it is frequently used the user should consider using 993 * std::list. 994 */ 995 template<typename... _Args> 996 iterator 997 emplace(const_iterator __position, _Args&&... __args) 998 { return _M_emplace_aux(__position, std::forward<_Args>(__args)...); } 999 1000 /** 1001 * @brief Inserts given value into %vector before specified iterator. 1002 * @param __position A const_iterator into the %vector. 1003 * @param __x Data to be inserted. 1004 * @return An iterator that points to the inserted data. 1005 * 1006 * This function will insert a copy of the given value before 1007 * the specified location. Note that this kind of operation 1008 * could be expensive for a %vector and if it is frequently 1009 * used the user should consider using std::list. 1010 */ 1011 iterator 1012 insert(const_iterator __position, const value_type& __x); 1013 #else 1014 /** 1015 * @brief Inserts given value into %vector before specified iterator. 1016 * @param __position An iterator into the %vector. 1017 * @param __x Data to be inserted. 1018 * @return An iterator that points to the inserted data. 1019 * 1020 * This function will insert a copy of the given value before 1021 * the specified location. Note that this kind of operation 1022 * could be expensive for a %vector and if it is frequently 1023 * used the user should consider using std::list. 1024 */ 1025 iterator 1026 insert(iterator __position, const value_type& __x); 1027 #endif 1028 1029 #if __cplusplus >= 201103L 1030 /** 1031 * @brief Inserts given rvalue into %vector before specified iterator. 1032 * @param __position A const_iterator into the %vector. 1033 * @param __x Data to be inserted. 1034 * @return An iterator that points to the inserted data. 1035 * 1036 * This function will insert a copy of the given rvalue before 1037 * the specified location. Note that this kind of operation 1038 * could be expensive for a %vector and if it is frequently 1039 * used the user should consider using std::list. 1040 */ 1041 iterator 1042 insert(const_iterator __position, value_type&& __x) 1043 { return _M_insert_rval(__position, std::move(__x)); } 1044 1045 /** 1046 * @brief Inserts an initializer_list into the %vector. 1047 * @param __position An iterator into the %vector. 1048 * @param __l An initializer_list. 1049 * 1050 * This function will insert copies of the data in the 1051 * initializer_list @a l into the %vector before the location 1052 * specified by @a position. 1053 * 1054 * Note that this kind of operation could be expensive for a 1055 * %vector and if it is frequently used the user should 1056 * consider using std::list. 1057 */ 1058 iterator 1059 insert(const_iterator __position, initializer_list<value_type> __l) 1060 { 1061 auto __offset = __position - cbegin(); 1062 _M_range_insert(begin() + __offset, __l.begin(), __l.end(), 1063 std::random_access_iterator_tag()); 1064 return begin() + __offset; 1065 } 1066 #endif 1067 1068 #if __cplusplus >= 201103L 1069 /** 1070 * @brief Inserts a number of copies of given data into the %vector. 1071 * @param __position A const_iterator into the %vector. 1072 * @param __n Number of elements to be inserted. 1073 * @param __x Data to be inserted. 1074 * @return An iterator that points to the inserted data. 1075 * 1076 * This function will insert a specified number of copies of 1077 * the given data before the location specified by @a position. 1078 * 1079 * Note that this kind of operation could be expensive for a 1080 * %vector and if it is frequently used the user should 1081 * consider using std::list. 1082 */ 1083 iterator 1084 insert(const_iterator __position, size_type __n, const value_type& __x) 1085 { 1086 difference_type __offset = __position - cbegin(); 1087 _M_fill_insert(begin() + __offset, __n, __x); 1088 return begin() + __offset; 1089 } 1090 #else 1091 /** 1092 * @brief Inserts a number of copies of given data into the %vector. 1093 * @param __position An iterator into the %vector. 1094 * @param __n Number of elements to be inserted. 1095 * @param __x Data to be inserted. 1096 * 1097 * This function will insert a specified number of copies of 1098 * the given data before the location specified by @a position. 1099 * 1100 * Note that this kind of operation could be expensive for a 1101 * %vector and if it is frequently used the user should 1102 * consider using std::list. 1103 */ 1104 void 1105 insert(iterator __position, size_type __n, const value_type& __x) 1106 { _M_fill_insert(__position, __n, __x); } 1107 #endif 1108 1109 #if __cplusplus >= 201103L 1110 /** 1111 * @brief Inserts a range into the %vector. 1112 * @param __position A const_iterator into the %vector. 1113 * @param __first An input iterator. 1114 * @param __last An input iterator. 1115 * @return An iterator that points to the inserted data. 1116 * 1117 * This function will insert copies of the data in the range 1118 * [__first,__last) into the %vector before the location specified 1119 * by @a pos. 1120 * 1121 * Note that this kind of operation could be expensive for a 1122 * %vector and if it is frequently used the user should 1123 * consider using std::list. 1124 */ 1125 template<typename _InputIterator, 1126 typename = std::_RequireInputIter<_InputIterator>> 1127 iterator 1128 insert(const_iterator __position, _InputIterator __first, 1129 _InputIterator __last) 1130 { 1131 difference_type __offset = __position - cbegin(); 1132 _M_insert_dispatch(begin() + __offset, 1133 __first, __last, __false_type()); 1134 return begin() + __offset; 1135 } 1136 #else 1137 /** 1138 * @brief Inserts a range into the %vector. 1139 * @param __position An iterator into the %vector. 1140 * @param __first An input iterator. 1141 * @param __last An input iterator. 1142 * 1143 * This function will insert copies of the data in the range 1144 * [__first,__last) into the %vector before the location specified 1145 * by @a pos. 1146 * 1147 * Note that this kind of operation could be expensive for a 1148 * %vector and if it is frequently used the user should 1149 * consider using std::list. 1150 */ 1151 template<typename _InputIterator> 1152 void 1153 insert(iterator __position, _InputIterator __first, 1154 _InputIterator __last) 1155 { 1156 // Check whether it's an integral type. If so, it's not an iterator. 1157 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 1158 _M_insert_dispatch(__position, __first, __last, _Integral()); 1159 } 1160 #endif 1161 1162 /** 1163 * @brief Remove element at given position. 1164 * @param __position Iterator pointing to element to be erased. 1165 * @return An iterator pointing to the next element (or end()). 1166 * 1167 * This function will erase the element at the given position and thus 1168 * shorten the %vector by one. 1169 * 1170 * Note This operation could be expensive and if it is 1171 * frequently used the user should consider using std::list. 1172 * The user is also cautioned that this function only erases 1173 * the element, and that if the element is itself a pointer, 1174 * the pointed-to memory is not touched in any way. Managing 1175 * the pointer is the user's responsibility. 1176 */ 1177 iterator 1178 #if __cplusplus >= 201103L 1179 erase(const_iterator __position) 1180 { return _M_erase(begin() + (__position - cbegin())); } 1181 #else 1182 erase(iterator __position) 1183 { return _M_erase(__position); } 1184 #endif 1185 1186 /** 1187 * @brief Remove a range of elements. 1188 * @param __first Iterator pointing to the first element to be erased. 1189 * @param __last Iterator pointing to one past the last element to be 1190 * erased. 1191 * @return An iterator pointing to the element pointed to by @a __last 1192 * prior to erasing (or end()). 1193 * 1194 * This function will erase the elements in the range 1195 * [__first,__last) and shorten the %vector accordingly. 1196 * 1197 * Note This operation could be expensive and if it is 1198 * frequently used the user should consider using std::list. 1199 * The user is also cautioned that this function only erases 1200 * the elements, and that if the elements themselves are 1201 * pointers, the pointed-to memory is not touched in any way. 1202 * Managing the pointer is the user's responsibility. 1203 */ 1204 iterator 1205 #if __cplusplus >= 201103L 1206 erase(const_iterator __first, const_iterator __last) 1207 { 1208 const auto __beg = begin(); 1209 const auto __cbeg = cbegin(); 1210 return _M_erase(__beg + (__first - __cbeg), __beg + (__last - __cbeg)); 1211 } 1212 #else 1213 erase(iterator __first, iterator __last) 1214 { return _M_erase(__first, __last); } 1215 #endif 1216 1217 /** 1218 * @brief Swaps data with another %vector. 1219 * @param __x A %vector of the same element and allocator types. 1220 * 1221 * This exchanges the elements between two vectors in constant time. 1222 * (Three pointers, so it should be quite fast.) 1223 * Note that the global std::swap() function is specialized such that 1224 * std::swap(v1,v2) will feed to this function. 1225 * 1226 * Whether the allocators are swapped depends on the allocator traits. 1227 */ 1228 void 1229 swap(vector& __x) _GLIBCXX_NOEXCEPT 1230 { 1231 #if __cplusplus >= 201103L 1232 __glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value 1233 || _M_get_Tp_allocator() == __x._M_get_Tp_allocator()); 1234 #endif 1235 this->_M_impl._M_swap_data(__x._M_impl); 1236 _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(), 1237 __x._M_get_Tp_allocator()); 1238 } 1239 1240 /** 1241 * Erases all the elements. Note that this function only erases the 1242 * elements, and that if the elements themselves are pointers, the 1243 * pointed-to memory is not touched in any way. Managing the pointer is 1244 * the user's responsibility. 1245 */ 1246 void 1247 clear() _GLIBCXX_NOEXCEPT 1248 { _M_erase_at_end(this->_M_impl._M_start); } 1249 1250 protected: 1251 /** 1252 * Memory expansion handler. Uses the member allocation function to 1253 * obtain @a n bytes of memory, and then copies [first,last) into it. 1254 */ 1255 template<typename _ForwardIterator> 1256 pointer 1257 _M_allocate_and_copy(size_type __n, 1258 _ForwardIterator __first, _ForwardIterator __last) 1259 { 1260 pointer __result = this->_M_allocate(__n); 1261 __try 1262 { 1263 std::__uninitialized_copy_a(__first, __last, __result, 1264 _M_get_Tp_allocator()); 1265 return __result; 1266 } 1267 __catch(...) 1268 { 1269 _M_deallocate(__result, __n); 1270 __throw_exception_again; 1271 } 1272 } 1273 1274 1275 // Internal constructor functions follow. 1276 1277 // Called by the range constructor to implement [23.1.1]/9 1278 1279 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1280 // 438. Ambiguity in the "do the right thing" clause 1281 template<typename _Integer> 1282 void 1283 _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type) 1284 { 1285 this->_M_impl._M_start = _M_allocate(static_cast<size_type>(__n)); 1286 this->_M_impl._M_end_of_storage = 1287 this->_M_impl._M_start + static_cast<size_type>(__n); 1288 _M_fill_initialize(static_cast<size_type>(__n), __value); 1289 } 1290 1291 // Called by the range constructor to implement [23.1.1]/9 1292 template<typename _InputIterator> 1293 void 1294 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 1295 __false_type) 1296 { 1297 typedef typename std::iterator_traits<_InputIterator>:: 1298 iterator_category _IterCategory; 1299 _M_range_initialize(__first, __last, _IterCategory()); 1300 } 1301 1302 // Called by the second initialize_dispatch above 1303 template<typename _InputIterator> 1304 void 1305 _M_range_initialize(_InputIterator __first, _InputIterator __last, 1306 std::input_iterator_tag) 1307 { 1308 __try { 1309 for (; __first != __last; ++__first) 1310 #if __cplusplus >= 201103L 1311 emplace_back(*__first); 1312 #else 1313 push_back(*__first); 1314 #endif 1315 } __catch(...) { 1316 clear(); 1317 __throw_exception_again; 1318 } 1319 } 1320 1321 // Called by the second initialize_dispatch above 1322 template<typename _ForwardIterator> 1323 void 1324 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, 1325 std::forward_iterator_tag) 1326 { 1327 const size_type __n = std::distance(__first, __last); 1328 this->_M_impl._M_start = this->_M_allocate(__n); 1329 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 1330 this->_M_impl._M_finish = 1331 std::__uninitialized_copy_a(__first, __last, 1332 this->_M_impl._M_start, 1333 _M_get_Tp_allocator()); 1334 } 1335 1336 // Called by the first initialize_dispatch above and by the 1337 // vector(n,value,a) constructor. 1338 void 1339 _M_fill_initialize(size_type __n, const value_type& __value) 1340 { 1341 this->_M_impl._M_finish = 1342 std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value, 1343 _M_get_Tp_allocator()); 1344 } 1345 1346 #if __cplusplus >= 201103L 1347 // Called by the vector(n) constructor. 1348 void 1349 _M_default_initialize(size_type __n) 1350 { 1351 this->_M_impl._M_finish = 1352 std::__uninitialized_default_n_a(this->_M_impl._M_start, __n, 1353 _M_get_Tp_allocator()); 1354 } 1355 #endif 1356 1357 // Internal assign functions follow. The *_aux functions do the actual 1358 // assignment work for the range versions. 1359 1360 // Called by the range assign to implement [23.1.1]/9 1361 1362 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1363 // 438. Ambiguity in the "do the right thing" clause 1364 template<typename _Integer> 1365 void 1366 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 1367 { _M_fill_assign(__n, __val); } 1368 1369 // Called by the range assign to implement [23.1.1]/9 1370 template<typename _InputIterator> 1371 void 1372 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 1373 __false_type) 1374 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } 1375 1376 // Called by the second assign_dispatch above 1377 template<typename _InputIterator> 1378 void 1379 _M_assign_aux(_InputIterator __first, _InputIterator __last, 1380 std::input_iterator_tag); 1381 1382 // Called by the second assign_dispatch above 1383 template<typename _ForwardIterator> 1384 void 1385 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 1386 std::forward_iterator_tag); 1387 1388 // Called by assign(n,t), and the range assign when it turns out 1389 // to be the same thing. 1390 void 1391 _M_fill_assign(size_type __n, const value_type& __val); 1392 1393 // Internal insert functions follow. 1394 1395 // Called by the range insert to implement [23.1.1]/9 1396 1397 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1398 // 438. Ambiguity in the "do the right thing" clause 1399 template<typename _Integer> 1400 void 1401 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val, 1402 __true_type) 1403 { _M_fill_insert(__pos, __n, __val); } 1404 1405 // Called by the range insert to implement [23.1.1]/9 1406 template<typename _InputIterator> 1407 void 1408 _M_insert_dispatch(iterator __pos, _InputIterator __first, 1409 _InputIterator __last, __false_type) 1410 { 1411 _M_range_insert(__pos, __first, __last, 1412 std::__iterator_category(__first)); 1413 } 1414 1415 // Called by the second insert_dispatch above 1416 template<typename _InputIterator> 1417 void 1418 _M_range_insert(iterator __pos, _InputIterator __first, 1419 _InputIterator __last, std::input_iterator_tag); 1420 1421 // Called by the second insert_dispatch above 1422 template<typename _ForwardIterator> 1423 void 1424 _M_range_insert(iterator __pos, _ForwardIterator __first, 1425 _ForwardIterator __last, std::forward_iterator_tag); 1426 1427 // Called by insert(p,n,x), and the range insert when it turns out to be 1428 // the same thing. 1429 void 1430 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x); 1431 1432 #if __cplusplus >= 201103L 1433 // Called by resize(n). 1434 void 1435 _M_default_append(size_type __n); 1436 1437 bool 1438 _M_shrink_to_fit(); 1439 #endif 1440 1441 #if __cplusplus < 201103L 1442 // Called by insert(p,x) 1443 void 1444 _M_insert_aux(iterator __position, const value_type& __x); 1445 1446 void 1447 _M_realloc_insert(iterator __position, const value_type& __x); 1448 #else 1449 // A value_type object constructed with _Alloc_traits::construct() 1450 // and destroyed with _Alloc_traits::destroy(). 1451 struct _Temporary_value 1452 { 1453 template<typename... _Args> 1454 explicit 1455 _Temporary_value(vector* __vec, _Args&&... __args) : _M_this(__vec) 1456 { 1457 _Alloc_traits::construct(_M_this->_M_impl, _M_ptr(), 1458 std::forward<_Args>(__args)...); 1459 } 1460 1461 ~_Temporary_value() 1462 { _Alloc_traits::destroy(_M_this->_M_impl, _M_ptr()); } 1463 1464 value_type& 1465 _M_val() { return *reinterpret_cast<_Tp*>(&__buf); } 1466 1467 private: 1468 pointer 1469 _M_ptr() { return pointer_traits<pointer>::pointer_to(_M_val()); } 1470 1471 vector* _M_this; 1472 typename aligned_storage<sizeof(_Tp), alignof(_Tp)>::type __buf; 1473 }; 1474 1475 // Called by insert(p,x) and other functions when insertion needs to 1476 // reallocate or move existing elements. _Arg is either _Tp& or _Tp. 1477 template<typename _Arg> 1478 void 1479 _M_insert_aux(iterator __position, _Arg&& __arg); 1480 1481 template<typename... _Args> 1482 void 1483 _M_realloc_insert(iterator __position, _Args&&... __args); 1484 1485 // Either move-construct at the end, or forward to _M_insert_aux. 1486 iterator 1487 _M_insert_rval(const_iterator __position, value_type&& __v); 1488 1489 // Try to emplace at the end, otherwise forward to _M_insert_aux. 1490 template<typename... _Args> 1491 iterator 1492 _M_emplace_aux(const_iterator __position, _Args&&... __args); 1493 1494 // Emplacing an rvalue of the correct type can use _M_insert_rval. 1495 iterator 1496 _M_emplace_aux(const_iterator __position, value_type&& __v) 1497 { return _M_insert_rval(__position, std::move(__v)); } 1498 #endif 1499 1500 // Called by _M_fill_insert, _M_insert_aux etc. 1501 size_type 1502 _M_check_len(size_type __n, const char* __s) const 1503 { 1504 if (max_size() - size() < __n) 1505 __throw_length_error(__N(__s)); 1506 1507 const size_type __len = size() + std::max(size(), __n); 1508 return (__len < size() || __len > max_size()) ? max_size() : __len; 1509 } 1510 1511 // Internal erase functions follow. 1512 1513 // Called by erase(q1,q2), clear(), resize(), _M_fill_assign, 1514 // _M_assign_aux. 1515 void 1516 _M_erase_at_end(pointer __pos) _GLIBCXX_NOEXCEPT 1517 { 1518 std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator()); 1519 this->_M_impl._M_finish = __pos; 1520 } 1521 1522 iterator 1523 _M_erase(iterator __position); 1524 1525 iterator 1526 _M_erase(iterator __first, iterator __last); 1527 1528 #if __cplusplus >= 201103L 1529 private: 1530 // Constant-time move assignment when source object's memory can be 1531 // moved, either because the source's allocator will move too 1532 // or because the allocators are equal. 1533 void 1534 _M_move_assign(vector&& __x, std::true_type) noexcept 1535 { 1536 vector __tmp(get_allocator()); 1537 this->_M_impl._M_swap_data(__tmp._M_impl); 1538 this->_M_impl._M_swap_data(__x._M_impl); 1539 std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator()); 1540 } 1541 1542 // Do move assignment when it might not be possible to move source 1543 // object's memory, resulting in a linear-time operation. 1544 void 1545 _M_move_assign(vector&& __x, std::false_type) 1546 { 1547 if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator()) 1548 _M_move_assign(std::move(__x), std::true_type()); 1549 else 1550 { 1551 // The rvalue's allocator cannot be moved and is not equal, 1552 // so we need to individually move each element. 1553 this->assign(std::__make_move_if_noexcept_iterator(__x.begin()), 1554 std::__make_move_if_noexcept_iterator(__x.end())); 1555 __x.clear(); 1556 } 1557 } 1558 #endif 1559 1560 template<typename _Up> 1561 _Up* 1562 _M_data_ptr(_Up* __ptr) const _GLIBCXX_NOEXCEPT 1563 { return __ptr; } 1564 1565 #if __cplusplus >= 201103L 1566 template<typename _Ptr> 1567 typename std::pointer_traits<_Ptr>::element_type* 1568 _M_data_ptr(_Ptr __ptr) const 1569 { return empty() ? nullptr : std::__addressof(*__ptr); } 1570 #else 1571 template<typename _Up> 1572 _Up* 1573 _M_data_ptr(_Up* __ptr) _GLIBCXX_NOEXCEPT 1574 { return __ptr; } 1575 1576 template<typename _Ptr> 1577 value_type* 1578 _M_data_ptr(_Ptr __ptr) 1579 { return __ptr.operator->(); } 1580 1581 template<typename _Ptr> 1582 const value_type* 1583 _M_data_ptr(_Ptr __ptr) const 1584 { return __ptr.operator->(); } 1585 #endif 1586 }; 1587 1588 1589 /** 1590 * @brief Vector equality comparison. 1591 * @param __x A %vector. 1592 * @param __y A %vector of the same type as @a __x. 1593 * @return True iff the size and elements of the vectors are equal. 1594 * 1595 * This is an equivalence relation. It is linear in the size of the 1596 * vectors. Vectors are considered equivalent if their sizes are equal, 1597 * and if corresponding elements compare equal. 1598 */ 1599 template<typename _Tp, typename _Alloc> 1600 inline bool 1601 operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 1602 { return (__x.size() == __y.size() 1603 && std::equal(__x.begin(), __x.end(), __y.begin())); } 1604 1605 /** 1606 * @brief Vector ordering relation. 1607 * @param __x A %vector. 1608 * @param __y A %vector of the same type as @a __x. 1609 * @return True iff @a __x is lexicographically less than @a __y. 1610 * 1611 * This is a total ordering relation. It is linear in the size of the 1612 * vectors. The elements must be comparable with @c <. 1613 * 1614 * See std::lexicographical_compare() for how the determination is made. 1615 */ 1616 template<typename _Tp, typename _Alloc> 1617 inline bool 1618 operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 1619 { return std::lexicographical_compare(__x.begin(), __x.end(), 1620 __y.begin(), __y.end()); } 1621 1622 /// Based on operator== 1623 template<typename _Tp, typename _Alloc> 1624 inline bool 1625 operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 1626 { return !(__x == __y); } 1627 1628 /// Based on operator< 1629 template<typename _Tp, typename _Alloc> 1630 inline bool 1631 operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 1632 { return __y < __x; } 1633 1634 /// Based on operator< 1635 template<typename _Tp, typename _Alloc> 1636 inline bool 1637 operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 1638 { return !(__y < __x); } 1639 1640 /// Based on operator< 1641 template<typename _Tp, typename _Alloc> 1642 inline bool 1643 operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 1644 { return !(__x < __y); } 1645 1646 /// See std::vector::swap(). 1647 template<typename _Tp, typename _Alloc> 1648 inline void 1649 swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y) 1650 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y))) 1651 { __x.swap(__y); } 1652 1653 _GLIBCXX_END_NAMESPACE_CONTAINER 1654 } // namespace std 1655 1656 #endif /* _STL_VECTOR_H */ 1657