1// Vector implementation (out of line) -*- C++ -*- 2 3// Copyright (C) 2001-2020 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 59namespace std _GLIBCXX_VISIBILITY(default) 60{ 61_GLIBCXX_BEGIN_NAMESPACE_VERSION 62_GLIBCXX_BEGIN_NAMESPACE_CONTAINER 63 64 template<typename _Tp, typename _Alloc> 65 void 66 vector<_Tp, _Alloc>:: 67 reserve(size_type __n) 68 { 69 if (__n > this->max_size()) 70 __throw_length_error(__N("vector::reserve")); 71 if (this->capacity() < __n) 72 { 73 const size_type __old_size = size(); 74 pointer __tmp; 75#if __cplusplus >= 201103L 76 if _GLIBCXX17_CONSTEXPR (_S_use_relocate()) 77 { 78 __tmp = this->_M_allocate(__n); 79 _S_relocate(this->_M_impl._M_start, this->_M_impl._M_finish, 80 __tmp, _M_get_Tp_allocator()); 81 } 82 else 83#endif 84 { 85 __tmp = _M_allocate_and_copy(__n, 86 _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_start), 87 _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_finish)); 88 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 89 _M_get_Tp_allocator()); 90 } 91 _GLIBCXX_ASAN_ANNOTATE_REINIT; 92 _M_deallocate(this->_M_impl._M_start, 93 this->_M_impl._M_end_of_storage 94 - this->_M_impl._M_start); 95 this->_M_impl._M_start = __tmp; 96 this->_M_impl._M_finish = __tmp + __old_size; 97 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 98 } 99 } 100 101#if __cplusplus >= 201103L 102 template<typename _Tp, typename _Alloc> 103 template<typename... _Args> 104#if __cplusplus > 201402L 105 typename vector<_Tp, _Alloc>::reference 106#else 107 void 108#endif 109 vector<_Tp, _Alloc>:: 110 emplace_back(_Args&&... __args) 111 { 112 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 113 { 114 _GLIBCXX_ASAN_ANNOTATE_GROW(1); 115 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, 116 std::forward<_Args>(__args)...); 117 ++this->_M_impl._M_finish; 118 _GLIBCXX_ASAN_ANNOTATE_GREW(1); 119 } 120 else 121 _M_realloc_insert(end(), std::forward<_Args>(__args)...); 122#if __cplusplus > 201402L 123 return back(); 124#endif 125 } 126#endif 127 128 template<typename _Tp, typename _Alloc> 129 typename vector<_Tp, _Alloc>::iterator 130 vector<_Tp, _Alloc>:: 131#if __cplusplus >= 201103L 132 insert(const_iterator __position, const value_type& __x) 133#else 134 insert(iterator __position, const value_type& __x) 135#endif 136 { 137 const size_type __n = __position - begin(); 138 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 139 if (__position == end()) 140 { 141 _GLIBCXX_ASAN_ANNOTATE_GROW(1); 142 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, 143 __x); 144 ++this->_M_impl._M_finish; 145 _GLIBCXX_ASAN_ANNOTATE_GREW(1); 146 } 147 else 148 { 149#if __cplusplus >= 201103L 150 const auto __pos = begin() + (__position - cbegin()); 151 // __x could be an existing element of this vector, so make a 152 // copy of it before _M_insert_aux moves elements around. 153 _Temporary_value __x_copy(this, __x); 154 _M_insert_aux(__pos, std::move(__x_copy._M_val())); 155#else 156 _M_insert_aux(__position, __x); 157#endif 158 } 159 else 160#if __cplusplus >= 201103L 161 _M_realloc_insert(begin() + (__position - cbegin()), __x); 162#else 163 _M_realloc_insert(__position, __x); 164#endif 165 166 return iterator(this->_M_impl._M_start + __n); 167 } 168 169 template<typename _Tp, typename _Alloc> 170 typename vector<_Tp, _Alloc>::iterator 171 vector<_Tp, _Alloc>:: 172 _M_erase(iterator __position) 173 { 174 if (__position + 1 != end()) 175 _GLIBCXX_MOVE3(__position + 1, end(), __position); 176 --this->_M_impl._M_finish; 177 _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish); 178 _GLIBCXX_ASAN_ANNOTATE_SHRINK(1); 179 return __position; 180 } 181 182 template<typename _Tp, typename _Alloc> 183 typename vector<_Tp, _Alloc>::iterator 184 vector<_Tp, _Alloc>:: 185 _M_erase(iterator __first, iterator __last) 186 { 187 if (__first != __last) 188 { 189 if (__last != end()) 190 _GLIBCXX_MOVE3(__last, end(), __first); 191 _M_erase_at_end(__first.base() + (end() - __last)); 192 } 193 return __first; 194 } 195 196 template<typename _Tp, typename _Alloc> 197 vector<_Tp, _Alloc>& 198 vector<_Tp, _Alloc>:: 199 operator=(const vector<_Tp, _Alloc>& __x) 200 { 201 if (&__x != this) 202 { 203 _GLIBCXX_ASAN_ANNOTATE_REINIT; 204#if __cplusplus >= 201103L 205 if (_Alloc_traits::_S_propagate_on_copy_assign()) 206 { 207 if (!_Alloc_traits::_S_always_equal() 208 && _M_get_Tp_allocator() != __x._M_get_Tp_allocator()) 209 { 210 // replacement allocator cannot free existing storage 211 this->clear(); 212 _M_deallocate(this->_M_impl._M_start, 213 this->_M_impl._M_end_of_storage 214 - this->_M_impl._M_start); 215 this->_M_impl._M_start = nullptr; 216 this->_M_impl._M_finish = nullptr; 217 this->_M_impl._M_end_of_storage = nullptr; 218 } 219 std::__alloc_on_copy(_M_get_Tp_allocator(), 220 __x._M_get_Tp_allocator()); 221 } 222#endif 223 const size_type __xlen = __x.size(); 224 if (__xlen > capacity()) 225 { 226 pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(), 227 __x.end()); 228 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 229 _M_get_Tp_allocator()); 230 _M_deallocate(this->_M_impl._M_start, 231 this->_M_impl._M_end_of_storage 232 - this->_M_impl._M_start); 233 this->_M_impl._M_start = __tmp; 234 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen; 235 } 236 else if (size() >= __xlen) 237 { 238 std::_Destroy(std::copy(__x.begin(), __x.end(), begin()), 239 end(), _M_get_Tp_allocator()); 240 } 241 else 242 { 243 std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(), 244 this->_M_impl._M_start); 245 std::__uninitialized_copy_a(__x._M_impl._M_start + size(), 246 __x._M_impl._M_finish, 247 this->_M_impl._M_finish, 248 _M_get_Tp_allocator()); 249 } 250 this->_M_impl._M_finish = this->_M_impl._M_start + __xlen; 251 } 252 return *this; 253 } 254 255 template<typename _Tp, typename _Alloc> 256 void 257 vector<_Tp, _Alloc>:: 258 _M_fill_assign(size_t __n, const value_type& __val) 259 { 260 if (__n > capacity()) 261 { 262 vector __tmp(__n, __val, _M_get_Tp_allocator()); 263 __tmp._M_impl._M_swap_data(this->_M_impl); 264 } 265 else if (__n > size()) 266 { 267 std::fill(begin(), end(), __val); 268 const size_type __add = __n - size(); 269 _GLIBCXX_ASAN_ANNOTATE_GROW(__add); 270 this->_M_impl._M_finish = 271 std::__uninitialized_fill_n_a(this->_M_impl._M_finish, 272 __add, __val, _M_get_Tp_allocator()); 273 _GLIBCXX_ASAN_ANNOTATE_GREW(__add); 274 } 275 else 276 _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val)); 277 } 278 279 template<typename _Tp, typename _Alloc> 280 template<typename _InputIterator> 281 void 282 vector<_Tp, _Alloc>:: 283 _M_assign_aux(_InputIterator __first, _InputIterator __last, 284 std::input_iterator_tag) 285 { 286 pointer __cur(this->_M_impl._M_start); 287 for (; __first != __last && __cur != this->_M_impl._M_finish; 288 ++__cur, (void)++__first) 289 *__cur = *__first; 290 if (__first == __last) 291 _M_erase_at_end(__cur); 292 else 293 _M_range_insert(end(), __first, __last, 294 std::__iterator_category(__first)); 295 } 296 297 template<typename _Tp, typename _Alloc> 298 template<typename _ForwardIterator> 299 void 300 vector<_Tp, _Alloc>:: 301 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 302 std::forward_iterator_tag) 303 { 304 const size_type __len = std::distance(__first, __last); 305 306 if (__len > capacity()) 307 { 308 _S_check_init_len(__len, _M_get_Tp_allocator()); 309 pointer __tmp(_M_allocate_and_copy(__len, __first, __last)); 310 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 311 _M_get_Tp_allocator()); 312 _GLIBCXX_ASAN_ANNOTATE_REINIT; 313 _M_deallocate(this->_M_impl._M_start, 314 this->_M_impl._M_end_of_storage 315 - this->_M_impl._M_start); 316 this->_M_impl._M_start = __tmp; 317 this->_M_impl._M_finish = this->_M_impl._M_start + __len; 318 this->_M_impl._M_end_of_storage = this->_M_impl._M_finish; 319 } 320 else if (size() >= __len) 321 _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start)); 322 else 323 { 324 _ForwardIterator __mid = __first; 325 std::advance(__mid, size()); 326 std::copy(__first, __mid, this->_M_impl._M_start); 327 const size_type __attribute__((__unused__)) __n = __len - size(); 328 _GLIBCXX_ASAN_ANNOTATE_GROW(__n); 329 this->_M_impl._M_finish = 330 std::__uninitialized_copy_a(__mid, __last, 331 this->_M_impl._M_finish, 332 _M_get_Tp_allocator()); 333 _GLIBCXX_ASAN_ANNOTATE_GREW(__n); 334 } 335 } 336 337#if __cplusplus >= 201103L 338 template<typename _Tp, typename _Alloc> 339 auto 340 vector<_Tp, _Alloc>:: 341 _M_insert_rval(const_iterator __position, value_type&& __v) -> iterator 342 { 343 const auto __n = __position - cbegin(); 344 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 345 if (__position == cend()) 346 { 347 _GLIBCXX_ASAN_ANNOTATE_GROW(1); 348 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, 349 std::move(__v)); 350 ++this->_M_impl._M_finish; 351 _GLIBCXX_ASAN_ANNOTATE_GREW(1); 352 } 353 else 354 _M_insert_aux(begin() + __n, std::move(__v)); 355 else 356 _M_realloc_insert(begin() + __n, std::move(__v)); 357 358 return iterator(this->_M_impl._M_start + __n); 359 } 360 361 template<typename _Tp, typename _Alloc> 362 template<typename... _Args> 363 auto 364 vector<_Tp, _Alloc>:: 365 _M_emplace_aux(const_iterator __position, _Args&&... __args) 366 -> iterator 367 { 368 const auto __n = __position - cbegin(); 369 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 370 if (__position == cend()) 371 { 372 _GLIBCXX_ASAN_ANNOTATE_GROW(1); 373 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, 374 std::forward<_Args>(__args)...); 375 ++this->_M_impl._M_finish; 376 _GLIBCXX_ASAN_ANNOTATE_GREW(1); 377 } 378 else 379 { 380 // We need to construct a temporary because something in __args... 381 // could alias one of the elements of the container and so we 382 // need to use it before _M_insert_aux moves elements around. 383 _Temporary_value __tmp(this, std::forward<_Args>(__args)...); 384 _M_insert_aux(begin() + __n, std::move(__tmp._M_val())); 385 } 386 else 387 _M_realloc_insert(begin() + __n, std::forward<_Args>(__args)...); 388 389 return iterator(this->_M_impl._M_start + __n); 390 } 391 392 template<typename _Tp, typename _Alloc> 393 template<typename _Arg> 394 void 395 vector<_Tp, _Alloc>:: 396 _M_insert_aux(iterator __position, _Arg&& __arg) 397#else 398 template<typename _Tp, typename _Alloc> 399 void 400 vector<_Tp, _Alloc>:: 401 _M_insert_aux(iterator __position, const _Tp& __x) 402#endif 403 { 404 _GLIBCXX_ASAN_ANNOTATE_GROW(1); 405 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, 406 _GLIBCXX_MOVE(*(this->_M_impl._M_finish - 1))); 407 ++this->_M_impl._M_finish; 408 _GLIBCXX_ASAN_ANNOTATE_GREW(1); 409#if __cplusplus < 201103L 410 _Tp __x_copy = __x; 411#endif 412 _GLIBCXX_MOVE_BACKWARD3(__position.base(), 413 this->_M_impl._M_finish - 2, 414 this->_M_impl._M_finish - 1); 415#if __cplusplus < 201103L 416 *__position = __x_copy; 417#else 418 *__position = std::forward<_Arg>(__arg); 419#endif 420 } 421 422#if __cplusplus >= 201103L 423 template<typename _Tp, typename _Alloc> 424 template<typename... _Args> 425 void 426 vector<_Tp, _Alloc>:: 427 _M_realloc_insert(iterator __position, _Args&&... __args) 428#else 429 template<typename _Tp, typename _Alloc> 430 void 431 vector<_Tp, _Alloc>:: 432 _M_realloc_insert(iterator __position, const _Tp& __x) 433#endif 434 { 435 const size_type __len = 436 _M_check_len(size_type(1), "vector::_M_realloc_insert"); 437 pointer __old_start = this->_M_impl._M_start; 438 pointer __old_finish = this->_M_impl._M_finish; 439 const size_type __elems_before = __position - begin(); 440 pointer __new_start(this->_M_allocate(__len)); 441 pointer __new_finish(__new_start); 442 __try 443 { 444 // The order of the three operations is dictated by the C++11 445 // case, where the moves could alter a new element belonging 446 // to the existing vector. This is an issue only for callers 447 // taking the element by lvalue ref (see last bullet of C++11 448 // [res.on.arguments]). 449 _Alloc_traits::construct(this->_M_impl, 450 __new_start + __elems_before, 451#if __cplusplus >= 201103L 452 std::forward<_Args>(__args)...); 453#else 454 __x); 455#endif 456 __new_finish = pointer(); 457 458#if __cplusplus >= 201103L 459 if _GLIBCXX17_CONSTEXPR (_S_use_relocate()) 460 { 461 __new_finish = _S_relocate(__old_start, __position.base(), 462 __new_start, _M_get_Tp_allocator()); 463 464 ++__new_finish; 465 466 __new_finish = _S_relocate(__position.base(), __old_finish, 467 __new_finish, _M_get_Tp_allocator()); 468 } 469 else 470#endif 471 { 472 __new_finish 473 = std::__uninitialized_move_if_noexcept_a 474 (__old_start, __position.base(), 475 __new_start, _M_get_Tp_allocator()); 476 477 ++__new_finish; 478 479 __new_finish 480 = std::__uninitialized_move_if_noexcept_a 481 (__position.base(), __old_finish, 482 __new_finish, _M_get_Tp_allocator()); 483 } 484 } 485 __catch(...) 486 { 487 if (!__new_finish) 488 _Alloc_traits::destroy(this->_M_impl, 489 __new_start + __elems_before); 490 else 491 std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator()); 492 _M_deallocate(__new_start, __len); 493 __throw_exception_again; 494 } 495#if __cplusplus >= 201103L 496 if _GLIBCXX17_CONSTEXPR (!_S_use_relocate()) 497#endif 498 std::_Destroy(__old_start, __old_finish, _M_get_Tp_allocator()); 499 _GLIBCXX_ASAN_ANNOTATE_REINIT; 500 _M_deallocate(__old_start, 501 this->_M_impl._M_end_of_storage - __old_start); 502 this->_M_impl._M_start = __new_start; 503 this->_M_impl._M_finish = __new_finish; 504 this->_M_impl._M_end_of_storage = __new_start + __len; 505 } 506 507 template<typename _Tp, typename _Alloc> 508 void 509 vector<_Tp, _Alloc>:: 510 _M_fill_insert(iterator __position, size_type __n, const value_type& __x) 511 { 512 if (__n != 0) 513 { 514 if (size_type(this->_M_impl._M_end_of_storage 515 - this->_M_impl._M_finish) >= __n) 516 { 517#if __cplusplus < 201103L 518 value_type __x_copy = __x; 519#else 520 _Temporary_value __tmp(this, __x); 521 value_type& __x_copy = __tmp._M_val(); 522#endif 523 const size_type __elems_after = end() - __position; 524 pointer __old_finish(this->_M_impl._M_finish); 525 if (__elems_after > __n) 526 { 527 _GLIBCXX_ASAN_ANNOTATE_GROW(__n); 528 std::__uninitialized_move_a(this->_M_impl._M_finish - __n, 529 this->_M_impl._M_finish, 530 this->_M_impl._M_finish, 531 _M_get_Tp_allocator()); 532 this->_M_impl._M_finish += __n; 533 _GLIBCXX_ASAN_ANNOTATE_GREW(__n); 534 _GLIBCXX_MOVE_BACKWARD3(__position.base(), 535 __old_finish - __n, __old_finish); 536 std::fill(__position.base(), __position.base() + __n, 537 __x_copy); 538 } 539 else 540 { 541 _GLIBCXX_ASAN_ANNOTATE_GROW(__n); 542 this->_M_impl._M_finish = 543 std::__uninitialized_fill_n_a(this->_M_impl._M_finish, 544 __n - __elems_after, 545 __x_copy, 546 _M_get_Tp_allocator()); 547 _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after); 548 std::__uninitialized_move_a(__position.base(), __old_finish, 549 this->_M_impl._M_finish, 550 _M_get_Tp_allocator()); 551 this->_M_impl._M_finish += __elems_after; 552 _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after); 553 std::fill(__position.base(), __old_finish, __x_copy); 554 } 555 } 556 else 557 { 558 const size_type __len = 559 _M_check_len(__n, "vector::_M_fill_insert"); 560 const size_type __elems_before = __position - begin(); 561 pointer __new_start(this->_M_allocate(__len)); 562 pointer __new_finish(__new_start); 563 __try 564 { 565 // See _M_realloc_insert above. 566 std::__uninitialized_fill_n_a(__new_start + __elems_before, 567 __n, __x, 568 _M_get_Tp_allocator()); 569 __new_finish = pointer(); 570 571 __new_finish 572 = std::__uninitialized_move_if_noexcept_a 573 (this->_M_impl._M_start, __position.base(), 574 __new_start, _M_get_Tp_allocator()); 575 576 __new_finish += __n; 577 578 __new_finish 579 = std::__uninitialized_move_if_noexcept_a 580 (__position.base(), this->_M_impl._M_finish, 581 __new_finish, _M_get_Tp_allocator()); 582 } 583 __catch(...) 584 { 585 if (!__new_finish) 586 std::_Destroy(__new_start + __elems_before, 587 __new_start + __elems_before + __n, 588 _M_get_Tp_allocator()); 589 else 590 std::_Destroy(__new_start, __new_finish, 591 _M_get_Tp_allocator()); 592 _M_deallocate(__new_start, __len); 593 __throw_exception_again; 594 } 595 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 596 _M_get_Tp_allocator()); 597 _GLIBCXX_ASAN_ANNOTATE_REINIT; 598 _M_deallocate(this->_M_impl._M_start, 599 this->_M_impl._M_end_of_storage 600 - this->_M_impl._M_start); 601 this->_M_impl._M_start = __new_start; 602 this->_M_impl._M_finish = __new_finish; 603 this->_M_impl._M_end_of_storage = __new_start + __len; 604 } 605 } 606 } 607 608#if __cplusplus >= 201103L 609 template<typename _Tp, typename _Alloc> 610 void 611 vector<_Tp, _Alloc>:: 612 _M_default_append(size_type __n) 613 { 614 if (__n != 0) 615 { 616 const size_type __size = size(); 617 size_type __navail = size_type(this->_M_impl._M_end_of_storage 618 - this->_M_impl._M_finish); 619 620 if (__size > max_size() || __navail > max_size() - __size) 621 __builtin_unreachable(); 622 623 if (__navail >= __n) 624 { 625 _GLIBCXX_ASAN_ANNOTATE_GROW(__n); 626 this->_M_impl._M_finish = 627 std::__uninitialized_default_n_a(this->_M_impl._M_finish, 628 __n, _M_get_Tp_allocator()); 629 _GLIBCXX_ASAN_ANNOTATE_GREW(__n); 630 } 631 else 632 { 633 const size_type __len = 634 _M_check_len(__n, "vector::_M_default_append"); 635 pointer __new_start(this->_M_allocate(__len)); 636 if _GLIBCXX17_CONSTEXPR (_S_use_relocate()) 637 { 638 __try 639 { 640 std::__uninitialized_default_n_a(__new_start + __size, 641 __n, _M_get_Tp_allocator()); 642 } 643 __catch(...) 644 { 645 _M_deallocate(__new_start, __len); 646 __throw_exception_again; 647 } 648 _S_relocate(this->_M_impl._M_start, this->_M_impl._M_finish, 649 __new_start, _M_get_Tp_allocator()); 650 } 651 else 652 { 653 pointer __destroy_from = pointer(); 654 __try 655 { 656 std::__uninitialized_default_n_a(__new_start + __size, 657 __n, _M_get_Tp_allocator()); 658 __destroy_from = __new_start + __size; 659 std::__uninitialized_move_if_noexcept_a( 660 this->_M_impl._M_start, this->_M_impl._M_finish, 661 __new_start, _M_get_Tp_allocator()); 662 } 663 __catch(...) 664 { 665 if (__destroy_from) 666 std::_Destroy(__destroy_from, __destroy_from + __n, 667 _M_get_Tp_allocator()); 668 _M_deallocate(__new_start, __len); 669 __throw_exception_again; 670 } 671 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 672 _M_get_Tp_allocator()); 673 } 674 _GLIBCXX_ASAN_ANNOTATE_REINIT; 675 _M_deallocate(this->_M_impl._M_start, 676 this->_M_impl._M_end_of_storage 677 - this->_M_impl._M_start); 678 this->_M_impl._M_start = __new_start; 679 this->_M_impl._M_finish = __new_start + __size + __n; 680 this->_M_impl._M_end_of_storage = __new_start + __len; 681 } 682 } 683 } 684 685 template<typename _Tp, typename _Alloc> 686 bool 687 vector<_Tp, _Alloc>:: 688 _M_shrink_to_fit() 689 { 690 if (capacity() == size()) 691 return false; 692 _GLIBCXX_ASAN_ANNOTATE_REINIT; 693 return std::__shrink_to_fit_aux<vector>::_S_do_it(*this); 694 } 695#endif 696 697 template<typename _Tp, typename _Alloc> 698 template<typename _InputIterator> 699 void 700 vector<_Tp, _Alloc>:: 701 _M_range_insert(iterator __pos, _InputIterator __first, 702 _InputIterator __last, std::input_iterator_tag) 703 { 704 if (__pos == end()) 705 { 706 for (; __first != __last; ++__first) 707 insert(end(), *__first); 708 } 709 else if (__first != __last) 710 { 711 vector __tmp(__first, __last, _M_get_Tp_allocator()); 712 insert(__pos, 713 _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.begin()), 714 _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.end())); 715 } 716 } 717 718 template<typename _Tp, typename _Alloc> 719 template<typename _ForwardIterator> 720 void 721 vector<_Tp, _Alloc>:: 722 _M_range_insert(iterator __position, _ForwardIterator __first, 723 _ForwardIterator __last, std::forward_iterator_tag) 724 { 725 if (__first != __last) 726 { 727 const size_type __n = std::distance(__first, __last); 728 if (size_type(this->_M_impl._M_end_of_storage 729 - this->_M_impl._M_finish) >= __n) 730 { 731 const size_type __elems_after = end() - __position; 732 pointer __old_finish(this->_M_impl._M_finish); 733 if (__elems_after > __n) 734 { 735 _GLIBCXX_ASAN_ANNOTATE_GROW(__n); 736 std::__uninitialized_move_a(this->_M_impl._M_finish - __n, 737 this->_M_impl._M_finish, 738 this->_M_impl._M_finish, 739 _M_get_Tp_allocator()); 740 this->_M_impl._M_finish += __n; 741 _GLIBCXX_ASAN_ANNOTATE_GREW(__n); 742 _GLIBCXX_MOVE_BACKWARD3(__position.base(), 743 __old_finish - __n, __old_finish); 744 std::copy(__first, __last, __position); 745 } 746 else 747 { 748 _ForwardIterator __mid = __first; 749 std::advance(__mid, __elems_after); 750 _GLIBCXX_ASAN_ANNOTATE_GROW(__n); 751 std::__uninitialized_copy_a(__mid, __last, 752 this->_M_impl._M_finish, 753 _M_get_Tp_allocator()); 754 this->_M_impl._M_finish += __n - __elems_after; 755 _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after); 756 std::__uninitialized_move_a(__position.base(), 757 __old_finish, 758 this->_M_impl._M_finish, 759 _M_get_Tp_allocator()); 760 this->_M_impl._M_finish += __elems_after; 761 _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after); 762 std::copy(__first, __mid, __position); 763 } 764 } 765 else 766 { 767 const size_type __len = 768 _M_check_len(__n, "vector::_M_range_insert"); 769 pointer __new_start(this->_M_allocate(__len)); 770 pointer __new_finish(__new_start); 771 __try 772 { 773 __new_finish 774 = std::__uninitialized_move_if_noexcept_a 775 (this->_M_impl._M_start, __position.base(), 776 __new_start, _M_get_Tp_allocator()); 777 __new_finish 778 = std::__uninitialized_copy_a(__first, __last, 779 __new_finish, 780 _M_get_Tp_allocator()); 781 __new_finish 782 = std::__uninitialized_move_if_noexcept_a 783 (__position.base(), this->_M_impl._M_finish, 784 __new_finish, _M_get_Tp_allocator()); 785 } 786 __catch(...) 787 { 788 std::_Destroy(__new_start, __new_finish, 789 _M_get_Tp_allocator()); 790 _M_deallocate(__new_start, __len); 791 __throw_exception_again; 792 } 793 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 794 _M_get_Tp_allocator()); 795 _GLIBCXX_ASAN_ANNOTATE_REINIT; 796 _M_deallocate(this->_M_impl._M_start, 797 this->_M_impl._M_end_of_storage 798 - this->_M_impl._M_start); 799 this->_M_impl._M_start = __new_start; 800 this->_M_impl._M_finish = __new_finish; 801 this->_M_impl._M_end_of_storage = __new_start + __len; 802 } 803 } 804 } 805 806 807 // vector<bool> 808 template<typename _Alloc> 809 void 810 vector<bool, _Alloc>:: 811 _M_reallocate(size_type __n) 812 { 813 _Bit_pointer __q = this->_M_allocate(__n); 814 iterator __start(std::__addressof(*__q), 0); 815 iterator __finish(_M_copy_aligned(begin(), end(), __start)); 816 this->_M_deallocate(); 817 this->_M_impl._M_start = __start; 818 this->_M_impl._M_finish = __finish; 819 this->_M_impl._M_end_of_storage = __q + _S_nword(__n); 820 } 821 822 template<typename _Alloc> 823 void 824 vector<bool, _Alloc>:: 825 _M_fill_insert(iterator __position, size_type __n, bool __x) 826 { 827 if (__n == 0) 828 return; 829 if (capacity() - size() >= __n) 830 { 831 std::copy_backward(__position, end(), 832 this->_M_impl._M_finish + difference_type(__n)); 833 std::fill(__position, __position + difference_type(__n), __x); 834 this->_M_impl._M_finish += difference_type(__n); 835 } 836 else 837 { 838 const size_type __len = 839 _M_check_len(__n, "vector<bool>::_M_fill_insert"); 840 _Bit_pointer __q = this->_M_allocate(__len); 841 iterator __start(std::__addressof(*__q), 0); 842 iterator __i = _M_copy_aligned(begin(), __position, __start); 843 std::fill(__i, __i + difference_type(__n), __x); 844 iterator __finish = std::copy(__position, end(), 845 __i + difference_type(__n)); 846 this->_M_deallocate(); 847 this->_M_impl._M_end_of_storage = __q + _S_nword(__len); 848 this->_M_impl._M_start = __start; 849 this->_M_impl._M_finish = __finish; 850 } 851 } 852 853 template<typename _Alloc> 854 template<typename _ForwardIterator> 855 void 856 vector<bool, _Alloc>:: 857 _M_insert_range(iterator __position, _ForwardIterator __first, 858 _ForwardIterator __last, std::forward_iterator_tag) 859 { 860 if (__first != __last) 861 { 862 size_type __n = std::distance(__first, __last); 863 if (capacity() - size() >= __n) 864 { 865 std::copy_backward(__position, end(), 866 this->_M_impl._M_finish 867 + difference_type(__n)); 868 std::copy(__first, __last, __position); 869 this->_M_impl._M_finish += difference_type(__n); 870 } 871 else 872 { 873 const size_type __len = 874 _M_check_len(__n, "vector<bool>::_M_insert_range"); 875 _Bit_pointer __q = this->_M_allocate(__len); 876 iterator __start(std::__addressof(*__q), 0); 877 iterator __i = _M_copy_aligned(begin(), __position, __start); 878 __i = std::copy(__first, __last, __i); 879 iterator __finish = std::copy(__position, end(), __i); 880 this->_M_deallocate(); 881 this->_M_impl._M_end_of_storage = __q + _S_nword(__len); 882 this->_M_impl._M_start = __start; 883 this->_M_impl._M_finish = __finish; 884 } 885 } 886 } 887 888 template<typename _Alloc> 889 void 890 vector<bool, _Alloc>:: 891 _M_insert_aux(iterator __position, bool __x) 892 { 893 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr()) 894 { 895 std::copy_backward(__position, this->_M_impl._M_finish, 896 this->_M_impl._M_finish + 1); 897 *__position = __x; 898 ++this->_M_impl._M_finish; 899 } 900 else 901 { 902 const size_type __len = 903 _M_check_len(size_type(1), "vector<bool>::_M_insert_aux"); 904 _Bit_pointer __q = this->_M_allocate(__len); 905 iterator __start(std::__addressof(*__q), 0); 906 iterator __i = _M_copy_aligned(begin(), __position, __start); 907 *__i++ = __x; 908 iterator __finish = std::copy(__position, end(), __i); 909 this->_M_deallocate(); 910 this->_M_impl._M_end_of_storage = __q + _S_nword(__len); 911 this->_M_impl._M_start = __start; 912 this->_M_impl._M_finish = __finish; 913 } 914 } 915 916 template<typename _Alloc> 917 typename vector<bool, _Alloc>::iterator 918 vector<bool, _Alloc>:: 919 _M_erase(iterator __position) 920 { 921 if (__position + 1 != end()) 922 std::copy(__position + 1, end(), __position); 923 --this->_M_impl._M_finish; 924 return __position; 925 } 926 927 template<typename _Alloc> 928 typename vector<bool, _Alloc>::iterator 929 vector<bool, _Alloc>:: 930 _M_erase(iterator __first, iterator __last) 931 { 932 if (__first != __last) 933 _M_erase_at_end(std::copy(__last, end(), __first)); 934 return __first; 935 } 936 937#if __cplusplus >= 201103L 938 template<typename _Alloc> 939 bool 940 vector<bool, _Alloc>:: 941 _M_shrink_to_fit() 942 { 943 if (capacity() - size() < int(_S_word_bit)) 944 return false; 945 __try 946 { 947 if (size_type __n = size()) 948 _M_reallocate(__n); 949 else 950 { 951 this->_M_deallocate(); 952 this->_M_impl._M_reset(); 953 } 954 return true; 955 } 956 __catch(...) 957 { return false; } 958 } 959#endif 960 961_GLIBCXX_END_NAMESPACE_CONTAINER 962_GLIBCXX_END_NAMESPACE_VERSION 963} // namespace std 964 965#if __cplusplus >= 201103L 966 967namespace std _GLIBCXX_VISIBILITY(default) 968{ 969_GLIBCXX_BEGIN_NAMESPACE_VERSION 970 971 template<typename _Alloc> 972 size_t 973 hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>:: 974 operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const noexcept 975 { 976 size_t __hash = 0; 977 using _GLIBCXX_STD_C::_S_word_bit; 978 using _GLIBCXX_STD_C::_Bit_type; 979 980 const size_t __words = __b.size() / _S_word_bit; 981 if (__words) 982 { 983 const size_t __clength = __words * sizeof(_Bit_type); 984 __hash = std::_Hash_impl::hash(__b._M_impl._M_start._M_p, __clength); 985 } 986 987 const size_t __extrabits = __b.size() % _S_word_bit; 988 if (__extrabits) 989 { 990 _Bit_type __hiword = *__b._M_impl._M_finish._M_p; 991 __hiword &= ~((~static_cast<_Bit_type>(0)) << __extrabits); 992 993 const size_t __clength 994 = (__extrabits + __CHAR_BIT__ - 1) / __CHAR_BIT__; 995 if (__words) 996 __hash = std::_Hash_impl::hash(&__hiword, __clength, __hash); 997 else 998 __hash = std::_Hash_impl::hash(&__hiword, __clength); 999 } 1000 1001 return __hash; 1002 } 1003 1004_GLIBCXX_END_NAMESPACE_VERSION 1005} // namespace std 1006 1007#endif // C++11 1008 1009#undef _GLIBCXX_ASAN_ANNOTATE_REINIT 1010#undef _GLIBCXX_ASAN_ANNOTATE_GROW 1011#undef _GLIBCXX_ASAN_ANNOTATE_GREW 1012#undef _GLIBCXX_ASAN_ANNOTATE_SHRINK 1013 1014#endif /* _VECTOR_TCC */ 1015