2D grid container with arbitrary multiple data types

Question

I've been toying with the idea of making a simple game. In game development, it is good to do things in a more struct-of-arrays style rather than arrays-of-structs style, due to cache locality. However, I wanted to fool around even more, so my class puts all the data in one contiguous block of memory. It was my first time using placement new, and I rather enjoyed the template metaprogramming. I'm not 100% sure that my memory management was done correctly. There are some non-standard parts of the code because I was using Visual Studio:

parameter-pack.hpp

#pragma once

#include <utility> // std::integer_sequence

/**
 * @file Contains structs for doing calculations with parameter packs
 * @details Most of the functions here are for sizeof() calculations related to parameter packs
 */

namespace utils { namespace mp {

/**
 * \brief A struct to "hold" a parameter pack.
 * \tparam Ts The parameter pack that this struct "holds"
 */
template<class... Ts>
struct Pack
{};

/**
 * \brief Obtain the Nth type in a parameter pack.
 * \tparam N The index to obtain
 * \tparam T The beginning of the parameter pack list
 * \tparam Ts The rest of the parameter pack list
 * \see get_t
 */
template<size_t N, class T, class... Ts>
struct Get
{
    static_assert(N < sizeof...(Ts) + 1, "N was too large; out of bounds");
    using type = typename Get<N - 1, Ts...>::type;
};

// Recursion base case
template<class T, class... Ts>
struct Get<0, T, Ts...>
{
    using type = T;
};

/**
 * \brief The type of the element at the Nth position in the parameter pack.
 * \details This is simply a shortened form of Get, but it is easier to use
 *          because you don't have to type out `typename`
 * \tparam N The index of the type to obtain
 * \tparam Ts The parameter pack list that we want to know about
 */
template<size_t N, class... Ts>
using get_t = typename Get<N, Ts...>::type;

/**
 * \brief Obtains the size of the nth element, in bytes, like `sizeof`
 * \tparam N The element to find the sizeof
 * \tparam T The first type in the parameter pack
 * \tparam Ts The rest of the types
 */
template<size_t N, class T, class... Ts>
struct SizeOfNth
{
    static constexpr size_t value = sizeof(get_t<N, T, Ts...>);;
};

/**
 * \brief Sums the size of the first N (including the specified position) types, in bytes.
 * \tparam N The last element to sum the size in bytes up.
 * \tparam T The first type in the parameter pack
 * \tparam Ts The rest of the types
 */
template<size_t N, class T, class... Ts>
struct SizeUpToNth
{
    static_assert(N < sizeof...(Ts) + 1, "N was too large; out of bounds");
    static constexpr size_t value = sizeof(T) + SizeUpToNth<N - 1, Ts...>::value;
};

// Recursion base case
template<class T, class... Ts>
struct SizeUpToNth<0, T, Ts...>
{
    static constexpr size_t value = sizeof(T);
};

/**
 * \brief Obtains the total sum of the size of the types.
 * \tparam Ts The parameter pack types to compute the total size of
 */
template<class... Ts>
struct CombinedSizeOf
{
    static_assert(sizeof...(Ts) > 0, "Useless to discover the size of an empty pack");
    static constexpr size_t value = SizeUpToNth<sizeof...(Ts) - 1, Ts...>::value;
};

}}

grid-data.hpp

#pragma once

#include <new> // placement new
#include <utility>

#include "parameter-pack.hpp"

