1 | // Vector implementation (out of line) -*- C++ -*- |
2 | |
3 | // Copyright (C) 2001-2024 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 | _GLIBCXX20_CONSTEXPR |
66 | void |
67 | vector<_Tp, _Alloc>:: |
68 | reserve(size_type __n) |
69 | { |
70 | if (__n > this->max_size()) |
71 | __throw_length_error(__N("vector::reserve" )); |
72 | if (this->capacity() < __n) |
73 | { |
74 | const size_type __old_size = size(); |
75 | pointer __tmp; |
76 | #if __cplusplus >= 201103L |
77 | if _GLIBCXX17_CONSTEXPR (_S_use_relocate()) |
78 | { |
79 | __tmp = this->_M_allocate(__n); |
80 | _S_relocate(first: this->_M_impl._M_start, last: this->_M_impl._M_finish, |
81 | result: __tmp, alloc&: _M_get_Tp_allocator()); |
82 | } |
83 | else |
84 | #endif |
85 | { |
86 | __tmp = _M_allocate_and_copy(__n, |
87 | _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_start), |
88 | _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_finish)); |
89 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, |
90 | _M_get_Tp_allocator()); |
91 | } |
92 | _GLIBCXX_ASAN_ANNOTATE_REINIT; |
93 | _M_deallocate(this->_M_impl._M_start, |
94 | this->_M_impl._M_end_of_storage |
95 | - this->_M_impl._M_start); |
96 | this->_M_impl._M_start = __tmp; |
97 | this->_M_impl._M_finish = __tmp + __old_size; |
98 | this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; |
99 | } |
100 | } |
101 | |
102 | #if __cplusplus >= 201103L |
103 | template<typename _Tp, typename _Alloc> |
104 | template<typename... _Args> |
105 | #if __cplusplus > 201402L |
106 | _GLIBCXX20_CONSTEXPR |
107 | typename vector<_Tp, _Alloc>::reference |
108 | #else |
109 | void |
110 | #endif |
111 | vector<_Tp, _Alloc>:: |
112 | emplace_back(_Args&&... __args) |
113 | { |
114 | if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) |
115 | { |
116 | _GLIBCXX_ASAN_ANNOTATE_GROW(1); |
117 | _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, |
118 | std::forward<_Args>(__args)...); |
119 | ++this->_M_impl._M_finish; |
120 | _GLIBCXX_ASAN_ANNOTATE_GREW(1); |
121 | } |
122 | else |
123 | _M_realloc_append(std::forward<_Args>(__args)...); |
124 | #if __cplusplus > 201402L |
125 | return back(); |
126 | #endif |
127 | } |
128 | #endif |
129 | |
130 | template<typename _Tp, typename _Alloc> |
131 | _GLIBCXX20_CONSTEXPR |
132 | typename vector<_Tp, _Alloc>::iterator |
133 | vector<_Tp, _Alloc>:: |
134 | #if __cplusplus >= 201103L |
135 | insert(const_iterator __position, const value_type& __x) |
136 | #else |
137 | insert(iterator __position, const value_type& __x) |
138 | #endif |
139 | { |
140 | const size_type __n = __position - begin(); |
141 | if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) |
142 | { |
143 | __glibcxx_assert(__position != const_iterator()); |
144 | if (!(__position != const_iterator())) |
145 | __builtin_unreachable(); // PR 106434 |
146 | |
147 | if (__position == end()) |
148 | { |
149 | _GLIBCXX_ASAN_ANNOTATE_GROW(1); |
150 | _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, |
151 | __x); |
152 | ++this->_M_impl._M_finish; |
153 | _GLIBCXX_ASAN_ANNOTATE_GREW(1); |
154 | } |
155 | else |
156 | { |
157 | #if __cplusplus >= 201103L |
158 | const auto __pos = begin() + (__position - cbegin()); |
159 | // __x could be an existing element of this vector, so make a |
160 | // copy of it before _M_insert_aux moves elements around. |
161 | _Temporary_value __x_copy(this, __x); |
162 | _M_insert_aux(__pos, std::move(__x_copy._M_val())); |
163 | #else |
164 | _M_insert_aux(__position, __x); |
165 | #endif |
166 | } |
167 | } |
168 | else |
169 | #if __cplusplus >= 201103L |
170 | _M_realloc_insert(begin() + (__position - cbegin()), __x); |
171 | #else |
172 | _M_realloc_insert(__position, __x); |
173 | #endif |
174 | |
175 | return iterator(this->_M_impl._M_start + __n); |
176 | } |
177 | |
178 | template<typename _Tp, typename _Alloc> |
179 | _GLIBCXX20_CONSTEXPR |
180 | typename vector<_Tp, _Alloc>::iterator |
181 | vector<_Tp, _Alloc>:: |
182 | _M_erase(iterator __position) |
183 | { |
184 | if (__position + 1 != end()) |
185 | _GLIBCXX_MOVE3(__position + 1, end(), __position); |
186 | --this->_M_impl._M_finish; |
187 | _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish); |
188 | _GLIBCXX_ASAN_ANNOTATE_SHRINK(1); |
189 | return __position; |
190 | } |
191 | |
192 | template<typename _Tp, typename _Alloc> |
193 | _GLIBCXX20_CONSTEXPR |
194 | typename vector<_Tp, _Alloc>::iterator |
195 | vector<_Tp, _Alloc>:: |
196 | _M_erase(iterator __first, iterator __last) |
197 | { |
198 | if (__first != __last) |
199 | { |
200 | if (__last != end()) |
201 | _GLIBCXX_MOVE3(__last, end(), __first); |
202 | _M_erase_at_end(pos: __first.base() + (end() - __last)); |
203 | } |
204 | return __first; |
205 | } |
206 | |
207 | template<typename _Tp, typename _Alloc> |
208 | _GLIBCXX20_CONSTEXPR |
209 | vector<_Tp, _Alloc>& |
210 | vector<_Tp, _Alloc>:: |
211 | operator=(const vector<_Tp, _Alloc>& __x) |
212 | { |
213 | if (std::__addressof(__x) != this) |
214 | { |
215 | _GLIBCXX_ASAN_ANNOTATE_REINIT; |
216 | #if __cplusplus >= 201103L |
217 | if (_Alloc_traits::_S_propagate_on_copy_assign()) |
218 | { |
219 | if (!_Alloc_traits::_S_always_equal() |
220 | && _M_get_Tp_allocator() != __x._M_get_Tp_allocator()) |
221 | { |
222 | // replacement allocator cannot free existing storage |
223 | this->clear(); |
224 | _M_deallocate(this->_M_impl._M_start, |
225 | this->_M_impl._M_end_of_storage |
226 | - this->_M_impl._M_start); |
227 | this->_M_impl._M_start = nullptr; |
228 | this->_M_impl._M_finish = nullptr; |
229 | this->_M_impl._M_end_of_storage = nullptr; |
230 | } |
231 | std::__alloc_on_copy(_M_get_Tp_allocator(), |
232 | __x._M_get_Tp_allocator()); |
233 | } |
234 | #endif |
235 | const size_type __xlen = __x.size(); |
236 | if (__xlen > capacity()) |
237 | { |
238 | pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(), |
239 | __x.end()); |
240 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, |
241 | _M_get_Tp_allocator()); |
242 | _M_deallocate(this->_M_impl._M_start, |
243 | this->_M_impl._M_end_of_storage |
244 | - this->_M_impl._M_start); |
245 | this->_M_impl._M_start = __tmp; |
246 | this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen; |
247 | } |
248 | else if (size() >= __xlen) |
249 | { |
250 | std::_Destroy(std::copy(__x.begin(), __x.end(), begin()), |
251 | end(), _M_get_Tp_allocator()); |
252 | } |
253 | else |
254 | { |
255 | std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(), |
256 | this->_M_impl._M_start); |
257 | std::__uninitialized_copy_a(__x._M_impl._M_start + size(), |
258 | __x._M_impl._M_finish, |
259 | this->_M_impl._M_finish, |
260 | _M_get_Tp_allocator()); |
261 | } |
262 | this->_M_impl._M_finish = this->_M_impl._M_start + __xlen; |
263 | } |
264 | return *this; |
265 | } |
266 | |
267 | template<typename _Tp, typename _Alloc> |
268 | _GLIBCXX20_CONSTEXPR |
269 | void |
270 | vector<_Tp, _Alloc>:: |
271 | _M_fill_assign(size_t __n, const value_type& __val) |
272 | { |
273 | const size_type __sz = size(); |
274 | if (__n > capacity()) |
275 | { |
276 | if (__n <= __sz) |
277 | __builtin_unreachable(); |
278 | vector __tmp(__n, __val, _M_get_Tp_allocator()); |
279 | __tmp._M_impl._M_swap_data(this->_M_impl); |
280 | } |
281 | else if (__n > __sz) |
282 | { |
283 | std::fill(begin(), end(), __val); |
284 | const size_type __add = __n - __sz; |
285 | _GLIBCXX_ASAN_ANNOTATE_GROW(__add); |
286 | this->_M_impl._M_finish = |
287 | std::__uninitialized_fill_n_a(this->_M_impl._M_finish, |
288 | __add, __val, _M_get_Tp_allocator()); |
289 | _GLIBCXX_ASAN_ANNOTATE_GREW(__add); |
290 | } |
291 | else |
292 | _M_erase_at_end(pos: std::fill_n(this->_M_impl._M_start, __n, __val)); |
293 | } |
294 | |
295 | template<typename _Tp, typename _Alloc> |
296 | template<typename _InputIterator> |
297 | _GLIBCXX20_CONSTEXPR |
298 | void |
299 | vector<_Tp, _Alloc>:: |
300 | _M_assign_aux(_InputIterator __first, _InputIterator __last, |
301 | std::input_iterator_tag) |
302 | { |
303 | pointer __cur(this->_M_impl._M_start); |
304 | for (; __first != __last && __cur != this->_M_impl._M_finish; |
305 | ++__cur, (void)++__first) |
306 | *__cur = *__first; |
307 | if (__first == __last) |
308 | _M_erase_at_end(pos: __cur); |
309 | else |
310 | _M_range_insert(end(), __first, __last, |
311 | std::__iterator_category(__first)); |
312 | } |
313 | |
314 | template<typename _Tp, typename _Alloc> |
315 | template<typename _ForwardIterator> |
316 | _GLIBCXX20_CONSTEXPR |
317 | void |
318 | vector<_Tp, _Alloc>:: |
319 | _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, |
320 | std::forward_iterator_tag) |
321 | { |
322 | const size_type __sz = size(); |
323 | const size_type __len = std::distance(__first, __last); |
324 | |
325 | if (__len > capacity()) |
326 | { |
327 | if (__len <= __sz) |
328 | __builtin_unreachable(); |
329 | |
330 | _S_check_init_len(n: __len, a: _M_get_Tp_allocator()); |
331 | pointer __tmp(_M_allocate_and_copy(__len, __first, __last)); |
332 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, |
333 | _M_get_Tp_allocator()); |
334 | _GLIBCXX_ASAN_ANNOTATE_REINIT; |
335 | _M_deallocate(this->_M_impl._M_start, |
336 | this->_M_impl._M_end_of_storage |
337 | - this->_M_impl._M_start); |
338 | this->_M_impl._M_start = __tmp; |
339 | this->_M_impl._M_finish = this->_M_impl._M_start + __len; |
340 | this->_M_impl._M_end_of_storage = this->_M_impl._M_finish; |
341 | } |
342 | else if (__sz >= __len) |
343 | _M_erase_at_end(pos: std::copy(__first, __last, this->_M_impl._M_start)); |
344 | else |
345 | { |
346 | _ForwardIterator __mid = __first; |
347 | std::advance(__mid, __sz); |
348 | std::copy(__first, __mid, this->_M_impl._M_start); |
349 | const size_type __attribute__((__unused__)) __n = __len - __sz; |
350 | _GLIBCXX_ASAN_ANNOTATE_GROW(__n); |
351 | this->_M_impl._M_finish = |
352 | std::__uninitialized_copy_a(__mid, __last, |
353 | this->_M_impl._M_finish, |
354 | _M_get_Tp_allocator()); |
355 | _GLIBCXX_ASAN_ANNOTATE_GREW(__n); |
356 | } |
357 | } |
358 | |
359 | #if __cplusplus >= 201103L |
360 | template<typename _Tp, typename _Alloc> |
361 | _GLIBCXX20_CONSTEXPR |
362 | auto |
363 | vector<_Tp, _Alloc>:: |
364 | _M_insert_rval(const_iterator __position, value_type&& __v) -> iterator |
365 | { |
366 | const auto __n = __position - cbegin(); |
367 | if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) |
368 | if (__position == cend()) |
369 | { |
370 | _GLIBCXX_ASAN_ANNOTATE_GROW(1); |
371 | _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, |
372 | std::move(__v)); |
373 | ++this->_M_impl._M_finish; |
374 | _GLIBCXX_ASAN_ANNOTATE_GREW(1); |
375 | } |
376 | else |
377 | _M_insert_aux(begin() + __n, std::move(__v)); |
378 | else |
379 | _M_realloc_insert(begin() + __n, std::move(__v)); |
380 | |
381 | return iterator(this->_M_impl._M_start + __n); |
382 | } |
383 | |
384 | template<typename _Tp, typename _Alloc> |
385 | template<typename... _Args> |
386 | _GLIBCXX20_CONSTEXPR |
387 | auto |
388 | vector<_Tp, _Alloc>:: |
389 | _M_emplace_aux(const_iterator __position, _Args&&... __args) |
390 | -> iterator |
391 | { |
392 | const auto __n = __position - cbegin(); |
393 | if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) |
394 | if (__position == cend()) |
395 | { |
396 | _GLIBCXX_ASAN_ANNOTATE_GROW(1); |
397 | _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, |
398 | std::forward<_Args>(__args)...); |
399 | ++this->_M_impl._M_finish; |
400 | _GLIBCXX_ASAN_ANNOTATE_GREW(1); |
401 | } |
402 | else |
403 | { |
404 | // We need to construct a temporary because something in __args... |
405 | // could alias one of the elements of the container and so we |
406 | // need to use it before _M_insert_aux moves elements around. |
407 | _Temporary_value __tmp(this, std::forward<_Args>(__args)...); |
408 | _M_insert_aux(begin() + __n, std::move(__tmp._M_val())); |
409 | } |
410 | else |
411 | _M_realloc_insert(begin() + __n, std::forward<_Args>(__args)...); |
412 | |
413 | return iterator(this->_M_impl._M_start + __n); |
414 | } |
415 | |
416 | template<typename _Tp, typename _Alloc> |
417 | template<typename _Arg> |
418 | _GLIBCXX20_CONSTEXPR |
419 | void |
420 | vector<_Tp, _Alloc>:: |
421 | _M_insert_aux(iterator __position, _Arg&& __arg) |
422 | #else |
423 | template<typename _Tp, typename _Alloc> |
424 | void |
425 | vector<_Tp, _Alloc>:: |
426 | _M_insert_aux(iterator __position, const _Tp& __x) |
427 | #endif |
428 | { |
429 | _GLIBCXX_ASAN_ANNOTATE_GROW(1); |
430 | _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, |
431 | _GLIBCXX_MOVE(*(this->_M_impl._M_finish - 1))); |
432 | ++this->_M_impl._M_finish; |
433 | _GLIBCXX_ASAN_ANNOTATE_GREW(1); |
434 | #if __cplusplus < 201103L |
435 | _Tp __x_copy = __x; |
436 | #endif |
437 | _GLIBCXX_MOVE_BACKWARD3(__position.base(), |
438 | this->_M_impl._M_finish - 2, |
439 | this->_M_impl._M_finish - 1); |
440 | #if __cplusplus < 201103L |
441 | *__position = __x_copy; |
442 | #else |
443 | *__position = std::forward<_Arg>(__arg); |
444 | #endif |
445 | } |
446 | |
447 | #if __cplusplus >= 201103L |
448 | template<typename _Tp, typename _Alloc> |
449 | template<typename... _Args> |
450 | _GLIBCXX20_CONSTEXPR |
451 | void |
452 | vector<_Tp, _Alloc>:: |
453 | _M_realloc_insert(iterator __position, _Args&&... __args) |
454 | #else |
455 | template<typename _Tp, typename _Alloc> |
456 | void |
457 | vector<_Tp, _Alloc>:: |
458 | _M_realloc_insert(iterator __position, const _Tp& __x) |
459 | #endif |
460 | { |
461 | const size_type __len = _M_check_len(n: 1u, s: "vector::_M_realloc_insert" ); |
462 | if (__len <= 0) |
463 | __builtin_unreachable (); |
464 | pointer __old_start = this->_M_impl._M_start; |
465 | pointer __old_finish = this->_M_impl._M_finish; |
466 | const size_type __elems_before = __position - begin(); |
467 | pointer __new_start(this->_M_allocate(__len)); |
468 | pointer __new_finish(__new_start); |
469 | |
470 | // RAII guard for allocated storage. |
471 | struct _Guard |
472 | { |
473 | pointer _M_storage; // Storage to deallocate |
474 | size_type _M_len; |
475 | _Tp_alloc_type& _M_alloc; |
476 | |
477 | _GLIBCXX20_CONSTEXPR |
478 | _Guard(pointer __s, size_type __l, _Tp_alloc_type& __a) |
479 | : _M_storage(__s), _M_len(__l), _M_alloc(__a) |
480 | { } |
481 | |
482 | _GLIBCXX20_CONSTEXPR |
483 | ~_Guard() |
484 | { |
485 | if (_M_storage) |
486 | __gnu_cxx::__alloc_traits<_Tp_alloc_type>:: |
487 | deallocate(_M_alloc, _M_storage, _M_len); |
488 | } |
489 | |
490 | private: |
491 | _Guard(const _Guard&); |
492 | }; |
493 | |
494 | { |
495 | _Guard __guard(__new_start, __len, _M_impl); |
496 | |
497 | // The order of the three operations is dictated by the C++11 |
498 | // case, where the moves could alter a new element belonging |
499 | // to the existing vector. This is an issue only for callers |
500 | // taking the element by lvalue ref (see last bullet of C++11 |
501 | // [res.on.arguments]). |
502 | |
503 | // If this throws, the existing elements are unchanged. |
504 | #if __cplusplus >= 201103L |
505 | _Alloc_traits::construct(this->_M_impl, |
506 | std::__to_address(__new_start + __elems_before), |
507 | std::forward<_Args>(__args)...); |
508 | #else |
509 | _Alloc_traits::construct(this->_M_impl, |
510 | __new_start + __elems_before, |
511 | __x); |
512 | #endif |
513 | |
514 | #if __cplusplus >= 201103L |
515 | if _GLIBCXX17_CONSTEXPR (_S_use_relocate()) |
516 | { |
517 | // Relocation cannot throw. |
518 | __new_finish = _S_relocate(first: __old_start, last: __position.base(), |
519 | result: __new_start, alloc&: _M_get_Tp_allocator()); |
520 | ++__new_finish; |
521 | __new_finish = _S_relocate(first: __position.base(), last: __old_finish, |
522 | result: __new_finish, alloc&: _M_get_Tp_allocator()); |
523 | } |
524 | else |
525 | #endif |
526 | { |
527 | // RAII type to destroy initialized elements. |
528 | struct _Guard_elts |
529 | { |
530 | pointer _M_first, _M_last; // Elements to destroy |
531 | _Tp_alloc_type& _M_alloc; |
532 | |
533 | _GLIBCXX20_CONSTEXPR |
534 | _Guard_elts(pointer __elt, _Tp_alloc_type& __a) |
535 | : _M_first(__elt), _M_last(__elt + 1), _M_alloc(__a) |
536 | { } |
537 | |
538 | _GLIBCXX20_CONSTEXPR |
539 | ~_Guard_elts() |
540 | { std::_Destroy(_M_first, _M_last, _M_alloc); } |
541 | |
542 | private: |
543 | _Guard_elts(const _Guard_elts&); |
544 | }; |
545 | |
546 | // Guard the new element so it will be destroyed if anything throws. |
547 | _Guard_elts __guard_elts(__new_start + __elems_before, _M_impl); |
548 | |
549 | __new_finish = std::__uninitialized_move_if_noexcept_a( |
550 | __old_start, __position.base(), |
551 | __new_start, _M_get_Tp_allocator()); |
552 | |
553 | ++__new_finish; |
554 | // Guard everything before the new element too. |
555 | __guard_elts._M_first = __new_start; |
556 | |
557 | __new_finish = std::__uninitialized_move_if_noexcept_a( |
558 | __position.base(), __old_finish, |
559 | __new_finish, _M_get_Tp_allocator()); |
560 | |
561 | // New storage has been fully initialized, destroy the old elements. |
562 | __guard_elts._M_first = __old_start; |
563 | __guard_elts._M_last = __old_finish; |
564 | } |
565 | __guard._M_storage = __old_start; |
566 | __guard._M_len = this->_M_impl._M_end_of_storage - __old_start; |
567 | } |
568 | // deallocate should be called before assignments to _M_impl, |
569 | // to avoid call-clobbering |
570 | |
571 | this->_M_impl._M_start = __new_start; |
572 | this->_M_impl._M_finish = __new_finish; |
573 | this->_M_impl._M_end_of_storage = __new_start + __len; |
574 | } |
575 | |
576 | #if __cplusplus >= 201103L |
577 | template<typename _Tp, typename _Alloc> |
578 | template<typename... _Args> |
579 | _GLIBCXX20_CONSTEXPR |
580 | void |
581 | vector<_Tp, _Alloc>:: |
582 | _M_realloc_append(_Args&&... __args) |
583 | #else |
584 | template<typename _Tp, typename _Alloc> |
585 | void |
586 | vector<_Tp, _Alloc>:: |
587 | _M_realloc_append(const _Tp& __x) |
588 | #endif |
589 | { |
590 | const size_type __len = _M_check_len(n: 1u, s: "vector::_M_realloc_append" ); |
591 | if (__len <= 0) |
592 | __builtin_unreachable (); |
593 | pointer __old_start = this->_M_impl._M_start; |
594 | pointer __old_finish = this->_M_impl._M_finish; |
595 | const size_type __elems = end() - begin(); |
596 | pointer __new_start(this->_M_allocate(__len)); |
597 | pointer __new_finish(__new_start); |
598 | |
599 | // RAII guard for allocated storage. |
600 | struct _Guard |
601 | { |
602 | pointer _M_storage; // Storage to deallocate |
603 | size_type _M_len; |
604 | _Tp_alloc_type& _M_alloc; |
605 | |
606 | _GLIBCXX20_CONSTEXPR |
607 | _Guard(pointer __s, size_type __l, _Tp_alloc_type& __a) |
608 | : _M_storage(__s), _M_len(__l), _M_alloc(__a) |
609 | { } |
610 | |
611 | _GLIBCXX20_CONSTEXPR |
612 | ~_Guard() |
613 | { |
614 | if (_M_storage) |
615 | __gnu_cxx::__alloc_traits<_Tp_alloc_type>:: |
616 | deallocate(_M_alloc, _M_storage, _M_len); |
617 | } |
618 | |
619 | private: |
620 | _Guard(const _Guard&); |
621 | }; |
622 | |
623 | { |
624 | _Guard __guard(__new_start, __len, _M_impl); |
625 | |
626 | // The order of the three operations is dictated by the C++11 |
627 | // case, where the moves could alter a new element belonging |
628 | // to the existing vector. This is an issue only for callers |
629 | // taking the element by lvalue ref (see last bullet of C++11 |
630 | // [res.on.arguments]). |
631 | |
632 | // If this throws, the existing elements are unchanged. |
633 | #if __cplusplus >= 201103L |
634 | _Alloc_traits::construct(this->_M_impl, |
635 | std::__to_address(__new_start + __elems), |
636 | std::forward<_Args>(__args)...); |
637 | #else |
638 | _Alloc_traits::construct(this->_M_impl, |
639 | __new_start + __elems, |
640 | __x); |
641 | #endif |
642 | |
643 | #if __cplusplus >= 201103L |
644 | if _GLIBCXX17_CONSTEXPR (_S_use_relocate()) |
645 | { |
646 | // Relocation cannot throw. |
647 | __new_finish = _S_relocate(first: __old_start, last: __old_finish, |
648 | result: __new_start, alloc&: _M_get_Tp_allocator()); |
649 | ++__new_finish; |
650 | } |
651 | else |
652 | #endif |
653 | { |
654 | // RAII type to destroy initialized elements. |
655 | struct _Guard_elts |
656 | { |
657 | pointer _M_first, _M_last; // Elements to destroy |
658 | _Tp_alloc_type& _M_alloc; |
659 | |
660 | _GLIBCXX20_CONSTEXPR |
661 | _Guard_elts(pointer __elt, _Tp_alloc_type& __a) |
662 | : _M_first(__elt), _M_last(__elt + 1), _M_alloc(__a) |
663 | { } |
664 | |
665 | _GLIBCXX20_CONSTEXPR |
666 | ~_Guard_elts() |
667 | { std::_Destroy(_M_first, _M_last, _M_alloc); } |
668 | |
669 | private: |
670 | _Guard_elts(const _Guard_elts&); |
671 | }; |
672 | |
673 | // Guard the new element so it will be destroyed if anything throws. |
674 | _Guard_elts __guard_elts(__new_start + __elems, _M_impl); |
675 | |
676 | __new_finish = std::__uninitialized_move_if_noexcept_a( |
677 | __old_start, __old_finish, |
678 | __new_start, _M_get_Tp_allocator()); |
679 | |
680 | ++__new_finish; |
681 | |
682 | // New storage has been fully initialized, destroy the old elements. |
683 | __guard_elts._M_first = __old_start; |
684 | __guard_elts._M_last = __old_finish; |
685 | } |
686 | __guard._M_storage = __old_start; |
687 | __guard._M_len = this->_M_impl._M_end_of_storage - __old_start; |
688 | } |
689 | // deallocate should be called before assignments to _M_impl, |
690 | // to avoid call-clobbering |
691 | |
692 | this->_M_impl._M_start = __new_start; |
693 | this->_M_impl._M_finish = __new_finish; |
694 | this->_M_impl._M_end_of_storage = __new_start + __len; |
695 | } |
696 | |
697 | template<typename _Tp, typename _Alloc> |
698 | _GLIBCXX20_CONSTEXPR |
699 | void |
700 | vector<_Tp, _Alloc>:: |
701 | _M_fill_insert(iterator __position, size_type __n, const value_type& __x) |
702 | { |
703 | if (__n != 0) |
704 | { |
705 | if (size_type(this->_M_impl._M_end_of_storage |
706 | - this->_M_impl._M_finish) >= __n) |
707 | { |
708 | #if __cplusplus < 201103L |
709 | value_type __x_copy = __x; |
710 | #else |
711 | _Temporary_value __tmp(this, __x); |
712 | value_type& __x_copy = __tmp._M_val(); |
713 | #endif |
714 | const size_type __elems_after = end() - __position; |
715 | pointer __old_finish(this->_M_impl._M_finish); |
716 | if (__elems_after > __n) |
717 | { |
718 | _GLIBCXX_ASAN_ANNOTATE_GROW(__n); |
719 | std::__uninitialized_move_a(__old_finish - __n, |
720 | __old_finish, |
721 | __old_finish, |
722 | _M_get_Tp_allocator()); |
723 | this->_M_impl._M_finish += __n; |
724 | _GLIBCXX_ASAN_ANNOTATE_GREW(__n); |
725 | _GLIBCXX_MOVE_BACKWARD3(__position.base(), |
726 | __old_finish - __n, __old_finish); |
727 | std::fill(__position.base(), __position.base() + __n, |
728 | __x_copy); |
729 | } |
730 | else |
731 | { |
732 | _GLIBCXX_ASAN_ANNOTATE_GROW(__n); |
733 | this->_M_impl._M_finish = |
734 | std::__uninitialized_fill_n_a(__old_finish, |
735 | __n - __elems_after, |
736 | __x_copy, |
737 | _M_get_Tp_allocator()); |
738 | _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after); |
739 | std::__uninitialized_move_a(__position.base(), __old_finish, |
740 | this->_M_impl._M_finish, |
741 | _M_get_Tp_allocator()); |
742 | this->_M_impl._M_finish += __elems_after; |
743 | _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after); |
744 | std::fill(__position.base(), __old_finish, __x_copy); |
745 | } |
746 | } |
747 | else |
748 | { |
749 | // Make local copies of these members because the compiler thinks |
750 | // the allocator can alter them if 'this' is globally reachable. |
751 | pointer __old_start = this->_M_impl._M_start; |
752 | pointer __old_finish = this->_M_impl._M_finish; |
753 | const pointer __pos = __position.base(); |
754 | |
755 | const size_type __len = |
756 | _M_check_len(__n, s: "vector::_M_fill_insert" ); |
757 | const size_type __elems_before = __pos - __old_start; |
758 | pointer __new_start(this->_M_allocate(__len)); |
759 | pointer __new_finish(__new_start); |
760 | __try |
761 | { |
762 | // See _M_realloc_insert above. |
763 | std::__uninitialized_fill_n_a(__new_start + __elems_before, |
764 | __n, __x, |
765 | _M_get_Tp_allocator()); |
766 | __new_finish = pointer(); |
767 | |
768 | __new_finish |
769 | = std::__uninitialized_move_if_noexcept_a |
770 | (__old_start, __pos, __new_start, _M_get_Tp_allocator()); |
771 | |
772 | __new_finish += __n; |
773 | |
774 | __new_finish |
775 | = std::__uninitialized_move_if_noexcept_a |
776 | (__pos, __old_finish, __new_finish, _M_get_Tp_allocator()); |
777 | } |
778 | __catch(...) |
779 | { |
780 | if (!__new_finish) |
781 | std::_Destroy(__new_start + __elems_before, |
782 | __new_start + __elems_before + __n, |
783 | _M_get_Tp_allocator()); |
784 | else |
785 | std::_Destroy(__new_start, __new_finish, |
786 | _M_get_Tp_allocator()); |
787 | _M_deallocate(__new_start, __len); |
788 | __throw_exception_again; |
789 | } |
790 | std::_Destroy(__old_start, __old_finish, _M_get_Tp_allocator()); |
791 | _GLIBCXX_ASAN_ANNOTATE_REINIT; |
792 | _M_deallocate(__old_start, |
793 | this->_M_impl._M_end_of_storage - __old_start); |
794 | this->_M_impl._M_start = __new_start; |
795 | this->_M_impl._M_finish = __new_finish; |
796 | this->_M_impl._M_end_of_storage = __new_start + __len; |
797 | } |
798 | } |
799 | } |
800 | |
801 | #if __cplusplus >= 201103L |
802 | template<typename _Tp, typename _Alloc> |
803 | _GLIBCXX20_CONSTEXPR |
804 | void |
805 | vector<_Tp, _Alloc>:: |
806 | _M_default_append(size_type __n) |
807 | { |
808 | if (__n != 0) |
809 | { |
810 | const size_type __size = size(); |
811 | size_type __navail = size_type(this->_M_impl._M_end_of_storage |
812 | - this->_M_impl._M_finish); |
813 | |
814 | if (__size > max_size() || __navail > max_size() - __size) |
815 | __builtin_unreachable(); |
816 | |
817 | if (__navail >= __n) |
818 | { |
819 | _GLIBCXX_ASAN_ANNOTATE_GROW(__n); |
820 | this->_M_impl._M_finish = |
821 | std::__uninitialized_default_n_a(this->_M_impl._M_finish, |
822 | __n, _M_get_Tp_allocator()); |
823 | _GLIBCXX_ASAN_ANNOTATE_GREW(__n); |
824 | } |
825 | else |
826 | { |
827 | // Make local copies of these members because the compiler thinks |
828 | // the allocator can alter them if 'this' is globally reachable. |
829 | pointer __old_start = this->_M_impl._M_start; |
830 | pointer __old_finish = this->_M_impl._M_finish; |
831 | |
832 | const size_type __len = |
833 | _M_check_len(__n, s: "vector::_M_default_append" ); |
834 | pointer __new_start(this->_M_allocate(__len)); |
835 | |
836 | // RAII guard for allocated storage. |
837 | struct _Guard |
838 | { |
839 | pointer _M_storage; // Storage to deallocate |
840 | size_type _M_len; |
841 | _Tp_alloc_type& _M_alloc; |
842 | |
843 | _GLIBCXX20_CONSTEXPR |
844 | _Guard(pointer __s, size_type __l, _Tp_alloc_type& __a) |
845 | : _M_storage(__s), _M_len(__l), _M_alloc(__a) |
846 | { } |
847 | |
848 | _GLIBCXX20_CONSTEXPR |
849 | ~_Guard() |
850 | { |
851 | if (_M_storage) |
852 | __gnu_cxx::__alloc_traits<_Tp_alloc_type>:: |
853 | deallocate(_M_alloc, _M_storage, _M_len); |
854 | } |
855 | |
856 | private: |
857 | _Guard(const _Guard&); |
858 | }; |
859 | |
860 | { |
861 | _Guard __guard(__new_start, __len, _M_impl); |
862 | |
863 | std::__uninitialized_default_n_a(__new_start + __size, __n, |
864 | _M_get_Tp_allocator()); |
865 | |
866 | if _GLIBCXX17_CONSTEXPR (_S_use_relocate()) |
867 | { |
868 | _S_relocate(first: __old_start, last: __old_finish, |
869 | result: __new_start, alloc&: _M_get_Tp_allocator()); |
870 | } |
871 | else |
872 | { |
873 | // RAII type to destroy initialized elements. |
874 | struct _Guard_elts |
875 | { |
876 | pointer _M_first, _M_last; // Elements to destroy |
877 | _Tp_alloc_type& _M_alloc; |
878 | |
879 | _GLIBCXX20_CONSTEXPR |
880 | _Guard_elts(pointer __first, size_type __n, |
881 | _Tp_alloc_type& __a) |
882 | : _M_first(__first), _M_last(__first + __n), _M_alloc(__a) |
883 | { } |
884 | |
885 | _GLIBCXX20_CONSTEXPR |
886 | ~_Guard_elts() |
887 | { std::_Destroy(_M_first, _M_last, _M_alloc); } |
888 | |
889 | private: |
890 | _Guard_elts(const _Guard_elts&); |
891 | }; |
892 | _Guard_elts __guard_elts(__new_start + __size, __n, _M_impl); |
893 | |
894 | std::__uninitialized_move_if_noexcept_a( |
895 | __old_start, __old_finish, __new_start, |
896 | _M_get_Tp_allocator()); |
897 | |
898 | __guard_elts._M_first = __old_start; |
899 | __guard_elts._M_last = __old_finish; |
900 | } |
901 | _GLIBCXX_ASAN_ANNOTATE_REINIT; |
902 | __guard._M_storage = __old_start; |
903 | __guard._M_len = this->_M_impl._M_end_of_storage - __old_start; |
904 | } |
905 | // deallocate should be called before assignments to _M_impl, |
906 | // to avoid call-clobbering |
907 | |
908 | this->_M_impl._M_start = __new_start; |
909 | this->_M_impl._M_finish = __new_start + __size + __n; |
910 | this->_M_impl._M_end_of_storage = __new_start + __len; |
911 | } |
912 | } |
913 | } |
914 | |
915 | template<typename _Tp, typename _Alloc> |
916 | _GLIBCXX20_CONSTEXPR |
917 | bool |
918 | vector<_Tp, _Alloc>:: |
919 | _M_shrink_to_fit() |
920 | { |
921 | if (capacity() == size()) |
922 | return false; |
923 | _GLIBCXX_ASAN_ANNOTATE_REINIT; |
924 | return std::__shrink_to_fit_aux<vector>::_S_do_it(*this); |
925 | } |
926 | #endif |
927 | |
928 | template<typename _Tp, typename _Alloc> |
929 | template<typename _InputIterator> |
930 | _GLIBCXX20_CONSTEXPR |
931 | void |
932 | vector<_Tp, _Alloc>:: |
933 | _M_range_insert(iterator __pos, _InputIterator __first, |
934 | _InputIterator __last, std::input_iterator_tag) |
935 | { |
936 | if (__pos == end()) |
937 | { |
938 | for (; __first != __last; ++__first) |
939 | insert(end(), *__first); |
940 | } |
941 | else if (__first != __last) |
942 | { |
943 | vector __tmp(__first, __last, _M_get_Tp_allocator()); |
944 | insert(__pos, |
945 | _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.begin()), |
946 | _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.end())); |
947 | } |
948 | } |
949 | |
950 | template<typename _Tp, typename _Alloc> |
951 | template<typename _ForwardIterator> |
952 | _GLIBCXX20_CONSTEXPR |
953 | void |
954 | vector<_Tp, _Alloc>:: |
955 | _M_range_insert(iterator __position, _ForwardIterator __first, |
956 | _ForwardIterator __last, std::forward_iterator_tag) |
957 | { |
958 | if (__first != __last) |
959 | { |
960 | const size_type __n = std::distance(__first, __last); |
961 | if (size_type(this->_M_impl._M_end_of_storage |
962 | - this->_M_impl._M_finish) >= __n) |
963 | { |
964 | const size_type __elems_after = end() - __position; |
965 | pointer __old_finish(this->_M_impl._M_finish); |
966 | if (__elems_after > __n) |
967 | { |
968 | _GLIBCXX_ASAN_ANNOTATE_GROW(__n); |
969 | std::__uninitialized_move_a(this->_M_impl._M_finish - __n, |
970 | this->_M_impl._M_finish, |
971 | this->_M_impl._M_finish, |
972 | _M_get_Tp_allocator()); |
973 | this->_M_impl._M_finish += __n; |
974 | _GLIBCXX_ASAN_ANNOTATE_GREW(__n); |
975 | _GLIBCXX_MOVE_BACKWARD3(__position.base(), |
976 | __old_finish - __n, __old_finish); |
977 | std::copy(__first, __last, __position); |
978 | } |
979 | else |
980 | { |
981 | _ForwardIterator __mid = __first; |
982 | std::advance(__mid, __elems_after); |
983 | _GLIBCXX_ASAN_ANNOTATE_GROW(__n); |
984 | std::__uninitialized_copy_a(__mid, __last, |
985 | this->_M_impl._M_finish, |
986 | _M_get_Tp_allocator()); |
987 | this->_M_impl._M_finish += __n - __elems_after; |
988 | _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after); |
989 | std::__uninitialized_move_a(__position.base(), |
990 | __old_finish, |
991 | this->_M_impl._M_finish, |
992 | _M_get_Tp_allocator()); |
993 | this->_M_impl._M_finish += __elems_after; |
994 | _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after); |
995 | std::copy(__first, __mid, __position); |
996 | } |
997 | } |
998 | else |
999 | { |
1000 | // Make local copies of these members because the compiler |
1001 | // thinks the allocator can alter them if 'this' is globally |
1002 | // reachable. |
1003 | pointer __old_start = this->_M_impl._M_start; |
1004 | pointer __old_finish = this->_M_impl._M_finish; |
1005 | |
1006 | const size_type __len = |
1007 | _M_check_len(__n, s: "vector::_M_range_insert" ); |
1008 | pointer __new_start(this->_M_allocate(__len)); |
1009 | pointer __new_finish(__new_start); |
1010 | __try |
1011 | { |
1012 | __new_finish |
1013 | = std::__uninitialized_move_if_noexcept_a |
1014 | (__old_start, __position.base(), |
1015 | __new_start, _M_get_Tp_allocator()); |
1016 | __new_finish |
1017 | = std::__uninitialized_copy_a(__first, __last, |
1018 | __new_finish, |
1019 | _M_get_Tp_allocator()); |
1020 | __new_finish |
1021 | = std::__uninitialized_move_if_noexcept_a |
1022 | (__position.base(), __old_finish, |
1023 | __new_finish, _M_get_Tp_allocator()); |
1024 | } |
1025 | __catch(...) |
1026 | { |
1027 | std::_Destroy(__new_start, __new_finish, |
1028 | _M_get_Tp_allocator()); |
1029 | _M_deallocate(__new_start, __len); |
1030 | __throw_exception_again; |
1031 | } |
1032 | std::_Destroy(__old_start, __old_finish, |
1033 | _M_get_Tp_allocator()); |
1034 | _GLIBCXX_ASAN_ANNOTATE_REINIT; |
1035 | _M_deallocate(__old_start, |
1036 | this->_M_impl._M_end_of_storage - __old_start); |
1037 | this->_M_impl._M_start = __new_start; |
1038 | this->_M_impl._M_finish = __new_finish; |
1039 | this->_M_impl._M_end_of_storage = __new_start + __len; |
1040 | } |
1041 | } |
1042 | } |
1043 | |
1044 | |
1045 | // vector<bool> |
1046 | template<typename _Alloc> |
1047 | _GLIBCXX20_CONSTEXPR |
1048 | void |
1049 | vector<bool, _Alloc>:: |
1050 | _M_reallocate(size_type __n) |
1051 | { |
1052 | _Bit_pointer __q = this->_M_allocate(__n); |
1053 | iterator __start(std::__addressof(*__q), 0); |
1054 | iterator __finish(_M_copy_aligned(first: begin(), last: end(), result: __start)); |
1055 | this->_M_deallocate(); |
1056 | this->_M_impl._M_start = __start; |
1057 | this->_M_impl._M_finish = __finish; |
1058 | this->_M_impl._M_end_of_storage = __q + _S_nword(__n); |
1059 | } |
1060 | |
1061 | template<typename _Alloc> |
1062 | _GLIBCXX20_CONSTEXPR |
1063 | void |
1064 | vector<bool, _Alloc>:: |
1065 | _M_fill_insert(iterator __position, size_type __n, bool __x) |
1066 | { |
1067 | if (__n == 0) |
1068 | return; |
1069 | if (capacity() - size() >= __n) |
1070 | { |
1071 | std::copy_backward(__position, end(), |
1072 | this->_M_impl._M_finish + difference_type(__n)); |
1073 | std::fill(__position, __position + difference_type(__n), __x); |
1074 | this->_M_impl._M_finish += difference_type(__n); |
1075 | } |
1076 | else |
1077 | { |
1078 | const size_type __len = |
1079 | _M_check_len(__n, s: "vector<bool>::_M_fill_insert" ); |
1080 | _Bit_pointer __q = this->_M_allocate(__len); |
1081 | iterator __start(std::__addressof(*__q), 0); |
1082 | iterator __i = _M_copy_aligned(first: begin(), last: __position, result: __start); |
1083 | std::fill(__i, __i + difference_type(__n), __x); |
1084 | iterator __finish = std::copy(__position, end(), |
1085 | __i + difference_type(__n)); |
1086 | this->_M_deallocate(); |
1087 | this->_M_impl._M_end_of_storage = __q + _S_nword(__len); |
1088 | this->_M_impl._M_start = __start; |
1089 | this->_M_impl._M_finish = __finish; |
1090 | } |
1091 | } |
1092 | |
1093 | template<typename _Alloc> |
1094 | template<typename _ForwardIterator> |
1095 | _GLIBCXX20_CONSTEXPR |
1096 | void |
1097 | vector<bool, _Alloc>:: |
1098 | _M_insert_range(iterator __position, _ForwardIterator __first, |
1099 | _ForwardIterator __last, std::forward_iterator_tag) |
1100 | { |
1101 | if (__first != __last) |
1102 | { |
1103 | size_type __n = std::distance(__first, __last); |
1104 | if (capacity() - size() >= __n) |
1105 | { |
1106 | std::copy_backward(__position, end(), |
1107 | this->_M_impl._M_finish |
1108 | + difference_type(__n)); |
1109 | std::copy(__first, __last, __position); |
1110 | this->_M_impl._M_finish += difference_type(__n); |
1111 | } |
1112 | else |
1113 | { |
1114 | const size_type __len = |
1115 | _M_check_len(__n, s: "vector<bool>::_M_insert_range" ); |
1116 | const iterator __begin = begin(), __end = end(); |
1117 | _Bit_pointer __q = this->_M_allocate(__len); |
1118 | iterator __start(std::__addressof(*__q), 0); |
1119 | iterator __i = _M_copy_aligned(first: __begin, last: __position, result: __start); |
1120 | __i = std::copy(__first, __last, __i); |
1121 | iterator __finish = std::copy(__position, __end, __i); |
1122 | this->_M_deallocate(); |
1123 | this->_M_impl._M_end_of_storage = __q + _S_nword(__len); |
1124 | this->_M_impl._M_start = __start; |
1125 | this->_M_impl._M_finish = __finish; |
1126 | } |
1127 | } |
1128 | } |
1129 | |
1130 | template<typename _Alloc> |
1131 | _GLIBCXX20_CONSTEXPR |
1132 | void |
1133 | vector<bool, _Alloc>:: |
1134 | _M_insert_aux(iterator __position, bool __x) |
1135 | { |
1136 | if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr()) |
1137 | { |
1138 | std::copy_backward(__position, this->_M_impl._M_finish, |
1139 | this->_M_impl._M_finish + 1); |
1140 | *__position = __x; |
1141 | ++this->_M_impl._M_finish; |
1142 | } |
1143 | else |
1144 | { |
1145 | const size_type __len = |
1146 | _M_check_len(n: size_type(1), s: "vector<bool>::_M_insert_aux" ); |
1147 | _Bit_pointer __q = this->_M_allocate(__len); |
1148 | iterator __start(std::__addressof(*__q), 0); |
1149 | iterator __i = _M_copy_aligned(first: begin(), last: __position, result: __start); |
1150 | *__i++ = __x; |
1151 | iterator __finish = std::copy(__position, end(), __i); |
1152 | this->_M_deallocate(); |
1153 | this->_M_impl._M_end_of_storage = __q + _S_nword(__len); |
1154 | this->_M_impl._M_start = __start; |
1155 | this->_M_impl._M_finish = __finish; |
1156 | } |
1157 | } |
1158 | |
1159 | template<typename _Alloc> |
1160 | _GLIBCXX20_CONSTEXPR |
1161 | typename vector<bool, _Alloc>::iterator |
1162 | vector<bool, _Alloc>:: |
1163 | _M_erase(iterator __position) |
1164 | { |
1165 | if (__position + 1 != end()) |
1166 | std::copy(__position + 1, end(), __position); |
1167 | --this->_M_impl._M_finish; |
1168 | return __position; |
1169 | } |
1170 | |
1171 | template<typename _Alloc> |
1172 | _GLIBCXX20_CONSTEXPR |
1173 | typename vector<bool, _Alloc>::iterator |
1174 | vector<bool, _Alloc>:: |
1175 | _M_erase(iterator __first, iterator __last) |
1176 | { |
1177 | if (__first != __last) |
1178 | _M_erase_at_end(pos: std::copy(__last, end(), __first)); |
1179 | return __first; |
1180 | } |
1181 | |
1182 | #if __cplusplus >= 201103L |
1183 | template<typename _Alloc> |
1184 | _GLIBCXX20_CONSTEXPR |
1185 | bool |
1186 | vector<bool, _Alloc>:: |
1187 | _M_shrink_to_fit() |
1188 | { |
1189 | if (capacity() - size() < int(_S_word_bit)) |
1190 | return false; |
1191 | __try |
1192 | { |
1193 | if (size_type __n = size()) |
1194 | _M_reallocate(__n); |
1195 | else |
1196 | { |
1197 | this->_M_deallocate(); |
1198 | this->_M_impl._M_reset(); |
1199 | } |
1200 | return true; |
1201 | } |
1202 | __catch(...) |
1203 | { return false; } |
1204 | } |
1205 | #endif |
1206 | |
1207 | _GLIBCXX_END_NAMESPACE_CONTAINER |
1208 | _GLIBCXX_END_NAMESPACE_VERSION |
1209 | } // namespace std |
1210 | |
1211 | #if __cplusplus >= 201103L |
1212 | |
1213 | namespace std _GLIBCXX_VISIBILITY(default) |
1214 | { |
1215 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
1216 | |
1217 | template<typename _Alloc> |
1218 | size_t |
1219 | hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>:: |
1220 | operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const noexcept |
1221 | { |
1222 | size_t __hash = 0; |
1223 | const size_t __words = __b.size() / _S_word_bit; |
1224 | if (__words) |
1225 | { |
1226 | const size_t __clength = __words * sizeof(_Bit_type); |
1227 | __hash = std::_Hash_impl::hash(__b._M_impl._M_start._M_p, __clength); |
1228 | } |
1229 | |
1230 | const size_t = __b.size() % _S_word_bit; |
1231 | if (__extrabits) |
1232 | { |
1233 | _Bit_type __hiword = *__b._M_impl._M_finish._M_p; |
1234 | __hiword &= ~((~static_cast<_Bit_type>(0)) << __extrabits); |
1235 | |
1236 | const size_t __clength |
1237 | = (__extrabits + __CHAR_BIT__ - 1) / __CHAR_BIT__; |
1238 | if (__words) |
1239 | __hash = std::_Hash_impl::hash(ptr: &__hiword, __clength, seed: __hash); |
1240 | else |
1241 | __hash = std::_Hash_impl::hash(ptr: &__hiword, __clength); |
1242 | } |
1243 | |
1244 | return __hash; |
1245 | } |
1246 | |
1247 | _GLIBCXX_END_NAMESPACE_VERSION |
1248 | } // namespace std |
1249 | |
1250 | #endif // C++11 |
1251 | |
1252 | #undef _GLIBCXX_ASAN_ANNOTATE_REINIT |
1253 | #undef _GLIBCXX_ASAN_ANNOTATE_GROW |
1254 | #undef _GLIBCXX_ASAN_ANNOTATE_GREW |
1255 | #undef _GLIBCXX_ASAN_ANNOTATE_SHRINK |
1256 | |
1257 | #endif /* _VECTOR_TCC */ |
1258 | |