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