Generic multi dimension grid / array class in C++

I am writing a generic C++14 multi dimensional array for computational science purpose.

The "features" so far for the class tries to:

• store multi-dimensional grid values into a flatten array

• provide grid values access and flat index access from multi dim coordinates with \$O(1)\$ average complexity (worst case is \$O(N)\$)

• provide grid values access and coordinates access from flat index with \$O(1)\$ complexity

• provide iterators so that grid behaves like a STL container

• statically-sized arrays, efficient storage, similar to C-style array thanks to metaprogramming

The key point in this implementation is to provide easy flat index Grid[idx] conversion to/from multi-dim grid Grid[{x,y,z}]. For instance in 2D, we get {x,y} from {idx % N, idx / N} for instance where N is the total size of the grid. The aim is to make this generic.

```
#include
#include
#include
#include
#include

#include // just for std::generate in main()

// std::unordered_map needs std::hash specialization for std::array
namespace std {
template
struct hash > {
using argument_type = array ;
using result_type = size_t;
result_type operator()(const argument_type& a) const {
hash hasher;
result_type h = 0;
for (result_type i = 0; i
std::ostream& operator& arr) {
os
constexpr T meta_prod(T x) { return x; }

template
constexpr T meta_prod(T x, Ts... xs) { return x * meta_prod(xs...); }

template
constexpr T meta_pow(T base, E expo) { return (expo != 0 ) ? base * meta_pow(base, expo-1) : 1; }

// Compute the total number of elements 2x2x2 for two usage
// for Grid (specify all size dimensions)
template constexpr
std::enable_if_t
num_vertices() { return meta_prod(NDIM...); }

// for Grid (specify one size dimension and consider the same size for other dimensions)
template constexpr
std::enable_if_t
num_vertices() { return meta_pow(NDIM...,DIM); }

template
class MultiGrid {
public:
static_as

I think the major problem with this solution is Unnecessary Redundancy. Let's start with the signature:

template
class MultiGrid;

Why do you both need to specify the number of dimensions and the dimensions? You have to assert that the two line up, so why not just imply the #?

template 
class MultiGrid {
    static constexpr size_t NUM_DIMS = sizeof...(DIMS);
    static_assert(NUM_DIMS > 0, "because what are you doing?");
};

The idea that MultiGrid should be a 2x2x2 is a little too magical. If people want a 2x2x2 grid, they can write 2 three times. If they want a 2x2x2x....2 grid, they can write a metafunction themselves.

But that's just a minor quibble compared to... HOLY SIZE, BATMAN!

std::cout ) << std::endl;
// prints 1464

Uh, what now? I have a 5-dimension array that consists of 32 integers. That should be 128 bytes. You're using more than 10x the amount of memory necessary! And that underestimates the size since you have this huge unordered_map which is all on the heap. Why? Because in addition to storing your array (values_), you're storing completely unnecessary information in map_idx_to_coord_ and map_coord_to_idx_.

Why do I say unnecessary? Let's consider your access by ArrayCoord:

reference operator[] (const ArrayCoord& coord) { 
    return values_[map_coord_to_idx_.at(coord)]; 
}

Do we really need the map lookup there? Can we just mathematically determine the right idx from coord? Of course we can:

namespace detail {
    template 
    size_t flatten(Iter first, Iter, std::index_sequence ) {
        return *first;
    }

    template 
    size_t flatten(Iter first, Iter last, std::index_sequence ) {
        return *first * meta_prod(DIMS...) + 
               flatten(std::next(first), last, std::index_sequence{} );
    }
}    

reference operator[] (const ArrayCoord& coord) { 
    return values_[details::flatten(
        coord.begin(), coord.end(), std::index_sequence{})];
}

That will compute your index from an array of coordinates on the fly. It's still constant time and is guaranteed faster than your unordered_map solution anyway (which still has to walk the whole array at least twice - once to do the hash and again to do equality comparison). And will use zero extra space, so everything else will perform better too.

Drop the extra members. When you're writing containers, lean is king. This class should have exactly one member: values_.

StackExchange Code Review Q#97260, answer score: 6