Generic C++ multidimensional iterators

Question

In my current project I am dealing with a multidimensional datastructure. The underlying file is stored sequentially (i.e. one huge array, no vector of vectors). The algorithms that use these datastructures need to know the size of the individual dimensions.

I am wondering if a multidimensional iterator class has been definied somewhere in a generic way and if there are any standards or preferred ways on how to tackle this.

At the moment I am just using a linear iterator with some additional methods that return the size of each dimension and how many dimensions are there in the first part. The reason I don't like it is because I can't use std:: distance in a reasonable way for example (i.e. only returns distance of the whole structure, but not for each dimension separately).

For the most part I will access the datastructure in a linear fashion (first dimension start to finish -> next dimension+...and so on), but it would be good to know when one dimension "ends". I don't know how to do this with just operator*(), operator+() and operator==() in such an approach.

A vector of vectors approach is disfavored, because I don't want to split up the file. Also the algorithms must operate on structure with different dimensionality and are therefore hard to generalize (or maybe there is a way?).

Boost multi_array has the same problems (multiple "levels" of iterators).

I hope this is not too vague or abstract. Any hint in the right direction would be appreciated.

I was looking for a solution myself again and revisited boost:: multi_array. As it turns out it is possible to generate sub views on the data with them, but at the same time also take a direct iterator at the top level and implicitely "flatten" the data structure. The implemented versions of multi_array however do not suit my needs, therefore I probably will implement one myself (that handles the caching of the files in the background) that is compatible with the other multi_arrays.

I will update it again once the implementation is done.

Answer 1

I have just decided to open a public repository on Github : MultiDim Grid which might help for your needs. This is an ongoing project so I would be glad if you can try it and tell me what you miss / need.

I have started working on this with this topic on codereview.

Put it simply :

MultiDim Grid proposes a flat uni-dimensional array which offer a generic fast access between multi-dimension coordinates and flatten index.

You get a container behaviour so you have access to iterators.

Answer 2

That's not that difficult to implement. Just state precisely what functionality your project requires. Here's a dumb sample.

#include <iostream>
#include <array>
#include <vector>
#include <cassert>

template<typename T, int dim>
class DimVector : public std::vector<T> {
public:
    DimVector() {
        clear();
    }

    void clear() {
        for (auto& i : _sizes)
            i = 0;
        std::vector<T>::clear();
    }

    template<class ... Types>
    void resize(Types ... args) {
        std::array<int, dim> new_sizes = { args ... };
        resize(new_sizes);
    }

    void resize(std::array<int, dim> new_sizes) {
        clear();
        for (int i = 0; i < dim; ++i)
            if (new_sizes[i] == 0)
                return;
        _sizes = new_sizes;
        int realsize = _sizes[0];
        for (int i = 1; i < dim; ++i)
            realsize *= _sizes[i];
        std::vector<T>::resize(static_cast<size_t>(realsize));
    }

    decltype(auto) operator()(std::array<int, dim> pos) {
        // check indexes and compute original index
        size_t index;
        for (int i = 0; i < dim; ++i) {
            assert(0 <= pos[i] && pos[i] < _sizes[i]);
            index = (i == 0) ? pos[i] : (index * _sizes[i] + pos[i]);
        }
        return std::vector<T>::at(index);
    }

    template<class ... Types>
    decltype(auto) at(Types ... args) {
        std::array<int, dim> pos = { args ... };
        return (*this)(pos);
    }

    int size(int d) const {
        return _sizes[d];
    }


    class Iterator {
    public:
        T& operator*() const;
        T* operator->() const;
        bool operator!=(const Iterator& other) const {
            if (&_vec != &other._vec)
                return true;
            for (int i = 0; i < dim; ++i)
                if (_pos[i] != other._pos[i])
                    return true;
            return false;
        }
        int get_dim(int d) const {
            assert(0 <= d && d < dim);
            return _pos[d];
        }
        void add_dim(int d, int value = 1) {
            assert(0 <= d && d < dim);
            _pos[d] += value;
            assert(0 <= _pos[i] && _pos[i] < _vec._sizes[i]);
        }
    private:
        DimVector &_vec;
        std::array<int, dim> _pos;
        Iterator(DimVector& vec, std::array<int, dim> pos) : _vec(vec), _pos(pos) { }
    };

    Iterator getIterator(int pos[dim]) {
        return Iterator(*this, pos);
    }

private:
    std::array<int, dim> _sizes;
};

template<typename T, int dim>
inline T& DimVector<T, dim>::Iterator::operator*() const {
    return _vec(_pos);
}

template<typename T, int dim>
inline T* DimVector<T, dim>::Iterator::operator->() const {
    return &_vec(_pos);
}

using namespace std;

int main() {

    DimVector<int, 4> v;
    v.resize(1, 2, 3, 4);
    v.at(0, 0, 0, 1) = 1;
    v.at(0, 1, 0, 0) = 1;

    for (int w = 0; w < v.size(0); ++w) {
        for (int z = 0; z < v.size(1); ++z) {
            for (int y = 0; y < v.size(2); ++y) {
                for (int x = 0; x < v.size(3); ++x) {
                    cout << v.at(w, z, y, x) << ' ';
                }
                cout << endl;
            }
            cout << "----------------------------------" << endl;
        }
        cout << "==================================" << endl;
    }
    return 0;
}

TODO list:

• optimize: use T const& when possible
• optimizate iterator: precompute realindex and then just change that realindex
• implement const accessors
• implement ConstIterator
• implement operator>> and operator<< to serialize DimVector to/from file