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