1 // Vector implementation (out of line) -*- C++ -*- 2 3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 4 // 2011 Free Software Foundation, Inc. 5 // 6 // This file is part of the GNU ISO C++ Library. This library is free 7 // software; you can redistribute it and/or modify it under the 8 // terms of the GNU General Public License as published by the 9 // Free Software Foundation; either version 3, or (at your option) 10 // any later version. 11 12 // This library is distributed in the hope that it will be useful, 13 // but WITHOUT ANY WARRANTY; without even the implied warranty of 14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 // GNU General Public License for more details. 16 17 // Under Section 7 of GPL version 3, you are granted additional 18 // permissions described in the GCC Runtime Library Exception, version 19 // 3.1, as published by the Free Software Foundation. 20 21 // You should have received a copy of the GNU General Public License and 22 // a copy of the GCC Runtime Library Exception along with this program; 23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24 // <http://www.gnu.org/licenses/>. 25 26 /* 27 * 28 * Copyright (c) 1994 29 * Hewlett-Packard Company 30 * 31 * Permission to use, copy, modify, distribute and sell this software 32 * and its documentation for any purpose is hereby granted without fee, 33 * provided that the above copyright notice appear in all copies and 34 * that both that copyright notice and this permission notice appear 35 * in supporting documentation. Hewlett-Packard Company makes no 36 * representations about the suitability of this software for any 37 * purpose. It is provided "as is" without express or implied warranty. 38 * 39 * 40 * Copyright (c) 1996 41 * Silicon Graphics Computer Systems, Inc. 42 * 43 * Permission to use, copy, modify, distribute and sell this software 44 * and its documentation for any purpose is hereby granted without fee, 45 * provided that the above copyright notice appear in all copies and 46 * that both that copyright notice and this permission notice appear 47 * in supporting documentation. Silicon Graphics makes no 48 * representations about the suitability of this software for any 49 * purpose. It is provided "as is" without express or implied warranty. 50 */ 51 52 /** @file bits/vector.tcc 53 * This is an internal header file, included by other library headers. 54 * Do not attempt to use it directly. @headername{vector} 55 */ 56 57 #ifndef _VECTOR_TCC 58 #define _VECTOR_TCC 1 59 60 namespace std _GLIBCXX_VISIBILITY(default) 61 { 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 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 78 _M_get_Tp_allocator()); 79 _M_deallocate(this->_M_impl._M_start, 80 this->_M_impl._M_end_of_storage 81 - this->_M_impl._M_start); 82 this->_M_impl._M_start = __tmp; 83 this->_M_impl._M_finish = __tmp + __old_size; 84 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 85 } 86 } 87 88 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 89 template<typename _Tp, typename _Alloc> 90 template<typename... _Args> 91 void 92 vector<_Tp, _Alloc>:: 93 emplace_back(_Args&&... __args) 94 { 95 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 96 { 97 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, 98 std::forward<_Args>(__args)...); 99 ++this->_M_impl._M_finish; 100 } 101 else 102 _M_emplace_back_aux(std::forward<_Args>(__args)...); 103 } 104 #endif 105 106 template<typename _Tp, typename _Alloc> 107 typename vector<_Tp, _Alloc>::iterator 108 vector<_Tp, _Alloc>:: 109 insert(iterator __position, const value_type& __x) 110 { 111 const size_type __n = __position - begin(); 112 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage 113 && __position == end()) 114 { 115 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x); 116 ++this->_M_impl._M_finish; 117 } 118 else 119 { 120 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 121 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 122 { 123 _Tp __x_copy = __x; 124 _M_insert_aux(__position, std::move(__x_copy)); 125 } 126 else 127 #endif 128 _M_insert_aux(__position, __x); 129 } 130 return iterator(this->_M_impl._M_start + __n); 131 } 132 133 template<typename _Tp, typename _Alloc> 134 typename vector<_Tp, _Alloc>::iterator 135 vector<_Tp, _Alloc>:: 136 erase(iterator __position) 137 { 138 if (__position + 1 != end()) 139 _GLIBCXX_MOVE3(__position + 1, end(), __position); 140 --this->_M_impl._M_finish; 141 _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish); 142 return __position; 143 } 144 145 template<typename _Tp, typename _Alloc> 146 typename vector<_Tp, _Alloc>::iterator 147 vector<_Tp, _Alloc>:: 148 erase(iterator __first, iterator __last) 149 { 150 if (__first != __last) 151 { 152 if (__last != end()) 153 _GLIBCXX_MOVE3(__last, end(), __first); 154 _M_erase_at_end(__first.base() + (end() - __last)); 155 } 156 return __first; 157 } 158 159 template<typename _Tp, typename _Alloc> 160 vector<_Tp, _Alloc>& 161 vector<_Tp, _Alloc>:: 162 operator=(const vector<_Tp, _Alloc>& __x) 163 { 164 if (&__x != this) 165 { 166 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 167 if (_Alloc_traits::_S_propagate_on_copy_assign()) 168 { 169 if (!_Alloc_traits::_S_always_equal() 170 && _M_get_Tp_allocator() != __x._M_get_Tp_allocator()) 171 { 172 // replacement allocator cannot free existing storage 173 this->clear(); 174 _M_deallocate(this->_M_impl._M_start, 175 this->_M_impl._M_end_of_storage 176 - this->_M_impl._M_start); 177 this->_M_impl._M_start = nullptr; 178 this->_M_impl._M_finish = nullptr; 179 this->_M_impl._M_end_of_storage = nullptr; 180 } 181 std::__alloc_on_copy(_M_get_Tp_allocator(), 182 __x._M_get_Tp_allocator()); 183 } 184 #endif 185 const size_type __xlen = __x.size(); 186 if (__xlen > capacity()) 187 { 188 pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(), 189 __x.end()); 190 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 191 _M_get_Tp_allocator()); 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 = __tmp; 196 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen; 197 } 198 else if (size() >= __xlen) 199 { 200 std::_Destroy(std::copy(__x.begin(), __x.end(), begin()), 201 end(), _M_get_Tp_allocator()); 202 } 203 else 204 { 205 std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(), 206 this->_M_impl._M_start); 207 std::__uninitialized_copy_a(__x._M_impl._M_start + size(), 208 __x._M_impl._M_finish, 209 this->_M_impl._M_finish, 210 _M_get_Tp_allocator()); 211 } 212 this->_M_impl._M_finish = this->_M_impl._M_start + __xlen; 213 } 214 return *this; 215 } 216 217 template<typename _Tp, typename _Alloc> 218 void 219 vector<_Tp, _Alloc>:: 220 _M_fill_assign(size_t __n, const value_type& __val) 221 { 222 if (__n > capacity()) 223 { 224 vector __tmp(__n, __val, _M_get_Tp_allocator()); 225 __tmp.swap(*this); 226 } 227 else if (__n > size()) 228 { 229 std::fill(begin(), end(), __val); 230 std::__uninitialized_fill_n_a(this->_M_impl._M_finish, 231 __n - size(), __val, 232 _M_get_Tp_allocator()); 233 this->_M_impl._M_finish += __n - size(); 234 } 235 else 236 _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val)); 237 } 238 239 template<typename _Tp, typename _Alloc> 240 template<typename _InputIterator> 241 void 242 vector<_Tp, _Alloc>:: 243 _M_assign_aux(_InputIterator __first, _InputIterator __last, 244 std::input_iterator_tag) 245 { 246 pointer __cur(this->_M_impl._M_start); 247 for (; __first != __last && __cur != this->_M_impl._M_finish; 248 ++__cur, ++__first) 249 *__cur = *__first; 250 if (__first == __last) 251 _M_erase_at_end(__cur); 252 else 253 insert(end(), __first, __last); 254 } 255 256 template<typename _Tp, typename _Alloc> 257 template<typename _ForwardIterator> 258 void 259 vector<_Tp, _Alloc>:: 260 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 261 std::forward_iterator_tag) 262 { 263 const size_type __len = std::distance(__first, __last); 264 265 if (__len > capacity()) 266 { 267 pointer __tmp(_M_allocate_and_copy(__len, __first, __last)); 268 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 269 _M_get_Tp_allocator()); 270 _M_deallocate(this->_M_impl._M_start, 271 this->_M_impl._M_end_of_storage 272 - this->_M_impl._M_start); 273 this->_M_impl._M_start = __tmp; 274 this->_M_impl._M_finish = this->_M_impl._M_start + __len; 275 this->_M_impl._M_end_of_storage = this->_M_impl._M_finish; 276 } 277 else if (size() >= __len) 278 _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start)); 279 else 280 { 281 _ForwardIterator __mid = __first; 282 std::advance(__mid, size()); 283 std::copy(__first, __mid, this->_M_impl._M_start); 284 this->_M_impl._M_finish = 285 std::__uninitialized_copy_a(__mid, __last, 286 this->_M_impl._M_finish, 287 _M_get_Tp_allocator()); 288 } 289 } 290 291 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 292 template<typename _Tp, typename _Alloc> 293 template<typename... _Args> 294 typename vector<_Tp, _Alloc>::iterator 295 vector<_Tp, _Alloc>:: 296 emplace(iterator __position, _Args&&... __args) 297 { 298 const size_type __n = __position - begin(); 299 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage 300 && __position == end()) 301 { 302 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, 303 std::forward<_Args>(__args)...); 304 ++this->_M_impl._M_finish; 305 } 306 else 307 _M_insert_aux(__position, std::forward<_Args>(__args)...); 308 return iterator(this->_M_impl._M_start + __n); 309 } 310 311 template<typename _Tp, typename _Alloc> 312 template<typename... _Args> 313 void 314 vector<_Tp, _Alloc>:: 315 _M_insert_aux(iterator __position, _Args&&... __args) 316 #else 317 template<typename _Tp, typename _Alloc> 318 void 319 vector<_Tp, _Alloc>:: 320 _M_insert_aux(iterator __position, const _Tp& __x) 321 #endif 322 { 323 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 324 { 325 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, 326 _GLIBCXX_MOVE(*(this->_M_impl._M_finish 327 - 1))); 328 ++this->_M_impl._M_finish; 329 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 330 _Tp __x_copy = __x; 331 #endif 332 _GLIBCXX_MOVE_BACKWARD3(__position.base(), 333 this->_M_impl._M_finish - 2, 334 this->_M_impl._M_finish - 1); 335 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 336 *__position = __x_copy; 337 #else 338 *__position = _Tp(std::forward<_Args>(__args)...); 339 #endif 340 } 341 else 342 { 343 const size_type __len = 344 _M_check_len(size_type(1), "vector::_M_insert_aux"); 345 const size_type __elems_before = __position - begin(); 346 pointer __new_start(this->_M_allocate(__len)); 347 pointer __new_finish(__new_start); 348 __try 349 { 350 // The order of the three operations is dictated by the C++0x 351 // case, where the moves could alter a new element belonging 352 // to the existing vector. This is an issue only for callers 353 // taking the element by const lvalue ref (see 23.1/13). 354 _Alloc_traits::construct(this->_M_impl, 355 __new_start + __elems_before, 356 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 357 std::forward<_Args>(__args)...); 358 #else 359 __x); 360 #endif 361 __new_finish = 0; 362 363 __new_finish 364 = std::__uninitialized_move_if_noexcept_a 365 (this->_M_impl._M_start, __position.base(), 366 __new_start, _M_get_Tp_allocator()); 367 368 ++__new_finish; 369 370 __new_finish 371 = std::__uninitialized_move_if_noexcept_a 372 (__position.base(), this->_M_impl._M_finish, 373 __new_finish, _M_get_Tp_allocator()); 374 } 375 __catch(...) 376 { 377 if (!__new_finish) 378 _Alloc_traits::destroy(this->_M_impl, 379 __new_start + __elems_before); 380 else 381 std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator()); 382 _M_deallocate(__new_start, __len); 383 __throw_exception_again; 384 } 385 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 386 _M_get_Tp_allocator()); 387 _M_deallocate(this->_M_impl._M_start, 388 this->_M_impl._M_end_of_storage 389 - this->_M_impl._M_start); 390 this->_M_impl._M_start = __new_start; 391 this->_M_impl._M_finish = __new_finish; 392 this->_M_impl._M_end_of_storage = __new_start + __len; 393 } 394 } 395 396 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 397 template<typename _Tp, typename _Alloc> 398 template<typename... _Args> 399 void 400 vector<_Tp, _Alloc>:: 401 _M_emplace_back_aux(_Args&&... __args) 402 { 403 const size_type __len = 404 _M_check_len(size_type(1), "vector::_M_emplace_back_aux"); 405 pointer __new_start(this->_M_allocate(__len)); 406 pointer __new_finish(__new_start); 407 __try 408 { 409 _Alloc_traits::construct(this->_M_impl, __new_start + size(), 410 std::forward<_Args>(__args)...); 411 __new_finish = 0; 412 413 __new_finish 414 = std::__uninitialized_move_if_noexcept_a 415 (this->_M_impl._M_start, this->_M_impl._M_finish, 416 __new_start, _M_get_Tp_allocator()); 417 418 ++__new_finish; 419 } 420 __catch(...) 421 { 422 if (!__new_finish) 423 _Alloc_traits::destroy(this->_M_impl, __new_start + size()); 424 else 425 std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator()); 426 _M_deallocate(__new_start, __len); 427 __throw_exception_again; 428 } 429 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 430 _M_get_Tp_allocator()); 431 _M_deallocate(this->_M_impl._M_start, 432 this->_M_impl._M_end_of_storage 433 - this->_M_impl._M_start); 434 this->_M_impl._M_start = __new_start; 435 this->_M_impl._M_finish = __new_finish; 436 this->_M_impl._M_end_of_storage = __new_start + __len; 437 } 438 #endif 439 440 template<typename _Tp, typename _Alloc> 441 void 442 vector<_Tp, _Alloc>:: 443 _M_fill_insert(iterator __position, size_type __n, const value_type& __x) 444 { 445 if (__n != 0) 446 { 447 if (size_type(this->_M_impl._M_end_of_storage 448 - this->_M_impl._M_finish) >= __n) 449 { 450 value_type __x_copy = __x; 451 const size_type __elems_after = end() - __position; 452 pointer __old_finish(this->_M_impl._M_finish); 453 if (__elems_after > __n) 454 { 455 std::__uninitialized_move_a(this->_M_impl._M_finish - __n, 456 this->_M_impl._M_finish, 457 this->_M_impl._M_finish, 458 _M_get_Tp_allocator()); 459 this->_M_impl._M_finish += __n; 460 _GLIBCXX_MOVE_BACKWARD3(__position.base(), 461 __old_finish - __n, __old_finish); 462 std::fill(__position.base(), __position.base() + __n, 463 __x_copy); 464 } 465 else 466 { 467 std::__uninitialized_fill_n_a(this->_M_impl._M_finish, 468 __n - __elems_after, 469 __x_copy, 470 _M_get_Tp_allocator()); 471 this->_M_impl._M_finish += __n - __elems_after; 472 std::__uninitialized_move_a(__position.base(), __old_finish, 473 this->_M_impl._M_finish, 474 _M_get_Tp_allocator()); 475 this->_M_impl._M_finish += __elems_after; 476 std::fill(__position.base(), __old_finish, __x_copy); 477 } 478 } 479 else 480 { 481 const size_type __len = 482 _M_check_len(__n, "vector::_M_fill_insert"); 483 const size_type __elems_before = __position - begin(); 484 pointer __new_start(this->_M_allocate(__len)); 485 pointer __new_finish(__new_start); 486 __try 487 { 488 // See _M_insert_aux above. 489 std::__uninitialized_fill_n_a(__new_start + __elems_before, 490 __n, __x, 491 _M_get_Tp_allocator()); 492 __new_finish = 0; 493 494 __new_finish 495 = std::__uninitialized_move_if_noexcept_a 496 (this->_M_impl._M_start, __position.base(), 497 __new_start, _M_get_Tp_allocator()); 498 499 __new_finish += __n; 500 501 __new_finish 502 = std::__uninitialized_move_if_noexcept_a 503 (__position.base(), this->_M_impl._M_finish, 504 __new_finish, _M_get_Tp_allocator()); 505 } 506 __catch(...) 507 { 508 if (!__new_finish) 509 std::_Destroy(__new_start + __elems_before, 510 __new_start + __elems_before + __n, 511 _M_get_Tp_allocator()); 512 else 513 std::_Destroy(__new_start, __new_finish, 514 _M_get_Tp_allocator()); 515 _M_deallocate(__new_start, __len); 516 __throw_exception_again; 517 } 518 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 519 _M_get_Tp_allocator()); 520 _M_deallocate(this->_M_impl._M_start, 521 this->_M_impl._M_end_of_storage 522 - this->_M_impl._M_start); 523 this->_M_impl._M_start = __new_start; 524 this->_M_impl._M_finish = __new_finish; 525 this->_M_impl._M_end_of_storage = __new_start + __len; 526 } 527 } 528 } 529 530 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 531 template<typename _Tp, typename _Alloc> 532 void 533 vector<_Tp, _Alloc>:: 534 _M_default_append(size_type __n) 535 { 536 if (__n != 0) 537 { 538 if (size_type(this->_M_impl._M_end_of_storage 539 - this->_M_impl._M_finish) >= __n) 540 { 541 std::__uninitialized_default_n_a(this->_M_impl._M_finish, 542 __n, _M_get_Tp_allocator()); 543 this->_M_impl._M_finish += __n; 544 } 545 else 546 { 547 const size_type __len = 548 _M_check_len(__n, "vector::_M_default_append"); 549 const size_type __old_size = this->size(); 550 pointer __new_start(this->_M_allocate(__len)); 551 pointer __new_finish(__new_start); 552 __try 553 { 554 __new_finish 555 = std::__uninitialized_move_if_noexcept_a 556 (this->_M_impl._M_start, this->_M_impl._M_finish, 557 __new_start, _M_get_Tp_allocator()); 558 std::__uninitialized_default_n_a(__new_finish, __n, 559 _M_get_Tp_allocator()); 560 __new_finish += __n; 561 } 562 __catch(...) 563 { 564 std::_Destroy(__new_start, __new_finish, 565 _M_get_Tp_allocator()); 566 _M_deallocate(__new_start, __len); 567 __throw_exception_again; 568 } 569 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 570 _M_get_Tp_allocator()); 571 _M_deallocate(this->_M_impl._M_start, 572 this->_M_impl._M_end_of_storage 573 - this->_M_impl._M_start); 574 this->_M_impl._M_start = __new_start; 575 this->_M_impl._M_finish = __new_finish; 576 this->_M_impl._M_end_of_storage = __new_start + __len; 577 } 578 } 579 } 580 581 template<typename _Tp, typename _Alloc> 582 bool 583 vector<_Tp, _Alloc>:: 584 _M_shrink_to_fit() 585 { 586 if (capacity() == size()) 587 return false; 588 return std::__shrink_to_fit_aux<vector>::_S_do_it(*this); 589 } 590 #endif 591 592 template<typename _Tp, typename _Alloc> 593 template<typename _InputIterator> 594 void 595 vector<_Tp, _Alloc>:: 596 _M_range_insert(iterator __pos, _InputIterator __first, 597 _InputIterator __last, std::input_iterator_tag) 598 { 599 for (; __first != __last; ++__first) 600 { 601 __pos = insert(__pos, *__first); 602 ++__pos; 603 } 604 } 605 606 template<typename _Tp, typename _Alloc> 607 template<typename _ForwardIterator> 608 void 609 vector<_Tp, _Alloc>:: 610 _M_range_insert(iterator __position, _ForwardIterator __first, 611 _ForwardIterator __last, std::forward_iterator_tag) 612 { 613 if (__first != __last) 614 { 615 const size_type __n = std::distance(__first, __last); 616 if (size_type(this->_M_impl._M_end_of_storage 617 - this->_M_impl._M_finish) >= __n) 618 { 619 const size_type __elems_after = end() - __position; 620 pointer __old_finish(this->_M_impl._M_finish); 621 if (__elems_after > __n) 622 { 623 std::__uninitialized_move_a(this->_M_impl._M_finish - __n, 624 this->_M_impl._M_finish, 625 this->_M_impl._M_finish, 626 _M_get_Tp_allocator()); 627 this->_M_impl._M_finish += __n; 628 _GLIBCXX_MOVE_BACKWARD3(__position.base(), 629 __old_finish - __n, __old_finish); 630 std::copy(__first, __last, __position); 631 } 632 else 633 { 634 _ForwardIterator __mid = __first; 635 std::advance(__mid, __elems_after); 636 std::__uninitialized_copy_a(__mid, __last, 637 this->_M_impl._M_finish, 638 _M_get_Tp_allocator()); 639 this->_M_impl._M_finish += __n - __elems_after; 640 std::__uninitialized_move_a(__position.base(), 641 __old_finish, 642 this->_M_impl._M_finish, 643 _M_get_Tp_allocator()); 644 this->_M_impl._M_finish += __elems_after; 645 std::copy(__first, __mid, __position); 646 } 647 } 648 else 649 { 650 const size_type __len = 651 _M_check_len(__n, "vector::_M_range_insert"); 652 pointer __new_start(this->_M_allocate(__len)); 653 pointer __new_finish(__new_start); 654 __try 655 { 656 __new_finish 657 = std::__uninitialized_move_if_noexcept_a 658 (this->_M_impl._M_start, __position.base(), 659 __new_start, _M_get_Tp_allocator()); 660 __new_finish 661 = std::__uninitialized_copy_a(__first, __last, 662 __new_finish, 663 _M_get_Tp_allocator()); 664 __new_finish 665 = std::__uninitialized_move_if_noexcept_a 666 (__position.base(), this->_M_impl._M_finish, 667 __new_finish, _M_get_Tp_allocator()); 668 } 669 __catch(...) 670 { 671 std::_Destroy(__new_start, __new_finish, 672 _M_get_Tp_allocator()); 673 _M_deallocate(__new_start, __len); 674 __throw_exception_again; 675 } 676 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 677 _M_get_Tp_allocator()); 678 _M_deallocate(this->_M_impl._M_start, 679 this->_M_impl._M_end_of_storage 680 - this->_M_impl._M_start); 681 this->_M_impl._M_start = __new_start; 682 this->_M_impl._M_finish = __new_finish; 683 this->_M_impl._M_end_of_storage = __new_start + __len; 684 } 685 } 686 } 687 688 689 // vector<bool> 690 template<typename _Alloc> 691 void 692 vector<bool, _Alloc>:: 693 _M_reallocate(size_type __n) 694 { 695 _Bit_type* __q = this->_M_allocate(__n); 696 this->_M_impl._M_finish = _M_copy_aligned(begin(), end(), 697 iterator(__q, 0)); 698 this->_M_deallocate(); 699 this->_M_impl._M_start = iterator(__q, 0); 700 this->_M_impl._M_end_of_storage = __q + _S_nword(__n); 701 } 702 703 template<typename _Alloc> 704 void 705 vector<bool, _Alloc>:: 706 _M_fill_insert(iterator __position, size_type __n, bool __x) 707 { 708 if (__n == 0) 709 return; 710 if (capacity() - size() >= __n) 711 { 712 std::copy_backward(__position, end(), 713 this->_M_impl._M_finish + difference_type(__n)); 714 std::fill(__position, __position + difference_type(__n), __x); 715 this->_M_impl._M_finish += difference_type(__n); 716 } 717 else 718 { 719 const size_type __len = 720 _M_check_len(__n, "vector<bool>::_M_fill_insert"); 721 _Bit_type * __q = this->_M_allocate(__len); 722 iterator __i = _M_copy_aligned(begin(), __position, 723 iterator(__q, 0)); 724 std::fill(__i, __i + difference_type(__n), __x); 725 this->_M_impl._M_finish = std::copy(__position, end(), 726 __i + difference_type(__n)); 727 this->_M_deallocate(); 728 this->_M_impl._M_end_of_storage = __q + _S_nword(__len); 729 this->_M_impl._M_start = iterator(__q, 0); 730 } 731 } 732 733 template<typename _Alloc> 734 template<typename _ForwardIterator> 735 void 736 vector<bool, _Alloc>:: 737 _M_insert_range(iterator __position, _ForwardIterator __first, 738 _ForwardIterator __last, std::forward_iterator_tag) 739 { 740 if (__first != __last) 741 { 742 size_type __n = std::distance(__first, __last); 743 if (capacity() - size() >= __n) 744 { 745 std::copy_backward(__position, end(), 746 this->_M_impl._M_finish 747 + difference_type(__n)); 748 std::copy(__first, __last, __position); 749 this->_M_impl._M_finish += difference_type(__n); 750 } 751 else 752 { 753 const size_type __len = 754 _M_check_len(__n, "vector<bool>::_M_insert_range"); 755 _Bit_type * __q = this->_M_allocate(__len); 756 iterator __i = _M_copy_aligned(begin(), __position, 757 iterator(__q, 0)); 758 __i = std::copy(__first, __last, __i); 759 this->_M_impl._M_finish = std::copy(__position, end(), __i); 760 this->_M_deallocate(); 761 this->_M_impl._M_end_of_storage = __q + _S_nword(__len); 762 this->_M_impl._M_start = iterator(__q, 0); 763 } 764 } 765 } 766 767 template<typename _Alloc> 768 void 769 vector<bool, _Alloc>:: 770 _M_insert_aux(iterator __position, bool __x) 771 { 772 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage) 773 { 774 std::copy_backward(__position, this->_M_impl._M_finish, 775 this->_M_impl._M_finish + 1); 776 *__position = __x; 777 ++this->_M_impl._M_finish; 778 } 779 else 780 { 781 const size_type __len = 782 _M_check_len(size_type(1), "vector<bool>::_M_insert_aux"); 783 _Bit_type * __q = this->_M_allocate(__len); 784 iterator __i = _M_copy_aligned(begin(), __position, 785 iterator(__q, 0)); 786 *__i++ = __x; 787 this->_M_impl._M_finish = std::copy(__position, end(), __i); 788 this->_M_deallocate(); 789 this->_M_impl._M_end_of_storage = __q + _S_nword(__len); 790 this->_M_impl._M_start = iterator(__q, 0); 791 } 792 } 793 794 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 795 template<typename _Alloc> 796 bool 797 vector<bool, _Alloc>:: 798 _M_shrink_to_fit() 799 { 800 if (capacity() - size() < int(_S_word_bit)) 801 return false; 802 __try 803 { 804 _M_reallocate(size()); 805 return true; 806 } 807 __catch(...) 808 { return false; } 809 } 810 #endif 811 812 _GLIBCXX_END_NAMESPACE_CONTAINER 813 } // namespace std 814 815 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 816 817 namespace std _GLIBCXX_VISIBILITY(default) 818 { 819 _GLIBCXX_BEGIN_NAMESPACE_VERSION 820 821 template<typename _Alloc> 822 size_t 823 hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>:: 824 operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const noexcept 825 { 826 size_t __hash = 0; 827 using _GLIBCXX_STD_C::_S_word_bit; 828 using _GLIBCXX_STD_C::_Bit_type; 829 830 const size_t __words = __b.size() / _S_word_bit; 831 if (__words) 832 { 833 const size_t __clength = __words * sizeof(_Bit_type); 834 __hash = std::_Hash_impl::hash(__b._M_impl._M_start._M_p, __clength); 835 } 836 837 const size_t __extrabits = __b.size() % _S_word_bit; 838 if (__extrabits) 839 { 840 _Bit_type __hiword = *__b._M_impl._M_finish._M_p; 841 __hiword &= ~((~static_cast<_Bit_type>(0)) << __extrabits); 842 843 const size_t __clength 844 = (__extrabits + __CHAR_BIT__ - 1) / __CHAR_BIT__; 845 if (__words) 846 __hash = std::_Hash_impl::hash(&__hiword, __clength, __hash); 847 else 848 __hash = std::_Hash_impl::hash(&__hiword, __clength); 849 } 850 851 return __hash; 852 } 853 854 _GLIBCXX_END_NAMESPACE_VERSION 855 } // namespace std 856 857 #endif // __GXX_EXPERIMENTAL_CXX0X__ 858 859 #endif /* _VECTOR_TCC */ 860