On 17/07/25 11:26 -0400, Patrick Palka wrote:
On Thu, 17 Jul 2025, Tomasz Kamiński wrote:
From: Jonathan Wakely <jwak...@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 <tkami...@redhat.com>
Signed-off-by: Tomasz Kamiński <tkami...@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.
