libstdc++-v3/include/std/inplace_vector

// 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 __glibcxx_inplace_vector // C++ >= 26
#include <compare>
#include <initializer_list>
#include <bits/stdexcept_throw.h>
#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/stl_construct.h>
#include <bits/stl_uninitialized.h>
#include <bits/stl_algo.h> // rotate

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
_GLIBCXX_BEGIN_NAMESPACE_CONTAINER

  // [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();
	_S_reserve(__n);
	std::uninitialized_value_construct_n(data(), __n);
	_M_size = __n;
      }

      constexpr
      inplace_vector(size_type __n, const _Tp& __value)
      {
	_M_init();
	_S_reserve(__n);
	std::uninitialized_fill_n(data(), __n, __value);
	_M_size = __n;
      }

      template<__any_input_iterator _InputIterator>
	constexpr
	inplace_vector(_InputIterator __first, _InputIterator __last)
	: inplace_vector()
	{
	  if (const auto __n = _S_distance(__first, __last))
	    {
	      _S_reserve(__n);
	      std::uninitialized_copy(__first, __last, data());
	      _M_size = __n;
	    }
	  else
	    {
	      while (__first != __last)
		emplace_back(*__first++);
	    }
	}

      template <__detail::__container_compatible_range<_Tp> _Rg>
	constexpr
	inplace_vector(from_range_t, _Rg&& __rg)
	: inplace_vector()
	{ append_range(__rg); }

      constexpr
      inplace_vector(initializer_list<_Tp> __il)
      {
	_M_init();
	_S_reserve(__il.size());
	std::uninitialized_copy(__il.begin(), __il.end(), data());
	_M_size = __il.size();
      }

      inplace_vector(const inplace_vector&)
	requires is_trivially_copy_constructible_v<_Tp>
	= default;

      constexpr
      inplace_vector(const inplace_vector& __other)
      noexcept(is_nothrow_copy_constructible_v<_Tp>)
      {
	_M_init();
	std::uninitialized_copy(__other.begin(), __other.end(), data());
	_M_size = __other.size();
      }

      inplace_vector(inplace_vector&&)
	requires is_trivially_move_constructible_v<_Tp>
	= default;

      constexpr
      inplace_vector(inplace_vector&& __other)
      noexcept(is_nothrow_move_constructible_v<_Tp>)
      {
	_M_init();
	std::uninitialized_move(__other.begin(), __other.end(), data());
	_M_size = __other.size();
      }

      ~inplace_vector()
	requires is_trivially_destructible_v<_Tp>
	= default;

      constexpr
      ~inplace_vector()
      { clear(); }

      inplace_vector&
      operator=(const inplace_vector&)
	requires is_trivially_copy_assignable_v<_Tp>
		   && is_trivially_copy_constructible_v<_Tp>
		   && is_trivially_destructible_v<_Tp>
	= default;

      constexpr inplace_vector&
      operator=(const inplace_vector& __other)
      noexcept(is_nothrow_copy_assignable_v<_Tp>
		 && is_nothrow_copy_constructible_v<_Tp>)
      {
	if (std::addressof(__other) != this) [[likely]]
	  assign(__other.begin(), __other.end());
	return *this;
      }

      inplace_vector&
      operator=(inplace_vector&&)
	requires is_trivially_move_assignable_v<_Tp>
		   && is_trivially_move_constructible_v<_Tp>
		   && is_trivially_destructible_v<_Tp>
	= default;

      constexpr inplace_vector&
      operator=(inplace_vector&& __other)
      noexcept(is_nothrow_move_assignable_v<_Tp>
		 && is_nothrow_move_constructible_v<_Tp>)
      {
	if (std::addressof(__other) != this) [[likely]]
	  assign(std::make_move_iterator(__other.begin()),
		 std::make_move_iterator(__other.end()));
	return *this;
      }

      constexpr inplace_vector&
      operator=(initializer_list<_Tp> __il)
      {
	assign(__il.begin(), __il.end());
	return *this;
      }

      template<__any_input_iterator _InputIterator>
	constexpr void
	assign(_InputIterator __first, _InputIterator __last)
	{
	  if (const auto __n = _S_distance(__first, __last))
	    {
	      _S_reserve(__n);
	      if (_M_size <= __n)
		{
		  for (size_t __i = 0; __i < _M_size; ++__i, (void)++__first)
		    _M_elems[__i] = *__first;
		  std::uninitialized_copy(__first, __last, end());
		}
	      else
		std::destroy(std::copy(__first, __last, begin()), end());
	      _M_size = __n;
	    }
	  else
	    {
	      size_t __i = 0;
	      for (;__first != __last && __i < _M_size; ++__first)
		_M_elems[__i++] = *__first;
	      if (__first == __last)
		{
		  std::_Destroy_n(data() + __i, _M_size - __i);
		  _M_size = __i;
		}
	      else
		{
		  while (__first != __last)
		    emplace_back(*__first++);
		}
	    }
	}

      template<__detail::__container_compatible_range<_Tp> _Rg>
	constexpr void
	assign_range(_Rg&& __rg)
	{
	  if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
	    {
	      const auto __sz = ranges::distance(__rg);
	      if (__sz > _Nm)
		__throw_bad_alloc();
	      if (__sz <= size())
		{
		  ranges::copy_n(ranges::begin(__rg), __sz, data());
		  std::destroy(data() + __sz, data() + _M_size);
		}
	      else
		{
		  auto [__in, __out] = ranges::copy_n(
					 ranges::begin(__rg), _M_size,
					 data());
		  ranges::uninitialized_copy(
		    std::move(__in), ranges::end(__rg),
		    __out, unreachable_sentinel);
		}
	      _M_size = __sz;
	    }
	  else
	    {
	      auto __in = ranges::begin(__rg);
	      auto __end = ranges::end(__rg);
	      size_type __n = 0;
	      for (; __n < _M_size && __in != __end; ++__in)
		_M_elems[__n++] = *__in;

	      if (__in == __end)
		{
		  std::destroy(data() + __n, data() + _M_size);
		  _M_size = __n;
		  return;
		}
	      else if (__n < _Nm)
		{
		  auto __res = ranges::uninitialized_copy(
				std::move(__in), __end,
				data() + __n, data() + _Nm);
		  _M_size = __res.out - data();
		  if (__res.in == ranges::end(__rg))
		    return;
		}
	      __throw_bad_alloc();
	    }
	}

      constexpr void
      assign(size_type __n, const _Tp& __u)
      {
	_S_reserve(__n);
	if (_M_size <= __n)
	  std::uninitialized_fill_n(std::fill_n(data(), _M_size, __u),
				    __n - _M_size, __u);
	else
	  std::destroy_n(std::fill_n(data(), __n, __u), _M_size - __n);
	_M_size = __n;
      }

      constexpr void
      assign(initializer_list<_Tp> __il)
      { assign(__il.begin(), __il.end()); }

      // iterators
      [[nodiscard]]
      constexpr iterator
      begin() noexcept { return iterator(data()); }

      [[nodiscard]]
      constexpr const_iterator
      begin() const noexcept { return const_iterator(data()); }

      [[nodiscard]]
      constexpr iterator
      end() noexcept
      { return iterator(data() + _M_size); }

      [[nodiscard]]
      constexpr const_iterator
      end() const noexcept
      { return const_iterator(data() + _M_size); }

      [[nodiscard]]
      constexpr reverse_iterator
      rbegin() noexcept
      { return reverse_iterator(end()); }

      [[nodiscard]]
      constexpr const_reverse_iterator
      rbegin() const noexcept
      { return const_reverse_iterator(end()); }

      [[nodiscard]]
      constexpr reverse_iterator
      rend() noexcept { return reverse_iterator(begin()); }

      [[nodiscard]]
      constexpr const_reverse_iterator
      rend() const noexcept { return const_reverse_iterator(begin()); }

      [[nodiscard]]
      constexpr const_iterator
      cbegin() const noexcept { return begin(); }

      [[nodiscard]]
      constexpr const_iterator
      cend() const noexcept { return end(); }

      [[nodiscard]]
      constexpr const_reverse_iterator
      crbegin() const noexcept { return rbegin(); }

      [[nodiscard]]
      constexpr const_reverse_iterator
      crend() const noexcept { return rend(); }

      // [containers.sequences.inplace.vector.members] size/capacity
      [[nodiscard]]
      constexpr bool
      empty() const noexcept { return _M_size == 0; }

      [[nodiscard]]
      constexpr size_type
      size() const noexcept
      {
	if (_M_size > _Nm)
	  __builtin_unreachable();
	return _M_size;
      }

      [[nodiscard]]
      static constexpr size_type
      max_size() noexcept { return _Nm; }

      [[nodiscard]]
      static constexpr size_type
      capacity() noexcept { return _Nm; }

      constexpr void
      resize(size_type __n)
      {
	_S_reserve(__n);
	if (__n > _M_size)
	  std::uninitialized_value_construct_n(data() + _M_size, __n - _M_size);
	else if (__n < _M_size)
	  std::destroy_n(data() + __n, _M_size - __n);
	_M_size = __n;
      }

      constexpr void
      resize(size_type __n, const _Tp& __c)
      {
	_S_reserve(__n);
	if (__n > _M_size)
	  std::uninitialized_fill_n(data() + _M_size, __n - _M_size, __c);
	else if (__n < _M_size)
	  std::destroy_n(data() + __n, _M_size - __n);
	_M_size = __n;
      }

      static constexpr void
      reserve(size_type __n)
      { _S_reserve(__n); }

      static constexpr void
      shrink_to_fit() { }

      // element access
      [[nodiscard]]
      constexpr reference
      operator[](size_type __n)
      {
	__glibcxx_requires_subscript(__n);
	return _M_elems[__n];
      }

      [[nodiscard]]
      constexpr const_reference
      operator[](size_type __n) const
      {
	__glibcxx_requires_subscript(__n);
	return _M_elems[__n];
      }

      [[nodiscard]]
      constexpr const_reference
      at(size_type __n) const
      {
	if (__n >= _M_size)
	  std::__throw_out_of_range_fmt(__N("inplace_vector::at: __n "
					    "(which is %zu) "
					    ">= size() (which is %zu)"),
					__n, _M_size);
	return _M_elems[__n];
      }

      [[nodiscard]]
      constexpr reference
      at(size_type __n)
      {
	if (__n >= _M_size)
	  std::__throw_out_of_range_fmt(__N("inplace_vector::at: __n "
					    "(which is %zu) "
					    ">= size() (which is %zu)"),
					__n, _M_size);
	return _M_elems[__n];
      }

      [[nodiscard]]
      constexpr reference
      front()
      {
	__glibcxx_requires_nonempty();
	return _M_elems[0];
      }

      [[nodiscard]]
      constexpr const_reference
      front() const
      {
	__glibcxx_requires_nonempty();
	return _M_elems[0];
      }

      [[nodiscard]]
      constexpr reference
      back()
      {
	__glibcxx_requires_nonempty();
	return _M_elems[_M_size - 1];
      }

      [[nodiscard]]
      constexpr const_reference
      back() const
      {
	__glibcxx_requires_nonempty();
	return _M_elems[_M_size - 1];
      }

      // [containers.sequences.inplace.vector.data], data access

      [[nodiscard]]
      constexpr _Tp*
      data() noexcept
      { return static_cast<pointer>(_M_elems); }

      [[nodiscard]]
      constexpr const _Tp*
      data() const noexcept
      { return static_cast<const_pointer>(_M_elems); }

      // [containers.sequences.inplace.vector.modifiers], modifiers
      template<typename... _Args>
	constexpr _Tp&
	emplace_back(_Args&&... __args)
	{
	  if (_M_size >= _Nm)
	    __throw_bad_alloc();
	  return unchecked_emplace_back(std::forward<_Args>(__args)...);
	}

      constexpr _Tp&
      push_back(const _Tp& __x)
      { return emplace_back(__x); }

      constexpr _Tp&
      push_back(_Tp&& __x)
      { return emplace_back(std::move(__x)); }

      template<__detail::__container_compatible_range<_Tp> _Rg>
	constexpr void
	append_range(_Rg&& __rg)
	{
	  if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
	    {
	      const auto __sz = ranges::distance(__rg);
	      if (__sz > (_Nm - size()))
		__throw_bad_alloc();
	      // Bounded on output range due PR121143
	      ranges::uninitialized_copy(
		ranges::begin(__rg), unreachable_sentinel,
		data() + _M_size, data() + _M_size + __sz);
	      _M_size += size_type(__sz);
	    }
	  else
	    {
	      ranges::subrange<pointer> __tail(data() + _M_size, data() + _Nm);
	      auto [__in, __out] = ranges::uninitialized_copy(__rg, __tail);
	      _M_size = __out - data();
	      if (__in != ranges::end(__rg))
		__throw_bad_alloc();
	    }
	}

      constexpr void
      pop_back()
      {
	__glibcxx_requires_nonempty();
	--_M_size;
	_M_elems[_M_size].~_Tp();
      }

      template<typename... _Args>
	constexpr _Tp*
	try_emplace_back(_Args&&... __args)
	{
	  if (_M_size >= _Nm) [[unlikely]]
	    return nullptr;
	  auto& __r = unchecked_emplace_back(std::forward<_Args>(__args)...);
	  return __builtin_addressof(__r);
	}

      constexpr _Tp*
      try_push_back(const _Tp& __x)
      {
	if (_M_size >= _Nm) [[unlikely]]
	  return nullptr;
	return __builtin_addressof(unchecked_emplace_back(__x));
      }

      constexpr _Tp*
      try_push_back(_Tp&& __x)
      {
	if (_M_size >= _Nm) [[unlikely]]
	  return nullptr;
	return __builtin_addressof(unchecked_emplace_back(std::move(__x)));
      }

      template<__detail::__container_compatible_range<_Tp> _Rg>
	constexpr ranges::borrowed_iterator_t<_Rg>
	try_append_range(_Rg&& __rg)
	{
	  if constexpr (ranges::sized_range<_Rg>)
	    {
	      auto __n = ranges::distance(__rg);
	      if (__n == 0) [[unlikely]]
		return ranges::begin(__rg);

	      const auto __end = data() + _M_size;
	      const size_t __avail = _Nm - size();
	      if (__n <= __avail)
		_M_size += size_type(__n);
	      else
		{
		  __n = __avail;
		  _M_size = _Nm;
		}
	      return ranges::uninitialized_copy_n(
		       ranges::begin(__rg), __n,
		       __end, unreachable_sentinel).in;
	    }
	  else
	    {
	      ranges::subrange<pointer> __tail(data() + _M_size, data() + _Nm);
	      auto [__in, __out] = ranges::uninitialized_copy(__rg, __tail);
	      _M_size = __out - data();
	      return std::move(__in);
	    }
	}

      template<typename... _Args>
	constexpr _Tp&
	unchecked_emplace_back(_Args&&... __args)
	{
	  __glibcxx_assert(_M_size < _Nm);
	  auto __p = std::construct_at(data() + _M_size,
				       std::forward<_Args>(__args)...);
	  ++_M_size;
	  return *__p;
	}

      constexpr _Tp&
      unchecked_push_back(const _Tp& __x)
      { return unchecked_emplace_back(__x); }

      constexpr _Tp&
      unchecked_push_back(_Tp&& __x)
      { return unchecked_emplace_back(std::move(__x)); }

      template<typename... _Args>
	constexpr iterator
	emplace(const_iterator __position, _Args&&... __args)
	{
	  size_t __b = __position - cbegin(); // elements before position
	  __glibcxx_assert(__b <= _M_size);
	  if (_M_size >= _Nm)
	    __throw_bad_alloc();
	  iterator __pos = begin() + __b;
	  std::construct_at(data() + _M_size, std::forward<_Args>(__args)...);
	  if (_M_size++)
	    std::rotate(__pos, end() - 1, end());
	  return __pos;
	}

      constexpr iterator
      insert(const_iterator __position, const _Tp& __x)
      { return emplace(__position, __x); }

      constexpr iterator
      insert(const_iterator __position, _Tp&& __x)
      { return emplace(__position, std::move(__x)); }

      constexpr iterator
      insert(const_iterator __position, size_type __n, const _Tp& __x)
      {
	size_t __b = __position - cbegin(); // elements before position
	__glibcxx_assert(__b <= _M_size);
	if ((_Nm - _M_size) < __n)
	  __throw_bad_alloc();
	iterator __pos = begin() + __b;
	std::uninitialized_fill_n(data() + _M_size, __n, __x);
	if (std::__exchange(_M_size, _M_size + __n))
	  std::rotate(__pos, end() - __n, end());
	return __pos;
      }

      template<__any_input_iterator _InputIterator>
	constexpr iterator
	insert(const_iterator __position, _InputIterator __first,
	       _InputIterator __last)
	{
	  size_t __b = __position - cbegin(); // elements before position
	  __glibcxx_assert(__b <= _M_size);
	  iterator __pos = begin() + __b;
	  const size_t __s = _M_size;
	  if (const auto __n = _S_distance(__first, __last))
	    {
	      if ((_Nm - _M_size) < __n)
		__throw_bad_alloc();
	      std::uninitialized_copy(__first, __last, data() + _M_size);
	      _M_size += __n;
	    }
	  else
	    {
	      while (__first != __last)
		emplace_back(*__first++);
	    }
	  if (__s)
	    std::rotate(__pos, begin() + __s, end());
	  return __pos;
	}

      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);
		  _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);
		  _M_size += __n - __num_after;
		  ranges::uninitialized_move(__pos, __end,
					     __pos + __n, unreachable_sentinel);
		  _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;
	}

      constexpr iterator
      insert(const_iterator __position, initializer_list<_Tp> __il)
      { return insert(__position, __il.begin(), __il.end()); }

      constexpr iterator
      erase(const_iterator __position)
      {
	size_t __n = __position - cbegin();
	__glibcxx_assert(__n < _M_size);
	iterator __pos = begin() + __n;
	std::move(__pos + 1, end(), __pos);
	pop_back();
	return __pos;
      }

      constexpr iterator
      erase(const_iterator __first, const_iterator __last)
      {
	size_t __n = __first - cbegin();
	size_t __x = __last - __first;
	__glibcxx_assert(__n <= _M_size);
	__glibcxx_assert(__x <= _M_size);
	iterator __pos = begin() + __n;
	iterator __end = std::move(__pos + __x, end(), __pos);
	std::destroy_n(__end, __x);
	_M_size -= __x;
	return __pos;
      }

      constexpr void
      swap(inplace_vector& __x)
      noexcept(is_nothrow_swappable_v<_Tp> && is_nothrow_move_constructible_v<_Tp>)
      {
	inplace_vector* __vs[2]{ this, std::addressof(__x) };
	const auto __smaller = __vs[__x.size() < size()];
	const auto __bigger = __vs[__x.size() >= size()];
	size_type __n = __smaller->size();
	size_type __n2 = __bigger->size();

	if constexpr (is_nothrow_move_constructible_v<_Tp>)
	  {
	    for (size_type __i = __n; __i < __n2; ++__i)
	      {
		std::construct_at(__smaller->data() + __i,
				  std::move(*(__bigger->data() + __i)));
		std::destroy_at(__bigger->data() + __i);
	      }
	  }
	else
	  {
	    std::uninitialized_copy(__bigger->data() + __n,
				    __bigger->data() + __n2,
				    __smaller->data() + __n);
	    std::destroy(__bigger->data() + __n, __bigger->data() + __n2);
	  }
	__smaller->_M_size = __n2;
	__bigger->_M_size = __n;

	using std::swap;
	for (size_type __i = 0; __i < __n; __i++)
	  swap(_M_elems[__i], __x._M_elems[__i]);
      }

      constexpr void
      clear() noexcept
      {
	std::destroy_n(data(), size_t(_M_size));
	_M_size = 0;
      }

      constexpr friend bool
      operator==(const inplace_vector& __x, const inplace_vector& __y)
      { return std::equal(__x.begin(), __x.end(), __y.begin(), __y.end()); }

      constexpr friend auto
      operator<=>(const inplace_vector& __x, const inplace_vector& __y)
      requires requires (const _Tp __t) {
	{ __t < __t } -> __detail::__boolean_testable;
      }
      {
	return std::lexicographical_compare_three_way(__x.begin(), __x.end(),
						      __y.begin(), __y.end(),
						      __detail::__synth3way);
      }

      // [inplace.vector.special], specialized algorithms
      constexpr friend void
      swap(inplace_vector& __x, inplace_vector& __y)
      noexcept(is_nothrow_swappable_v<_Tp> && is_nothrow_move_constructible_v<_Tp>)
      { __x.swap(__y); }

    private:
      union {
	_Tp _M_elems[_Nm];
      };

      // Check whether integer type _UInt is wide enough to store _Nm,
      // so that we use a smaller type for _M_size when that saves space.
      template<typename _UInt, bool = (alignof(_Tp) <= sizeof(_UInt))>
	static constexpr bool __fits
	  = _Nm <= __gnu_cxx::__int_traits<_UInt>::__max;

      // Don't bother using a smaller type if alignment of the array elements
      // means that it doesn't actually save space.
      template<typename _UInt>
	static constexpr bool __fits<_UInt, false> = false;

      static consteval auto __select_size_type()
      {
	if constexpr (__fits<unsigned char>)
	  return (unsigned char)0;
#if __SHRT_WIDTH__ < __SIZE_WIDTH__
	else if constexpr (__fits<unsigned short>)
	  return (unsigned short)0;
#endif
#if __INT_WIDTH__ < __SIZE_WIDTH__ && __INT_WIDTH__ > __SHRT_WIDTH__
	else if constexpr (__fits<unsigned int>)
	  return 0u;
#endif
#if __LONG_WIDTH__ < __SIZE_WIDTH__ && __LONG_WIDTH__ > __INT_WIDTH__
	else if constexpr (__fits<unsigned long>)
	  return 0ul;
#endif
	else // Just use size_t.
	  return 0uz;
      }
      decltype(__select_size_type()) _M_size = 0;

      constexpr void
      _M_init()
      {
	if !consteval
	  {
#if __glibcxx_start_lifetime_as
	    std::start_lifetime_as_array<_Tp>(data(), _Nm);
#endif
	  }
	else
	  {
	    // TODO: use new(_M_elems) _Tp[_Nm]() once PR121068 is fixed
	    if constexpr (is_trivial_v<_Tp>)
	      for (size_t __i = 0; __i < _Nm; ++__i)
		_M_elems[__i] = _Tp();
	    else
	      __builtin_unreachable(); // only trivial types are supported at compile time
	  }
      }

      static constexpr void
      _S_reserve(size_t __n)
      {
	if (__n > _Nm)
	  __throw_bad_alloc();
      }

      template<typename _InputIterator>
	constexpr static auto
	_S_distance(_InputIterator __first, _InputIterator __last)
	{
	  if constexpr (sized_sentinel_for<_InputIterator, _InputIterator>
			  || forward_iterator<_InputIterator>)
	    return (size_type)ranges::distance(__first, __last);
	  else if constexpr (derived_from<__iter_category_t<_InputIterator>,
				     forward_iterator_tag>)
	    return (size_type)std::distance(__first, __last);
	  else
	    return false_type{};
	}
    };

  // specialization for zero capacity, that is required to be trivally copyable
  // and empty regardless of _Tp.
  template<typename _Tp>
    class inplace_vector<_Tp, 0>
    {
    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
      inplace_vector() = default;

      constexpr explicit
      inplace_vector(size_type __n)
      {
	if (__n != 0)
	  __throw_bad_alloc();
      }

      constexpr
      inplace_vector(size_type __n, const _Tp& __value)
      {
	if (__n != 0)
	  __throw_bad_alloc();
      }

      template<__any_input_iterator _InputIterator>
	constexpr
	inplace_vector(_InputIterator __first, _InputIterator __last)
	{
	  if (__first != __last)
	    __throw_bad_alloc();
	}

      template <__detail::__container_compatible_range<_Tp> _Rg>
	constexpr
	inplace_vector(from_range_t, _Rg&& __rg)
	{
	  if (ranges::begin(__rg) != ranges::end(__rg))
	    __throw_bad_alloc();
	}

      constexpr
      inplace_vector(initializer_list<_Tp> __il)
      {
	if (__il.size() != 0)
	  __throw_bad_alloc();
      }

      inplace_vector(const inplace_vector&) = default;
      inplace_vector(inplace_vector&&) = default;

      constexpr
      ~inplace_vector() = default;

      inplace_vector&
      operator=(const inplace_vector&) = default;

      inplace_vector&
      operator=(inplace_vector&&) = default;

      constexpr inplace_vector&
      operator=(initializer_list<_Tp> __il)
      {
	if (__il.size() != 0)
	  __throw_bad_alloc();
	return *this;
      }

      template<__any_input_iterator _InputIterator>
	constexpr void
	assign(_InputIterator __first, _InputIterator __last)
	{
	  if (__first != __last)
	    __throw_bad_alloc();
	}

      template<__detail::__container_compatible_range<_Tp> _Rg>
	constexpr void
	assign_range(_Rg&& __rg)
	{
	  if (ranges::begin(__rg) != ranges::end(__rg))
	    __throw_bad_alloc();
	}

      constexpr void
      assign(size_type __n, const _Tp& __u)
      {
	if (__n != 0)
	  __throw_bad_alloc();
      }

      constexpr void
      assign(initializer_list<_Tp> __il)
      {
	if (__il.size() != 0)
	  __throw_bad_alloc();
      }

      // iterators
      [[nodiscard]]
      constexpr iterator
      begin() noexcept { return iterator(nullptr); }

      [[nodiscard]]
      constexpr const_iterator
      begin() const noexcept { return const_iterator(nullptr); }

      [[nodiscard]]
      constexpr iterator
      end() noexcept { return iterator(nullptr); }

      [[nodiscard]]
      constexpr const_iterator
      end() const noexcept { return const_iterator(nullptr); }

      [[nodiscard]]
      constexpr reverse_iterator
      rbegin() noexcept
      { return reverse_iterator(end()); }

      [[nodiscard]]
      constexpr const_reverse_iterator
      rbegin() const noexcept
      { return const_reverse_iterator(end()); }

      [[nodiscard]]
      constexpr reverse_iterator
      rend() noexcept { return reverse_iterator(begin()); }

      [[nodiscard]]
      constexpr const_reverse_iterator
      rend() const noexcept { return const_reverse_iterator(begin()); }

      [[nodiscard]]
      constexpr const_iterator
      cbegin() const noexcept { return begin(); }

      [[nodiscard]]
      constexpr const_iterator
      cend() const noexcept { return end(); }

      [[nodiscard]]
      constexpr const_reverse_iterator
      crbegin() const noexcept { return rbegin(); }

      [[nodiscard]]
      constexpr const_reverse_iterator
      crend() const noexcept { return rend(); }

      // [containers.sequences.inplace.vector.members] size/capacity
      [[nodiscard]]
      constexpr bool
      empty() const noexcept { return true; }

      [[nodiscard]]
      constexpr size_type
      size() const noexcept { return 0; }

      [[nodiscard]]
      static constexpr size_type
      max_size() noexcept { return 0; }

      [[nodiscard]]
      static constexpr size_type
      capacity() noexcept { return 0; }

      constexpr void
      resize(size_type __n)
      {
	if (__n != 0)
	  __throw_bad_alloc();
      }

      constexpr void
      resize(size_type __n, const _Tp&)
      {
	if (__n != 0)
	  __throw_bad_alloc();
      }

      static constexpr void
      reserve(size_type __n)
      {
	if (__n != 0)
	  __throw_bad_alloc();
      }

      static constexpr void
      shrink_to_fit() { }

      // element access
      [[nodiscard,noreturn]]
      constexpr reference
      operator[](size_type)
      { __builtin_trap(); }

      [[nodiscard,noreturn]]
      constexpr const_reference
      operator[](size_type) const
      { __builtin_trap(); }

      [[nodiscard,noreturn]]
      constexpr const_reference
      at(size_type __n) const
      {
	std::__throw_out_of_range_fmt(__N("inplace_vector::at: __n "
					  "(which is %zu) "
					  ">= size() (which is 0)"),
				      __n);
      }

      [[nodiscard,noreturn]]
      constexpr reference
      at(size_type __n)
      {
	std::__throw_out_of_range_fmt(__N("inplace_vector::at: __n "
					  "(which is %zu) "
					  ">= size() (which is 0)"),
				      __n);
      }

      [[nodiscard,noreturn]]
      constexpr reference
      front()
      { __builtin_trap(); }

      [[nodiscard,noreturn]]
      constexpr const_reference
      front() const
      { __builtin_trap(); }

      [[nodiscard,noreturn]]
      constexpr reference
      back()
      { __builtin_trap(); }

      [[nodiscard,noreturn]]
      constexpr const_reference
      back() const
      { __builtin_trap(); }

      // [containers.sequences.inplace.vector.data], data access

      [[nodiscard]]
      constexpr _Tp*
      data() noexcept
      { return nullptr; }

      [[nodiscard]]
      constexpr const _Tp*
      data() const noexcept
      { return nullptr; }

      // [containers.sequences.inplace.vector.modifiers], modifiers
      template<typename... _Args>
	[[noreturn]]
	constexpr _Tp&
	emplace_back(_Args&&...)
	{ __throw_bad_alloc(); }

      [[noreturn]]
      constexpr _Tp&
      push_back(const _Tp&)
      { __throw_bad_alloc(); }

      [[noreturn]]
      constexpr _Tp&
      push_back(_Tp&&)
      { __throw_bad_alloc(); }

      template<__detail::__container_compatible_range<_Tp> _Rg>
	constexpr void
	append_range(_Rg&& __rg)
	{
	  if (ranges::begin(__rg) != ranges::end(__rg))
	    __throw_bad_alloc();
	}

      [[noreturn]]
      constexpr void
      pop_back()
      { __builtin_trap(); }

      template<typename... _Args>
	constexpr _Tp*
	try_emplace_back(_Args&&...)
	{ return nullptr; }

      constexpr _Tp*
      try_push_back(const _Tp&)
      { return nullptr; }

      constexpr _Tp*
      try_push_back(_Tp&&)
      { return nullptr; }

      template<__detail::__container_compatible_range<_Tp> _Rg>
	constexpr ranges::borrowed_iterator_t<_Rg>
	try_append_range(_Rg&& __rg)
	{ return ranges::begin(__rg); }

      template<typename... _Args>
	[[noreturn]]
	constexpr _Tp&
	unchecked_emplace_back(_Args&&...)
	{ __builtin_trap(); }

      [[noreturn]]
      constexpr _Tp&
      unchecked_push_back(const _Tp&)
      { __builtin_trap(); }

      [[noreturn]]
      constexpr _Tp&
      unchecked_push_back(_Tp&&)
      { __builtin_trap(); }

      template<typename... _Args>
	[[noreturn]]
	constexpr iterator
	emplace(const_iterator, _Args&&...)
	{ __throw_bad_alloc(); }

      [[noreturn]]
      constexpr iterator
      insert(const_iterator, const _Tp&)
      { __throw_bad_alloc(); }

      [[noreturn]]
      constexpr iterator
      insert(const_iterator, _Tp&&)
      { __throw_bad_alloc(); }

      constexpr iterator
      insert(const_iterator, size_type __n, const _Tp&)
      {
	if (__n != 0)
	  __throw_bad_alloc();
	return begin();
      }

      template<typename _InputIterator>
	constexpr iterator
	insert(const_iterator, _InputIterator __first, _InputIterator __last)
	{
	  if (__first != __last)
	    __throw_bad_alloc();
	  return begin();
	}

      template<__detail::__container_compatible_range<_Tp> _Rg>
	constexpr iterator
	insert_range(const_iterator, _Rg&& __rg)
	{
	  if (ranges::begin(__rg) != ranges::end(__rg))
	    __throw_bad_alloc();
	  return begin();
	}

      constexpr iterator
      insert(const_iterator, initializer_list<_Tp> __il)
      {
	if (__il.size() != 0)
	  __throw_bad_alloc();
	return begin();
      }

      [[noreturn]]
      constexpr iterator
      erase(const_iterator)
      { __builtin_trap(); }

      constexpr iterator
      erase(const_iterator __first, const_iterator __last)
      {
	__glibcxx_assert(__first == __last);
	return begin();
      }

      constexpr void
      swap(inplace_vector& __x)
      noexcept
      { }

      constexpr void
      clear() noexcept
      { }

      constexpr friend bool
      operator==(const inplace_vector&, const inplace_vector&)
      { return true; }

      constexpr friend auto
      operator<=>(const inplace_vector&, const inplace_vector&)
      requires requires (const _Tp __t) {
	{ __t < __t } -> __detail::__boolean_testable;
      }
      {	return std::strong_ordering::equal; }

      // n.b. there is not explicit wording requiring that swap for inplace_vector,
      // with zero size, works even if element type is not swappable. However given
      // that move operations are required to be present and trivial, it makes sense
      // to support them.
      constexpr friend void
      swap(inplace_vector&, inplace_vector&) noexcept
      { }
    };

_GLIBCXX_END_NAMESPACE_CONTAINER

  template<typename _Tp, size_t _Nm, typename _Predicate>
    constexpr size_t
    erase_if(_GLIBCXX_STD_C::inplace_vector<_Tp, _Nm>& __cont,
	     _Predicate __pred)
    {
      if constexpr (_Nm != 0)
	{
	  const auto __osz = __cont.size();
	  const auto __end = __cont.end();
	  auto __removed = std::__remove_if(__cont.begin(), __end,
					    std::move(__pred));
	  if (__removed != __end)
	    {
	      __cont.erase(__removed, __end);
	      return __osz - __cont.size();
	    }
	}

      return 0;
    }

  template<typename _Tp, size_t _Nm, typename _Up = _Tp>
    constexpr  size_t
    erase(_GLIBCXX_STD_C::inplace_vector<_Tp, _Nm>& __cont, const _Up& __value)
    { return std::erase_if(__cont, __gnu_cxx::__ops::__equal_to(__value)); }

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace

#ifdef _GLIBCXX_DEBUG
# include <debug/inplace_vector>
#endif

#endif // __glibcxx_inplace_vector
#endif // _GLIBCXX_INPLACE_VECTOR