[PATCH] libstdc++: Add std::inplace_vector for C++26 (P0843R14) [PR119137]
Jonathan Wakely
jwakely@redhat.com
Thu Jul 17 17:36:47 GMT 2025
On 17/07/25 11:26 -0400, Patrick Palka wrote:
>On Thu, 17 Jul 2025, Tomasz Kamiński wrote:
>
>> From: Jonathan Wakely <jwakely@redhat.com>
>>
>> Implement std::inplace_vector as specified in P0843R14, without follow
>> up papers, in particular P3074R7 (trivial unions). In consequence
>> inplace_vector<T, N> can be used inside constant evaluations only
>> if T is trivial of N is equal to zero.
>
>... or N is ...
>
>>
>> We provide a separate specialization for inplace_vector<T, 0> to meet
>> the requirements of N5008 [inplace.vector.overview] p5. In particular
>> objects of such types needs to be empty.
>
>Can't we just make the _M_elems data member conditionally present in the
>primary template and add N != 0 constraints where appropriate etc, or
>would that be too ugly?
>
>>
>> To allow contexpr variable of inplace_vector v, where v.size() < v.capacity(),
>
>constexpr
>
>> we need to guaranteed that all elements of the storage array are initialized,
>> even ones in range [v.data() + v.size(), v.data() + v.capacity()). This is
>> perfomed by _M_init function, that is alled by each constructored. By storing
>> the array in animous union, we can perform this intialization in constant
>
>anonymous, initialization
>
>> evaluation, avoiding the impact on runtime path.
>>
>> The size() function conveys the information that _M_size <= _Nm to compiler,
>> by calling __builtin_unreachable(). In particular this allows us to eliminate
>> FP warnings by using _Nm - size() instead of _Nm - _M_size, when computing
>> available elements.
>>
>> However, we still have one -Waggressive-loop-optimizations (to best of our
>> knowledge false-positive warning produced in cons/from_range.cc and
>> cons/throws.cc. Currently it is pruned using dg-prune-output and tracked by
>> PR121143.
>>
>> The included test cover almost all code paths at runtime, however some
>> compile time evaluation test are not yet implemented:
>> * operations on range, they depenend on making testsuite_iterators constexpr
>> * negative test for invoking operations with preconditions at compile time,
>> especially for zero size specialization.
>>
>> PR libstdc++/119137
>>
>> libstdc++-v3/ChangeLog:
>>
>> * doc/doxygen/user.cfg.in (INPUT): Add new header.
>> * include/Makefile.am: Add new header.
>> * include/Makefile.in: Regenerate.
>> * include/bits/version.def (inplace_vector): Define.
>> * include/bits/version.h: Regenerate.
>> * include/precompiled/stdc++.h: Include new header.
>> * src/c++23/std.cc.in: Export contents if new header.
>> * include/std/inplace_vector: New file.
>> * testsuite/23_containers/inplace_vector/access/capacity.cc: New file.
>> * testsuite/23_containers/inplace_vector/access/elem.cc: New file.
>> * testsuite/23_containers/inplace_vector/access/elem_neg.cc: New file.
>> * testsuite/23_containers/inplace_vector/cons/1.cc: New file.
>> * testsuite/23_containers/inplace_vector/cons/from_range.cc: New file.
>> * testsuite/23_containers/inplace_vector/cons/throws.cc: New file.
>> * testsuite/23_containers/inplace_vector/copy.cc: New file.
>> * testsuite/23_containers/inplace_vector/erasure.cc: New file.
>> * testsuite/23_containers/inplace_vector/modifiers/assign.cc: New file.
>> * testsuite/23_containers/inplace_vector/modifiers/erase.cc: New file.
>> * testsuite/23_containers/inplace_vector/modifiers/multi_insert.cc:
>> New file.
>> * testsuite/23_containers/inplace_vector/modifiers/single_insert.cc:
>> New file.
>> * testsuite/23_containers/inplace_vector/move.cc: New file.
>> * testsuite/23_containers/inplace_vector/relops.cc: New file.
>> * testsuite/23_containers/inplace_vector/version.cc: New file.
>> * testsuite/util/testsuite_iterators.h (input_iterator_wrapper::base):
>> Define.
>>
>> Co-authored-by: Tomasz Kamiński <tkaminsk@redhat.com>
>> Signed-off-by: Tomasz Kamiński <tkaminsk@redhat.com>
>> ---
>> Jonathan have provided initial implementation, that I (Tomasz) have
>> later finished and extended the test coverate. Details can be found at:
>> https://forge.sourceware.org/gcc/gcc-TEST/pulls/58
>>
>> Tested on x86_64-linux. OK for trunk?
>>
>> libstdc++-v3/doc/doxygen/user.cfg.in | 1 +
>> libstdc++-v3/include/Makefile.am | 1 +
>> libstdc++-v3/include/Makefile.in | 1 +
>> libstdc++-v3/include/bits/version.def | 8 +
>> libstdc++-v3/include/bits/version.h | 10 +
>> libstdc++-v3/include/precompiled/stdc++.h | 1 +
>> libstdc++-v3/include/std/inplace_vector | 1397 +++++++++++++++++
>> libstdc++-v3/src/c++23/std.cc.in | 10 +-
>> .../inplace_vector/access/capacity.cc | 51 +
>> .../inplace_vector/access/elem.cc | 103 ++
>> .../inplace_vector/access/elem_neg.cc | 29 +
>> .../23_containers/inplace_vector/cons/1.cc | 385 +++++
>> .../inplace_vector/cons/from_range.cc | 186 +++
>> .../inplace_vector/cons/throws.cc | 131 ++
>> .../23_containers/inplace_vector/copy.cc | 247 +++
>> .../23_containers/inplace_vector/erasure.cc | 49 +
>> .../inplace_vector/modifiers/assign.cc | 386 +++++
>> .../inplace_vector/modifiers/erase.cc | 117 ++
>> .../inplace_vector/modifiers/multi_insert.cc | 611 +++++++
>> .../inplace_vector/modifiers/single_insert.cc | 215 +++
>> .../23_containers/inplace_vector/move.cc | 358 +++++
>> .../23_containers/inplace_vector/relops.cc | 60 +
>> .../23_containers/inplace_vector/version.cc | 20 +
>> .../testsuite/util/testsuite_iterators.h | 6 +
>> 24 files changed, 4382 insertions(+), 1 deletion(-)
>> create mode 100644 libstdc++-v3/include/std/inplace_vector
>> create mode 100644 libstdc++-v3/testsuite/23_containers/inplace_vector/access/capacity.cc
>> create mode 100644 libstdc++-v3/testsuite/23_containers/inplace_vector/access/elem.cc
>> create mode 100644 libstdc++-v3/testsuite/23_containers/inplace_vector/access/elem_neg.cc
>> create mode 100644 libstdc++-v3/testsuite/23_containers/inplace_vector/cons/1.cc
>> create mode 100644 libstdc++-v3/testsuite/23_containers/inplace_vector/cons/from_range.cc
>> create mode 100644 libstdc++-v3/testsuite/23_containers/inplace_vector/cons/throws.cc
>> create mode 100644 libstdc++-v3/testsuite/23_containers/inplace_vector/copy.cc
>> create mode 100644 libstdc++-v3/testsuite/23_containers/inplace_vector/erasure.cc
>> create mode 100644 libstdc++-v3/testsuite/23_containers/inplace_vector/modifiers/assign.cc
>> create mode 100644 libstdc++-v3/testsuite/23_containers/inplace_vector/modifiers/erase.cc
>> create mode 100644 libstdc++-v3/testsuite/23_containers/inplace_vector/modifiers/multi_insert.cc
>> create mode 100644 libstdc++-v3/testsuite/23_containers/inplace_vector/modifiers/single_insert.cc
>> create mode 100644 libstdc++-v3/testsuite/23_containers/inplace_vector/move.cc
>> create mode 100644 libstdc++-v3/testsuite/23_containers/inplace_vector/relops.cc
>> create mode 100644 libstdc++-v3/testsuite/23_containers/inplace_vector/version.cc
>>
>> diff --git a/libstdc++-v3/doc/doxygen/user.cfg.in b/libstdc++-v3/doc/doxygen/user.cfg.in
>> index 536e035b023..8969bb8b948 100644
>> --- a/libstdc++-v3/doc/doxygen/user.cfg.in
>> +++ b/libstdc++-v3/doc/doxygen/user.cfg.in
>> @@ -869,6 +869,7 @@ INPUT = @srcdir@/doc/doxygen/doxygroups.cc \
>> include/functional \
>> include/future \
>> include/generator \
>> + include/inplace_vector \
>> include/iomanip \
>> include/ios \
>> include/iosfwd \
>> diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am
>> index cc402f0648f..6f248fe48cb 100644
>> --- a/libstdc++-v3/include/Makefile.am
>> +++ b/libstdc++-v3/include/Makefile.am
>> @@ -77,6 +77,7 @@ std_headers = \
>> ${std_srcdir}/forward_list \
>> ${std_srcdir}/fstream \
>> ${std_srcdir}/future \
>> + ${std_srcdir}/inplace_vector \
>> ${std_srcdir}/iomanip \
>> ${std_srcdir}/ios \
>> ${std_srcdir}/iosfwd \
>> diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in
>> index 0ef8564f238..014466fc40b 100644
>> --- a/libstdc++-v3/include/Makefile.in
>> +++ b/libstdc++-v3/include/Makefile.in
>> @@ -433,6 +433,7 @@ std_freestanding = \
>> @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/forward_list \
>> @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/fstream \
>> @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/future \
>> +@GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/inplace_vector \
>> @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/iomanip \
>> @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/ios \
>> @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/iosfwd \
>> diff --git a/libstdc++-v3/include/bits/version.def b/libstdc++-v3/include/bits/version.def
>> index 2f70a529927..dbe2cb8f175 100644
>> --- a/libstdc++-v3/include/bits/version.def
>> +++ b/libstdc++-v3/include/bits/version.def
>> @@ -1988,6 +1988,14 @@ ftms = {
>> };
>> };
>>
>> +ftms = {
>> + name = inplace_vector;
>> + values = {
>> + v = 202406;
>> + cxxmin = 26;
>> + };
>> +};
>> +
>> ftms = {
>> name = indirect;
>> values = {
>> diff --git a/libstdc++-v3/include/bits/version.h b/libstdc++-v3/include/bits/version.h
>> index 8e0ae682251..7bb6016df68 100644
>> --- a/libstdc++-v3/include/bits/version.h
>> +++ b/libstdc++-v3/include/bits/version.h
>> @@ -2229,6 +2229,16 @@
>> #endif /* !defined(__cpp_lib_modules) && defined(__glibcxx_want_modules) */
>> #undef __glibcxx_want_modules
>>
>> +#if !defined(__cpp_lib_inplace_vector)
>> +# if (__cplusplus > 202302L)
>> +# define __glibcxx_inplace_vector 202406L
>> +# if defined(__glibcxx_want_all) || defined(__glibcxx_want_inplace_vector)
>> +# define __cpp_lib_inplace_vector 202406L
>> +# endif
>> +# endif
>> +#endif /* !defined(__cpp_lib_inplace_vector) && defined(__glibcxx_want_inplace_vector) */
>> +#undef __glibcxx_want_inplace_vector
>> +
>> #if !defined(__cpp_lib_indirect)
>> # if (__cplusplus > 202302L) && _GLIBCXX_HOSTED
>> # define __glibcxx_indirect 202502L
>> diff --git a/libstdc++-v3/include/precompiled/stdc++.h b/libstdc++-v3/include/precompiled/stdc++.h
>> index e7d89c92704..733a5e5fb0b 100644
>> --- a/libstdc++-v3/include/precompiled/stdc++.h
>> +++ b/libstdc++-v3/include/precompiled/stdc++.h
>> @@ -237,6 +237,7 @@
>> #endif
>>
>> #if __cplusplus > 202302L
>> +#include <inplace_vector>
>> #include <text_encoding>
>> #include <stdbit.h>
>> #include <stdckdint.h>
>> diff --git a/libstdc++-v3/include/std/inplace_vector b/libstdc++-v3/include/std/inplace_vector
>> new file mode 100644
>> index 00000000000..780d84821ee
>> --- /dev/null
>> +++ b/libstdc++-v3/include/std/inplace_vector
>> @@ -0,0 +1,1397 @@
>> +// Sequence container with fixed capacity -*- C++ -*-
>> +
>> +// Copyright The GNU Toolchain Authors.
>> +//
>> +// This file is part of the GNU ISO C++ Library. This library is free
>> +// software; you can redistribute it and/or modify it under the
>> +// terms of the GNU General Public License as published by the
>> +// Free Software Foundation; either version 3, or (at your option)
>> +// any later version.
>> +
>> +// This library is distributed in the hope that it will be useful,
>> +// but WITHOUT ANY WARRANTY; without even the implied warranty of
>> +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
>> +// GNU General Public License for more details.
>> +
>> +// Under Section 7 of GPL version 3, you are granted additional
>> +// permissions described in the GCC Runtime Library Exception, version
>> +// 3.1, as published by the Free Software Foundation.
>> +
>> +// You should have received a copy of the GNU General Public License and
>> +// a copy of the GCC Runtime Library Exception along with this program;
>> +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
>> +// <http://www.gnu.org/licenses/>.
>> +
>> +/** @file include/inplace_vector
>> + * This is a Standard C++ Library header.
>> + * @ingroup sequences
>> + */
>> +
>> +#ifndef _GLIBCXX_INPLACE_VECTOR
>> +#define _GLIBCXX_INPLACE_VECTOR 1
>> +
>> +#pragma GCC system_header
>> +
>> +#define __glibcxx_want_inplace_vector
>> +#include <bits/version.h>
>> +
>> +#ifdef __cpp_lib_inplace_vector
>
>Maybe add a
>
>// C++ >= 26
>
>comment to this preprocessor condition
>
>> +#include <compare>
>> +#include <initializer_list>
>> +#include <bits/range_access.h>
>> +#include <bits/ranges_base.h> // borrowed_iterator_t, __detail::__container_compatible_range
>> +#include <bits/ranges_util.h> // subrange
>> +#include <bits/ranges_uninitialized.h>
>> +#include <bits/refwrap.h>
>> +#include <bits/stl_construct.h>
>> +#include <bits/stl_uninitialized.h>
>> +#include <bits/stl_algo.h> // rotate
>> +#include <ranges> // for views::as_rvalue TODO: move to another header?
>
>Looks like as_rvalue is no longer needed can we get of this include?
>
>> +
>> +namespace std _GLIBCXX_VISIBILITY(default)
>> +{
>> +_GLIBCXX_BEGIN_NAMESPACE_VERSION
>> +
>> +namespace __detail
>> +{
>> + // Is a Cpp17InputIterator or satisfies std::input_iterator.
>> + template<typename _InputIterator>
>> + concept __input_iterator
>> + = input_iterator<_InputIterator>
>> + || derived_from<__iter_category_t<_InputIterator>,
>> + input_iterator_tag>;
>
>There's __has_input_iter_cat which we can use here.
>I wonder why does inplace_vector specifically need to check
>for both C++20 and legacy InputIterators? I don't think other
>containers do this currently.
>
>> +}
>> +
>> + // [indirect], class template indirect
>> + template<typename _Tp, size_t _Nm>
>> + class inplace_vector
>> + {
>> + public:
>> +
>> + // types:
>> + using value_type = _Tp;
>> + using pointer = _Tp*;
>> + using const_pointer = const _Tp*;
>> + using reference = value_type&;
>> + using const_reference = const value_type&;
>> + using size_type = size_t;
>> + using difference_type = ptrdiff_t;
>> + using iterator
>> + = __gnu_cxx::__normal_iterator<_Tp*, inplace_vector>;
>> + using const_iterator
>> + = __gnu_cxx::__normal_iterator<const _Tp*, inplace_vector>;
>> + using reverse_iterator = std::reverse_iterator<iterator>;
>> + using const_reverse_iterator = std::reverse_iterator<const_iterator>;
>> +
>> + // [containers.sequences.inplace.vector.cons], construct/copy/destroy
>> + constexpr
>> + inplace_vector() noexcept
>> + { _M_init(); }
>> +
>> + constexpr explicit
>> + inplace_vector(size_type __n)
>> + {
>> + _M_init();
>> + _M_reserve(__n);
>> + std::uninitialized_value_construct_n(data(), __n);
>> + _M_size = __n;
>> + }
>> +
>> + constexpr
>> + inplace_vector(size_type __n, const _Tp& __value)
>> + {
>> + _M_init();
>> + _M_reserve(__n);
>> + std::uninitialized_fill_n(data(), __n, __value);
>> + _M_size = __n;
>> + }
>> +
>> + template<typename _InputIterator>
>> + requires __detail::__input_iterator<_InputIterator>
>
>template<__detail::__input_iterator _InputIterator>
>
>if you prefer
>
>> + constexpr
>> + inplace_vector(_InputIterator __first, _InputIterator __last)
>> + : inplace_vector()
>> + {
>> + if (const auto __n = _S_distance(__first, __last))
>> + {
>> + _M_reserve(__n);
>> + std::uninitialized_copy(__first, __last, data());
>
>I notice there's no explicit exception handling here and throughout
>the rest of the implementation. I guess the exception guarantees of
>inplace_vector are implicitly met since there's no allocation going on?
uninitialized_copy will clean up after an exception, and there's
nothing else happening in this branch.
>> + _M_size = __n;
>> + }
>> + else
>> + {
>> + while (__first != __last)
>> + emplace_back(*__first++);
Because this uses a delegating constructor, ~inplace_vector will run
if an exception happens. Every time we succeed at emplace_back we
increment the size, and the destructor will destroy that element.
I think all other functions should behave similarly, e.g. see
insert_range which is one of the more complex members:
>> + template<__detail::__container_compatible_range<_Tp> _Rg>
>> + constexpr iterator
>> + insert_range(const_iterator __position, _Rg&& __rg)
>> + {
>> + iterator __pos = begin() + (__position - cbegin());
>> + const auto __end = end();
>> + if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
>> + {
>> + const auto __len = ranges::distance(__rg);
>> + if (__len > (_Nm - size()))
>> + __throw_bad_alloc();
>> + if (!__len) [[unlikely]]
>> + return __pos;
>> +
>> + const size_type __n = size_type(__len);
>> + const size_type __num_after = __end - __pos;
>> + if (__num_after >= __n)
>> + {
>> + ranges::uninitialized_move(__end - __n, __end,
>> + __end, unreachable_sentinel);
We finished a call to uninitialized_move which created new elements,
so update the size, so that the destructor will clean up:
>> + _M_size += __n;
>> + ranges::move_backward(__pos, __end - __n, __end);
>> + ranges::copy(__rg, __pos);
>> + }
>> + else if constexpr (ranges::forward_range<_Rg>)
>> + {
>> + auto __mid = ranges::next(ranges::begin(__rg), __num_after);
>> + ranges::uninitialized_copy(__mid, ranges::end(__rg),
>> + __end, unreachable_sentinel);
Again, we created some new elements, so update the size:
>> + _M_size += __n - __num_after;
>> + ranges::uninitialized_move(__pos, __end,
>> + __pos + __n, unreachable_sentinel);
And again:
>> + _M_size += __num_after;
>> + ranges::copy(ranges::begin(__rg), __mid, __pos);
>> + }
>> + else
>> + {
>> + ranges::uninitialized_copy(
>> + ranges::begin(__rg), ranges::end(__rg),
>> + __end, unreachable_sentinel);
>> + _M_size += __n;
>> + std::rotate(__pos, __end, end());
>> + }
>> + }
>> + else
>> + {
>> + append_range(__rg);
>> + std::rotate(__pos, __end, end());
>> + }
>> + return __pos;
>> + }
So yes, in general we don't need to catch an exception and make sure
we deallocate anything, because we didn't allocate. And by carefully
updating _M_size as soon as we add new elements, we can trust that the
destructor will clean them all up.
> +
>> + template<typename _Tp, size_t _Nm, typename _Predicate>
>> + _GLIBCXX20_CONSTEXPR
>
>Can just use 'constexpr' here (and remove 'inline')
Oops, yes, copy&paste from vector's erase_if
>> + inline size_t
>> + erase_if(inplace_vector<_Tp, _Nm>& __cont, _Predicate __pred)
>> + {
>> + using namespace __gnu_cxx;
>> + _GLIBCXX_STD_C::inplace_vector<_Tp, _Nm>& __ucont = __cont;
>> + const auto __osz = __cont.size();
>> + const auto __end = __ucont.end();
>> + auto __removed = std::__remove_if(__ucont.begin(), __end,
>> + __ops::__pred_iter(std::ref(__pred)));
>> + if (__removed != __end)
>> + {
>> + __cont.erase(__niter_wrap(__cont.begin(), __removed),
>> + __cont.end());
>> + return __osz - __cont.size();
>> + }
>> + return 0;
>> + }
>> +
>> +
>> + template<typename _Tp, size_t _Nm, typename _Up>
>> + _GLIBCXX20_CONSTEXPR
>
>same
>
>> + inline size_t
>> + erase(inplace_vector<_Tp, _Nm>& __cont, const _Up& __value)
>> + {
>> + using namespace __gnu_cxx;
>> + using namespace __gnu_cxx;
>
>Redundant 'using namespace'
>
>> + _GLIBCXX_STD_C::inplace_vector<_Tp, _Nm>& __ucont = __cont;
>> + const auto __osz = __cont.size();
>> + const auto __end = __ucont.end();
>> + auto __removed = std::__remove_if(__ucont.begin(), __end,
>> + __ops::__iter_equals_val(__value));
>> + if (__removed != __end)
>> + {
>> + __cont.erase(__niter_wrap(__cont.begin(), __removed),
>> + __cont.end());
>> + return __osz - __cont.size();
>> + }
>> + return 0;
>> + }
>
>I don't know what the _GLIBCXX_STD_C:: is for, and I had some
>stylistic suggestions for these functions, but I see they currently
>mirror the erase_if/erase implementations which I guess is nice
>for consistency.
It's for debug mode, copied from vector's erase, but not needed here.
In non-debug mode _GLIBCXX_STD_C is just std. In debug mode it's the
namespace for the unsafe containers. That's needed because in debug
mode std::vector is the "safe" vector, and _GLIBCXX_STD_C::vector is
how you have to refer to its unsafe base class (the normal non-debug
std::vector, but in a different namespace because the name std::vector
has been hijacked by the debug one).
Using the macro here means we operate directly on the unsafe base, not
the debug container. So we call remove_if on the underlying unsafe
iterators, and skip all the checks that would happen if we used the
safe iterators. That's OK because we know that [begin(),end()) is a
valid range, and we trust that __remove_if will not go out of bounds.
But there's no debug inplace_vector (yet?) so it's not needed here.
Your other comments look good too, thanks.
More information about the Libstdc++
mailing list