constexpr friendly vector with static storage and no allocation

Question

My take 2 on constexpr friendly StaticVector.

• If the value_type is trivial, it can be user in constexpr functions normally.

• If the value_type is not trivial, it uses placement new / destroy and types are properly handled.

• Third way to use is with external buffer. For example you can allocate 16GB with mmap and give the pointer to the StaticVector. Then you can use say 20KB and because of the virtual memory the memory consumption will be capped to 20-24MB, but in same time you will be 100% sure there will be no reallocation and pointers to the values will be stable.

Here is the code, usage it at the end:

#ifndef MY_STATIC_VECTOR_H_
#define MY_STATIC_VECTOR_H_
#include <memory> // std::uninitialized_copy, std::uninitialized_move
#include <stdexcept> // std::bad_alloc
#include <type_traits>
#include <initializer_list>
//
// Based on
// http://codereview.stackexchange.com/questions/123402/c-vector-the-basics
// http://lokiastari.com/blog/2016/03/19/vector-simple-optimizations/
//
namespace static_vector_implementation_{
 template <typename Derived, typename T, std::size_t Capacity, bool Trivial>
 struct StaticVectorBase_;
 template <typename Derived, typename T, std::size_t Capacity>
 struct StaticVectorBase_<Derived, T, Capacity, true>{
 constexpr static bool IS_POD = true;
 using value_type = T;
 using size_type = std::size_t;
 public:
 constexpr value_type *data() noexcept{
 return buffer_;
 }
 constexpr const value_type *data() const noexcept{
 return buffer_;
 }
 constexpr static size_type capacity() noexcept{
 return Capacity;
 }
 protected:
 value_type buffer_[Capacity]{};
 size_type size_ = 0;
 };
 template <typename Derived, typename T, std::size_t Capacity>
 struct StaticVectorBase_<Derived, T, Capacity, false>{
 constexpr static bool IS_POD = false;
 using value_type = T;
 using size_type = std::size_t;
 public:
 constexpr value_type *data() noexcept{
 return reinterpret_cast<value_type *>(buffer_);
 }
 constexpr const value_type *data() const noexcept{
 return reinterpret_cast<const value_type *>(buffer_);
 }
 constexpr static size_type capacity() noexcept{
 return Capacity;
 }
 public:
 ~StaticVectorBase_() noexcept {
 Derived &self = static_cast<Derived &>(*this);
 self.deallocate_();
 }
 protected:
 alignas(value_type)
 char buffer_[Capacity * sizeof(value_type)]{};
 size_type size_ = 0;
 };
 template <typename Derived, typename T>
 struct StaticVectorBase_<Derived, T, 0, true>{
 constexpr static bool IS_POD = true;
 using value_type = T;
 using size_type = std::size_t;
 public:
 StaticVectorBase_(value_type *buffer, size_type capacity) : buffer_(buffer), capacity_(capacity){}
 public:
 constexpr value_type *data() noexcept{
 return buffer_;
 }
 constexpr const value_type *data() const noexcept{
 return buffer_;
 }
 constexpr size_type capacity() const noexcept{
 return capacity_;
 }
 protected:
 value_type *buffer_;
 size_type capacity_;
 size_type size_ = 0;
 };
 template <typename Derived, typename T>
 struct StaticVectorBase_<Derived, T, 0, false>{
 constexpr static bool IS_POD = false;
 using value_type = T;
 using size_type = std::size_t;
 public:
 StaticVectorBase_(char *buffer, size_type capacity) : buffer_(buffer), capacity_(capacity){}
 public:
 constexpr value_type *data() noexcept{
 return reinterpret_cast<value_type *>(buffer_);
 }
 constexpr const value_type *data() const noexcept{
 return reinterpret_cast<const value_type *>(buffer_);
 }
 constexpr size_type capacity() const noexcept{
 return capacity_;
 }
 public:
 // class is not movable
 ~StaticVectorBase_() noexcept {
 Derived &self = static_cast<Derived &>(*this);
 self.deallocate_();
 }
 protected:
 char *buffer_;
 size_type capacity_;
 size_type size_ = 0;
 };
} // namespace static_vector_implementation_
template<typename T, std::size_t Capacity>
class StaticVector : public static_vector_implementation_::StaticVectorBase_<
 StaticVector<T, Capacity>,
 T,
 Capacity,
 std::is_trivial_v<T> && std::is_standard_layout_v<T>
 >{
 using Base = static_vector_implementation_::StaticVectorBase_<
 StaticVector<T, Capacity>,
 T,
 Capacity,
 std::is_trivial_v<T> && std::is_standard_layout_v<T>
 >;
 using Base::IS_POD;
 template <typename, typename, std::size_t, bool>
 friend struct static_vector_implementation_::StaticVectorBase_;
public:
 // TYPES
 using value_type = T;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = value_type &;
 using const_reference = const value_type &;
 using pointer = value_type *;
 using const_pointer = const value_type *;
 using iterator = value_type *;
 using const_iterator = const value_type *;
private:
 // size_type size_ = 0;
 using Base::size_;
public:
 // STANDARD C-TORS FOR Capacity != 0
 constexpr StaticVector() = default;
 constexpr StaticVector(size_type const count, value_type const &value){
 assign_(count, value);
 }
 template<class Iterator>
 constexpr StaticVector(Iterator begin, Iterator end){
 assign_(begin, end);
 }
 template<typename ...Args>
 constexpr StaticVector(std::initializer_list<value_type> const &list){
 assign_(list.begin(), list.end());
 }
 // STANDARD C-TORS FOR Capacity == 0
 template<typename buffer_value_type>
 constexpr StaticVector(
 buffer_value_type *data, size_type size) : Base(data, size){
 }
 template<typename buffer_value_type>
 constexpr StaticVector(size_type const count, value_type const &value,
 buffer_value_type *data, size_type size) : Base(data, size){
 assign_(count, value);
 }
 template<class Iterator, typename buffer_value_type>
 constexpr StaticVector(Iterator begin, Iterator end,
 buffer_value_type *data, size_type size) : Base(data, size){
 assign_(begin, end);
 }
 template<typename buffer_value_type>
 constexpr StaticVector(std::initializer_list<value_type> const &list,
 buffer_value_type *data, size_type size) : Base(data, size){
 assign_(list.begin(), list.end());
 }
 // COPY / MOVE C-TORS
 constexpr StaticVector(StaticVector const &other){
 static_assert(Capacity, "BufferedVector can not be copied/moved!");
 copy_<0>(other.begin(), other.end());
 }
 constexpr StaticVector(StaticVector &&other) noexcept{
 static_assert(Capacity, "BufferedVector can not be copied/moved!");
 move_<0>(other.begin(), other.end());
 }
 constexpr StaticVector &operator=(StaticVector const &other) {
 static_assert(Capacity, "BufferedVector can not be copied/moved!");
 if (this == &other)
 return *this;
 copy_<1>(other.begin(), other.end());
 return *this;
 }
 constexpr StaticVector &operator=(StaticVector &&other) noexcept {
 static_assert(Capacity, "BufferedVector can not be copied/moved!");
 if (this == &other)
 return *this;
 move_<1>(other.begin(), other.end());
 return *this;
 }
 // MISC
 constexpr
 void reserve(size_type const) noexcept{
 }
 constexpr
 void clear() noexcept{
 destroy_();
 size_ = 0;
 }
 // COMPARISSON
 constexpr bool operator==(const StaticVector &other) const noexcept{
 if (size_ != other.size_)
 return false;
 // std::equal, but constexpr
 auto first = other.begin();
 auto last = other.end();
 auto me = begin();
 for(; first != last; ++first, ++me)
 if ( ! (*first == *me) )
 return false;
 return true;
 }
 constexpr bool operator!=(const StaticVector &other) const noexcept{
 return ! operator==(other);
 }
 // ITERATORS
 constexpr
 iterator begin() noexcept{
 return data();
 }
 constexpr
 iterator end() noexcept{
 return data() + size();
 }
 // CONST ITERATORS
 constexpr const_iterator begin() const noexcept{
 return data();
 }
 constexpr const_iterator end() const noexcept{
 return data() + size();
 }
 // C++11 CONST ITERATORS
 constexpr const_iterator cbegin() const noexcept{
 return begin();
 }
 constexpr const_iterator cend() const noexcept{
 return end();
 }
 // Size
 constexpr size_type size() const noexcept{
 return size_;
 }
 constexpr bool empty() const noexcept{
 return size() == 0;
 }
 constexpr bool full() const noexcept{
 return size() == capacity();
 }
 // MORE Size
 // constexpr size_type capacity() const noexcept;
 using Base::capacity;
 constexpr size_type max_size() const noexcept{
 return capacity();
 }
 // DATA - in Base
 // constexpr value_type *data() noexcept;
 // constexpr const value_type *data() const noexcept;
 using Base::data;
 // ACCESS WITH RANGE CHECK
 constexpr
 value_type &at(size_type const index){
 validateIndex_(index);
 return data()[index];
 }
 constexpr const value_type &at(size_type const index) const{
 validateIndex_(index);
 return data()[index];
 }
 // ACCESS DIRECTLY
 constexpr
 value_type &operator[](size_type const index) noexcept{
 // see [1] behavior is undefined
 return data()[index];
 }
 constexpr const value_type &operator[](size_type const index) const noexcept{
 // see [1] behavior is undefined
 return data()[index];
 }
 // FRONT
 constexpr
 value_type &front() noexcept{
 // see [1] behavior is undefined
 return data()[0];
 }
 constexpr const value_type &front() const noexcept{
 // see [1] behavior is undefined
 return data()[0];
 }
 // BACK
 constexpr
 value_type &back() noexcept{
 // see [1] behavior is undefined
 return data()[size_ - 1];
 }
 constexpr const value_type &back() const noexcept{
 // see [1] behavior is undefined
 return data()[size_ - 1];
 }
 // MUTATIONS
 constexpr
 void push_back(){
 return emplace_back();
 }
 constexpr
 void push_back(const value_type &value){
 return emplace_back(value);
 }
 constexpr
 void push_back(value_type &&value){
 return emplace_back(std::move(value));
 }
 template<typename... Args>
 constexpr
 void emplace_back(Args&&... args){
 if (full())
 throw std::bad_alloc{};
 if constexpr(!IS_POD){
 new (&data()[size_]) value_type(std::forward<Args>(args)...);
 // incr is here because new can throw exception,
 // in some theoretical case
 ++size_;
 }else{
 data()[size_++] = value_type(std::forward<Args>(args)...);
 }
 }
 // POP_BACK
 constexpr
 void pop_back() noexcept{
 // see [1]
 if constexpr(!IS_POD)
 back().~value_type();
 --size_;
 }
public:
 // APPEND
 constexpr
 void assign(size_type const count, value_type const &value){
 assign_<1>(count, value);
 }
 template<class Iterator>
 constexpr
 void assign(Iterator first, Iterator last){
 assign_<1>(first, last);
 }
 constexpr
 void assign(std::initializer_list<value_type> const &list){
 assign(list.begin(), list.end());
 }
private:
 // construct / copy elements from vector in exception safe way
 template<bool Destruct>
 constexpr
 void assign_(size_type const count, value_type const &value){
 if constexpr(Destruct)
 clear();
 // reserve(count);
 for(size_type i = 0; i < count; ++i)
 push_back(value);
 }
 template<bool Destruct, class Iterator>
 constexpr
 void assign_(Iterator first, Iterator last){
 if constexpr(Destruct)
 clear();
 // reserve(std::distance(first, last));
 for(auto it = first; it != last; ++it)
 push_back(*it);
 }
 // copy / move elements
 template<bool Destruct, class Iterator>
 constexpr
 void copy_(Iterator first, Iterator last){
 if constexpr(std::is_nothrow_copy_constructible_v<value_type>){
 #if defined(__clang__) || defined(__GNUC__)
 if (__builtin_is_constant_evaluated()){
 // constant evaluation,
 // assign is constexpr and exception friendly
 return assign_<Destruct>(first, last);
 }
 # endif
 if constexpr(Destruct)
 destroy_();
 size_type const size = static_cast<size_type>(std::distance(first, last));
 // reserve(size);
 size_ = size;
 std::uninitialized_copy(first, last, data());
 }else{
 assign_<Destruct>(first, last);
 }
 }
 template<bool Destruct, class Iterator>
 constexpr
 void move_(Iterator first, Iterator last){
 if constexpr(IS_POD){
 // POD move is copy
 return copy_<Destruct>(first, last);
 }
 if constexpr(std::is_nothrow_move_constructible_v<value_type>){
 #if defined(__clang__) || defined(__GNUC__)
 if (__builtin_is_constant_evaluated()){
 // constant evaluation,
 // assign is constexpr and exception friendly
 return assign_<Destruct>(first, last);
 }
 # endif
 if constexpr(Destruct)
 destroy_();
 size_type const size = static_cast<size_type>(std::distance(first, last));
 // reserve(size);
 size_ = size;
 std::uninitialized_move(first, last, data());
 }else{
 assign_<Destruct>(first, last);
 }
 }
 // destruct all elements
 constexpr
 void destroy_() noexcept{
 if constexpr(!IS_POD)
 std::destroy(begin(), end());
 }
 // destruct all elements and "deallocate" the buffer
 constexpr
 void deallocate_() noexcept{
 destroy_();
 }
 // throw if index is incorrect
 constexpr
 void validateIndex_(size_type const index) const{
 if (index >= size_){
 throw std::out_of_range("Out of Range");
 }
 }
 // Remark [1]
 //
 // If the container is not empty,
 // the function never throws exceptions (no-throw guarantee).
 // Otherwise, it causes undefined behavior.
};
template<typename T>
using BufferedVector = StaticVector<T, 0>;
#endif

