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