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