On Thu, 17 Jul 2025, Jonathan Wakely wrote:
> 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.
>
> They don't, but maybe they should (PR 100070, and the work I've been
> doing for std::distance and std::prev for PR 102181).
Ah, and specifically for containers this is allowed by
[container.reqmnts]/69:
The behavior of certain container member functions and deduction guides
depends on whether types qualify as input iterators or allocators.
The extent to which an implementation determines that a type cannot be
an input iterator is unspecified, except that as a minimum integral
types shall not qualify as input iterators.
We should define this generalized __input_iterator concept in a common
place, say next to __has_input_iter_cat.
