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