Storing end pointer to uninitialized array in constexpr context-CodePudding

I'm trying to create a constexpr friendly small buffer optimized vector type that stores a begin, end and capacity pointer as usual, but when it is default constructed the begin and capacity pointer point towards local memory before reallocating to heap when required. However I cannot figure out how to store the capacity pointer in the constexpr context, because I want it to be able to support non-trivially constructed types. In order to store non-trivially constructed types I cannot use std::aligned_storage because of the full type erasure which will not allow me to get the elements later (because reinterpret_cast is not allowed), so I decided to store the elements in an array of unions (kind of like optional does it). Storing it like this allows me to get the elements later through union access and allows me to leave the array uninitialized, but i cannot figure out how to store a value pointer to capacity end when it is stored inside of unions because it does not detect the whole one beyond last pointer stuff when pointing to a union value. Ofcourse all of this requires c 20.

#include <algorithm>
#include <memory>
#include <utility>
#include <array>

struct Null{};

template<typename T>
union Storage
{
    Null uninitialized;
    T value;

    constexpr Storage()
    : uninitialized{}
    {}

    template<typename... Args>
    constexpr Storage(Args&&... args)
    : value(std::forward<Args>(args)...)
    {}

    constexpr ~Storage(){}
};

template<typename T, size_t N>
struct Vec
{
    std::array<Storage<T>, N> storage;

    T* begin; 
    T* end;   

    constexpr Vec()
    : begin(makeBegin())
    , end(makeEnd())
    {}

    constexpr T* makeBegin()
    {
        return &storage[0].value;
    }
    constexpr T* makeEnd()
    {
        return (&storage[N].value);
    }
};


constexpr bool test()
{
    Vec<std::pair<float, float>, 10> vec{};

    for(auto it = vec.begin; it < vec.end;   it)
    {
        std::construct_at(it, 10.0f, 10.0f);
    }

    return vec.begin[5] == std::pair{ 10.0f, 10.0f };
}


int main()
{
    static_assert(test());
}

https://godbolt.org/z/46o19qcvP

Is there another way to get a pointer to stored non-trivially constructible types like pairs in an array without initializing them?

CodePudding user response：

There are multiple problems with your code:

T* is not a valid iterator for your representation, as the Ts are actually a member of a structure. The iterator needs to operate on the array's value type.
Using storage[N] is an out of bounds access, even if you just try to use the address of the member within.

One way fix both problems is to use a custom iterator type. As was mentioned in the comment that wouldn't be necessarily ideal. A different idea is to store a T[N] in the union. To do so, the union will need suitable constructors/destructors but as the intent is to use array as an uninitialized storage that's fine. Of course, any constructed elements need to be destroyed appropriately at some point. Here is the corresponding code:

#include <algorithm>
#include <memory>
#include <utility>
#include <array>

template<typename T, size_t N>
struct Vec
{
    union u {
        constexpr u(){}
        constexpr ~u(){}
        T array[N];
    } storage;
    
    T* begin;
    T* end;
    
    constexpr Vec()
    : begin(makeBegin())
    , end(makeEnd())
    {}
    
    constexpr T* makeBegin()
    {   
        return storage.array;
    }
    constexpr T* makeEnd()
    {   
        return this->makeBegin()   N;
    }
};


constexpr bool test()
{   
    Vec<std::pair<float, float>, 10> vec{};
    
    for(auto it = vec.begin; it < vec.end;   it)
    {   
        std::construct_at(&*it, 10.0f, 10.0f);
    }
    
    return vec.begin[5] == std::pair{ 10.0f, 10.0f };
}


int main()
{   
    static_assert(test());
}

CodePudding user response：

Not sure if I fully understood what you're after to be honest, but if you're looking for a compile time container whose types can be uninitialized you can use an std::variant as your element type.

In order to store non trivially constructible types that won't be initialized upon construction of your container you set the first alternative to std::monostate (this is similar to your Null type).

One issue with the API I have below is it's a little inconsistent; for example sometimes I return an std::variant and other times I return a pointer to the alternative (or null in the event the std::variant at the specified index wasn't initialized with a value).

You can, of course, change the API to suit your needs (like always returning the std::variant by reference and allowing the caller to test if it contains a "valid" value and if not, set it).

Note: At the moment, this only compiles with GCC and MSVC.

template<typename T, std::size_t N>
class cvec 
{ 
    using element_type = std::variant<std::monostate, T>;
    using size_type = std::size_t;

public:
    template<typename ...Args>
    constexpr void emplace_at( size_type index, Args&& ...args ) {
        buffer_[ index ].template emplace<T>( std::forward<Args>( args )... );
    }

    constexpr void insert( size_type index, T&& value )
    { buffer_[ index ] = std::move( value ); }

    constexpr void insert( size_type index, const T& value )
    { buffer_[ index ] = value; }

    constexpr auto try_get_at( size_type index )
    { return std::get_if<T>( &buffer_[ index ] ); }

    constexpr decltype( auto ) end( )
    { return std::end( buffer_ ); }

    constexpr decltype( auto ) begin( )
    { return std::begin( buffer_ ); }

    constexpr decltype( auto ) operator[ ]( size_type index ) 
    { return buffer_[ index ]; }

private:
    std::array<element_type, N> buffer_{ };
};

consteval bool test( )
{
    using pair = std::pair<float, float>;
    cvec<pair, 10> vec{ };

    for( int i = 0; i < 10; i   )
    {
        vec.emplace_at( i, 10.0f, 10.0f );
    }
    return *vec.try_get_at( 5 ) == std::pair{ 10.0f, 10.0f };
}



int main( )
{
    static_assert( test( ) );
}