libstdc++
inplace_vector
Go to the documentation of this file.
1// Sequence container with fixed capacity -*- C++ -*-
2
3// Copyright The GNU Toolchain Authors.
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/** @file include/inplace_vector
26 * This is a Standard C++ Library header.
27 * @ingroup sequences
28 */
29
30#ifndef _GLIBCXX_INPLACE_VECTOR
31#define _GLIBCXX_INPLACE_VECTOR 1
32
33#pragma GCC system_header
34
35#define __glibcxx_want_inplace_vector
36#include <bits/version.h>
37
38#ifdef __glibcxx_inplace_vector // C++ >= 26
39#include <compare>
40#include <initializer_list>
41#include <optional>
43#include <bits/range_access.h>
44#include <bits/ranges_base.h> // borrowed_iterator_t, __detail::__container_compatible_range
45#include <bits/ranges_util.h> // subrange
47#include <bits/stl_construct.h>
49#include <bits/stl_algo.h> // rotate
50#include <bits/erase_if.h>
51
52namespace std _GLIBCXX_VISIBILITY(default)
53{
54_GLIBCXX_BEGIN_NAMESPACE_VERSION
55_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
56
57 // [indirect], class template indirect
58 template<typename _Tp, size_t _Nm>
59 class inplace_vector
60 {
61 public:
62
63 // types:
64 using value_type = _Tp;
65 using pointer = _Tp*;
66 using const_pointer = const _Tp*;
67 using reference = value_type&;
68 using const_reference = const value_type&;
69 using size_type = size_t;
70 using difference_type = ptrdiff_t;
71 using iterator
72 = __gnu_cxx::__normal_iterator<_Tp*, inplace_vector>;
73 using const_iterator
74 = __gnu_cxx::__normal_iterator<const _Tp*, inplace_vector>;
75 using reverse_iterator = std::reverse_iterator<iterator>;
76 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
77
78 // [containers.sequences.inplace.vector.cons], construct/copy/destroy
79 constexpr
80 inplace_vector() noexcept
81 { _M_init(); }
82
83 constexpr explicit
84 inplace_vector(size_type __n)
85 {
86 _M_init();
87 _S_check_size(__n);
89 _M_size = __n;
90 }
91
92 constexpr
93 inplace_vector(size_type __n, const _Tp& __value)
94 {
95 _M_init();
96 _S_check_size(__n);
97 std::uninitialized_fill_n(data(), __n, __value);
98 _M_size = __n;
99 }
100
101 template<__any_input_iterator _InputIterator>
102 constexpr
103 inplace_vector(_InputIterator __first, _InputIterator __last)
104 : inplace_vector()
105 {
106 if constexpr (__any_sizeable_iterator<_InputIterator>)
107 {
108 const size_type __n = _S_distance_if_fits(0, __first, __last);
109 std::uninitialized_copy(__first, __last, data());
110 _M_size = __n;
111 }
112 else
113 {
114 while (__first != __last)
115 emplace_back(*__first++);
116 }
117 }
118
119 template <__detail::__container_compatible_range<_Tp> _Rg>
120 constexpr
121 inplace_vector(from_range_t, _Rg&& __rg)
122 : inplace_vector()
123 { append_range(__rg); }
124
125 constexpr
126 inplace_vector(initializer_list<_Tp> __il)
127 {
128 _M_init();
129 _S_check_size(__il.size());
130 std::uninitialized_copy(__il.begin(), __il.end(), data());
131 _M_size = __il.size();
132 }
133
134 inplace_vector(const inplace_vector&)
135 requires is_trivially_copy_constructible_v<_Tp>
136 = default;
137
138 constexpr
139 inplace_vector(const inplace_vector& __other)
140 noexcept(is_nothrow_copy_constructible_v<_Tp>)
141 {
142 _M_init();
143 std::uninitialized_copy(__other.begin(), __other.end(), data());
144 _M_size = __other.size();
145 }
146
147 inplace_vector(inplace_vector&&)
148 requires is_trivially_move_constructible_v<_Tp>
149 = default;
150
151 constexpr
152 inplace_vector(inplace_vector&& __other)
153 noexcept(is_nothrow_move_constructible_v<_Tp>)
154 {
155 _M_init();
156 std::uninitialized_move(__other.begin(), __other.end(), data());
157 _M_size = __other.size();
158 }
159
160 ~inplace_vector()
161 requires is_trivially_destructible_v<_Tp>
162 = default;
163
164 constexpr
165 ~inplace_vector()
166 { clear(); }
167
168 inplace_vector&
169 operator=(const inplace_vector&)
170 requires is_trivially_copy_assignable_v<_Tp>
171 && is_trivially_copy_constructible_v<_Tp>
172 && is_trivially_destructible_v<_Tp>
173 = default;
174
175 constexpr inplace_vector&
176 operator=(const inplace_vector& __other)
177 noexcept(is_nothrow_copy_assignable_v<_Tp>
178 && is_nothrow_copy_constructible_v<_Tp>)
179 {
180 if (std::addressof(__other) != this) [[likely]]
181 assign(__other.begin(), __other.end());
182 return *this;
183 }
184
185 inplace_vector&
186 operator=(inplace_vector&&)
187 requires is_trivially_move_assignable_v<_Tp>
188 && is_trivially_move_constructible_v<_Tp>
189 && is_trivially_destructible_v<_Tp>
190 = default;
191
192 constexpr inplace_vector&
193 operator=(inplace_vector&& __other)
194 noexcept(is_nothrow_move_assignable_v<_Tp>
195 && is_nothrow_move_constructible_v<_Tp>)
196 {
197 if (std::addressof(__other) != this) [[likely]]
198 assign(std::make_move_iterator(__other.begin()),
199 std::make_move_iterator(__other.end()));
200 return *this;
201 }
202
203 constexpr inplace_vector&
204 operator=(initializer_list<_Tp> __il)
205 {
206 assign(__il.begin(), __il.end());
207 return *this;
208 }
209
210 template<__any_input_iterator _InputIterator>
211 constexpr void
212 assign(_InputIterator __first, _InputIterator __last)
213 {
214 if constexpr (__any_sizeable_iterator<_InputIterator>)
215 {
216 const size_type __n = _S_distance_if_fits(0, __first, __last);
217 if (_M_size <= __n)
218 {
219 for (size_t __i = 0; __i < _M_size; ++__i, (void)++__first)
220 _M_elems[__i] = *__first;
221 std::uninitialized_copy(__first, __last, end());
222 }
223 else
224 std::destroy(std::copy(__first, __last, begin()), end());
225 _M_size = __n;
226 }
227 else
228 {
229 size_t __i = 0;
230 for (;__first != __last && __i < _M_size; ++__first)
231 _M_elems[__i++] = *__first;
232 if (__first == __last)
233 {
234 std::_Destroy_n(data() + __i, _M_size - __i);
235 _M_size = __i;
236 }
237 else
238 {
239 while (__first != __last)
240 emplace_back(*__first++);
241 }
242 }
243 }
244
245 template<__detail::__container_compatible_range<_Tp> _Rg>
246 constexpr void
247 assign_range(_Rg&& __rg)
248 {
249 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
250 {
251 const size_type __sz = _S_distance_if_fits(0, __rg);
252 if (__sz <= size())
253 {
254 ranges::copy_n(ranges::begin(__rg), __sz, data());
255 std::destroy(data() + __sz, data() + _M_size);
256 }
257 else
258 {
259 auto [__in, __out] = ranges::copy_n(
260 ranges::begin(__rg), _M_size,
261 data());
262 ranges::uninitialized_copy(
263 std::move(__in), ranges::end(__rg),
264 __out, unreachable_sentinel);
265 }
266 _M_size = __sz;
267 }
268 else
269 {
270 auto __in = ranges::begin(__rg);
271 auto __end = ranges::end(__rg);
272 size_type __n = 0;
273 for (; __n < _M_size && __in != __end; ++__in)
274 _M_elems[__n++] = *__in;
275
276 if (__in == __end)
277 {
278 std::destroy(data() + __n, data() + _M_size);
279 _M_size = __n;
280 return;
281 }
282 else if (__n < _Nm)
283 {
284 auto __res = ranges::uninitialized_copy(
285 std::move(__in), __end,
286 data() + __n, data() + _Nm);
287 _M_size = __res.out - data();
288 if (__res.in == ranges::end(__rg))
289 return;
290 }
291 __throw_bad_alloc();
292 }
293 }
294
295 constexpr void
296 assign(size_type __n, const _Tp& __u)
297 {
298 _S_check_size(__n);
299 if (_M_size <= __n)
300 std::uninitialized_fill_n(std::fill_n(data(), _M_size, __u),
301 __n - _M_size, __u);
302 else
303 std::destroy_n(std::fill_n(data(), __n, __u), _M_size - __n);
304 _M_size = __n;
305 }
306
307 constexpr void
308 assign(initializer_list<_Tp> __il)
309 { assign(__il.begin(), __il.end()); }
310
311 // iterators
312 [[nodiscard]]
313 constexpr iterator
314 begin() noexcept { return iterator(data()); }
315
316 [[nodiscard]]
317 constexpr const_iterator
318 begin() const noexcept { return const_iterator(data()); }
319
320 [[nodiscard]]
321 constexpr iterator
322 end() noexcept
323 { return iterator(data() + _M_size); }
324
325 [[nodiscard]]
326 constexpr const_iterator
327 end() const noexcept
328 { return const_iterator(data() + _M_size); }
329
330 [[nodiscard]]
331 constexpr reverse_iterator
332 rbegin() noexcept
333 { return reverse_iterator(end()); }
334
335 [[nodiscard]]
336 constexpr const_reverse_iterator
337 rbegin() const noexcept
338 { return const_reverse_iterator(end()); }
339
340 [[nodiscard]]
341 constexpr reverse_iterator
342 rend() noexcept { return reverse_iterator(begin()); }
343
344 [[nodiscard]]
345 constexpr const_reverse_iterator
346 rend() const noexcept { return const_reverse_iterator(begin()); }
347
348 [[nodiscard]]
349 constexpr const_iterator
350 cbegin() const noexcept { return begin(); }
351
352 [[nodiscard]]
353 constexpr const_iterator
354 cend() const noexcept { return end(); }
355
356 [[nodiscard]]
357 constexpr const_reverse_iterator
358 crbegin() const noexcept { return rbegin(); }
359
360 [[nodiscard]]
361 constexpr const_reverse_iterator
362 crend() const noexcept { return rend(); }
363
364 // [containers.sequences.inplace.vector.members] size/capacity
365 [[nodiscard]]
366 constexpr bool
367 empty() const noexcept { return _M_size == 0; }
368
369 [[nodiscard]]
370 constexpr size_type
371 size() const noexcept
372 {
373 if (_M_size > _Nm)
374 __builtin_unreachable();
375 return _M_size;
376 }
377
378 [[nodiscard]]
379 static constexpr size_type
380 max_size() noexcept { return _Nm; }
381
382 [[nodiscard]]
383 static constexpr size_type
384 capacity() noexcept { return _Nm; }
385
386 constexpr void
387 resize(size_type __n)
388 {
389 _S_check_size(__n);
390 if (__n > _M_size)
391 std::uninitialized_value_construct_n(data() + _M_size, __n - _M_size);
392 else if (__n < _M_size)
393 std::destroy_n(data() + __n, _M_size - __n);
394 _M_size = __n;
395 }
396
397 constexpr void
398 resize(size_type __n, const _Tp& __c)
399 {
400 _S_check_size(__n);
401 if (__n > _M_size)
402 std::uninitialized_fill_n(data() + _M_size, __n - _M_size, __c);
403 else if (__n < _M_size)
404 std::destroy_n(data() + __n, _M_size - __n);
405 _M_size = __n;
406 }
407
408 static constexpr void
409 reserve(size_type __n)
410 { _S_check_size(__n); }
411
412 static constexpr void
413 shrink_to_fit() { }
414
415 // element access
416 [[nodiscard]]
417 constexpr reference
418 operator[](size_type __n)
419 {
420 __glibcxx_requires_subscript(__n);
421 return _M_elems[__n];
422 }
423
424 [[nodiscard]]
425 constexpr const_reference
426 operator[](size_type __n) const
427 {
428 __glibcxx_requires_subscript(__n);
429 return _M_elems[__n];
430 }
431
432 [[nodiscard]]
433 constexpr const_reference
434 at(size_type __n) const
435 {
436 if (__n >= _M_size)
437 std::__throw_out_of_range_fmt(__N("inplace_vector::at: __n "
438 "(which is %zu) "
439 ">= size() (which is %zu)"),
440 __n, _M_size);
441 return _M_elems[__n];
442 }
443
444 [[nodiscard]]
445 constexpr reference
446 at(size_type __n)
447 {
448 if (__n >= _M_size)
449 std::__throw_out_of_range_fmt(__N("inplace_vector::at: __n "
450 "(which is %zu) "
451 ">= size() (which is %zu)"),
452 __n, _M_size);
453 return _M_elems[__n];
454 }
455
456 [[nodiscard]]
457 constexpr reference
458 front()
459 {
460 __glibcxx_requires_nonempty();
461 return _M_elems[0];
462 }
463
464 [[nodiscard]]
465 constexpr const_reference
466 front() const
467 {
468 __glibcxx_requires_nonempty();
469 return _M_elems[0];
470 }
471
472 [[nodiscard]]
473 constexpr reference
474 back()
475 {
476 __glibcxx_requires_nonempty();
477 return _M_elems[_M_size - 1];
478 }
479
480 [[nodiscard]]
481 constexpr const_reference
482 back() const
483 {
484 __glibcxx_requires_nonempty();
485 return _M_elems[_M_size - 1];
486 }
487
488 // [containers.sequences.inplace.vector.data], data access
489
490 [[nodiscard]]
491 constexpr _Tp*
492 data() noexcept
493 { return static_cast<pointer>(_M_elems); }
494
495 [[nodiscard]]
496 constexpr const _Tp*
497 data() const noexcept
498 { return static_cast<const_pointer>(_M_elems); }
499
500 // [containers.sequences.inplace.vector.modifiers], modifiers
501 template<typename... _Args>
502 constexpr _Tp&
503 emplace_back(_Args&&... __args)
504 {
505 if (_M_size >= _Nm)
506 __throw_bad_alloc();
507 return unchecked_emplace_back(std::forward<_Args>(__args)...);
508 }
509
510 constexpr _Tp&
511 push_back(const _Tp& __x)
512 { return emplace_back(__x); }
513
514 constexpr _Tp&
515 push_back(_Tp&& __x)
516 { return emplace_back(std::move(__x)); }
517
518 template<__detail::__container_compatible_range<_Tp> _Rg>
519 constexpr void
520 append_range(_Rg&& __rg)
521 {
522 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
523 {
524 const size_t __sz = _S_distance_if_fits(_M_size, __rg);
525 // Bounded on output range due PR121143
526 ranges::uninitialized_copy(
527 ranges::begin(__rg), unreachable_sentinel,
528 data() + _M_size, data() + _M_size + __sz);
529 _M_size += __sz;
530 }
531 else
532 {
533 ranges::subrange<pointer> __tail(data() + _M_size, data() + _Nm);
534 auto [__in, __out] = ranges::uninitialized_copy(__rg, __tail);
535 _M_size = __out - data();
536 if (__in != ranges::end(__rg))
537 __throw_bad_alloc();
538 }
539 }
540
541 constexpr void
542 pop_back()
543 {
544 __glibcxx_requires_nonempty();
545 --_M_size;
546 _M_elems[_M_size].~_Tp();
547 }
548
549 template<typename... _Args>
550 constexpr optional<_Tp&>
551 try_emplace_back(_Args&&... __args)
552 {
553 if (_M_size >= _Nm) [[unlikely]]
554 return nullopt;
555 return optional<_Tp&>(in_place,
556 unchecked_emplace_back(std::forward<_Args>(__args)...));
557 }
558
559 constexpr optional<_Tp&>
560 try_push_back(const _Tp& __x)
561 {
562 if (_M_size >= _Nm) [[unlikely]]
563 return nullopt;
564 return optional<_Tp&>(in_place, unchecked_emplace_back(__x));
565 }
566
567 constexpr optional<_Tp&>
568 try_push_back(_Tp&& __x)
569 {
570 if (_M_size >= _Nm) [[unlikely]]
571 return nullopt;
572 return optional<_Tp&>(in_place, unchecked_emplace_back(std::move(__x)));
573 }
574
575 template<typename... _Args>
576 constexpr _Tp&
577 unchecked_emplace_back(_Args&&... __args)
578 {
579 __glibcxx_assert(_M_size < _Nm);
580 auto __p = std::construct_at(data() + _M_size,
581 std::forward<_Args>(__args)...);
582 ++_M_size;
583 return *__p;
584 }
585
586 constexpr _Tp&
587 unchecked_push_back(const _Tp& __x)
588 { return unchecked_emplace_back(__x); }
589
590 constexpr _Tp&
591 unchecked_push_back(_Tp&& __x)
592 { return unchecked_emplace_back(std::move(__x)); }
593
594 template<typename... _Args>
595 constexpr iterator
596 emplace(const_iterator __position, _Args&&... __args)
597 {
598 size_t __b = __position - cbegin(); // elements before position
599 __glibcxx_assert(__b <= _M_size);
600 if (_M_size >= _Nm)
601 __throw_bad_alloc();
602 iterator __pos = begin() + __b;
603 std::construct_at(data() + _M_size, std::forward<_Args>(__args)...);
604 if (_M_size++)
605 std::rotate(__pos, end() - 1, end());
606 return __pos;
607 }
608
609 constexpr iterator
610 insert(const_iterator __position, const _Tp& __x)
611 { return emplace(__position, __x); }
612
613 constexpr iterator
614 insert(const_iterator __position, _Tp&& __x)
615 { return emplace(__position, std::move(__x)); }
616
617 constexpr iterator
618 insert(const_iterator __position, size_type __n, const _Tp& __x)
619 {
620 size_t __b = __position - cbegin(); // elements before position
621 __glibcxx_assert(__b <= _M_size);
622 if ((_Nm - _M_size) < __n)
623 __throw_bad_alloc();
624 iterator __pos = begin() + __b;
625 std::uninitialized_fill_n(data() + _M_size, __n, __x);
626 if (std::__exchange(_M_size, _M_size + __n))
627 std::rotate(__pos, end() - __n, end());
628 return __pos;
629 }
630
631 template<__any_input_iterator _InputIterator>
632 constexpr iterator
633 insert(const_iterator __position, _InputIterator __first,
634 _InputIterator __last)
635 {
636 size_t __b = __position - cbegin(); // elements before position
637 __glibcxx_assert(__b <= _M_size);
638 iterator __pos = begin() + __b;
639 const size_t __s = _M_size;
640 if constexpr (__any_sizeable_iterator<_InputIterator>)
641 {
642 const size_type __n = _S_distance_if_fits(_M_size, __first, __last);
643 std::uninitialized_copy(__first, __last, data() + _M_size);
644 _M_size += __n;
645 }
646 else
647 {
648 while (__first != __last)
649 emplace_back(*__first++);
650 }
651 if (__b < __s)
652 std::rotate(__pos, begin() + __s, end());
653 return __pos;
654 }
655
656 template<__detail::__container_compatible_range<_Tp> _Rg>
657 constexpr iterator
658 insert_range(const_iterator __position, _Rg&& __rg)
659 {
660 iterator __pos = begin() + (__position - cbegin());
661 const auto __end = end();
662 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
663 {
664 const size_type __sz = _S_distance_if_fits(_M_size, __rg);
665 if (!__sz) [[unlikely]]
666 return __pos;
667
668 const size_type __num_after = __end - __pos;
669 if (__num_after >= __sz)
670 {
671 ranges::uninitialized_move(__end - __sz, __end,
672 __end, unreachable_sentinel);
673 _M_size += __sz;
674 ranges::move_backward(__pos, __end - __sz, __end);
675 ranges::copy(__rg, __pos);
676 }
677 else if constexpr (ranges::forward_range<_Rg>)
678 {
679 auto __mid = ranges::next(ranges::begin(__rg), __num_after);
680 ranges::uninitialized_copy(__mid, ranges::end(__rg),
681 __end, unreachable_sentinel);
682 _M_size += __sz - __num_after;
683 ranges::uninitialized_move(__pos, __end,
684 __pos + __sz, unreachable_sentinel);
685 _M_size += __num_after;
686 ranges::copy(ranges::begin(__rg), __mid, __pos);
687 }
688 else
689 {
690 ranges::uninitialized_copy(
691 ranges::begin(__rg), ranges::end(__rg),
692 __end, unreachable_sentinel);
693 _M_size += __sz;
694 std::rotate(__pos, __end, end());
695 }
696 }
697 else
698 {
699 append_range(__rg);
700 std::rotate(__pos, __end, end());
701 }
702 return __pos;
703 }
704
705 constexpr iterator
706 insert(const_iterator __position, initializer_list<_Tp> __il)
707 { return insert(__position, __il.begin(), __il.end()); }
708
709 constexpr iterator
710 erase(const_iterator __position)
711 {
712 size_t __n = __position - cbegin();
713 __glibcxx_assert(__n < _M_size);
714 iterator __pos = begin() + __n;
715 std::move(__pos + 1, end(), __pos);
716 pop_back();
717 return __pos;
718 }
719
720 constexpr iterator
721 erase(const_iterator __first, const_iterator __last)
722 {
723 size_t __n = __first - cbegin();
724 size_t __x = __last - __first;
725 __glibcxx_assert(__n <= _M_size);
726 __glibcxx_assert(__x <= _M_size);
727 iterator __pos = begin() + __n;
728 iterator __end = std::move(__pos + __x, end(), __pos);
729 std::destroy_n(__end, __x);
730 _M_size -= __x;
731 return __pos;
732 }
733
734 constexpr void
735 swap(inplace_vector& __x)
736 noexcept(is_nothrow_swappable_v<_Tp> && is_nothrow_move_constructible_v<_Tp>)
737 {
738 inplace_vector* __vs[2]{ this, std::addressof(__x) };
739 const auto __smaller = __vs[__x.size() < size()];
740 const auto __bigger = __vs[__x.size() >= size()];
741 size_type __n = __smaller->size();
742 size_type __n2 = __bigger->size();
743
744 if constexpr (is_nothrow_move_constructible_v<_Tp>)
745 {
746 for (size_type __i = __n; __i < __n2; ++__i)
747 {
748 std::construct_at(__smaller->data() + __i,
749 std::move(*(__bigger->data() + __i)));
750 std::destroy_at(__bigger->data() + __i);
751 }
752 }
753 else
754 {
755 std::uninitialized_copy(__bigger->data() + __n,
756 __bigger->data() + __n2,
757 __smaller->data() + __n);
758 std::destroy(__bigger->data() + __n, __bigger->data() + __n2);
759 }
760 __smaller->_M_size = __n2;
761 __bigger->_M_size = __n;
762
763 using std::swap;
764 for (size_type __i = 0; __i < __n; __i++)
765 swap(_M_elems[__i], __x._M_elems[__i]);
766 }
767
768 constexpr void
769 clear() noexcept
770 {
771 std::destroy_n(data(), size_t(_M_size));
772 _M_size = 0;
773 }
774
775 constexpr friend bool
776 operator==(const inplace_vector& __x, const inplace_vector& __y)
777 { return std::equal(__x.begin(), __x.end(), __y.begin(), __y.end()); }
778
779 constexpr friend auto
780 operator<=>(const inplace_vector& __x, const inplace_vector& __y)
781 requires requires (const _Tp __t) {
782 { __t < __t } -> __detail::__boolean_testable;
783 }
784 {
785 return std::lexicographical_compare_three_way(__x.begin(), __x.end(),
786 __y.begin(), __y.end(),
787 __detail::__synth3way);
788 }
789
790 // [inplace.vector.special], specialized algorithms
791 constexpr friend void
792 swap(inplace_vector& __x, inplace_vector& __y)
793 noexcept(is_nothrow_swappable_v<_Tp> && is_nothrow_move_constructible_v<_Tp>)
794 { __x.swap(__y); }
795
796 private:
797 union {
798 _Tp _M_elems[_Nm];
799 };
800
801 // Check whether integer type _UInt is wide enough to store _Nm,
802 // so that we use a smaller type for _M_size when that saves space.
803 template<typename _UInt, bool = (alignof(_Tp) <= sizeof(_UInt))>
804 static constexpr bool __fits
805 = _Nm <= __gnu_cxx::__int_traits<_UInt>::__max;
806
807 // Don't bother using a smaller type if alignment of the array elements
808 // means that it doesn't actually save space.
809 template<typename _UInt>
810 static constexpr bool __fits<_UInt, false> = false;
811
812 static consteval auto __select_size_type()
813 {
814 if constexpr (__fits<unsigned char>)
815 return (unsigned char)0;
816#if __SHRT_WIDTH__ < __SIZE_WIDTH__
817 else if constexpr (__fits<unsigned short>)
818 return (unsigned short)0;
819#endif
820#if __INT_WIDTH__ < __SIZE_WIDTH__ && __INT_WIDTH__ > __SHRT_WIDTH__
821 else if constexpr (__fits<unsigned int>)
822 return 0u;
823#endif
824#if __LONG_WIDTH__ < __SIZE_WIDTH__ && __LONG_WIDTH__ > __INT_WIDTH__
825 else if constexpr (__fits<unsigned long>)
826 return 0ul;
827#endif
828 else // Just use size_t.
829 return 0uz;
830 }
831 decltype(__select_size_type()) _M_size = 0;
832
833 constexpr void
834 _M_init()
835 {
836 if consteval
837 {
838 if constexpr (is_trivially_default_constructible_v<_Tp>
839 && is_trivially_copyable_v<_Tp>)
840 for (size_t __i = 0; __i < _Nm; ++__i)
841 _M_elems[__i] = _Tp();
842 else
843#if __has_builtin(__builtin_constexpr_diag)
844 __builtin_constexpr_diag(2, "",
845 "std::inplace_vector supports only trivally copyable and "
846 "trivially default constructible types at compile time");
847#else
848 __builtin_unreachable();
849#endif
850 }
851 }
852
853 template<typename _Integer>
854 static constexpr size_type
855 _S_check_size(_Integer __n, size_type __size = 0)
856 {
857 if constexpr (__detail::__is_signed_integer_like<_Integer>)
858 if (__n < 0)
859 __throw_bad_alloc();
860 if (__n > (_Nm - __size))
861 __throw_bad_alloc();
862 return static_cast<size_type>(__n);
863 }
864
865 template<typename _Iterator, typename _Sentinel>
866 static constexpr size_type
867 _S_check_distance(_Iterator __first, _Sentinel __last, size_type __size)
868 {
869 for (size_type __i = __size; __i < _Nm; ++__i)
870 if (__first == __last)
871 return __i - __size;
872 else
873 ++__first;
874
875 if (__first == __last)
876 return _Nm - __size;
877
878 __throw_bad_alloc();
879 }
880
881 // Returns the size of the range if it will fit in the remaining
882 // capacity (_Nm - used), otherwise throws bad_alloc.
883 template<typename _InputIterator>
884 constexpr static size_t
885 _S_distance_if_fits(size_t __size, _InputIterator __first, _InputIterator __last)
886 {
887 if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>)
888 return _S_check_size(__last - __first, __size);
889 else
890 return _S_check_distance(__first, __last, __size);
891 }
892
893 // See above.
894 template<typename _Rg>
895 constexpr static size_t
896 _S_distance_if_fits(size_t __size, _Rg& __rg)
897 {
898 if constexpr (ranges::sized_range<_Rg>)
899 return _S_check_size(ranges::size(__rg), __size);
900 else
901 return _S_check_distance(ranges::begin(__rg), ranges::end(__rg),
902 __size);
903 }
904 };
905
906 // specialization for zero capacity, that is required to be trivally copyable
907 // and empty regardless of _Tp.
908 template<typename _Tp>
909 class inplace_vector<_Tp, 0>
910 {
911 public:
912 // types:
913 using value_type = _Tp;
914 using pointer = _Tp*;
915 using const_pointer = const _Tp*;
916 using reference = value_type&;
917 using const_reference = const value_type&;
918 using size_type = size_t;
919 using difference_type = ptrdiff_t;
920 using iterator
921 = __gnu_cxx::__normal_iterator<_Tp*, inplace_vector>;
922 using const_iterator
923 = __gnu_cxx::__normal_iterator<const _Tp*, inplace_vector>;
924 using reverse_iterator = std::reverse_iterator<iterator>;
925 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
926
927 // [containers.sequences.inplace.vector.cons], construct/copy/destroy
928 inplace_vector() = default;
929
930 constexpr explicit
931 inplace_vector(size_type __n)
932 {
933 if (__n != 0)
934 __throw_bad_alloc();
935 }
936
937 constexpr
938 inplace_vector(size_type __n, const _Tp& __value)
939 {
940 if (__n != 0)
941 __throw_bad_alloc();
942 }
943
944 template<__any_input_iterator _InputIterator>
945 constexpr
946 inplace_vector(_InputIterator __first, _InputIterator __last)
947 {
948 if (__first != __last)
949 __throw_bad_alloc();
950 }
951
952 template <__detail::__container_compatible_range<_Tp> _Rg>
953 constexpr
954 inplace_vector(from_range_t, _Rg&& __rg)
955 {
956 if (ranges::begin(__rg) != ranges::end(__rg))
957 __throw_bad_alloc();
958 }
959
960 constexpr
961 inplace_vector(initializer_list<_Tp> __il)
962 {
963 if (__il.size() != 0)
964 __throw_bad_alloc();
965 }
966
967 inplace_vector(const inplace_vector&) = default;
968 inplace_vector(inplace_vector&&) = default;
969
970 constexpr
971 ~inplace_vector() = default;
972
973 inplace_vector&
974 operator=(const inplace_vector&) = default;
975
976 inplace_vector&
977 operator=(inplace_vector&&) = default;
978
979 constexpr inplace_vector&
980 operator=(initializer_list<_Tp> __il)
981 {
982 if (__il.size() != 0)
983 __throw_bad_alloc();
984 return *this;
985 }
986
987 template<__any_input_iterator _InputIterator>
988 constexpr void
989 assign(_InputIterator __first, _InputIterator __last)
990 {
991 if (__first != __last)
992 __throw_bad_alloc();
993 }
994
995 template<__detail::__container_compatible_range<_Tp> _Rg>
996 constexpr void
997 assign_range(_Rg&& __rg)
998 {
999 if (ranges::begin(__rg) != ranges::end(__rg))
1000 __throw_bad_alloc();
1001 }
1002
1003 constexpr void
1004 assign(size_type __n, const _Tp& __u)
1005 {
1006 if (__n != 0)
1007 __throw_bad_alloc();
1008 }
1009
1010 constexpr void
1011 assign(initializer_list<_Tp> __il)
1012 {
1013 if (__il.size() != 0)
1014 __throw_bad_alloc();
1015 }
1016
1017 // iterators
1018 [[nodiscard]]
1019 constexpr iterator
1020 begin() noexcept { return iterator(nullptr); }
1021
1022 [[nodiscard]]
1023 constexpr const_iterator
1024 begin() const noexcept { return const_iterator(nullptr); }
1025
1026 [[nodiscard]]
1027 constexpr iterator
1028 end() noexcept { return iterator(nullptr); }
1029
1030 [[nodiscard]]
1031 constexpr const_iterator
1032 end() const noexcept { return const_iterator(nullptr); }
1033
1034 [[nodiscard]]
1035 constexpr reverse_iterator
1036 rbegin() noexcept
1037 { return reverse_iterator(end()); }
1038
1039 [[nodiscard]]
1040 constexpr const_reverse_iterator
1041 rbegin() const noexcept
1042 { return const_reverse_iterator(end()); }
1043
1044 [[nodiscard]]
1045 constexpr reverse_iterator
1046 rend() noexcept { return reverse_iterator(begin()); }
1047
1048 [[nodiscard]]
1049 constexpr const_reverse_iterator
1050 rend() const noexcept { return const_reverse_iterator(begin()); }
1051
1052 [[nodiscard]]
1053 constexpr const_iterator
1054 cbegin() const noexcept { return begin(); }
1055
1056 [[nodiscard]]
1057 constexpr const_iterator
1058 cend() const noexcept { return end(); }
1059
1060 [[nodiscard]]
1061 constexpr const_reverse_iterator
1062 crbegin() const noexcept { return rbegin(); }
1063
1064 [[nodiscard]]
1065 constexpr const_reverse_iterator
1066 crend() const noexcept { return rend(); }
1067
1068 // [containers.sequences.inplace.vector.members] size/capacity
1069 [[nodiscard]]
1070 constexpr bool
1071 empty() const noexcept { return true; }
1072
1073 [[nodiscard]]
1074 constexpr size_type
1075 size() const noexcept { return 0; }
1076
1077 [[nodiscard]]
1078 static constexpr size_type
1079 max_size() noexcept { return 0; }
1080
1081 [[nodiscard]]
1082 static constexpr size_type
1083 capacity() noexcept { return 0; }
1084
1085 constexpr void
1086 resize(size_type __n)
1087 {
1088 if (__n != 0)
1089 __throw_bad_alloc();
1090 }
1091
1092 constexpr void
1093 resize(size_type __n, const _Tp&)
1094 {
1095 if (__n != 0)
1096 __throw_bad_alloc();
1097 }
1098
1099 static constexpr void
1100 reserve(size_type __n)
1101 {
1102 if (__n != 0)
1103 __throw_bad_alloc();
1104 }
1105
1106 static constexpr void
1107 shrink_to_fit() { }
1108
1109 // element access
1110 [[nodiscard,noreturn]]
1111 constexpr reference
1112 operator[](size_type)
1113 { __builtin_trap(); }
1114
1115 [[nodiscard,noreturn]]
1116 constexpr const_reference
1117 operator[](size_type) const
1118 { __builtin_trap(); }
1119
1120 [[nodiscard,noreturn]]
1121 constexpr const_reference
1122 at(size_type __n) const
1123 {
1124 std::__throw_out_of_range_fmt(__N("inplace_vector::at: __n "
1125 "(which is %zu) "
1126 ">= size() (which is 0)"),
1127 __n);
1128 }
1129
1130 [[nodiscard,noreturn]]
1131 constexpr reference
1132 at(size_type __n)
1133 {
1134 std::__throw_out_of_range_fmt(__N("inplace_vector::at: __n "
1135 "(which is %zu) "
1136 ">= size() (which is 0)"),
1137 __n);
1138 }
1139
1140 [[nodiscard,noreturn]]
1141 constexpr reference
1142 front()
1143 { __builtin_trap(); }
1144
1145 [[nodiscard,noreturn]]
1146 constexpr const_reference
1147 front() const
1148 { __builtin_trap(); }
1149
1150 [[nodiscard,noreturn]]
1151 constexpr reference
1152 back()
1153 { __builtin_trap(); }
1154
1155 [[nodiscard,noreturn]]
1156 constexpr const_reference
1157 back() const
1158 { __builtin_trap(); }
1159
1160 // [containers.sequences.inplace.vector.data], data access
1161
1162 [[nodiscard]]
1163 constexpr _Tp*
1164 data() noexcept
1165 { return nullptr; }
1166
1167 [[nodiscard]]
1168 constexpr const _Tp*
1169 data() const noexcept
1170 { return nullptr; }
1171
1172 // [containers.sequences.inplace.vector.modifiers], modifiers
1173 template<typename... _Args>
1174 [[noreturn]]
1175 constexpr _Tp&
1176 emplace_back(_Args&&...)
1177 { __throw_bad_alloc(); }
1178
1179 [[noreturn]]
1180 constexpr _Tp&
1181 push_back(const _Tp&)
1182 { __throw_bad_alloc(); }
1183
1184 [[noreturn]]
1185 constexpr _Tp&
1186 push_back(_Tp&&)
1187 { __throw_bad_alloc(); }
1188
1189 template<__detail::__container_compatible_range<_Tp> _Rg>
1190 constexpr void
1191 append_range(_Rg&& __rg)
1192 {
1193 if (ranges::begin(__rg) != ranges::end(__rg))
1194 __throw_bad_alloc();
1195 }
1196
1197 [[noreturn]]
1198 constexpr void
1199 pop_back()
1200 { __builtin_trap(); }
1201
1202 template<typename... _Args>
1203 constexpr optional<_Tp&>
1204 try_emplace_back(_Args&&...)
1205 { return nullopt; }
1206
1207 constexpr optional<_Tp&>
1208 try_push_back(const _Tp&)
1209 { return nullopt; }
1210
1211 constexpr optional<_Tp&>
1212 try_push_back(_Tp&&)
1213 { return nullopt; }
1214
1215 template<typename... _Args>
1216 [[noreturn]]
1217 constexpr _Tp&
1218 unchecked_emplace_back(_Args&&...)
1219 { __builtin_trap(); }
1220
1221 [[noreturn]]
1222 constexpr _Tp&
1223 unchecked_push_back(const _Tp&)
1224 { __builtin_trap(); }
1225
1226 [[noreturn]]
1227 constexpr _Tp&
1228 unchecked_push_back(_Tp&&)
1229 { __builtin_trap(); }
1230
1231 template<typename... _Args>
1232 [[noreturn]]
1233 constexpr iterator
1234 emplace(const_iterator, _Args&&...)
1235 { __throw_bad_alloc(); }
1236
1237 [[noreturn]]
1238 constexpr iterator
1239 insert(const_iterator, const _Tp&)
1240 { __throw_bad_alloc(); }
1241
1242 [[noreturn]]
1243 constexpr iterator
1244 insert(const_iterator, _Tp&&)
1245 { __throw_bad_alloc(); }
1246
1247 constexpr iterator
1248 insert(const_iterator, size_type __n, const _Tp&)
1249 {
1250 if (__n != 0)
1251 __throw_bad_alloc();
1252 return begin();
1253 }
1254
1255 template<typename _InputIterator>
1256 constexpr iterator
1257 insert(const_iterator, _InputIterator __first, _InputIterator __last)
1258 {
1259 if (__first != __last)
1260 __throw_bad_alloc();
1261 return begin();
1262 }
1263
1264 template<__detail::__container_compatible_range<_Tp> _Rg>
1265 constexpr iterator
1266 insert_range(const_iterator, _Rg&& __rg)
1267 {
1268 if (ranges::begin(__rg) != ranges::end(__rg))
1269 __throw_bad_alloc();
1270 return begin();
1271 }
1272
1273 constexpr iterator
1274 insert(const_iterator, initializer_list<_Tp> __il)
1275 {
1276 if (__il.size() != 0)
1277 __throw_bad_alloc();
1278 return begin();
1279 }
1280
1281 [[noreturn]]
1282 constexpr iterator
1283 erase(const_iterator)
1284 { __builtin_trap(); }
1285
1286 constexpr iterator
1287 erase(const_iterator __first, const_iterator __last)
1288 {
1289 __glibcxx_assert(__first == __last);
1290 return begin();
1291 }
1292
1293 constexpr void
1294 swap(inplace_vector& __x)
1295 noexcept
1296 { }
1297
1298 constexpr void
1299 clear() noexcept
1300 { }
1301
1302 constexpr friend bool
1303 operator==(const inplace_vector&, const inplace_vector&)
1304 { return true; }
1305
1306 constexpr friend auto
1307 operator<=>(const inplace_vector&, const inplace_vector&)
1308 requires requires (const _Tp __t) {
1309 { __t < __t } -> __detail::__boolean_testable;
1310 }
1311 { return std::strong_ordering::equal; }
1312
1313 // n.b. there is not explicit wording requiring that swap for inplace_vector,
1314 // with zero size, works even if element type is not swappable. However given
1315 // that move operations are required to be present and trivial, it makes sense
1316 // to support them.
1317 constexpr friend void
1318 swap(inplace_vector&, inplace_vector&) noexcept
1319 { }
1320 };
1321
1322_GLIBCXX_END_NAMESPACE_CONTAINER
1323
1324 template<typename _Tp, size_t _Nm, typename _Predicate>
1325 constexpr size_t
1326 erase_if(_GLIBCXX_STD_C::inplace_vector<_Tp, _Nm>& __cont,
1327 _Predicate __pred)
1328 {
1329 if constexpr (_Nm != 0)
1330 return __detail::__erase_if(__cont, __cont, std::move(__pred));
1331
1332 return 0;
1333 }
1334
1335 template<typename _Tp, size_t _Nm, typename _Up = _Tp>
1336 constexpr size_t
1337 erase(_GLIBCXX_STD_C::inplace_vector<_Tp, _Nm>& __cont, const _Up& __value)
1338 { return std::erase_if(__cont, __gnu_cxx::__ops::__equal_to(__value)); }
1339
1340_GLIBCXX_END_NAMESPACE_VERSION
1341} // namespace
1342
1343#ifdef _GLIBCXX_DEBUG
1344# include <debug/inplace_vector>
1345#endif
1346
1347#endif // __glibcxx_inplace_vector
1348#endif // _GLIBCXX_INPLACE_VECTOR
constexpr _ForwardIterator uninitialized_value_construct_n(_ForwardIterator __first, _Size __count)
Value-initializes objects in the range [first,first+count).
constexpr _ForwardIterator uninitialized_move(_InputIterator __first, _InputIterator __last, _ForwardIterator __result)
Move-construct from the range [first,last) into result.
constexpr _ForwardIterator uninitialized_fill_n(_ForwardIterator __first, _Size __n, const _Tp &__x)
Copies the value x into the range [first,first+n).
constexpr _ForwardIterator uninitialized_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result)
Copies the range [first,last) into result.
constexpr _Tp * addressof(_Tp &__r) noexcept
Returns the actual address of the object or function referenced by r, even in the presence of an over...
Definition move.h:176
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:138
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition move.h:72
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
Definition valarray:1251
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition valarray:1229
constexpr auto lexicographical_compare_three_way(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _Comp __comp) -> decltype(__comp(*__first1, *__first2))
Performs dictionary comparison on ranges.
constexpr nullopt_t nullopt
Tag to disengage optional objects.
ISO C++ entities toplevel namespace is std.
constexpr auto rbegin(_Container &__cont) noexcept(noexcept(__cont.rbegin())) -> decltype(__cont.rbegin())
Return a reverse iterator pointing to the last element of the container.
constexpr _ForwardIterator _Destroy_n(_ForwardIterator __first, _Size __count)
constexpr auto cend(const _Container &__cont) noexcept(noexcept(std::end(__cont))) -> decltype(std::end(__cont))
Return an iterator pointing to one past the last element of the const container.
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
constexpr auto crbegin(const _Container &__cont) noexcept(noexcept(std::rbegin(__cont))) -> decltype(std::rbegin(__cont))
Return a reverse iterator pointing to the last element of the const container.
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
constexpr auto data(_Container &__cont) noexcept(noexcept(__cont.data())) -> decltype(__cont.data())
Return the data pointer of a container.
constexpr auto cbegin(const _Container &__cont) noexcept(noexcept(std::begin(__cont))) -> decltype(std::begin(__cont))
Return an iterator pointing to the first element of the const container.
constexpr auto rend(_Container &__cont) noexcept(noexcept(__cont.rend())) -> decltype(__cont.rend())
Return a reverse iterator pointing one past the first element of the container.
constexpr auto crend(const _Container &__cont) noexcept(noexcept(std::rend(__cont))) -> decltype(std::rend(__cont))
Return a reverse iterator pointing one past the first element of the const container.
initializer_list
Common iterator class.