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