namespace utils {

/**
 * \brief Contains information internal to the utils namespace. Not public api; could change without warning.
 */
namespace internal {

/**
 * \brief A simple tag for use in tag dispatching within the utils::GridData type.
 */
struct GridData_ConstructorTag
{};

}

using coord_t = size_t;

/**
 * \brief Stores a multitude of types in a grid.
 * \details Rather than having an "array of structs", this implements an optimized version of a
 *          "struct of arrays", where the arrays are actually a 2D grid. This can store several
 *          pieces of information together in the grid, but optimized for cache efficiency.
 *          <br>
 *          This container assumes that it owns any objects stored within it, and it will call the
 *          destructor on any and all stored objects. Also note that if the constructor fails due
 *          to exceptions in initialization, destructors of the type that this container holds are
 *          likely to be called on garbage data.
 *          <br>
 *          Example Usage:
 *          \code{.cpp}
 *          GridData<int32_t, bool> grid{ 100, 100 };
 *          // A grid of height and walkability.
 *          // Loop through and initialize grid
 *          grid.foreach<0>([] (coord_t x, coord_t y, int32_t data) { // Do something with the data });
 *          \endcode
 * \tparam Ts The types to store in the grid.
 */
template<class... Ts>
class GridData
{
    // Simple constructor with the tag; this just initializes the data members; it does not call the
    // constructors of the elements it contains.
    GridData(size_t width, size_t height, internal::GridData_ConstructorTag)
        : width_{ width }
        , height_{ height }
        , data_{ new char[utils::mp::CombinedSizeOf<Ts...>::value * width * height] } {}

public:
    /**
     * \brief Creates a GridData with all its data members default-initialized.
     * \details The default constructors of the elements in the container MUST not
     *          throw, or the destructors may end up being called on garbage data.
     *          To initialize the data members, it becomes necessary to use copy-assignment.
     *          Consider using the other constructor; it can be faster.
     * \param width The width of the grid
     * \param height The height of the grid
     */
    GridData(size_t width, size_t height)
        : GridData{ width, height, internal::GridData_ConstructorTag{} } {
        initializeNoInitializers(std::index_sequence_for<Ts...>{});
    }

    /**
     * \brief Creates a GridData with all its data members initialized to the result of calling the corresponding
     *        initialization function
     * \details Each position in the grid is initialized by calling the function, then `std::move`-ing the result
     *          into the container. The initialization functions MUST not throw, or the destructors for the container's
     *          elements are likely to be called on garbage data. Consider using the other constructor if
     *          copy-assignment is more desirable than `std::move`.
     * \tparam Fs Functions with signature `Ts(coord_t x, coord_t y)`
     * \param width The width of the grid
     * \param height The height of the grid
     * \param initializers The initializers used to initialize the data members
     */
    template<class... Fs>
    GridData(size_t width, size_t height, Fs &&... initializers)
        : GridData{ width, height, internal::GridData_ConstructorTag{} } {
        initialize(std::index_sequence_for<Ts...>{}, std::forward<Fs>(initializers)...);
    }

    /**
     * \brief You should not be copying this object.
     * \details It is designed to hold a large amount of data; you do not want to copy the entire thing
     */
    GridData(const GridData &) = delete;

    /**
     * \brief 
     * \param m 
     */
    GridData(GridData &&m) noexcept
        : width_{ m.width_ }
        , height_{ m.height_ }
        , data_{ m.data_ } {
        m.data_ = nullptr;
    }

    /**
     * \brief Destroys this container, destroying all its elements and freeing any used memory.
     */
    ~GridData() {
        if (data_) {
            destroy(std::index_sequence_for<Ts...>{});
            delete[] data_;
            data_ = nullptr;
        }
    }

    GridData& operator=(const GridData &) = delete;
    GridData& operator=(GridData &&) = delete;

    /**
     * \brief Obtains data at the specified location, with the specified type.
     * \tparam N The type of data elements to get
     * \param x The x coordinate we want to inspect
     * \param y The y coordinate we want to inspect
     * \return The data at the specified coordinate, of the specified type.
     */
    template<size_t N>
    const utils::mp::get_t<N, Ts...>& get(coord_t x, coord_t y) const {
        return *reinterpret_cast<utils::mp::get_t<N, Ts...> *>(this->template elementStart<N>(x, y));
    }

    /**
     * \brief Obtains the data at the specified location, with the specified type. Can be used to set data at a location.
     * \details Note that anything assigned into this container is assumed to be owned by the container.
     * \tparam N The type of data elements to get
     * \param x The x coordinate we want to inspect
     * \param y The y coordinate we want to inspect
     * \return The data at the specified coordinate, of the specified type.
     */
    template<size_t N>
    utils::mp::get_t<N, Ts...>& get(coord_t x, coord_t y) {
        return *reinterpret_cast<utils::mp::get_t<N, Ts...> *>(this->template elementStart<N>(x, y));
    }

    /**
     * \brief Calls the function for each x and y coordinate of the grid.
     * \tparam N The class of types to apply the function over
     * \tparam F A function of the form `void(coord_t, coord_t, T)`. It could return anything, but doesn't need to.
     * \param f The function to apply over the entire class of types.
     */
    template<size_t N, class F>
    void foreach(F &&f) {
        for (coord_t y = 0; y < height(); y++) {
            for (coord_t x = 0; x < width(); x++) {
                (void) f(x, y, get<N>(x, y));
            }
        }
    }

