1 // Vector implementation (out of line) -*- C++ -*- 2 3 // Copyright (C) 2001-2024 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/vector.tcc 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 _VECTOR_TCC 57 #define _VECTOR_TCC 1 58 59 namespace std _GLIBCXX_VISIBILITY(default) 60 { 61 _GLIBCXX_BEGIN_NAMESPACE_VERSION 62 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 63 64 template<typename _Tp, typename _Alloc> 65 _GLIBCXX20_CONSTEXPR 66 void 67 vector<_Tp, _Alloc>:: 68 reserve(size_type __n) 69 { 70 if (__n > this->max_size()) 71 __throw_length_error(__N("vector::reserve")); 72 if (this->capacity() < __n) 73 { 74 const size_type __old_size = size(); 75 pointer __tmp; 76 #if __cplusplus >= 201103L 77 if _GLIBCXX17_CONSTEXPR (_S_use_relocate()) 78 { 79 __tmp = this->_M_allocate(__n); 80 _S_relocate(this->_M_impl._M_start, this->_M_impl._M_finish, 81 __tmp, _M_get_Tp_allocator()); 82 } 83 else 84 #endif 85 { 86 __tmp = _M_allocate_and_copy(__n, 87 _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_start), 88 _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_finish)); 89 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 90 _M_get_Tp_allocator()); 91 } 92 _GLIBCXX_ASAN_ANNOTATE_REINIT; 93 _M_deallocate(this->_M_impl._M_start, 94 this->_M_impl._M_end_of_storage 95 - this->_M_impl._M_start); 96 this->_M_impl._M_start = __tmp; 97 this->_M_impl._M_finish = __tmp + __old_size; 98 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 99 } 100 } 101 102 #if __cplusplus >= 201103L 103 template<typename _Tp, typename _Alloc> 104 template<typename... _Args> 105 #if __cplusplus > 201402L 106 _GLIBCXX20_CONSTEXPR 107 typename vector<_Tp, _Alloc>::reference 108 #else 109 void 110 #endif 111 vector<_Tp, _Alloc>:: 112 emplace_back(_Args&&... __args) 113 { 114 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 115 { 116 _GLIBCXX_ASAN_ANNOTATE_GROW(1); 117 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, 118 std::forward<_Args>(__args)...); 119 ++this->_M_impl._M_finish; 120 _GLIBCXX_ASAN_ANNOTATE_GREW(1); 121 } 122 else 123 _M_realloc_append(std::forward<_Args>(__args)...); 124 #if __cplusplus > 201402L 125 return back(); 126 #endif 127 } 128 #endif 129 130 template<typename _Tp, typename _Alloc> 131 _GLIBCXX20_CONSTEXPR 132 typename vector<_Tp, _Alloc>::iterator 133 vector<_Tp, _Alloc>:: 134 #if __cplusplus >= 201103L 135 insert(const_iterator __position, const value_type& __x) 136 #else 137 insert(iterator __position, const value_type& __x) 138 #endif 139 { 140 const size_type __n = __position - begin(); 141 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 142 { 143 __glibcxx_assert(__position != const_iterator()); 144 if (!(__position != const_iterator())) 145 __builtin_unreachable(); // PR 106434 146 147 if (__position == end()) 148 { 149 _GLIBCXX_ASAN_ANNOTATE_GROW(1); 150 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, 151 __x); 152 ++this->_M_impl._M_finish; 153 _GLIBCXX_ASAN_ANNOTATE_GREW(1); 154 } 155 else 156 { 157 #if __cplusplus >= 201103L 158 const auto __pos = begin() + (__position - cbegin()); 159 // __x could be an existing element of this vector, so make a 160 // copy of it before _M_insert_aux moves elements around. 161 _Temporary_value __x_copy(this, __x); 162 _M_insert_aux(__pos, std::move(__x_copy._M_val())); 163 #else 164 _M_insert_aux(__position, __x); 165 #endif 166 } 167 } 168 else 169 #if __cplusplus >= 201103L 170 _M_realloc_insert(begin() + (__position - cbegin()), __x); 171 #else 172 _M_realloc_insert(__position, __x); 173 #endif 174 175 return iterator(this->_M_impl._M_start + __n); 176 } 177 178 template<typename _Tp, typename _Alloc> 179 _GLIBCXX20_CONSTEXPR 180 typename vector<_Tp, _Alloc>::iterator 181 vector<_Tp, _Alloc>:: 182 _M_erase(iterator __position) 183 { 184 if (__position + 1 != end()) 185 _GLIBCXX_MOVE3(__position + 1, end(), __position); 186 --this->_M_impl._M_finish; 187 _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish); 188 _GLIBCXX_ASAN_ANNOTATE_SHRINK(1); 189 return __position; 190 } 191 192 template<typename _Tp, typename _Alloc> 193 _GLIBCXX20_CONSTEXPR 194 typename vector<_Tp, _Alloc>::iterator 195 vector<_Tp, _Alloc>:: 196 _M_erase(iterator __first, iterator __last) 197 { 198 if (__first != __last) 199 { 200 if (__last != end()) 201 _GLIBCXX_MOVE3(__last, end(), __first); 202 _M_erase_at_end(__first.base() + (end() - __last)); 203 } 204 return __first; 205 } 206 207 template<typename _Tp, typename _Alloc> 208 _GLIBCXX20_CONSTEXPR 209 vector<_Tp, _Alloc>& 210 vector<_Tp, _Alloc>:: 211 operator=(const vector<_Tp, _Alloc>& __x) 212 { 213 if (std::__addressof(__x) != this) 214 { 215 _GLIBCXX_ASAN_ANNOTATE_REINIT; 216 #if __cplusplus >= 201103L 217 if (_Alloc_traits::_S_propagate_on_copy_assign()) 218 { 219 if (!_Alloc_traits::_S_always_equal() 220 && _M_get_Tp_allocator() != __x._M_get_Tp_allocator()) 221 { 222 // replacement allocator cannot free existing storage 223 this->clear(); 224 _M_deallocate(this->_M_impl._M_start, 225 this->_M_impl._M_end_of_storage 226 - this->_M_impl._M_start); 227 this->_M_impl._M_start = nullptr; 228 this->_M_impl._M_finish = nullptr; 229 this->_M_impl._M_end_of_storage = nullptr; 230 } 231 std::__alloc_on_copy(_M_get_Tp_allocator(), 232 __x._M_get_Tp_allocator()); 233 } 234 #endif 235 const size_type __xlen = __x.size(); 236 if (__xlen > capacity()) 237 { 238 pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(), 239 __x.end()); 240 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 241 _M_get_Tp_allocator()); 242 _M_deallocate(this->_M_impl._M_start, 243 this->_M_impl._M_end_of_storage 244 - this->_M_impl._M_start); 245 this->_M_impl._M_start = __tmp; 246 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen; 247 } 248 else if (size() >= __xlen) 249 { 250 std::_Destroy(std::copy(__x.begin(), __x.end(), begin()), 251 end(), _M_get_Tp_allocator()); 252 } 253 else 254 { 255 std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(), 256 this->_M_impl._M_start); 257 std::__uninitialized_copy_a(__x._M_impl._M_start + size(), 258 __x._M_impl._M_finish, 259 this->_M_impl._M_finish, 260 _M_get_Tp_allocator()); 261 } 262 this->_M_impl._M_finish = this->_M_impl._M_start + __xlen; 263 } 264 return *this; 265 } 266 267 template<typename _Tp, typename _Alloc> 268 _GLIBCXX20_CONSTEXPR 269 void 270 vector<_Tp, _Alloc>:: 271 _M_fill_assign(size_t __n, const value_type& __val) 272 { 273 const size_type __sz = size(); 274 if (__n > capacity()) 275 { 276 if (__n <= __sz) 277 __builtin_unreachable(); 278 vector __tmp(__n, __val, _M_get_Tp_allocator()); 279 __tmp._M_impl._M_swap_data(this->_M_impl); 280 } 281 else if (__n > __sz) 282 { 283 std::fill(begin(), end(), __val); 284 const size_type __add = __n - __sz; 285 _GLIBCXX_ASAN_ANNOTATE_GROW(__add); 286 this->_M_impl._M_finish = 287 std::__uninitialized_fill_n_a(this->_M_impl._M_finish, 288 __add, __val, _M_get_Tp_allocator()); 289 _GLIBCXX_ASAN_ANNOTATE_GREW(__add); 290 } 291 else 292 _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val)); 293 } 294 295 template<typename _Tp, typename _Alloc> 296 template<typename _InputIterator> 297 _GLIBCXX20_CONSTEXPR 298 void 299 vector<_Tp, _Alloc>:: 300 _M_assign_aux(_InputIterator __first, _InputIterator __last, 301 std::input_iterator_tag) 302 { 303 pointer __cur(this->_M_impl._M_start); 304 for (; __first != __last && __cur != this->_M_impl._M_finish; 305 ++__cur, (void)++__first) 306 *__cur = *__first; 307 if (__first == __last) 308 _M_erase_at_end(__cur); 309 else 310 _M_range_insert(end(), __first, __last, 311 std::__iterator_category(__first)); 312 } 313 314 template<typename _Tp, typename _Alloc> 315 template<typename _ForwardIterator> 316 _GLIBCXX20_CONSTEXPR 317 void 318 vector<_Tp, _Alloc>:: 319 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 320 std::forward_iterator_tag) 321 { 322 const size_type __sz = size(); 323 const size_type __len = std::distance(__first, __last); 324 325 if (__len > capacity()) 326 { 327 if (__len <= __sz) 328 __builtin_unreachable(); 329 330 _S_check_init_len(__len, _M_get_Tp_allocator()); 331 pointer __tmp(_M_allocate_and_copy(__len, __first, __last)); 332 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 333 _M_get_Tp_allocator()); 334 _GLIBCXX_ASAN_ANNOTATE_REINIT; 335 _M_deallocate(this->_M_impl._M_start, 336 this->_M_impl._M_end_of_storage 337 - this->_M_impl._M_start); 338 this->_M_impl._M_start = __tmp; 339 this->_M_impl._M_finish = this->_M_impl._M_start + __len; 340 this->_M_impl._M_end_of_storage = this->_M_impl._M_finish; 341 } 342 else if (__sz >= __len) 343 _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start)); 344 else 345 { 346 _ForwardIterator __mid = __first; 347 std::advance(__mid, __sz); 348 std::copy(__first, __mid, this->_M_impl._M_start); 349 const size_type __attribute__((__unused__)) __n = __len - __sz; 350 _GLIBCXX_ASAN_ANNOTATE_GROW(__n); 351 this->_M_impl._M_finish = 352 std::__uninitialized_copy_a(__mid, __last, 353 this->_M_impl._M_finish, 354 _M_get_Tp_allocator()); 355 _GLIBCXX_ASAN_ANNOTATE_GREW(__n); 356 } 357 } 358 359 #if __cplusplus >= 201103L 360 template<typename _Tp, typename _Alloc> 361 _GLIBCXX20_CONSTEXPR 362 auto 363 vector<_Tp, _Alloc>:: 364 _M_insert_rval(const_iterator __position, value_type&& __v) -> iterator 365 { 366 const auto __n = __position - cbegin(); 367 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 368 if (__position == cend()) 369 { 370 _GLIBCXX_ASAN_ANNOTATE_GROW(1); 371 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, 372 std::move(__v)); 373 ++this->_M_impl._M_finish; 374 _GLIBCXX_ASAN_ANNOTATE_GREW(1); 375 } 376 else 377 _M_insert_aux(begin() + __n, std::move(__v)); 378 else 379 _M_realloc_insert(begin() + __n, std::move(__v)); 380 381 return iterator(this->_M_impl._M_start + __n); 382 } 383 384 template<typename _Tp, typename _Alloc> 385 template<typename... _Args> 386 _GLIBCXX20_CONSTEXPR 387 auto 388 vector<_Tp, _Alloc>:: 389 _M_emplace_aux(const_iterator __position, _Args&&... __args) 390 -> iterator 391 { 392 const auto __n = __position - cbegin(); 393 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 394 if (__position == cend()) 395 { 396 _GLIBCXX_ASAN_ANNOTATE_GROW(1); 397 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, 398 std::forward<_Args>(__args)...); 399 ++this->_M_impl._M_finish; 400 _GLIBCXX_ASAN_ANNOTATE_GREW(1); 401 } 402 else 403 { 404 // We need to construct a temporary because something in __args... 405 // could alias one of the elements of the container and so we 406 // need to use it before _M_insert_aux moves elements around. 407 _Temporary_value __tmp(this, std::forward<_Args>(__args)...); 408 _M_insert_aux(begin() + __n, std::move(__tmp._M_val())); 409 } 410 else 411 _M_realloc_insert(begin() + __n, std::forward<_Args>(__args)...); 412 413 return iterator(this->_M_impl._M_start + __n); 414 } 415 416 template<typename _Tp, typename _Alloc> 417 template<typename _Arg> 418 _GLIBCXX20_CONSTEXPR 419 void 420 vector<_Tp, _Alloc>:: 421 _M_insert_aux(iterator __position, _Arg&& __arg) 422 #else 423 template<typename _Tp, typename _Alloc> 424 void 425 vector<_Tp, _Alloc>:: 426 _M_insert_aux(iterator __position, const _Tp& __x) 427 #endif 428 { 429 _GLIBCXX_ASAN_ANNOTATE_GROW(1); 430 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, 431 _GLIBCXX_MOVE(*(this->_M_impl._M_finish - 1))); 432 ++this->_M_impl._M_finish; 433 _GLIBCXX_ASAN_ANNOTATE_GREW(1); 434 #if __cplusplus < 201103L 435 _Tp __x_copy = __x; 436 #endif 437 _GLIBCXX_MOVE_BACKWARD3(__position.base(), 438 this->_M_impl._M_finish - 2, 439 this->_M_impl._M_finish - 1); 440 #if __cplusplus < 201103L 441 *__position = __x_copy; 442 #else 443 *__position = std::forward<_Arg>(__arg); 444 #endif 445 } 446 447 #if __cplusplus >= 201103L 448 template<typename _Tp, typename _Alloc> 449 template<typename... _Args> 450 _GLIBCXX20_CONSTEXPR 451 void 452 vector<_Tp, _Alloc>:: 453 _M_realloc_insert(iterator __position, _Args&&... __args) 454 #else 455 template<typename _Tp, typename _Alloc> 456 void 457 vector<_Tp, _Alloc>:: 458 _M_realloc_insert(iterator __position, const _Tp& __x) 459 #endif 460 { 461 const size_type __len = _M_check_len(1u, "vector::_M_realloc_insert"); 462 if (__len <= 0) 463 __builtin_unreachable (); 464 pointer __old_start = this->_M_impl._M_start; 465 pointer __old_finish = this->_M_impl._M_finish; 466 const size_type __elems_before = __position - begin(); 467 pointer __new_start(this->_M_allocate(__len)); 468 pointer __new_finish(__new_start); 469 470 // RAII guard for allocated storage. 471 struct _Guard 472 { 473 pointer _M_storage; // Storage to deallocate 474 size_type _M_len; 475 _Tp_alloc_type& _M_alloc; 476 477 _GLIBCXX20_CONSTEXPR 478 _Guard(pointer __s, size_type __l, _Tp_alloc_type& __a) 479 : _M_storage(__s), _M_len(__l), _M_alloc(__a) 480 { } 481 482 _GLIBCXX20_CONSTEXPR 483 ~_Guard() 484 { 485 if (_M_storage) 486 __gnu_cxx::__alloc_traits<_Tp_alloc_type>:: 487 deallocate(_M_alloc, _M_storage, _M_len); 488 } 489 490 private: 491 _Guard(const _Guard&); 492 }; 493 494 { 495 _Guard __guard(__new_start, __len, _M_impl); 496 497 // The order of the three operations is dictated by the C++11 498 // case, where the moves could alter a new element belonging 499 // to the existing vector. This is an issue only for callers 500 // taking the element by lvalue ref (see last bullet of C++11 501 // [res.on.arguments]). 502 503 // If this throws, the existing elements are unchanged. 504 #if __cplusplus >= 201103L 505 _Alloc_traits::construct(this->_M_impl, 506 std::__to_address(__new_start + __elems_before), 507 std::forward<_Args>(__args)...); 508 #else 509 _Alloc_traits::construct(this->_M_impl, 510 __new_start + __elems_before, 511 __x); 512 #endif 513 514 #if __cplusplus >= 201103L 515 if _GLIBCXX17_CONSTEXPR (_S_use_relocate()) 516 { 517 // Relocation cannot throw. 518 __new_finish = _S_relocate(__old_start, __position.base(), 519 __new_start, _M_get_Tp_allocator()); 520 ++__new_finish; 521 __new_finish = _S_relocate(__position.base(), __old_finish, 522 __new_finish, _M_get_Tp_allocator()); 523 } 524 else 525 #endif 526 { 527 // RAII type to destroy initialized elements. 528 struct _Guard_elts 529 { 530 pointer _M_first, _M_last; // Elements to destroy 531 _Tp_alloc_type& _M_alloc; 532 533 _GLIBCXX20_CONSTEXPR 534 _Guard_elts(pointer __elt, _Tp_alloc_type& __a) 535 : _M_first(__elt), _M_last(__elt + 1), _M_alloc(__a) 536 { } 537 538 _GLIBCXX20_CONSTEXPR 539 ~_Guard_elts() 540 { std::_Destroy(_M_first, _M_last, _M_alloc); } 541 542 private: 543 _Guard_elts(const _Guard_elts&); 544 }; 545 546 // Guard the new element so it will be destroyed if anything throws. 547 _Guard_elts __guard_elts(__new_start + __elems_before, _M_impl); 548 549 __new_finish = std::__uninitialized_move_if_noexcept_a( 550 __old_start, __position.base(), 551 __new_start, _M_get_Tp_allocator()); 552 553 ++__new_finish; 554 // Guard everything before the new element too. 555 __guard_elts._M_first = __new_start; 556 557 __new_finish = std::__uninitialized_move_if_noexcept_a( 558 __position.base(), __old_finish, 559 __new_finish, _M_get_Tp_allocator()); 560 561 // New storage has been fully initialized, destroy the old elements. 562 __guard_elts._M_first = __old_start; 563 __guard_elts._M_last = __old_finish; 564 } 565 __guard._M_storage = __old_start; 566 __guard._M_len = this->_M_impl._M_end_of_storage - __old_start; 567 } 568 // deallocate should be called before assignments to _M_impl, 569 // to avoid call-clobbering 570 571 this->_M_impl._M_start = __new_start; 572 this->_M_impl._M_finish = __new_finish; 573 this->_M_impl._M_end_of_storage = __new_start + __len; 574 } 575 576 #if __cplusplus >= 201103L 577 template<typename _Tp, typename _Alloc> 578 template<typename... _Args> 579 _GLIBCXX20_CONSTEXPR 580 void 581 vector<_Tp, _Alloc>:: 582 _M_realloc_append(_Args&&... __args) 583 #else 584 template<typename _Tp, typename _Alloc> 585 void 586 vector<_Tp, _Alloc>:: 587 _M_realloc_append(const _Tp& __x) 588 #endif 589 { 590 const size_type __len = _M_check_len(1u, "vector::_M_realloc_append"); 591 if (__len <= 0) 592 __builtin_unreachable (); 593 pointer __old_start = this->_M_impl._M_start; 594 pointer __old_finish = this->_M_impl._M_finish; 595 const size_type __elems = end() - begin(); 596 pointer __new_start(this->_M_allocate(__len)); 597 pointer __new_finish(__new_start); 598 599 // RAII guard for allocated storage. 600 struct _Guard 601 { 602 pointer _M_storage; // Storage to deallocate 603 size_type _M_len; 604 _Tp_alloc_type& _M_alloc; 605 606 _GLIBCXX20_CONSTEXPR 607 _Guard(pointer __s, size_type __l, _Tp_alloc_type& __a) 608 : _M_storage(__s), _M_len(__l), _M_alloc(__a) 609 { } 610 611 _GLIBCXX20_CONSTEXPR 612 ~_Guard() 613 { 614 if (_M_storage) 615 __gnu_cxx::__alloc_traits<_Tp_alloc_type>:: 616 deallocate(_M_alloc, _M_storage, _M_len); 617 } 618 619 private: 620 _Guard(const _Guard&); 621 }; 622 623 { 624 _Guard __guard(__new_start, __len, _M_impl); 625 626 // The order of the three operations is dictated by the C++11 627 // case, where the moves could alter a new element belonging 628 // to the existing vector. This is an issue only for callers 629 // taking the element by lvalue ref (see last bullet of C++11 630 // [res.on.arguments]). 631 632 // If this throws, the existing elements are unchanged. 633 #if __cplusplus >= 201103L 634 _Alloc_traits::construct(this->_M_impl, 635 std::__to_address(__new_start + __elems), 636 std::forward<_Args>(__args)...); 637 #else 638 _Alloc_traits::construct(this->_M_impl, 639 __new_start + __elems, 640 __x); 641 #endif 642 643 #if __cplusplus >= 201103L 644 if _GLIBCXX17_CONSTEXPR (_S_use_relocate()) 645 { 646 // Relocation cannot throw. 647 __new_finish = _S_relocate(__old_start, __old_finish, 648 __new_start, _M_get_Tp_allocator()); 649 ++__new_finish; 650 } 651 else 652 #endif 653 { 654 // RAII type to destroy initialized elements. 655 struct _Guard_elts 656 { 657 pointer _M_first, _M_last; // Elements to destroy 658 _Tp_alloc_type& _M_alloc; 659 660 _GLIBCXX20_CONSTEXPR 661 _Guard_elts(pointer __elt, _Tp_alloc_type& __a) 662 : _M_first(__elt), _M_last(__elt + 1), _M_alloc(__a) 663 { } 664 665 _GLIBCXX20_CONSTEXPR 666 ~_Guard_elts() 667 { std::_Destroy(_M_first, _M_last, _M_alloc); } 668 669 private: 670 _Guard_elts(const _Guard_elts&); 671 }; 672 673 // Guard the new element so it will be destroyed if anything throws. 674 _Guard_elts __guard_elts(__new_start + __elems, _M_impl); 675 676 __new_finish = std::__uninitialized_move_if_noexcept_a( 677 __old_start, __old_finish, 678 __new_start, _M_get_Tp_allocator()); 679 680 ++__new_finish; 681 682 // New storage has been fully initialized, destroy the old elements. 683 __guard_elts._M_first = __old_start; 684 __guard_elts._M_last = __old_finish; 685 } 686 __guard._M_storage = __old_start; 687 __guard._M_len = this->_M_impl._M_end_of_storage - __old_start; 688 } 689 // deallocate should be called before assignments to _M_impl, 690 // to avoid call-clobbering 691 692 this->_M_impl._M_start = __new_start; 693 this->_M_impl._M_finish = __new_finish; 694 this->_M_impl._M_end_of_storage = __new_start + __len; 695 } 696 697 template<typename _Tp, typename _Alloc> 698 _GLIBCXX20_CONSTEXPR 699 void 700 vector<_Tp, _Alloc>:: 701 _M_fill_insert(iterator __position, size_type __n, const value_type& __x) 702 { 703 if (__n != 0) 704 { 705 if (size_type(this->_M_impl._M_end_of_storage 706 - this->_M_impl._M_finish) >= __n) 707 { 708 #if __cplusplus < 201103L 709 value_type __x_copy = __x; 710 #else 711 _Temporary_value __tmp(this, __x); 712 value_type& __x_copy = __tmp._M_val(); 713 #endif 714 const size_type __elems_after = end() - __position; 715 pointer __old_finish(this->_M_impl._M_finish); 716 if (__elems_after > __n) 717 { 718 _GLIBCXX_ASAN_ANNOTATE_GROW(__n); 719 std::__uninitialized_move_a(__old_finish - __n, 720 __old_finish, 721 __old_finish, 722 _M_get_Tp_allocator()); 723 this->_M_impl._M_finish += __n; 724 _GLIBCXX_ASAN_ANNOTATE_GREW(__n); 725 _GLIBCXX_MOVE_BACKWARD3(__position.base(), 726 __old_finish - __n, __old_finish); 727 std::fill(__position.base(), __position.base() + __n, 728 __x_copy); 729 } 730 else 731 { 732 _GLIBCXX_ASAN_ANNOTATE_GROW(__n); 733 this->_M_impl._M_finish = 734 std::__uninitialized_fill_n_a(__old_finish, 735 __n - __elems_after, 736 __x_copy, 737 _M_get_Tp_allocator()); 738 _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after); 739 std::__uninitialized_move_a(__position.base(), __old_finish, 740 this->_M_impl._M_finish, 741 _M_get_Tp_allocator()); 742 this->_M_impl._M_finish += __elems_after; 743 _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after); 744 std::fill(__position.base(), __old_finish, __x_copy); 745 } 746 } 747 else 748 { 749 // Make local copies of these members because the compiler thinks 750 // the allocator can alter them if 'this' is globally reachable. 751 pointer __old_start = this->_M_impl._M_start; 752 pointer __old_finish = this->_M_impl._M_finish; 753 const pointer __pos = __position.base(); 754 755 const size_type __len = 756 _M_check_len(__n, "vector::_M_fill_insert"); 757 const size_type __elems_before = __pos - __old_start; 758 pointer __new_start(this->_M_allocate(__len)); 759 pointer __new_finish(__new_start); 760 __try 761 { 762 // See _M_realloc_insert above. 763 std::__uninitialized_fill_n_a(__new_start + __elems_before, 764 __n, __x, 765 _M_get_Tp_allocator()); 766 __new_finish = pointer(); 767 768 __new_finish 769 = std::__uninitialized_move_if_noexcept_a 770 (__old_start, __pos, __new_start, _M_get_Tp_allocator()); 771 772 __new_finish += __n; 773 774 __new_finish 775 = std::__uninitialized_move_if_noexcept_a 776 (__pos, __old_finish, __new_finish, _M_get_Tp_allocator()); 777 } 778 __catch(...) 779 { 780 if (!__new_finish) 781 std::_Destroy(__new_start + __elems_before, 782 __new_start + __elems_before + __n, 783 _M_get_Tp_allocator()); 784 else 785 std::_Destroy(__new_start, __new_finish, 786 _M_get_Tp_allocator()); 787 _M_deallocate(__new_start, __len); 788 __throw_exception_again; 789 } 790 std::_Destroy(__old_start, __old_finish, _M_get_Tp_allocator()); 791 _GLIBCXX_ASAN_ANNOTATE_REINIT; 792 _M_deallocate(__old_start, 793 this->_M_impl._M_end_of_storage - __old_start); 794 this->_M_impl._M_start = __new_start; 795 this->_M_impl._M_finish = __new_finish; 796 this->_M_impl._M_end_of_storage = __new_start + __len; 797 } 798 } 799 } 800 801 #if __cplusplus >= 201103L 802 template<typename _Tp, typename _Alloc> 803 _GLIBCXX20_CONSTEXPR 804 void 805 vector<_Tp, _Alloc>:: 806 _M_default_append(size_type __n) 807 { 808 if (__n != 0) 809 { 810 const size_type __size = size(); 811 size_type __navail = size_type(this->_M_impl._M_end_of_storage 812 - this->_M_impl._M_finish); 813 814 if (__size > max_size() || __navail > max_size() - __size) 815 __builtin_unreachable(); 816 817 if (__navail >= __n) 818 { 819 if (!this->_M_impl._M_finish) 820 __builtin_unreachable(); 821 822 _GLIBCXX_ASAN_ANNOTATE_GROW(__n); 823 this->_M_impl._M_finish = 824 std::__uninitialized_default_n_a(this->_M_impl._M_finish, 825 __n, _M_get_Tp_allocator()); 826 _GLIBCXX_ASAN_ANNOTATE_GREW(__n); 827 } 828 else 829 { 830 // Make local copies of these members because the compiler thinks 831 // the allocator can alter them if 'this' is globally reachable. 832 pointer __old_start = this->_M_impl._M_start; 833 pointer __old_finish = this->_M_impl._M_finish; 834 835 const size_type __len = 836 _M_check_len(__n, "vector::_M_default_append"); 837 pointer __new_start(this->_M_allocate(__len)); 838 839 // RAII guard for allocated storage. 840 struct _Guard 841 { 842 pointer _M_storage; // Storage to deallocate 843 size_type _M_len; 844 _Tp_alloc_type& _M_alloc; 845 846 _GLIBCXX20_CONSTEXPR 847 _Guard(pointer __s, size_type __l, _Tp_alloc_type& __a) 848 : _M_storage(__s), _M_len(__l), _M_alloc(__a) 849 { } 850 851 _GLIBCXX20_CONSTEXPR 852 ~_Guard() 853 { 854 if (_M_storage) 855 __gnu_cxx::__alloc_traits<_Tp_alloc_type>:: 856 deallocate(_M_alloc, _M_storage, _M_len); 857 } 858 859 private: 860 _Guard(const _Guard&); 861 }; 862 863 { 864 _Guard __guard(__new_start, __len, _M_impl); 865 866 std::__uninitialized_default_n_a(__new_start + __size, __n, 867 _M_get_Tp_allocator()); 868 869 if _GLIBCXX17_CONSTEXPR (_S_use_relocate()) 870 { 871 _S_relocate(__old_start, __old_finish, 872 __new_start, _M_get_Tp_allocator()); 873 } 874 else 875 { 876 // RAII type to destroy initialized elements. 877 struct _Guard_elts 878 { 879 pointer _M_first, _M_last; // Elements to destroy 880 _Tp_alloc_type& _M_alloc; 881 882 _GLIBCXX20_CONSTEXPR 883 _Guard_elts(pointer __first, size_type __n, 884 _Tp_alloc_type& __a) 885 : _M_first(__first), _M_last(__first + __n), _M_alloc(__a) 886 { } 887 888 _GLIBCXX20_CONSTEXPR 889 ~_Guard_elts() 890 { std::_Destroy(_M_first, _M_last, _M_alloc); } 891 892 private: 893 _Guard_elts(const _Guard_elts&); 894 }; 895 _Guard_elts __guard_elts(__new_start + __size, __n, _M_impl); 896 897 std::__uninitialized_move_if_noexcept_a( 898 __old_start, __old_finish, __new_start, 899 _M_get_Tp_allocator()); 900 901 __guard_elts._M_first = __old_start; 902 __guard_elts._M_last = __old_finish; 903 } 904 _GLIBCXX_ASAN_ANNOTATE_REINIT; 905 __guard._M_storage = __old_start; 906 __guard._M_len = this->_M_impl._M_end_of_storage - __old_start; 907 } 908 // deallocate should be called before assignments to _M_impl, 909 // to avoid call-clobbering 910 911 this->_M_impl._M_start = __new_start; 912 this->_M_impl._M_finish = __new_start + __size + __n; 913 this->_M_impl._M_end_of_storage = __new_start + __len; 914 } 915 } 916 } 917 918 template<typename _Tp, typename _Alloc> 919 _GLIBCXX20_CONSTEXPR 920 bool 921 vector<_Tp, _Alloc>:: 922 _M_shrink_to_fit() 923 { 924 if (capacity() == size()) 925 return false; 926 _GLIBCXX_ASAN_ANNOTATE_REINIT; 927 return std::__shrink_to_fit_aux<vector>::_S_do_it(*this); 928 } 929 #endif 930 931 template<typename _Tp, typename _Alloc> 932 template<typename _InputIterator> 933 _GLIBCXX20_CONSTEXPR 934 void 935 vector<_Tp, _Alloc>:: 936 _M_range_insert(iterator __pos, _InputIterator __first, 937 _InputIterator __last, std::input_iterator_tag) 938 { 939 if (__pos == end()) 940 { 941 for (; __first != __last; ++__first) 942 insert(end(), *__first); 943 } 944 else if (__first != __last) 945 { 946 vector __tmp(__first, __last, _M_get_Tp_allocator()); 947 insert(__pos, 948 _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.begin()), 949 _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.end())); 950 } 951 } 952 953 template<typename _Tp, typename _Alloc> 954 template<typename _ForwardIterator> 955 _GLIBCXX20_CONSTEXPR 956 void 957 vector<_Tp, _Alloc>:: 958 _M_range_insert(iterator __position, _ForwardIterator __first, 959 _ForwardIterator __last, std::forward_iterator_tag) 960 { 961 if (__first != __last) 962 { 963 const size_type __n = std::distance(__first, __last); 964 if (size_type(this->_M_impl._M_end_of_storage 965 - this->_M_impl._M_finish) >= __n) 966 { 967 const size_type __elems_after = end() - __position; 968 pointer __old_finish(this->_M_impl._M_finish); 969 if (__elems_after > __n) 970 { 971 _GLIBCXX_ASAN_ANNOTATE_GROW(__n); 972 std::__uninitialized_move_a(this->_M_impl._M_finish - __n, 973 this->_M_impl._M_finish, 974 this->_M_impl._M_finish, 975 _M_get_Tp_allocator()); 976 this->_M_impl._M_finish += __n; 977 _GLIBCXX_ASAN_ANNOTATE_GREW(__n); 978 _GLIBCXX_MOVE_BACKWARD3(__position.base(), 979 __old_finish - __n, __old_finish); 980 std::copy(__first, __last, __position); 981 } 982 else 983 { 984 _ForwardIterator __mid = __first; 985 std::advance(__mid, __elems_after); 986 _GLIBCXX_ASAN_ANNOTATE_GROW(__n); 987 std::__uninitialized_copy_a(__mid, __last, 988 this->_M_impl._M_finish, 989 _M_get_Tp_allocator()); 990 this->_M_impl._M_finish += __n - __elems_after; 991 _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after); 992 std::__uninitialized_move_a(__position.base(), 993 __old_finish, 994 this->_M_impl._M_finish, 995 _M_get_Tp_allocator()); 996 this->_M_impl._M_finish += __elems_after; 997 _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after); 998 std::copy(__first, __mid, __position); 999 } 1000 } 1001 else 1002 { 1003 // Make local copies of these members because the compiler 1004 // thinks the allocator can alter them if 'this' is globally 1005 // reachable. 1006 pointer __old_start = this->_M_impl._M_start; 1007 pointer __old_finish = this->_M_impl._M_finish; 1008 if ((__old_finish - __old_start) < 0) 1009 __builtin_unreachable(); 1010 1011 const size_type __len = 1012 _M_check_len(__n, "vector::_M_range_insert"); 1013 #if __cplusplus < 201103L 1014 if (__len < (__n + (__old_finish - __old_start))) 1015 __builtin_unreachable(); 1016 #endif 1017 1018 pointer __new_start(this->_M_allocate(__len)); 1019 pointer __new_finish(__new_start); 1020 __try 1021 { 1022 __new_finish 1023 = std::__uninitialized_move_if_noexcept_a 1024 (__old_start, __position.base(), 1025 __new_start, _M_get_Tp_allocator()); 1026 __new_finish 1027 = std::__uninitialized_copy_a(__first, __last, 1028 __new_finish, 1029 _M_get_Tp_allocator()); 1030 __new_finish 1031 = std::__uninitialized_move_if_noexcept_a 1032 (__position.base(), __old_finish, 1033 __new_finish, _M_get_Tp_allocator()); 1034 } 1035 __catch(...) 1036 { 1037 std::_Destroy(__new_start, __new_finish, 1038 _M_get_Tp_allocator()); 1039 _M_deallocate(__new_start, __len); 1040 __throw_exception_again; 1041 } 1042 std::_Destroy(__old_start, __old_finish, 1043 _M_get_Tp_allocator()); 1044 _GLIBCXX_ASAN_ANNOTATE_REINIT; 1045 _M_deallocate(__old_start, 1046 this->_M_impl._M_end_of_storage - __old_start); 1047 this->_M_impl._M_start = __new_start; 1048 this->_M_impl._M_finish = __new_finish; 1049 this->_M_impl._M_end_of_storage = __new_start + __len; 1050 } 1051 } 1052 } 1053 1054 1055 // vector<bool> 1056 template<typename _Alloc> 1057 _GLIBCXX20_CONSTEXPR 1058 void 1059 vector<bool, _Alloc>:: 1060 _M_reallocate(size_type __n) 1061 { 1062 const iterator __begin = begin(), __end = end(); 1063 if (size_type(__end - __begin) > __n) 1064 __builtin_unreachable(); 1065 _Bit_pointer __q = this->_M_allocate(__n); 1066 iterator __start(std::__addressof(*__q), 0); 1067 iterator __finish(_M_copy_aligned(__begin, __end, __start)); 1068 this->_M_deallocate(); 1069 this->_M_impl._M_start = __start; 1070 this->_M_impl._M_finish = __finish; 1071 this->_M_impl._M_end_of_storage = __q + _S_nword(__n); 1072 } 1073 1074 template<typename _Alloc> 1075 _GLIBCXX20_CONSTEXPR 1076 void 1077 vector<bool, _Alloc>:: 1078 _M_fill_insert(iterator __position, size_type __n, bool __x) 1079 { 1080 if (__n == 0) 1081 return; 1082 if (capacity() - size() >= __n) 1083 { 1084 std::copy_backward(__position, end(), 1085 this->_M_impl._M_finish + difference_type(__n)); 1086 std::fill(__position, __position + difference_type(__n), __x); 1087 this->_M_impl._M_finish += difference_type(__n); 1088 } 1089 else 1090 { 1091 const size_type __len = 1092 _M_check_len(__n, "vector<bool>::_M_fill_insert"); 1093 iterator __begin = begin(), __end = end(); 1094 _Bit_pointer __q = this->_M_allocate(__len); 1095 iterator __start(std::__addressof(*__q), 0); 1096 iterator __i = _M_copy_aligned(__begin, __position, __start); 1097 std::fill(__i, __i + difference_type(__n), __x); 1098 iterator __finish = std::copy(__position, __end, 1099 __i + difference_type(__n)); 1100 this->_M_deallocate(); 1101 this->_M_impl._M_end_of_storage = __q + _S_nword(__len); 1102 this->_M_impl._M_start = __start; 1103 this->_M_impl._M_finish = __finish; 1104 } 1105 } 1106 1107 template<typename _Alloc> 1108 template<typename _ForwardIterator> 1109 _GLIBCXX20_CONSTEXPR 1110 void 1111 vector<bool, _Alloc>:: 1112 _M_insert_range(iterator __position, _ForwardIterator __first, 1113 _ForwardIterator __last, std::forward_iterator_tag) 1114 { 1115 if (__first != __last) 1116 { 1117 size_type __n = std::distance(__first, __last); 1118 if (capacity() - size() >= __n) 1119 { 1120 std::copy_backward(__position, end(), 1121 this->_M_impl._M_finish 1122 + difference_type(__n)); 1123 std::copy(__first, __last, __position); 1124 this->_M_impl._M_finish += difference_type(__n); 1125 } 1126 else 1127 { 1128 const size_type __len = 1129 _M_check_len(__n, "vector<bool>::_M_insert_range"); 1130 const iterator __begin = begin(), __end = end(); 1131 _Bit_pointer __q = this->_M_allocate(__len); 1132 iterator __start(std::__addressof(*__q), 0); 1133 iterator __i = _M_copy_aligned(__begin, __position, __start); 1134 __i = std::copy(__first, __last, __i); 1135 iterator __finish = std::copy(__position, __end, __i); 1136 this->_M_deallocate(); 1137 this->_M_impl._M_end_of_storage = __q + _S_nword(__len); 1138 this->_M_impl._M_start = __start; 1139 this->_M_impl._M_finish = __finish; 1140 } 1141 } 1142 } 1143 1144 template<typename _Alloc> 1145 _GLIBCXX20_CONSTEXPR 1146 void 1147 vector<bool, _Alloc>:: 1148 _M_insert_aux(iterator __position, bool __x) 1149 { 1150 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr()) 1151 { 1152 std::copy_backward(__position, this->_M_impl._M_finish, 1153 this->_M_impl._M_finish + 1); 1154 *__position = __x; 1155 ++this->_M_impl._M_finish; 1156 } 1157 else 1158 { 1159 const size_type __len = 1160 _M_check_len(size_type(1), "vector<bool>::_M_insert_aux"); 1161 _Bit_pointer __q = this->_M_allocate(__len); 1162 iterator __start(std::__addressof(*__q), 0); 1163 iterator __i = _M_copy_aligned(begin(), __position, __start); 1164 *__i++ = __x; 1165 iterator __finish = std::copy(__position, end(), __i); 1166 this->_M_deallocate(); 1167 this->_M_impl._M_end_of_storage = __q + _S_nword(__len); 1168 this->_M_impl._M_start = __start; 1169 this->_M_impl._M_finish = __finish; 1170 } 1171 } 1172 1173 template<typename _Alloc> 1174 _GLIBCXX20_CONSTEXPR 1175 typename vector<bool, _Alloc>::iterator 1176 vector<bool, _Alloc>:: 1177 _M_erase(iterator __position) 1178 { 1179 if (__position + 1 != end()) 1180 std::copy(__position + 1, end(), __position); 1181 --this->_M_impl._M_finish; 1182 return __position; 1183 } 1184 1185 template<typename _Alloc> 1186 _GLIBCXX20_CONSTEXPR 1187 typename vector<bool, _Alloc>::iterator 1188 vector<bool, _Alloc>:: 1189 _M_erase(iterator __first, iterator __last) 1190 { 1191 if (__first != __last) 1192 _M_erase_at_end(std::copy(__last, end(), __first)); 1193 return __first; 1194 } 1195 1196 #if __cplusplus >= 201103L 1197 template<typename _Alloc> 1198 _GLIBCXX20_CONSTEXPR 1199 bool 1200 vector<bool, _Alloc>:: 1201 _M_shrink_to_fit() 1202 { 1203 if (capacity() - size() < int(_S_word_bit)) 1204 return false; 1205 __try 1206 { 1207 if (size_type __n = size()) 1208 _M_reallocate(__n); 1209 else 1210 { 1211 this->_M_deallocate(); 1212 this->_M_impl._M_reset(); 1213 } 1214 return true; 1215 } 1216 __catch(...) 1217 { return false; } 1218 } 1219 #endif 1220 1221 _GLIBCXX_END_NAMESPACE_CONTAINER 1222 _GLIBCXX_END_NAMESPACE_VERSION 1223 } // namespace std 1224 1225 #if __cplusplus >= 201103L 1226 1227 namespace std _GLIBCXX_VISIBILITY(default) 1228 { 1229 _GLIBCXX_BEGIN_NAMESPACE_VERSION 1230 1231 template<typename _Alloc> 1232 size_t 1233 hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>:: 1234 operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const noexcept 1235 { 1236 size_t __hash = 0; 1237 const size_t __words = __b.size() / _S_word_bit; 1238 if (__words) 1239 { 1240 const size_t __clength = __words * sizeof(_Bit_type); 1241 __hash = std::_Hash_impl::hash(__b._M_impl._M_start._M_p, __clength); 1242 } 1243 1244 const size_t __extrabits = __b.size() % _S_word_bit; 1245 if (__extrabits) 1246 { 1247 _Bit_type __hiword = *__b._M_impl._M_finish._M_p; 1248 __hiword &= ~((~static_cast<_Bit_type>(0)) << __extrabits); 1249 1250 const size_t __clength 1251 = (__extrabits + __CHAR_BIT__ - 1) / __CHAR_BIT__; 1252 if (__words) 1253 __hash = std::_Hash_impl::hash(&__hiword, __clength, __hash); 1254 else 1255 __hash = std::_Hash_impl::hash(&__hiword, __clength); 1256 } 1257 1258 return __hash; 1259 } 1260 1261 _GLIBCXX_END_NAMESPACE_VERSION 1262 } // namespace std 1263 1264 #endif // C++11 1265 1266 #undef _GLIBCXX_ASAN_ANNOTATE_REINIT 1267 #undef _GLIBCXX_ASAN_ANNOTATE_GROW 1268 #undef _GLIBCXX_ASAN_ANNOTATE_GREW 1269 #undef _GLIBCXX_ASAN_ANNOTATE_SHRINK 1270 1271 #endif /* _VECTOR_TCC */ 1272
Indexes created Sat Feb 28 05:31:39 UTC 2026