HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

2D grid container with arbitrary multiple data types

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
containergridwitharbitrarymultipletypesdata

Problem

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 // 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
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
struct Get
{
static_assert(N ::type;
};

// Recursion base case
template
struct Get
{
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
using get_t = typename Get::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
struct SizeOfNth
{
static constexpr size_t value = sizeof(get_t);;
};

/**
* \brief Sums the size of the fi

Solution

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 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, 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::value, you can do:

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


In fact, you can even make templates:

template
static constexpr size_of = utils::mp::SizeOfNth::value;

template
static constexpr size_up_to = utils::mp::SizeUpToNth::value;


This way you can write:

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


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

template
using type = utils::mp::get_t;


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

new (elementStart(x, y)) type(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
struct SizeUpToNth
{
    static constexpr size_t value = 0;
};

template
struct CombinedSizeOf
{
    static constexpr size_t value = SizeUpToNth::value;
};


Then elementStart() becomes:

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


destroyBlock() doesn't need to know T

It can derive the type of element just from N:

template
void destroyBlock() {
    using T = type;
    for (coord_t y = 0; y (x, y).T();
        }
    }
}

template
void destroy(std::index_sequence) {
    int unused[] = { (destroyBlock(), 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 grid(100, 100);

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

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


You might also consider being able to create a view of multiple elements at the same time, for example grid.view(), 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
void destroy(std::index_sequence) {
    (destroyBlock(), ...);
}


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 GridData
{
std::tuple, ...> data_;

Code Snippets

template<class... Ts>
class GridData
{
    static constexpr std::size_t combined_size = utils::mp::CombinedSizeOf<Ts...>::value;
    ...
};
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;
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_);
}
template<std::size_t N>
using type = utils::mp::get_t<N, Ts...>;
new (elementStart<N>(x, y)) type<N>(std::move(f(x, y)));

Context

StackExchange Code Review Q#146518, answer score: 3

Revisions (0)

No revisions yet.