    size_t height() const { return height_; }
    size_t width() const { return width_; }
private:
    coord_t width_;
    coord_t height_;
    char *data_;

    template<size_t N>
    char* elementStart(coord_t x, coord_t y) {
        char *start = data_ + (utils::mp::SizeUpToNth<N, Ts...>::value - utils::mp::SizeOfNth<N, Ts...>::value) * width_ * height_;
        return start + utils::mp::SizeOfNth<N, Ts...>::value * (x + y * width_);
    }

    template<size_t N, class F>
    void initializeBlock(F &&f) {
        for (coord_t y = 0; y < height_; y++) {
            for (coord_t x = 0; x < width_; x++) {
                new(elementStart<N>(x, y)) utils::mp::get_t<N, Ts...>(std::move(f(x, y)));
            }
        }
    }

    template<size_t... I, class... Fs>
    void initialize(std::index_sequence<I...>, Fs &&... fs) {
        int unused[] = { (initializeBlock<I>(fs) , 1)... };
        (void) unused;
    }

    template<size_t N>
    void initializeBlockNoInitializers() {
        for (coord_t y = 0; y < height_; y++) {
            for (coord_t x = 0; x < width_; x++) {
                new(elementStart<N>(x, y)) utils::mp::get_t<N, Ts...>;
            }
        }
    }

    template<size_t... I>
    void initializeNoInitializers(std::index_sequence<I...>) {
        int unused[] = { (initializeBlockNoInitializers<I>() , 1)... };
        (void) unused;
    }

    template<size_t N, class T>
    void destroyBlock() {
        for (coord_t y = 0; y < height_; y++) {
            for (coord_t x = 0; x < width_; x++) {
                T *t = reinterpret_cast<T*>(elementStart<N>(x, y));
                t->~T();
            }
        }
    }

    template<size_t... I>
    void destroy(std::index_sequence<I...>) {
        int unused[] = { (destroyBlock<I, utils::mp::get_t<I, Ts...>>() , 1)... };
        (void) unused;
    }
};

}

I did also test it using Google Test, but I'm not that worried about the quality of my test code:

test-grid-data.cpp

#include "grid-data.hpp"

#include "gtest/gtest.h"

#include <string>
#include <tuple>

using namespace utils;

TEST(Utils_GridData, WorksForOneType) {
    GridData<std::string> data{ 100, 100 };
    for (size_t y = 0; y < data.height(); y++) {
        for (size_t x = 0; x < data.width(); x++) {
            data.template get<0>(x, y) = std::to_string(y * data.width() + x);
        }
    }

    for (size_t y = 0; y < data.height(); y++) {
        for (size_t x = 0; x < data.width(); x++) {
            EXPECT_EQ(data.template get<0>(x, y), std::to_string(y * data.width() + x));
        }
    }
}

TEST(Utils_GridData, WorksForOneTypeWithInitializers) {
    GridData<std::string> data{ 100, 100, [] (size_t x, size_t y) { return std::to_string(y * 100 + x); } };

    for (size_t y = 0; y < data.height(); y++) {
        for (size_t x = 0; x < data.width(); x++) {
            EXPECT_EQ(data.template get<0>(x, y), std::to_string(y * data.width() + x));
        }
    }
}

TEST(Utils_GridData, WorksForTwoTypes) {
    GridData<uint32_t, std::pair<uint32_t, uint32_t>> data{ 100, 100 };
    for (size_t y = 0; y < data.height(); y++) {
        for (size_t x = 0; x < data.width(); x++) {
            data.template get<0>(x, y) = y * data.width() + x;
            data.template get<1>(x, y) = { x, y };
        }
    }

    for (size_t y = 0; y < data.height(); y++) {
        for (size_t x = 0; x < data.width(); x++) {
            EXPECT_EQ(data.template get<0>(x, y), y * data.width() + x);
            EXPECT_EQ(data.template get<1>(x, y), std::make_pair(x, y));
        }
    }
}

