1 // Vector implementation (out of line) -*- C++ -*-
3 // Copyright (C) 2001-2016 Free Software Foundation, Inc.
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)
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.
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.
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/>.
28 * Hewlett-Packard Company
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.
40 * Silicon Graphics Computer Systems, Inc.
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.
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}
59 namespace std _GLIBCXX_VISIBILITY(default)
61 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
63 template<typename _Tp, typename _Alloc>
66 reserve(size_type __n)
68 if (__n > this->max_size())
69 __throw_length_error(__N("vector::reserve"));
70 if (this->capacity() < __n)
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;
87 #if __cplusplus >= 201103L
88 template<typename _Tp, typename _Alloc>
89 template<typename... _Args>
92 emplace_back(_Args&&... __args)
94 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
96 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
97 std::forward<_Args>(__args)...);
98 ++this->_M_impl._M_finish;
101 _M_realloc_insert(end(), std::forward<_Args>(__args)...);
105 template<typename _Tp, typename _Alloc>
106 typename vector<_Tp, _Alloc>::iterator
107 vector<_Tp, _Alloc>::
108 #if __cplusplus >= 201103L
109 insert(const_iterator __position, const value_type& __x)
111 insert(iterator __position, const value_type& __x)
114 const size_type __n = __position - begin();
115 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
116 if (__position == end())
118 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
120 ++this->_M_impl._M_finish;
124 #if __cplusplus >= 201103L
125 const auto __pos = begin() + (__position - cbegin());
126 // __x could be an existing element of this vector, so make a
127 // copy of it before _M_insert_aux moves elements around.
128 _Temporary_value __x_copy(this, __x);
129 _M_insert_aux(__pos, std::move(__x_copy._M_val()));
131 _M_insert_aux(__position, __x);
135 #if __cplusplus >= 201103L
136 _M_realloc_insert(begin() + (__position - cbegin()), __x);
138 _M_realloc_insert(__position, __x);
141 return iterator(this->_M_impl._M_start + __n);
144 template<typename _Tp, typename _Alloc>
145 typename vector<_Tp, _Alloc>::iterator
146 vector<_Tp, _Alloc>::
147 _M_erase(iterator __position)
149 if (__position + 1 != end())
150 _GLIBCXX_MOVE3(__position + 1, end(), __position);
151 --this->_M_impl._M_finish;
152 _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
156 template<typename _Tp, typename _Alloc>
157 typename vector<_Tp, _Alloc>::iterator
158 vector<_Tp, _Alloc>::
159 _M_erase(iterator __first, iterator __last)
161 if (__first != __last)
164 _GLIBCXX_MOVE3(__last, end(), __first);
165 _M_erase_at_end(__first.base() + (end() - __last));
170 template<typename _Tp, typename _Alloc>
172 vector<_Tp, _Alloc>::
173 operator=(const vector<_Tp, _Alloc>& __x)
177 #if __cplusplus >= 201103L
178 if (_Alloc_traits::_S_propagate_on_copy_assign())
180 if (!_Alloc_traits::_S_always_equal()
181 && _M_get_Tp_allocator() != __x._M_get_Tp_allocator())
183 // replacement allocator cannot free existing storage
185 _M_deallocate(this->_M_impl._M_start,
186 this->_M_impl._M_end_of_storage
187 - this->_M_impl._M_start);
188 this->_M_impl._M_start = nullptr;
189 this->_M_impl._M_finish = nullptr;
190 this->_M_impl._M_end_of_storage = nullptr;
192 std::__alloc_on_copy(_M_get_Tp_allocator(),
193 __x._M_get_Tp_allocator());
196 const size_type __xlen = __x.size();
197 if (__xlen > capacity())
199 pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(),
201 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
202 _M_get_Tp_allocator());
203 _M_deallocate(this->_M_impl._M_start,
204 this->_M_impl._M_end_of_storage
205 - this->_M_impl._M_start);
206 this->_M_impl._M_start = __tmp;
207 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen;
209 else if (size() >= __xlen)
211 std::_Destroy(std::copy(__x.begin(), __x.end(), begin()),
212 end(), _M_get_Tp_allocator());
216 std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(),
217 this->_M_impl._M_start);
218 std::__uninitialized_copy_a(__x._M_impl._M_start + size(),
219 __x._M_impl._M_finish,
220 this->_M_impl._M_finish,
221 _M_get_Tp_allocator());
223 this->_M_impl._M_finish = this->_M_impl._M_start + __xlen;
228 template<typename _Tp, typename _Alloc>
230 vector<_Tp, _Alloc>::
231 _M_fill_assign(size_t __n, const value_type& __val)
233 if (__n > capacity())
235 vector __tmp(__n, __val, _M_get_Tp_allocator());
236 __tmp._M_impl._M_swap_data(this->_M_impl);
238 else if (__n > size())
240 std::fill(begin(), end(), __val);
241 this->_M_impl._M_finish =
242 std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
244 _M_get_Tp_allocator());
247 _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val));
250 template<typename _Tp, typename _Alloc>
251 template<typename _InputIterator>
253 vector<_Tp, _Alloc>::
254 _M_assign_aux(_InputIterator __first, _InputIterator __last,
255 std::input_iterator_tag)
257 pointer __cur(this->_M_impl._M_start);
258 for (; __first != __last && __cur != this->_M_impl._M_finish;
261 if (__first == __last)
262 _M_erase_at_end(__cur);
264 _M_range_insert(end(), __first, __last,
265 std::__iterator_category(__first));
268 template<typename _Tp, typename _Alloc>
269 template<typename _ForwardIterator>
271 vector<_Tp, _Alloc>::
272 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
273 std::forward_iterator_tag)
275 const size_type __len = std::distance(__first, __last);
277 if (__len > capacity())
279 pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
280 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
281 _M_get_Tp_allocator());
282 _M_deallocate(this->_M_impl._M_start,
283 this->_M_impl._M_end_of_storage
284 - this->_M_impl._M_start);
285 this->_M_impl._M_start = __tmp;
286 this->_M_impl._M_finish = this->_M_impl._M_start + __len;
287 this->_M_impl._M_end_of_storage = this->_M_impl._M_finish;
289 else if (size() >= __len)
290 _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start));
293 _ForwardIterator __mid = __first;
294 std::advance(__mid, size());
295 std::copy(__first, __mid, this->_M_impl._M_start);
296 this->_M_impl._M_finish =
297 std::__uninitialized_copy_a(__mid, __last,
298 this->_M_impl._M_finish,
299 _M_get_Tp_allocator());
303 #if __cplusplus >= 201103L
304 template<typename _Tp, typename _Alloc>
306 vector<_Tp, _Alloc>::
307 _M_insert_rval(const_iterator __position, value_type&& __v) -> iterator
309 const auto __n = __position - cbegin();
310 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
311 if (__position == cend())
313 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
315 ++this->_M_impl._M_finish;
318 _M_insert_aux(begin() + __n, std::move(__v));
320 _M_realloc_insert(begin() + __n, std::move(__v));
322 return iterator(this->_M_impl._M_start + __n);
325 template<typename _Tp, typename _Alloc>
326 template<typename... _Args>
328 vector<_Tp, _Alloc>::
329 _M_emplace_aux(const_iterator __position, _Args&&... __args)
332 const auto __n = __position - cbegin();
333 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
334 if (__position == cend())
336 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
337 std::forward<_Args>(__args)...);
338 ++this->_M_impl._M_finish;
342 // We need to construct a temporary because something in __args...
343 // could alias one of the elements of the container and so we
344 // need to use it before _M_insert_aux moves elements around.
345 _Temporary_value __tmp(this, std::forward<_Args>(__args)...);
346 _M_insert_aux(begin() + __n, std::move(__tmp._M_val()));
349 _M_realloc_insert(begin() + __n, std::forward<_Args>(__args)...);
351 return iterator(this->_M_impl._M_start + __n);
354 template<typename _Tp, typename _Alloc>
355 template<typename _Arg>
357 vector<_Tp, _Alloc>::
358 _M_insert_aux(iterator __position, _Arg&& __arg)
360 template<typename _Tp, typename _Alloc>
362 vector<_Tp, _Alloc>::
363 _M_insert_aux(iterator __position, const _Tp& __x)
366 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
367 _GLIBCXX_MOVE(*(this->_M_impl._M_finish
369 ++this->_M_impl._M_finish;
370 #if __cplusplus < 201103L
373 _GLIBCXX_MOVE_BACKWARD3(__position.base(),
374 this->_M_impl._M_finish - 2,
375 this->_M_impl._M_finish - 1);
376 #if __cplusplus < 201103L
377 *__position = __x_copy;
379 *__position = std::forward<_Arg>(__arg);
383 #if __cplusplus >= 201103L
384 template<typename _Tp, typename _Alloc>
385 template<typename... _Args>
387 vector<_Tp, _Alloc>::
388 _M_realloc_insert(iterator __position, _Args&&... __args)
390 template<typename _Tp, typename _Alloc>
392 vector<_Tp, _Alloc>::
393 _M_realloc_insert(iterator __position, const _Tp& __x)
396 const size_type __len =
397 _M_check_len(size_type(1), "vector::_M_realloc_insert");
398 const size_type __elems_before = __position - begin();
399 pointer __new_start(this->_M_allocate(__len));
400 pointer __new_finish(__new_start);
403 // The order of the three operations is dictated by the C++11
404 // case, where the moves could alter a new element belonging
405 // to the existing vector. This is an issue only for callers
406 // taking the element by lvalue ref (see last bullet of C++11
407 // [res.on.arguments]).
408 _Alloc_traits::construct(this->_M_impl,
409 __new_start + __elems_before,
410 #if __cplusplus >= 201103L
411 std::forward<_Args>(__args)...);
415 __new_finish = pointer();
418 = std::__uninitialized_move_if_noexcept_a
419 (this->_M_impl._M_start, __position.base(),
420 __new_start, _M_get_Tp_allocator());
425 = std::__uninitialized_move_if_noexcept_a
426 (__position.base(), this->_M_impl._M_finish,
427 __new_finish, _M_get_Tp_allocator());
432 _Alloc_traits::destroy(this->_M_impl,
433 __new_start + __elems_before);
435 std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
436 _M_deallocate(__new_start, __len);
437 __throw_exception_again;
439 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
440 _M_get_Tp_allocator());
441 _M_deallocate(this->_M_impl._M_start,
442 this->_M_impl._M_end_of_storage
443 - this->_M_impl._M_start);
444 this->_M_impl._M_start = __new_start;
445 this->_M_impl._M_finish = __new_finish;
446 this->_M_impl._M_end_of_storage = __new_start + __len;
449 template<typename _Tp, typename _Alloc>
451 vector<_Tp, _Alloc>::
452 _M_fill_insert(iterator __position, size_type __n, const value_type& __x)
456 if (size_type(this->_M_impl._M_end_of_storage
457 - this->_M_impl._M_finish) >= __n)
459 #if __cplusplus < 201103L
460 value_type __x_copy = __x;
462 _Temporary_value __tmp(this, __x);
463 value_type& __x_copy = __tmp._M_val();
465 const size_type __elems_after = end() - __position;
466 pointer __old_finish(this->_M_impl._M_finish);
467 if (__elems_after > __n)
469 std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
470 this->_M_impl._M_finish,
471 this->_M_impl._M_finish,
472 _M_get_Tp_allocator());
473 this->_M_impl._M_finish += __n;
474 _GLIBCXX_MOVE_BACKWARD3(__position.base(),
475 __old_finish - __n, __old_finish);
476 std::fill(__position.base(), __position.base() + __n,
481 this->_M_impl._M_finish =
482 std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
485 _M_get_Tp_allocator());
486 std::__uninitialized_move_a(__position.base(), __old_finish,
487 this->_M_impl._M_finish,
488 _M_get_Tp_allocator());
489 this->_M_impl._M_finish += __elems_after;
490 std::fill(__position.base(), __old_finish, __x_copy);
495 const size_type __len =
496 _M_check_len(__n, "vector::_M_fill_insert");
497 const size_type __elems_before = __position - begin();
498 pointer __new_start(this->_M_allocate(__len));
499 pointer __new_finish(__new_start);
502 // See _M_realloc_insert above.
503 std::__uninitialized_fill_n_a(__new_start + __elems_before,
505 _M_get_Tp_allocator());
506 __new_finish = pointer();
509 = std::__uninitialized_move_if_noexcept_a
510 (this->_M_impl._M_start, __position.base(),
511 __new_start, _M_get_Tp_allocator());
516 = std::__uninitialized_move_if_noexcept_a
517 (__position.base(), this->_M_impl._M_finish,
518 __new_finish, _M_get_Tp_allocator());
523 std::_Destroy(__new_start + __elems_before,
524 __new_start + __elems_before + __n,
525 _M_get_Tp_allocator());
527 std::_Destroy(__new_start, __new_finish,
528 _M_get_Tp_allocator());
529 _M_deallocate(__new_start, __len);
530 __throw_exception_again;
532 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
533 _M_get_Tp_allocator());
534 _M_deallocate(this->_M_impl._M_start,
535 this->_M_impl._M_end_of_storage
536 - this->_M_impl._M_start);
537 this->_M_impl._M_start = __new_start;
538 this->_M_impl._M_finish = __new_finish;
539 this->_M_impl._M_end_of_storage = __new_start + __len;
544 #if __cplusplus >= 201103L
545 template<typename _Tp, typename _Alloc>
547 vector<_Tp, _Alloc>::
548 _M_default_append(size_type __n)
552 if (size_type(this->_M_impl._M_end_of_storage
553 - this->_M_impl._M_finish) >= __n)
555 this->_M_impl._M_finish =
556 std::__uninitialized_default_n_a(this->_M_impl._M_finish,
557 __n, _M_get_Tp_allocator());
561 const size_type __len =
562 _M_check_len(__n, "vector::_M_default_append");
563 const size_type __old_size = this->size();
564 pointer __new_start(this->_M_allocate(__len));
565 pointer __new_finish(__new_start);
569 = std::__uninitialized_move_if_noexcept_a
570 (this->_M_impl._M_start, this->_M_impl._M_finish,
571 __new_start, _M_get_Tp_allocator());
573 std::__uninitialized_default_n_a(__new_finish, __n,
574 _M_get_Tp_allocator());
578 std::_Destroy(__new_start, __new_finish,
579 _M_get_Tp_allocator());
580 _M_deallocate(__new_start, __len);
581 __throw_exception_again;
583 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
584 _M_get_Tp_allocator());
585 _M_deallocate(this->_M_impl._M_start,
586 this->_M_impl._M_end_of_storage
587 - this->_M_impl._M_start);
588 this->_M_impl._M_start = __new_start;
589 this->_M_impl._M_finish = __new_finish;
590 this->_M_impl._M_end_of_storage = __new_start + __len;
595 template<typename _Tp, typename _Alloc>
597 vector<_Tp, _Alloc>::
600 if (capacity() == size())
602 return std::__shrink_to_fit_aux<vector>::_S_do_it(*this);
606 template<typename _Tp, typename _Alloc>
607 template<typename _InputIterator>
609 vector<_Tp, _Alloc>::
610 _M_range_insert(iterator __pos, _InputIterator __first,
611 _InputIterator __last, std::input_iterator_tag)
613 for (; __first != __last; ++__first)
615 __pos = insert(__pos, *__first);
620 template<typename _Tp, typename _Alloc>
621 template<typename _ForwardIterator>
623 vector<_Tp, _Alloc>::
624 _M_range_insert(iterator __position, _ForwardIterator __first,
625 _ForwardIterator __last, std::forward_iterator_tag)
627 if (__first != __last)
629 const size_type __n = std::distance(__first, __last);
630 if (size_type(this->_M_impl._M_end_of_storage
631 - this->_M_impl._M_finish) >= __n)
633 const size_type __elems_after = end() - __position;
634 pointer __old_finish(this->_M_impl._M_finish);
635 if (__elems_after > __n)
637 std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
638 this->_M_impl._M_finish,
639 this->_M_impl._M_finish,
640 _M_get_Tp_allocator());
641 this->_M_impl._M_finish += __n;
642 _GLIBCXX_MOVE_BACKWARD3(__position.base(),
643 __old_finish - __n, __old_finish);
644 std::copy(__first, __last, __position);
648 _ForwardIterator __mid = __first;
649 std::advance(__mid, __elems_after);
650 std::__uninitialized_copy_a(__mid, __last,
651 this->_M_impl._M_finish,
652 _M_get_Tp_allocator());
653 this->_M_impl._M_finish += __n - __elems_after;
654 std::__uninitialized_move_a(__position.base(),
656 this->_M_impl._M_finish,
657 _M_get_Tp_allocator());
658 this->_M_impl._M_finish += __elems_after;
659 std::copy(__first, __mid, __position);
664 const size_type __len =
665 _M_check_len(__n, "vector::_M_range_insert");
666 pointer __new_start(this->_M_allocate(__len));
667 pointer __new_finish(__new_start);
671 = std::__uninitialized_move_if_noexcept_a
672 (this->_M_impl._M_start, __position.base(),
673 __new_start, _M_get_Tp_allocator());
675 = std::__uninitialized_copy_a(__first, __last,
677 _M_get_Tp_allocator());
679 = std::__uninitialized_move_if_noexcept_a
680 (__position.base(), this->_M_impl._M_finish,
681 __new_finish, _M_get_Tp_allocator());
685 std::_Destroy(__new_start, __new_finish,
686 _M_get_Tp_allocator());
687 _M_deallocate(__new_start, __len);
688 __throw_exception_again;
690 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
691 _M_get_Tp_allocator());
692 _M_deallocate(this->_M_impl._M_start,
693 this->_M_impl._M_end_of_storage
694 - this->_M_impl._M_start);
695 this->_M_impl._M_start = __new_start;
696 this->_M_impl._M_finish = __new_finish;
697 this->_M_impl._M_end_of_storage = __new_start + __len;
704 template<typename _Alloc>
706 vector<bool, _Alloc>::
707 _M_reallocate(size_type __n)
709 _Bit_pointer __q = this->_M_allocate(__n);
710 iterator __start(std::__addressof(*__q), 0);
711 iterator __finish(_M_copy_aligned(begin(), end(), __start));
712 this->_M_deallocate();
713 this->_M_impl._M_start = __start;
714 this->_M_impl._M_finish = __finish;
715 this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
718 template<typename _Alloc>
720 vector<bool, _Alloc>::
721 _M_fill_insert(iterator __position, size_type __n, bool __x)
725 if (capacity() - size() >= __n)
727 std::copy_backward(__position, end(),
728 this->_M_impl._M_finish + difference_type(__n));
729 std::fill(__position, __position + difference_type(__n), __x);
730 this->_M_impl._M_finish += difference_type(__n);
734 const size_type __len =
735 _M_check_len(__n, "vector<bool>::_M_fill_insert");
736 _Bit_pointer __q = this->_M_allocate(__len);
737 iterator __start(std::__addressof(*__q), 0);
738 iterator __i = _M_copy_aligned(begin(), __position, __start);
739 std::fill(__i, __i + difference_type(__n), __x);
740 iterator __finish = std::copy(__position, end(),
741 __i + difference_type(__n));
742 this->_M_deallocate();
743 this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
744 this->_M_impl._M_start = __start;
745 this->_M_impl._M_finish = __finish;
749 template<typename _Alloc>
750 template<typename _ForwardIterator>
752 vector<bool, _Alloc>::
753 _M_insert_range(iterator __position, _ForwardIterator __first,
754 _ForwardIterator __last, std::forward_iterator_tag)
756 if (__first != __last)
758 size_type __n = std::distance(__first, __last);
759 if (capacity() - size() >= __n)
761 std::copy_backward(__position, end(),
762 this->_M_impl._M_finish
763 + difference_type(__n));
764 std::copy(__first, __last, __position);
765 this->_M_impl._M_finish += difference_type(__n);
769 const size_type __len =
770 _M_check_len(__n, "vector<bool>::_M_insert_range");
771 _Bit_pointer __q = this->_M_allocate(__len);
772 iterator __start(std::__addressof(*__q), 0);
773 iterator __i = _M_copy_aligned(begin(), __position, __start);
774 __i = std::copy(__first, __last, __i);
775 iterator __finish = std::copy(__position, end(), __i);
776 this->_M_deallocate();
777 this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
778 this->_M_impl._M_start = __start;
779 this->_M_impl._M_finish = __finish;
784 template<typename _Alloc>
786 vector<bool, _Alloc>::
787 _M_insert_aux(iterator __position, bool __x)
789 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr())
791 std::copy_backward(__position, this->_M_impl._M_finish,
792 this->_M_impl._M_finish + 1);
794 ++this->_M_impl._M_finish;
798 const size_type __len =
799 _M_check_len(size_type(1), "vector<bool>::_M_insert_aux");
800 _Bit_pointer __q = this->_M_allocate(__len);
801 iterator __start(std::__addressof(*__q), 0);
802 iterator __i = _M_copy_aligned(begin(), __position, __start);
804 iterator __finish = std::copy(__position, end(), __i);
805 this->_M_deallocate();
806 this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
807 this->_M_impl._M_start = __start;
808 this->_M_impl._M_finish = __finish;
812 template<typename _Alloc>
813 typename vector<bool, _Alloc>::iterator
814 vector<bool, _Alloc>::
815 _M_erase(iterator __position)
817 if (__position + 1 != end())
818 std::copy(__position + 1, end(), __position);
819 --this->_M_impl._M_finish;
823 template<typename _Alloc>
824 typename vector<bool, _Alloc>::iterator
825 vector<bool, _Alloc>::
826 _M_erase(iterator __first, iterator __last)
828 if (__first != __last)
829 _M_erase_at_end(std::copy(__last, end(), __first));
833 #if __cplusplus >= 201103L
834 template<typename _Alloc>
836 vector<bool, _Alloc>::
839 if (capacity() - size() < int(_S_word_bit))
843 _M_reallocate(size());
851 _GLIBCXX_END_NAMESPACE_CONTAINER
854 #if __cplusplus >= 201103L
856 namespace std _GLIBCXX_VISIBILITY(default)
858 _GLIBCXX_BEGIN_NAMESPACE_VERSION
860 template<typename _Alloc>
862 hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>::
863 operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const noexcept
866 using _GLIBCXX_STD_C::_S_word_bit;
867 using _GLIBCXX_STD_C::_Bit_type;
869 const size_t __words = __b.size() / _S_word_bit;
872 const size_t __clength = __words * sizeof(_Bit_type);
873 __hash = std::_Hash_impl::hash(__b._M_impl._M_start._M_p, __clength);
876 const size_t __extrabits = __b.size() % _S_word_bit;
879 _Bit_type __hiword = *__b._M_impl._M_finish._M_p;
880 __hiword &= ~((~static_cast<_Bit_type>(0)) << __extrabits);
882 const size_t __clength
883 = (__extrabits + __CHAR_BIT__ - 1) / __CHAR_BIT__;
885 __hash = std::_Hash_impl::hash(&__hiword, __clength, __hash);
887 __hash = std::_Hash_impl::hash(&__hiword, __clength);
893 _GLIBCXX_END_NAMESPACE_VERSION
898 #endif /* _VECTOR_TCC */