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