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