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