TEST(Utils_GridData, WorksForTwoTypesWithInitializers) {
    GridData<uint32_t, std::pair<uint32_t, uint32_t>> data{
        100, 100,
        [] (size_t x, size_t y) { return y * 100 + x; },
        [] (size_t x, size_t y) { return std::make_pair(x, y); }
    };

    for (size_t y = 0; y < data.height(); y++) {
        for (size_t x = 0; x < data.width(); x++) {
            EXPECT_EQ(data.template get<0>(x, y), y * data.width() + x);
            EXPECT_EQ(data.template get<1>(x, y), std::make_pair(x, y));
        }
    }
}

TEST(Utils_GridData, WorksForManyWithInitializers) {
    GridData<uint32_t, std::pair<uint32_t, uint32_t>, bool, int32_t> data{
        100, 100,
        [] (size_t x, size_t y) { return y * 100 + x; },
        [] (size_t x, size_t y) { return std::make_pair(x, y); },
        [] (size_t x, size_t y) { return static_cast<bool>((x ^ y) & 1); },
        [] (size_t x, size_t y) { return static_cast<int32_t>(x - y); }
    };

    for (size_t y = 0; y < data.height(); y++) {
        for (size_t x = 0; x < data.width(); x++) {
            EXPECT_EQ(data.template get<0>(x, y), y * data.width() + x);
            EXPECT_EQ(data.template get<1>(x, y), std::make_pair(x, y));
            EXPECT_EQ(data.template get<2>(x, y), static_cast<bool>((x ^ y) & 1));
            EXPECT_EQ(data.template get<3>(x, y), static_cast<int32_t>(x - y));
        }
    }
}

TEST(Utils_GridData, ForeachWorks) {
    GridData<uint32_t, std::pair<uint32_t, uint32_t>, bool, int32_t> data{
        100, 100,
        [] (size_t x, size_t y) { return y * 100 + x; },
        [] (size_t x, size_t y) { return std::make_pair(x, y); },
        [] (size_t x, size_t y) { return static_cast<bool>((x ^ y) & 1); },
        [] (size_t x, size_t y) { return static_cast<int32_t>(x - y); }
    };

    bool succeeded = true;
    data.foreach<0>([&] (size_t x, size_t y, uint32_t result) {
        if (result != y * data.width() + x) succeeded = false;
    });
    EXPECT_TRUE(succeeded);

    succeeded = true;
    data.foreach<1>([&] (size_t x, size_t y, std::pair<uint32_t, uint32_t> result) {
        if (result != std::make_pair(x, y)) succeeded = false;
    });
    EXPECT_TRUE(succeeded);

    succeeded = true;
    data.foreach<2>([&] (size_t x, size_t y, bool result) {
        if (result != static_cast<bool>((x ^ y) & 1)) succeeded = false;
    });
    EXPECT_TRUE(succeeded);

    succeeded = true;
    data.foreach<3>([&] (size_t x, size_t y, int32_t result) {
        if (result != static_cast<int32_t>(x - y)) succeeded = false;
    });
    EXPECT_TRUE(succeeded);
}

TEST(Utils_GridData, WorksAfterBeingMoved) {
    GridData<uint32_t, std::pair<uint32_t, uint32_t>> data1{
        100, 100,
        [] (size_t x, size_t y) { return y * 100 + x; },
        [] (size_t x, size_t y) { return std::make_pair(x, y); }
    };

    GridData<uint32_t, std::pair<uint32_t, uint32_t>> data{ std::move(data1) };

    for (size_t y = 0; y < data.height(); y++) {
        for (size_t x = 0; x < data.width(); x++) {
            EXPECT_EQ(data.template get<0>(x, y), y * data.width() + x);
            EXPECT_EQ(data.template get<1>(x, y), std::make_pair(x, y));
        }
    }
}

Answer 1

Use std::size_t

The proper way to spell size_t is std::size_t. While often some library will pull in size_t into the global namespace, this is not guaranteed if you only include C++ headers. You should also #include <cstddef> or one of the other header files that is guaranteed to declare that type.

Inconsistent use of coord_t

You use coord_t for some parameters and size_t for others. Worst is that you store width and height as coord_t, but the constructor and getters use size_t. I would either use coord_t everywhere for width, height, x and y values, or just not use it at all but use std::size_t everywhere, as that is what a programmer would already be most familiar with.

Use a smart pointer to manage memory allocation

