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