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