Make data_ a std::unique_ptr<char[]>, then you don't have to worry about deleting the memory you allocated. Even better, you no longer have to worry about copy constructors and assignment operators anymore; these can be default generated and will do exactly what you want.

Use more auto

Use auto to avoid having to repeat types. For example, the return type of get() can be made auto.

Store the combined size in a static constexpr member

Instead of having to spell out utils::mp::CombinedSizeOf<Ts...>::value, you can do:

template<class... Ts>
class GridData
{
    static constexpr std::size_t combined_size = utils::mp::CombinedSizeOf<Ts...>::value;
    ...
};

In fact, you can even make templates:

template<std::size_t N>
static constexpr size_of = utils::mp::SizeOfNth<N, Ts...>::value;

template<std::size_t N>
static constexpr size_up_to = utils::mp::SizeUpToNth<N, Ts...>::value;

This way you can write:

template<size_t N>
char* elementStart(coord_t x, coord_t y) {
    auto start = data_ + size_up_to<N> - size_of<N> * width_ * height_;
    return start + size_of<N> * (x + y * width_);
}

Finally, you can also make templates out of type aliases:

template<std::size_t N>
using type = utils::mp::get_t<N, Ts...>;

And then for example use it like so in initializeBlock():

new (elementStart<N>(x, y)) type<N>(std::move(f(x, y)));

"Up to Nth" should not include Nth

In C++ where we use zero-based indexing, and when we loop "up to N" we usually don't include the Nth element. Do the same for your parameter pack utilities. This simplifies things in several places, sometimes just a + 1 or - 1 that can be removed, sometimes more complicated expressions simplify. Also don't forbid to get the size of an empty parameter pack, zero is a very reasonable value to return:

template<class T, class... Ts>
struct SizeUpToNth<0, T, Ts...>
{
    static constexpr size_t value = 0;
};

template<class... Ts>
struct CombinedSizeOf
{
    static constexpr size_t value = SizeUpToNth<sizeof...(Ts), Ts...>::value;
};

Then elementStart() becomes:

template<size_t N>
char* elementStart(coord_t x, coord_t y) {
    auto start = data_ + size_up_to<N> * width_ * height_;
    return start + size_of<N> * (x + y * width_);
}

destroyBlock() doesn't need to know T

It can derive the type of element just from N:

template<size_t N>
void destroyBlock() {
    using T = type<N>;
    for (coord_t y = 0; y < height_; y++) {
        for (coord_t x = 0; x < width_; x++) {
            get<N>(x, y).T();
        }
    }
}

template<size_t... I>
void destroy(std::index_sequence<I...>) {
    int unused[] = { (destroyBlock<I>(), 1)... };
    (void) unused;
}

Consider providing views

The C++20 ranges library added the concept of views for containers. Basically, a view acts like a STL container, but it merely refers to an existing container internally. It is very useful however, since it allows existing STL algorithms and range-for loops to work on those views.

You don't have to use C++20 to provide your own views. Consider creating a class that has begin() and end() functions that return iterators to the actual data stored in a grid. It might take quite a lot of code to implement this (so I won't even try to show something here), but the goal is to make iterating over the grid data much easier. Instead of passing a function to foreach(), it should be possible to write something like:

GridData<int, float, ...> grid(100, 100);

auto view_of_ints = grid.view<0>();
auto sum_of_ints = std::accumulate(view_of_ints.begin(), view_of_ints.end(), 0);

// Print all float values
for (auto& element: grid.view<1>()) {
    std::cout << element << ", ";
}

You might also consider being able to create a view of multiple elements at the same time, for example grid.view<0, 1>(), although that would be harder to implement.

Use fold expressions

Some of your code could also be simplified using C++17's fold expressions, for example:

template<size_t... I>
void destroy(std::index_sequence<I...>) {
    (destroyBlock<I>(), ...);
}

Don't put everything in one contiguous block of memory

A lot of complication comes from the fact that you decided to put everything into one contiguous block of memory. However, I don't think that will gain you any performance benefits, and it might not even save memory or make memory usage worse (think memory fragmentation if you create and destroy grids often).

If you relax this requirement, then you could have written:

template<class... Ts>
class GridData
{
    std::tuple<std::vector<Ts>, ...> data_;
    ...
public:
    ...
    template<std::size_t N>
    auto& get(std::size_t, std::size_t y) {
        return std::get<N>(data_)[x + y * width_];
    }
    ...
};