libstdc++
vector.tcc
Go to the documentation of this file.
1 // Vector implementation (out of line) -*- C++ -*-
2 
3 // Copyright (C) 2001-2019 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 
59 namespace std _GLIBCXX_VISIBILITY(default)
60 {
61 _GLIBCXX_BEGIN_NAMESPACE_VERSION
62 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
63 
64  template<typename _Tp, typename _Alloc>
65  void
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;
75 #if __cplusplus >= 201103L
76  if constexpr (__use_relocate)
77  {
78  __tmp = this->_M_allocate(__n);
79  std::__relocate_a(this->_M_impl._M_start,
80  this->_M_impl._M_finish,
81  __tmp, _M_get_Tp_allocator());
82  }
83  else
84 #endif
85  {
86  __tmp = _M_allocate_and_copy(__n,
87  _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_start),
88  _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_finish));
89  std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
90  _M_get_Tp_allocator());
91  }
92  _GLIBCXX_ASAN_ANNOTATE_REINIT;
93  _M_deallocate(this->_M_impl._M_start,
94  this->_M_impl._M_end_of_storage
95  - this->_M_impl._M_start);
96  this->_M_impl._M_start = __tmp;
97  this->_M_impl._M_finish = __tmp + __old_size;
98  this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
99  }
100  }
101 
102 #if __cplusplus >= 201103L
103  template<typename _Tp, typename _Alloc>
104  template<typename... _Args>
105 #if __cplusplus > 201402L
106  typename vector<_Tp, _Alloc>::reference
107 #else
108  void
109 #endif
111  emplace_back(_Args&&... __args)
112  {
113  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
114  {
115  _GLIBCXX_ASAN_ANNOTATE_GROW(1);
116  _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
117  std::forward<_Args>(__args)...);
118  ++this->_M_impl._M_finish;
119  _GLIBCXX_ASAN_ANNOTATE_GREW(1);
120  }
121  else
122  _M_realloc_insert(end(), std::forward<_Args>(__args)...);
123 #if __cplusplus > 201402L
124  return back();
125 #endif
126  }
127 #endif
128 
129  template<typename _Tp, typename _Alloc>
130  typename vector<_Tp, _Alloc>::iterator
132 #if __cplusplus >= 201103L
133  insert(const_iterator __position, const value_type& __x)
134 #else
135  insert(iterator __position, const value_type& __x)
136 #endif
137  {
138  const size_type __n = __position - begin();
139  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
140  if (__position == end())
141  {
142  _GLIBCXX_ASAN_ANNOTATE_GROW(1);
143  _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
144  __x);
145  ++this->_M_impl._M_finish;
146  _GLIBCXX_ASAN_ANNOTATE_GREW(1);
147  }
148  else
149  {
150 #if __cplusplus >= 201103L
151  const auto __pos = begin() + (__position - cbegin());
152  // __x could be an existing element of this vector, so make a
153  // copy of it before _M_insert_aux moves elements around.
154  _Temporary_value __x_copy(this, __x);
155  _M_insert_aux(__pos, std::move(__x_copy._M_val()));
156 #else
157  _M_insert_aux(__position, __x);
158 #endif
159  }
160  else
161 #if __cplusplus >= 201103L
162  _M_realloc_insert(begin() + (__position - cbegin()), __x);
163 #else
164  _M_realloc_insert(__position, __x);
165 #endif
166 
167  return iterator(this->_M_impl._M_start + __n);
168  }
169 
170  template<typename _Tp, typename _Alloc>
171  typename vector<_Tp, _Alloc>::iterator
173  _M_erase(iterator __position)
174  {
175  if (__position + 1 != end())
176  _GLIBCXX_MOVE3(__position + 1, end(), __position);
177  --this->_M_impl._M_finish;
178  _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
179  _GLIBCXX_ASAN_ANNOTATE_SHRINK(1);
180  return __position;
181  }
182 
183  template<typename _Tp, typename _Alloc>
184  typename vector<_Tp, _Alloc>::iterator
186  _M_erase(iterator __first, iterator __last)
187  {
188  if (__first != __last)
189  {
190  if (__last != end())
191  _GLIBCXX_MOVE3(__last, end(), __first);
192  _M_erase_at_end(__first.base() + (end() - __last));
193  }
194  return __first;
195  }
196 
197  template<typename _Tp, typename _Alloc>
201  {
202  if (&__x != this)
203  {
204  _GLIBCXX_ASAN_ANNOTATE_REINIT;
205 #if __cplusplus >= 201103L
206  if (_Alloc_traits::_S_propagate_on_copy_assign())
207  {
208  if (!_Alloc_traits::_S_always_equal()
209  && _M_get_Tp_allocator() != __x._M_get_Tp_allocator())
210  {
211  // replacement allocator cannot free existing storage
212  this->clear();
213  _M_deallocate(this->_M_impl._M_start,
214  this->_M_impl._M_end_of_storage
215  - this->_M_impl._M_start);
216  this->_M_impl._M_start = nullptr;
217  this->_M_impl._M_finish = nullptr;
218  this->_M_impl._M_end_of_storage = nullptr;
219  }
220  std::__alloc_on_copy(_M_get_Tp_allocator(),
221  __x._M_get_Tp_allocator());
222  }
223 #endif
224  const size_type __xlen = __x.size();
225  if (__xlen > capacity())
226  {
227  pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(),
228  __x.end());
229  std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
230  _M_get_Tp_allocator());
231  _M_deallocate(this->_M_impl._M_start,
232  this->_M_impl._M_end_of_storage
233  - this->_M_impl._M_start);
234  this->_M_impl._M_start = __tmp;
235  this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen;
236  }
237  else if (size() >= __xlen)
238  {
239  std::_Destroy(std::copy(__x.begin(), __x.end(), begin()),
240  end(), _M_get_Tp_allocator());
241  }
242  else
243  {
244  std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(),
245  this->_M_impl._M_start);
246  std::__uninitialized_copy_a(__x._M_impl._M_start + size(),
247  __x._M_impl._M_finish,
248  this->_M_impl._M_finish,
249  _M_get_Tp_allocator());
250  }
251  this->_M_impl._M_finish = this->_M_impl._M_start + __xlen;
252  }
253  return *this;
254  }
255 
256  template<typename _Tp, typename _Alloc>
257  void
259  _M_fill_assign(size_t __n, const value_type& __val)
260  {
261  if (__n > capacity())
262  {
263  vector __tmp(__n, __val, _M_get_Tp_allocator());
264  __tmp._M_impl._M_swap_data(this->_M_impl);
265  }
266  else if (__n > size())
267  {
268  std::fill(begin(), end(), __val);
269  const size_type __add = __n - size();
270  _GLIBCXX_ASAN_ANNOTATE_GROW(__add);
271  this->_M_impl._M_finish =
272  std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
273  __add, __val, _M_get_Tp_allocator());
274  _GLIBCXX_ASAN_ANNOTATE_GREW(__add);
275  }
276  else
277  _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val));
278  }
279 
280  template<typename _Tp, typename _Alloc>
281  template<typename _InputIterator>
282  void
284  _M_assign_aux(_InputIterator __first, _InputIterator __last,
286  {
287  pointer __cur(this->_M_impl._M_start);
288  for (; __first != __last && __cur != this->_M_impl._M_finish;
289  ++__cur, (void)++__first)
290  *__cur = *__first;
291  if (__first == __last)
292  _M_erase_at_end(__cur);
293  else
294  _M_range_insert(end(), __first, __last,
295  std::__iterator_category(__first));
296  }
297 
298  template<typename _Tp, typename _Alloc>
299  template<typename _ForwardIterator>
300  void
302  _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
304  {
305  const size_type __len = std::distance(__first, __last);
306 
307  if (__len > capacity())
308  {
309  _S_check_init_len(__len, _M_get_Tp_allocator());
310  pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
311  std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
312  _M_get_Tp_allocator());
313  _GLIBCXX_ASAN_ANNOTATE_REINIT;
314  _M_deallocate(this->_M_impl._M_start,
315  this->_M_impl._M_end_of_storage
316  - this->_M_impl._M_start);
317  this->_M_impl._M_start = __tmp;
318  this->_M_impl._M_finish = this->_M_impl._M_start + __len;
319  this->_M_impl._M_end_of_storage = this->_M_impl._M_finish;
320  }
321  else if (size() >= __len)
322  _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start));
323  else
324  {
325  _ForwardIterator __mid = __first;
326  std::advance(__mid, size());
327  std::copy(__first, __mid, this->_M_impl._M_start);
328  const size_type __attribute__((__unused__)) __n = __len - size();
329  _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
330  this->_M_impl._M_finish =
331  std::__uninitialized_copy_a(__mid, __last,
332  this->_M_impl._M_finish,
333  _M_get_Tp_allocator());
334  _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
335  }
336  }
337 
338 #if __cplusplus >= 201103L
339  template<typename _Tp, typename _Alloc>
340  auto
342  _M_insert_rval(const_iterator __position, value_type&& __v) -> iterator
343  {
344  const auto __n = __position - cbegin();
345  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
346  if (__position == cend())
347  {
348  _GLIBCXX_ASAN_ANNOTATE_GROW(1);
349  _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
350  std::move(__v));
351  ++this->_M_impl._M_finish;
352  _GLIBCXX_ASAN_ANNOTATE_GREW(1);
353  }
354  else
355  _M_insert_aux(begin() + __n, std::move(__v));
356  else
357  _M_realloc_insert(begin() + __n, std::move(__v));
358 
359  return iterator(this->_M_impl._M_start + __n);
360  }
361 
362  template<typename _Tp, typename _Alloc>
363  template<typename... _Args>
364  auto
366  _M_emplace_aux(const_iterator __position, _Args&&... __args)
367  -> iterator
368  {
369  const auto __n = __position - cbegin();
370  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
371  if (__position == cend())
372  {
373  _GLIBCXX_ASAN_ANNOTATE_GROW(1);
374  _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
375  std::forward<_Args>(__args)...);
376  ++this->_M_impl._M_finish;
377  _GLIBCXX_ASAN_ANNOTATE_GREW(1);
378  }
379  else
380  {
381  // We need to construct a temporary because something in __args...
382  // could alias one of the elements of the container and so we
383  // need to use it before _M_insert_aux moves elements around.
384  _Temporary_value __tmp(this, std::forward<_Args>(__args)...);
385  _M_insert_aux(begin() + __n, std::move(__tmp._M_val()));
386  }
387  else
388  _M_realloc_insert(begin() + __n, std::forward<_Args>(__args)...);
389 
390  return iterator(this->_M_impl._M_start + __n);
391  }
392 
393  template<typename _Tp, typename _Alloc>
394  template<typename _Arg>
395  void
397  _M_insert_aux(iterator __position, _Arg&& __arg)
398 #else
399  template<typename _Tp, typename _Alloc>
400  void
402  _M_insert_aux(iterator __position, const _Tp& __x)
403 #endif
404  {
405  _GLIBCXX_ASAN_ANNOTATE_GROW(1);
406  _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
407  _GLIBCXX_MOVE(*(this->_M_impl._M_finish - 1)));
408  ++this->_M_impl._M_finish;
409  _GLIBCXX_ASAN_ANNOTATE_GREW(1);
410 #if __cplusplus < 201103L
411  _Tp __x_copy = __x;
412 #endif
413  _GLIBCXX_MOVE_BACKWARD3(__position.base(),
414  this->_M_impl._M_finish - 2,
415  this->_M_impl._M_finish - 1);
416 #if __cplusplus < 201103L
417  *__position = __x_copy;
418 #else
419  *__position = std::forward<_Arg>(__arg);
420 #endif
421  }
422 
423 #if __cplusplus >= 201103L
424  template<typename _Tp, typename _Alloc>
425  template<typename... _Args>
426  void
428  _M_realloc_insert(iterator __position, _Args&&... __args)
429 #else
430  template<typename _Tp, typename _Alloc>
431  void
433  _M_realloc_insert(iterator __position, const _Tp& __x)
434 #endif
435  {
436  const size_type __len =
437  _M_check_len(size_type(1), "vector::_M_realloc_insert");
438  pointer __old_start = this->_M_impl._M_start;
439  pointer __old_finish = this->_M_impl._M_finish;
440  const size_type __elems_before = __position - begin();
441  pointer __new_start(this->_M_allocate(__len));
442  pointer __new_finish(__new_start);
443  __try
444  {
445  // The order of the three operations is dictated by the C++11
446  // case, where the moves could alter a new element belonging
447  // to the existing vector. This is an issue only for callers
448  // taking the element by lvalue ref (see last bullet of C++11
449  // [res.on.arguments]).
450  _Alloc_traits::construct(this->_M_impl,
451  __new_start + __elems_before,
452 #if __cplusplus >= 201103L
453  std::forward<_Args>(__args)...);
454 #else
455  __x);
456 #endif
457  __new_finish = pointer();
458 
459 #if __cplusplus >= 201103L
460  if constexpr (__use_relocate)
461  {
462  __new_finish
463  = std::__relocate_a
464  (__old_start, __position.base(),
465  __new_start, _M_get_Tp_allocator());
466 
467  ++__new_finish;
468 
469  __new_finish
470  = std::__relocate_a
471  (__position.base(), __old_finish,
472  __new_finish, _M_get_Tp_allocator());
473  }
474  else
475 #endif
476  {
477  __new_finish
478  = std::__uninitialized_move_if_noexcept_a
479  (__old_start, __position.base(),
480  __new_start, _M_get_Tp_allocator());
481 
482  ++__new_finish;
483 
484  __new_finish
485  = std::__uninitialized_move_if_noexcept_a
486  (__position.base(), __old_finish,
487  __new_finish, _M_get_Tp_allocator());
488  }
489  }
490  __catch(...)
491  {
492  if (!__new_finish)
493  _Alloc_traits::destroy(this->_M_impl,
494  __new_start + __elems_before);
495  else
496  std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
497  _M_deallocate(__new_start, __len);
498  __throw_exception_again;
499  }
500 #if __cplusplus >= 201103L
501  if constexpr (!__use_relocate)
502 #endif
503  std::_Destroy(__old_start, __old_finish, _M_get_Tp_allocator());
504  _GLIBCXX_ASAN_ANNOTATE_REINIT;
505  _M_deallocate(__old_start,
506  this->_M_impl._M_end_of_storage - __old_start);
507  this->_M_impl._M_start = __new_start;
508  this->_M_impl._M_finish = __new_finish;
509  this->_M_impl._M_end_of_storage = __new_start + __len;
510  }
511 
512  template<typename _Tp, typename _Alloc>
513  void
515  _M_fill_insert(iterator __position, size_type __n, const value_type& __x)
516  {
517  if (__n != 0)
518  {
519  if (size_type(this->_M_impl._M_end_of_storage
520  - this->_M_impl._M_finish) >= __n)
521  {
522 #if __cplusplus < 201103L
523  value_type __x_copy = __x;
524 #else
525  _Temporary_value __tmp(this, __x);
526  value_type& __x_copy = __tmp._M_val();
527 #endif
528  const size_type __elems_after = end() - __position;
529  pointer __old_finish(this->_M_impl._M_finish);
530  if (__elems_after > __n)
531  {
532  _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
533  std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
534  this->_M_impl._M_finish,
535  this->_M_impl._M_finish,
536  _M_get_Tp_allocator());
537  this->_M_impl._M_finish += __n;
538  _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
539  _GLIBCXX_MOVE_BACKWARD3(__position.base(),
540  __old_finish - __n, __old_finish);
541  std::fill(__position.base(), __position.base() + __n,
542  __x_copy);
543  }
544  else
545  {
546  _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
547  this->_M_impl._M_finish =
548  std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
549  __n - __elems_after,
550  __x_copy,
551  _M_get_Tp_allocator());
552  _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after);
553  std::__uninitialized_move_a(__position.base(), __old_finish,
554  this->_M_impl._M_finish,
555  _M_get_Tp_allocator());
556  this->_M_impl._M_finish += __elems_after;
557  _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after);
558  std::fill(__position.base(), __old_finish, __x_copy);
559  }
560  }
561  else
562  {
563  const size_type __len =
564  _M_check_len(__n, "vector::_M_fill_insert");
565  const size_type __elems_before = __position - begin();
566  pointer __new_start(this->_M_allocate(__len));
567  pointer __new_finish(__new_start);
568  __try
569  {
570  // See _M_realloc_insert above.
571  std::__uninitialized_fill_n_a(__new_start + __elems_before,
572  __n, __x,
573  _M_get_Tp_allocator());
574  __new_finish = pointer();
575 
576  __new_finish
577  = std::__uninitialized_move_if_noexcept_a
578  (this->_M_impl._M_start, __position.base(),
579  __new_start, _M_get_Tp_allocator());
580 
581  __new_finish += __n;
582 
583  __new_finish
584  = std::__uninitialized_move_if_noexcept_a
585  (__position.base(), this->_M_impl._M_finish,
586  __new_finish, _M_get_Tp_allocator());
587  }
588  __catch(...)
589  {
590  if (!__new_finish)
591  std::_Destroy(__new_start + __elems_before,
592  __new_start + __elems_before + __n,
593  _M_get_Tp_allocator());
594  else
595  std::_Destroy(__new_start, __new_finish,
596  _M_get_Tp_allocator());
597  _M_deallocate(__new_start, __len);
598  __throw_exception_again;
599  }
600  std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
601  _M_get_Tp_allocator());
602  _GLIBCXX_ASAN_ANNOTATE_REINIT;
603  _M_deallocate(this->_M_impl._M_start,
604  this->_M_impl._M_end_of_storage
605  - this->_M_impl._M_start);
606  this->_M_impl._M_start = __new_start;
607  this->_M_impl._M_finish = __new_finish;
608  this->_M_impl._M_end_of_storage = __new_start + __len;
609  }
610  }
611  }
612 
613 #if __cplusplus >= 201103L
614  template<typename _Tp, typename _Alloc>
615  void
617  _M_default_append(size_type __n)
618  {
619  if (__n != 0)
620  {
621  const size_type __size = size();
622  size_type __navail = size_type(this->_M_impl._M_end_of_storage
623  - this->_M_impl._M_finish);
624 
625  if (__size > max_size() || __navail > max_size() - __size)
626  __builtin_unreachable();
627 
628  if (__navail >= __n)
629  {
630  _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
631  this->_M_impl._M_finish =
632  std::__uninitialized_default_n_a(this->_M_impl._M_finish,
633  __n, _M_get_Tp_allocator());
634  _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
635  }
636  else
637  {
638  const size_type __len =
639  _M_check_len(__n, "vector::_M_default_append");
640  pointer __new_start(this->_M_allocate(__len));
641 #if __cplusplus >= 201103L
642  if constexpr (__use_relocate)
643  {
644  __try
645  {
646  std::__uninitialized_default_n_a(__new_start + __size,
647  __n, _M_get_Tp_allocator());
648  }
649  __catch(...)
650  {
651  _M_deallocate(__new_start, __len);
652  __throw_exception_again;
653  }
654  std::__relocate_a(this->_M_impl._M_start,
655  this->_M_impl._M_finish,
656  __new_start, _M_get_Tp_allocator());
657  }
658  else
659 #endif
660  {
661  pointer __destroy_from = pointer();
662  __try
663  {
664  std::__uninitialized_default_n_a(__new_start + __size,
665  __n, _M_get_Tp_allocator());
666  __destroy_from = __new_start + __size;
667  std::__uninitialized_move_if_noexcept_a(
668  this->_M_impl._M_start, this->_M_impl._M_finish,
669  __new_start, _M_get_Tp_allocator());
670  }
671  __catch(...)
672  {
673  if (__destroy_from)
674  std::_Destroy(__destroy_from, __destroy_from + __n,
675  _M_get_Tp_allocator());
676  _M_deallocate(__new_start, __len);
677  __throw_exception_again;
678  }
679  std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
680  _M_get_Tp_allocator());
681  }
682  _GLIBCXX_ASAN_ANNOTATE_REINIT;
683  _M_deallocate(this->_M_impl._M_start,
684  this->_M_impl._M_end_of_storage
685  - this->_M_impl._M_start);
686  this->_M_impl._M_start = __new_start;
687  this->_M_impl._M_finish = __new_start + __size + __n;
688  this->_M_impl._M_end_of_storage = __new_start + __len;
689  }
690  }
691  }
692 
693  template<typename _Tp, typename _Alloc>
694  bool
697  {
698  if (capacity() == size())
699  return false;
700  _GLIBCXX_ASAN_ANNOTATE_REINIT;
701  return std::__shrink_to_fit_aux<vector>::_S_do_it(*this);
702  }
703 #endif
704 
705  template<typename _Tp, typename _Alloc>
706  template<typename _InputIterator>
707  void
709  _M_range_insert(iterator __pos, _InputIterator __first,
710  _InputIterator __last, std::input_iterator_tag)
711  {
712  if (__pos == end())
713  {
714  for (; __first != __last; ++__first)
715  insert(end(), *__first);
716  }
717  else if (__first != __last)
718  {
719  vector __tmp(__first, __last, _M_get_Tp_allocator());
720  insert(__pos,
721  _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.begin()),
722  _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.end()));
723  }
724  }
725 
726  template<typename _Tp, typename _Alloc>
727  template<typename _ForwardIterator>
728  void
730  _M_range_insert(iterator __position, _ForwardIterator __first,
731  _ForwardIterator __last, std::forward_iterator_tag)
732  {
733  if (__first != __last)
734  {
735  const size_type __n = std::distance(__first, __last);
736  if (size_type(this->_M_impl._M_end_of_storage
737  - this->_M_impl._M_finish) >= __n)
738  {
739  const size_type __elems_after = end() - __position;
740  pointer __old_finish(this->_M_impl._M_finish);
741  if (__elems_after > __n)
742  {
743  _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
744  std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
745  this->_M_impl._M_finish,
746  this->_M_impl._M_finish,
747  _M_get_Tp_allocator());
748  this->_M_impl._M_finish += __n;
749  _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
750  _GLIBCXX_MOVE_BACKWARD3(__position.base(),
751  __old_finish - __n, __old_finish);
752  std::copy(__first, __last, __position);
753  }
754  else
755  {
756  _ForwardIterator __mid = __first;
757  std::advance(__mid, __elems_after);
758  _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
759  std::__uninitialized_copy_a(__mid, __last,
760  this->_M_impl._M_finish,
761  _M_get_Tp_allocator());
762  this->_M_impl._M_finish += __n - __elems_after;
763  _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after);
764  std::__uninitialized_move_a(__position.base(),
765  __old_finish,
766  this->_M_impl._M_finish,
767  _M_get_Tp_allocator());
768  this->_M_impl._M_finish += __elems_after;
769  _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after);
770  std::copy(__first, __mid, __position);
771  }
772  }
773  else
774  {
775  const size_type __len =
776  _M_check_len(__n, "vector::_M_range_insert");
777  pointer __new_start(this->_M_allocate(__len));
778  pointer __new_finish(__new_start);
779  __try
780  {
781  __new_finish
782  = std::__uninitialized_move_if_noexcept_a
783  (this->_M_impl._M_start, __position.base(),
784  __new_start, _M_get_Tp_allocator());
785  __new_finish
786  = std::__uninitialized_copy_a(__first, __last,
787  __new_finish,
788  _M_get_Tp_allocator());
789  __new_finish
790  = std::__uninitialized_move_if_noexcept_a
791  (__position.base(), this->_M_impl._M_finish,
792  __new_finish, _M_get_Tp_allocator());
793  }
794  __catch(...)
795  {
796  std::_Destroy(__new_start, __new_finish,
797  _M_get_Tp_allocator());
798  _M_deallocate(__new_start, __len);
799  __throw_exception_again;
800  }
801  std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
802  _M_get_Tp_allocator());
803  _GLIBCXX_ASAN_ANNOTATE_REINIT;
804  _M_deallocate(this->_M_impl._M_start,
805  this->_M_impl._M_end_of_storage
806  - this->_M_impl._M_start);
807  this->_M_impl._M_start = __new_start;
808  this->_M_impl._M_finish = __new_finish;
809  this->_M_impl._M_end_of_storage = __new_start + __len;
810  }
811  }
812  }
813 
814 
815  // vector<bool>
816  template<typename _Alloc>
817  void
819  _M_reallocate(size_type __n)
820  {
821  _Bit_pointer __q = this->_M_allocate(__n);
822  iterator __start(std::__addressof(*__q), 0);
823  iterator __finish(_M_copy_aligned(begin(), end(), __start));
824  this->_M_deallocate();
825  this->_M_impl._M_start = __start;
826  this->_M_impl._M_finish = __finish;
827  this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
828  }
829 
830  template<typename _Alloc>
831  void
833  _M_fill_insert(iterator __position, size_type __n, bool __x)
834  {
835  if (__n == 0)
836  return;
837  if (capacity() - size() >= __n)
838  {
839  std::copy_backward(__position, end(),
840  this->_M_impl._M_finish + difference_type(__n));
841  std::fill(__position, __position + difference_type(__n), __x);
842  this->_M_impl._M_finish += difference_type(__n);
843  }
844  else
845  {
846  const size_type __len =
847  _M_check_len(__n, "vector<bool>::_M_fill_insert");
848  _Bit_pointer __q = this->_M_allocate(__len);
849  iterator __start(std::__addressof(*__q), 0);
850  iterator __i = _M_copy_aligned(begin(), __position, __start);
851  std::fill(__i, __i + difference_type(__n), __x);
852  iterator __finish = std::copy(__position, end(),
853  __i + difference_type(__n));
854  this->_M_deallocate();
855  this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
856  this->_M_impl._M_start = __start;
857  this->_M_impl._M_finish = __finish;
858  }
859  }
860 
861  template<typename _Alloc>
862  template<typename _ForwardIterator>
863  void
865  _M_insert_range(iterator __position, _ForwardIterator __first,
866  _ForwardIterator __last, std::forward_iterator_tag)
867  {
868  if (__first != __last)
869  {
870  size_type __n = std::distance(__first, __last);
871  if (capacity() - size() >= __n)
872  {
873  std::copy_backward(__position, end(),
874  this->_M_impl._M_finish
875  + difference_type(__n));
876  std::copy(__first, __last, __position);
877  this->_M_impl._M_finish += difference_type(__n);
878  }
879  else
880  {
881  const size_type __len =
882  _M_check_len(__n, "vector<bool>::_M_insert_range");
883  _Bit_pointer __q = this->_M_allocate(__len);
884  iterator __start(std::__addressof(*__q), 0);
885  iterator __i = _M_copy_aligned(begin(), __position, __start);
886  __i = std::copy(__first, __last, __i);
887  iterator __finish = std::copy(__position, end(), __i);
888  this->_M_deallocate();
889  this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
890  this->_M_impl._M_start = __start;
891  this->_M_impl._M_finish = __finish;
892  }
893  }
894  }
895 
896  template<typename _Alloc>
897  void
899  _M_insert_aux(iterator __position, bool __x)
900  {
901  if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr())
902  {
903  std::copy_backward(__position, this->_M_impl._M_finish,
904  this->_M_impl._M_finish + 1);
905  *__position = __x;
906  ++this->_M_impl._M_finish;
907  }
908  else
909  {
910  const size_type __len =
911  _M_check_len(size_type(1), "vector<bool>::_M_insert_aux");
912  _Bit_pointer __q = this->_M_allocate(__len);
913  iterator __start(std::__addressof(*__q), 0);
914  iterator __i = _M_copy_aligned(begin(), __position, __start);
915  *__i++ = __x;
916  iterator __finish = std::copy(__position, end(), __i);
917  this->_M_deallocate();
918  this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
919  this->_M_impl._M_start = __start;
920  this->_M_impl._M_finish = __finish;
921  }
922  }
923 
924  template<typename _Alloc>
925  typename vector<bool, _Alloc>::iterator
927  _M_erase(iterator __position)
928  {
929  if (__position + 1 != end())
930  std::copy(__position + 1, end(), __position);
931  --this->_M_impl._M_finish;
932  return __position;
933  }
934 
935  template<typename _Alloc>
936  typename vector<bool, _Alloc>::iterator
938  _M_erase(iterator __first, iterator __last)
939  {
940  if (__first != __last)
941  _M_erase_at_end(std::copy(__last, end(), __first));
942  return __first;
943  }
944 
945 #if __cplusplus >= 201103L
946  template<typename _Alloc>
947  bool
950  {
951  if (capacity() - size() < int(_S_word_bit))
952  return false;
953  __try
954  {
955  _M_reallocate(size());
956  return true;
957  }
958  __catch(...)
959  { return false; }
960  }
961 #endif
962 
963 _GLIBCXX_END_NAMESPACE_CONTAINER
964 _GLIBCXX_END_NAMESPACE_VERSION
965 } // namespace std
966 
967 #if __cplusplus >= 201103L
968 
969 namespace std _GLIBCXX_VISIBILITY(default)
970 {
971 _GLIBCXX_BEGIN_NAMESPACE_VERSION
972 
973  template<typename _Alloc>
974  size_t
976  operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const noexcept
977  {
978  size_t __hash = 0;
979  using _GLIBCXX_STD_C::_S_word_bit;
980  using _GLIBCXX_STD_C::_Bit_type;
981 
982  const size_t __words = __b.size() / _S_word_bit;
983  if (__words)
984  {
985  const size_t __clength = __words * sizeof(_Bit_type);
986  __hash = std::_Hash_impl::hash(__b._M_impl._M_start._M_p, __clength);
987  }
988 
989  const size_t __extrabits = __b.size() % _S_word_bit;
990  if (__extrabits)
991  {
992  _Bit_type __hiword = *__b._M_impl._M_finish._M_p;
993  __hiword &= ~((~static_cast<_Bit_type>(0)) << __extrabits);
994 
995  const size_t __clength
996  = (__extrabits + __CHAR_BIT__ - 1) / __CHAR_BIT__;
997  if (__words)
998  __hash = std::_Hash_impl::hash(&__hiword, __clength, __hash);
999  else
1000  __hash = std::_Hash_impl::hash(&__hiword, __clength);
1001  }
1002 
1003  return __hash;
1004  }
1005 
1006 _GLIBCXX_END_NAMESPACE_VERSION
1007 } // namespace std
1008 
1009 #endif // C++11
1010 
1011 #undef _GLIBCXX_ASAN_ANNOTATE_REINIT
1012 #undef _GLIBCXX_ASAN_ANNOTATE_GROW
1013 #undef _GLIBCXX_ASAN_ANNOTATE_GREW
1014 #undef _GLIBCXX_ASAN_ANNOTATE_SHRINK
1015 
1016 #endif /* _VECTOR_TCC */
iterator end() noexcept
Definition: stl_vector.h:790
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list. ...
iterator begin() noexcept
Definition: stl_vector.h:772
vector & operator=(const vector &__x)
Vector assignment operator.
Definition: vector.tcc:200
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:47
Primary class template hash.
Definition: system_error:142
constexpr auto cend(const _Container &__cont) noexcept(noexcept(std::end(__cont))) -> decltype(std::end(__cont))
Return an iterator pointing to one past the last element of the const container.
Definition: range_access.h:127
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
ISO C++ entities toplevel namespace is std.
Marking input iterators.
void _Destroy(_Tp *__pointer)
Definition: stl_construct.h:97
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
size_type size() const noexcept
Definition: stl_vector.h:879
_GLIBCXX17_CONSTEXPR void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
size_type capacity() const noexcept
Definition: stl_vector.h:959
void reserve(size_type __n)
Attempt to preallocate enough memory for specified number of elements.
Definition: vector.tcc:67
Forward iterators support a superset of input iterator operations.
_OI fill_n(_OI __first, _Size __n, const _Tp &__value)
Fills the range [first,first+n) with copies of value.
Definition: stl_algobase.h:802
constexpr auto cbegin(const _Container &__cont) noexcept(noexcept(std::begin(__cont))) -> decltype(std::begin(__cont))
Return an iterator pointing to the first element of the const container.
Definition: range_access.h:116
A standard container which offers fixed time access to individual elements in any order...
Definition: stl_vector.h:386