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