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