Usage:

(please don't comment on the style of the usage example, I know I can remove duplication and make it better)

#include "staticvector.h"
#include <string>
#include <iostream>
#include <cassert>
constexpr auto getVector(){
 StaticVector<int, 8> v;
 v.reserve(6);
 v.push_back(10);
 v.push_back(20);
 v.push_back();
 v.emplace_back(40);
 v.push_back(1000);
 v.pop_back();
 v[2] = 30;
 return v;
}
constexpr static auto vi = getVector();
template<typename T>
void print(T const &v){
 for(auto const &x : v)
 std::cout << "- " << x << '\n';
}
int main(){
 if (1){
 StaticVector<std::string, 8> v;
 v.reserve(6);
 v.push_back("s1 aaaaaaaaaaaaaaaaaaaaaaa");
 v.push_back("s2 aaaaaaaaaaaaaaaaaaaaaaa");
 v.push_back();
 v.emplace_back("s4 aaaaaaaaaaaaaaaaaaaaaaa");
 v.push_back("last");
 v.pop_back();
 v[2] = "s3 aaaaaaaaaaaaaaaaaaaaaaa";
 auto v1 = v;
 assert(v == v1);
 auto v2 = std::move(v1);
 assert(v == v2);
 print(v);
 }
 if (1){
 print(vi);
 }
 if (1){
 StaticVector<int, 8> v;
 v.reserve(6);
 v.push_back(1);
 v.push_back(2);
 v.push_back();
 v.emplace_back(4);
 v.push_back(1000);
 v.pop_back();
 v[2] = 3;
 auto v1 = v;
 assert(v == v1);
 auto v2 = std::move(v1);
 assert(v == v2);
 print(v);
 }
 if (1){
 size_t const bufferSize = 8;
 char buffer[sizeof(std::string) * bufferSize];
 BufferedVector<std::string> v(buffer, bufferSize);
 v.reserve(6);
 v.push_back("s1 aaaaaaaaaaaaaaaaaaaaaaa");
 v.push_back("s2 aaaaaaaaaaaaaaaaaaaaaaa");
 v.push_back();
 v.emplace_back("s4 aaaaaaaaaaaaaaaaaaaaaaa");
 v.push_back("last");
 v.pop_back();
 v[2] = "s3 aaaaaaaaaaaaaaaaaaaaaaa";
 print(v);
 }
 if (1){
 size_t const bufferSize = 8;
 int buffer[bufferSize];
 BufferedVector<int> v(buffer, bufferSize);
 v.reserve(6);
 v.push_back(1);
 v.push_back(2);
 v.push_back();
 v.emplace_back(4);
 v.push_back(1000);
 v.pop_back();
 v[2] = 3;
 print(v);
 }
}

• Loki Astari: Based on my code. Nice.
• Nick: @LokiAstari Nice to hear from you! Yes. Old version that I used was based on yours code too.

Answer 1

A lot of effort has clearly gone into this, and you are doing many things right. Names of functions and variables are also clear and consistent. However, there are some issues:

Aim for what C++ is going to do

You marked your code c++17, and that version of C++ does not have a static vector implementation, nor does it have many other features that would make implementing one yourself easier. But it would be best if you make your code in such a way that moving to a newer version of C++ is easy, and even better, that your staticVector will be a drop-in replacement for c++26's std::inplace_vector. With that in mind:

Implement the interface of std::inplace_vector

I'm just going to list the differences between your class and std::inplace_vector here:

• Missing reverse_iterator and const_reverse_iterator, as well as the related member functions like rbegin().
• Missing constructor from a range (while ranges are not in C++17, you can actually write legal C++17 code that can handle range-like objects)
• Neither std::inplace_vector nor std::vector have a constructor that takes a pointer to value_type and a size. I know it is to create a static vector with an external buffer, but I wonder if it can be confused by someone
• C++ containers do not have a full(). Even though it's nice to have it, once code relies on it, it will be harder to drop in std::inplace_vector later.
• No emplace() that takes a position.
• No insert(), insert_range(), append_range(), try_append_range()
• No erase().
• No swap().
• No shrink_to_fit().
• No operator<() and friends.

Furthermore, the standard library has overloads for std::erase(), std::erase_if() and std::swap() for its container types.

Unnecessary specialization for POD types

I see that StaticVectorBase_ gets specialized depending on whether T is a POD or non-POD type. However, if you already handle the non-POD case correctly, what is the point of having a version for POD types? Note that placement new and calling the destructor of a POD-type are no-ops, so you are not optimizing anything here.

Buffer overflow in copy_() and move_()

The copy_() and move_() functions calculate the size from the given iterator pair, and blindly assume that this will always fit in the buffer. You should make sure

Too much noexcept

You have too many functions marked noexcept. You should only add that if you are absolutely certain nothing will throw. If a function contains any operation on value_types, however innocent, it probably means you don't know if it will throw or not.

Consider for example StaticVector::operator==(). Sure, it is very const, but at some point it is calling value_type::operator==(). That's a member function that is out of your control, so it might throw.

Note that destructors can also throw. This means your destructor, clear() and pop_back() should also not be noexcept.

While you could perhaps make these functions conditionally noexcept, note that the standard library does not do that.

Potential confusion with external buffers

There is a problem when you create a StaticVector with an external buffer and a non-POD T. Your constructor will at first glance happily take a T* as an argument. However, where does this pointer to Ts come from? Consider:

{
 std::array<T, 1000> external_buffer;
 StaticVector<T, 0> static_vector(external_buffer.data(), external_buffer.size());
 static_vector.emplace_back(...);
} // UB here

This would result in undefined behaviour, since both std::array and StaticVector would try to delete the first element.

Of course you might say that this doesn't compile, since the constructor for StaticVectorBase_ for external buffers and non-POD types only takes a char*. But of course someone would then "fix" the above code by writing:

{
 std::array<T, 1000> external_buffer;
 StaticVector<T, 0> static_vector(
 reinterpret_cast<char*>(external_buffer.data()),
 external_buffer.size()
 );
 static_vector.emplace_back(...);
} // Still UB here

Of course, you might say that the above is the problem of the caller, and that you'd want to use this with something memory-mapped anyway, and not with an existing container as a storage backend. So consider:

std::size_t buffer_size = 16 * 1024 * 1024 * 1024;
void *buffer = mmap(NULL, buffer_size, ...);
StaticVector<T, 0> static_vector(std::reinterpret_cast<char*>(buffer), buffer_size);

But oops, now capacity_ == buffer_size, but buffer_size is in bytes, where as capacity_ is the number of Ts. This might lead to a buffer overflow.

Other issues: what if buffer_value_type is a class derived from T? What if the external buffer is not correctly aligned for T?

It's hard to make this completely fool-proof. You could create a new type that enforces the caller to be very explicit:

struct RawMemory {
 void *data;
 std::size_t size;
};
... struct StaticVector: ... {
 ...
 constexpr explicit StaticVector(RawMemory buffer):
 Base(buffer.data, buffer.size) {}
 ...
};

But as indi suggested, even better would be to not add this functionality to your StaticVector, but instead use something like std::vector in combination with a polymorphic allocator, and have the allocator provide the external storage for the vector.

Add a test suite

To find bugs and to excercise the different ways to create and modify StaticVectors, create a test suite for it.

• indi: All of the "external buffer" stuff really doesn’t make a lot of sense. It makes the interface nonsensical—a StaticVector<T, N> has a maximum capacity of N except when it doesn’t, and it’s contents are "static" (whatever that may mean) except when they’re not, and the performance characteristics vary wildly... sometimes it’s constant-time movable, sometimes linear—which implies the "external buffer" case should be a completely different type. std::vector has always supported using an external buffer anyway, so it’s not clear why I’d use this type instead of that.
• Davislor: On second thought, edited my thoughts on duplicating the std::inplace_vector interface into my own answer.
• Nick: @indi When you are using external buffer, is same as if you are using internal, except is calculated from the buffer. Size is limited and can not go over the limit. I just using whatever I already programmed. Capacity is not used everywhere, so zero there is not really an issue except the user might be confused.

Answer 2

The Class Hierarchy

You currently have:

• StaticVectorBase_<Derived, T, Capacity, true>
• StaticVectorBase_<Derived, T, Capacity, false>
• StaticVectorBase_<Derived, T, 0, true>
• StaticVectorBase_<Derived, T, 0, false>
• StaticVector<T, Capacity>, inheriting from StaticVectorBase_< StaticVector<T, Capacity>, T, Capacity, std::is_trivial_v<T> && std::is_standard_layout_v<T>
• The type alias BufferedVector<T> for StaticVector<T, 0>

I suggest refactoring to have two classes:

• StaticVector<T, Capacity> with no base class and no overload for Trivial
• Some wrapper that gives an arbitrary buffer a vector interface, like BufferedVector<T>, but with no base class. (And the pedant in me wants to suggest, a more accurate name, like ExternalVector.)

G. Sliepen already has a good explanation for why you don’t need a POD/trivial overload: since trivial constructors and destructors are no-ops anyway, this doesn’t actually optimize anything.

I also strongly recommend against overloading Capacity of 0 to mean that a StaticVector with Capacity 0 is not a StaticVector or StaticVectorBase_ at all. For one thing, Capacity is no longer the capacity, and you can’t compare the number of inputs to it, and anything that takes a StaticVector<T, Capacity> will accept it and break. For another, copy and move have completely different behavior. A BufferedVector inherits a buffer_ data member from StaticVectorBase_, which is an array with zero elements, but is not declared to have no unique address, so the compiler will have to allocate a byte for it and possibly throw off all the data alignment. Any template on a StaticVector that refers to buffer[capacity_-1] will compile and blow up.

(Additionally, an array with zero bound is technically not legal in Standard C++, although GCC and most other compilers support it.)

Just make them separate classes. Duck-type them to the relevant container interfaces instead.

The Buffers

You declare buffer_ as type char, but the C++23 Standard actually allows allocated storage to be either unsigned char or std::byte. I can’t think of a compiler where this actually matters, but there’s no reason not to follow the spec.

One of your use cases was to allocate gigabytes of address space and then touch very little of it, but this is only going to work if you really can leave all elements past the current size_ uninitialized. This means destroying elements at the end when the array shrinks.

Use of Type Traits

It’s a very good idea to use the _v type-traits templates in if constexpr statements and template parameters, as you’re doing, but tests such as if constexpr(!IS_POD) are unnecessary because placement new works on them with zero overhead.

You do, however, want requires guards around your template member functions that generate only overloads for emplace that can actually construct a T, default-construct a T only if it is actually default-constructible, and so on. Edit: This is marked C++17, so you may need to use std::enable_if instead of requires.

The One Thing I Disagree with G. Sliepen About

Respectfully, there’s not too much noexcept. It just needs to be invoked more judiciously. For example, if the function calls a constructor of T with parameter pack Args, and that’s what might throw, give it the specifier

noexcept(std::is_nothrow_constructible_v<T, Args&&...>)

This also means you no longer want an if constexpr(is_nothrow_copy_constructible_v<T>) check: there is no reason to refuse to copy-construct if the copy constructor might throw.

The Other Thing I Don’t Disagree with, Per Se

But I want follow up to: G. Sliepen proposes that this class could be a drop-in replacement for std::inplace_vector and gives a list of differences between the interfaces.

One is that these have a member function, full(), that std::inplace_vector does not. If you do in fact want to meet to provide a seamless interface, you may want to provide a non-member function full, overloaded for each variation. Then you can add a compatibility header for clients who need full(container) to work with std::inplace_vector:

template<typename T, std::size_t N>
[[nodiscard]] constexpr bool full(const std::inplace_vector<T, N>& in) noexcept
{
 return in.size() >= in.max_size();
}

The Standard Library ended up doing this when it added non-member std::empty as the common interface. If you’re starting from scratch, you can decide whether you also want the member function at all.

Another item on the list is std::inplace_vector::shrink_to_fit. This is a no-op, and would logically be one for these classes too. It’s harmless and might help them duck-type to std::vector better.

The Constructors

You don’t really need the assign_ helpers. Once you destroy erased elements unconditionally, there is no need for a template with a Destroy parameter. Then, you can simply call std::uninitialized_fill_n, std::uninitialized_copy_n, etc.

Very important: do not use std::uninitialized_copy or std::uninitialized_move! They will cause a buffer overflow vulnerability! However, you can use std::uninitialized_copy_n and uninitialized_fill_n. What you do now, pushing to the end, is safe if you bounds-check.

Here, rather than accept all pairs of constructor arguments that have the same type, you want to have your iterator-pair and iterator-count constructors check

requires std::input_iterator<Iterator> &&
 std::constructible_from<T, std::iter_reference_t<Iterator> >

Now, you sometimes try to move rather than copy the elements. A technique you can use to optimize this is to check

std::is_rvalue_reference_v<std::iter_reference_t<Iterator> >

This succeeds when, for example, you pass in std::move_iterator(std::begin(src)) as the source iterator. You might want to use this in an if constexpr to decide between std::uninitialized_move_n and std::uninitialized_copy_n. However, if you’re writing a loop that checks for buffer overrun, such as the one you have now that uses push_back(T&&), or

for (auto it = begin; size_ < capacity_ && it < end; ++size_, ++it ) {
 new(buffer_ + sizeof(T)*size_) T{*it};
}

modern compilers will in fact detect when to move rather than copy the source elements. You might, however, want to check whether the iterators are contiguous, which lets you take the difference between last and first to count the number of elements in the input range, and then delegate to the iterator-and-count constructor, which can bounds-check and call std::uninitialized_copy_n or std::uninitialized_move_n.

Another optimization here could help one of your use cases. You say you want to allocate a large amount of address space for a sparse external vector and touch only the elements you use. If you specify that the external buffer passed to the function should be zero-initialized (the default for arrays with static storage, and something calloc(), Linux mmap() with the right flags and Windows VirtualAlloc2() all guarantee), and if the value type is an implicit-lifetime type, you can provide an interface to increase its allocated size as a no-op, without actually touching the pages of memory. You could still destroy and zero out any truncated elements to maintain the invariant that all elements past the end are zero-initialized. Otherwise, you can declare that the value of any element that was assigned to, truncated away, and then made valid again by a quickie-expand, is unspecified. In this case, truncating might really skip destroying truncated elements if possible, as implementations still could touch those pages of memory.

Defaults and Deletes

You currently have a destructor which tries to dynamically dispatch a deallocate_, which then just calls destroy_, which finally calls std::destroy(begin(), end()). The only part of this you need is a destructor that calls std::destroy on the allocated elements. (If you wanted to get cute, you could make the vectors trivially destructible if and only if the value type is.) As above, it should be noexcept(is_nothrow_destructible_v<T>).

You might want to allow a converting constructor from other appropriate ranges, possibly through the C++23 std::from_range_t interface, but possibly also by adding explicit constructors. Some of the lower-hanging fruit is a static vector, array or std::array with equal or smaller capacity.

The external-buffer version has no way to allocate a copy of the buffer, so it should be move-only. It should delete the copy-constructor and copy-assignment, and default the move-constructor and move-assignment. It should be default-constructible with a null pointer and capacity of 0, unless you have a reason not to. It should also be swappable.

The version with the internal buffer should always be default-constructible, with an empty buffer. The default constructors and assignments should suffice, although you might want to explicitly delete and perhaps even explicitly default them based on whether the value type is copyable and movable.

• Nick: Thanks. But very C++23 centric. If trivial things removed, it will not in constexpr.
• Davislor: @Nick I don’t think I understand your comment. Which trivial things, and what won’t be constexpr?
• Nick: in c++17 most of standard algorithms are not constexpr.
• Davislor: @Nick Okay. A constructor that calls std::uninitialized_fill_n or std::uninitialized-move_n will not be constexpr. You would want to use something like the for loop version for that.