Contiguous matrix with double subscript operator [][] in c++

Question

I'm trying to implement a simple Matrix struct that allows me to access it with double subscript operator and have the guarantee that the underlying elements are stored contiguously into memory.

Until now I was using std::array<std::array<float, 4>, 4> matrix. But as far as I understood there is no real guarantee that the elements will be stored contiguously.

So I came up with something like this:

struct RawMatrix4 {
    float m[16] = { 0.0f, 0.0f, 0.0f, 0.0f, 
                    0.0f, 0.0f, 0.0f, 0.0f, 
                    0.0f, 0.0f, 0.0f, 0.0f, 
                    0.0f, 0.0f, 0.0f, 0.0f };

    struct Row { 
        float *m;
        int rowIdx4;

        const float &operator[](int j) const { return (*this)[j]; }
        float &operator[](int j) {
            assert(j >= 0 && j < 4);
            return m[rowIdx4 + j];
        }
    };

    const Row operator[](int i) const { return (*this)[i]; }
    Row operator[](int i) {
        assert(i >= 0 && i < 4);
        return Row{m, i * 4};
    }
};

This allows me to create a RawMatrix4 m; and then access the elements like this m[0][0]. And since the underlying structure is an array of 16 elements I have the guarantee that the elements are stored contiguously in memory.

However I'm not sure this is the best way to do this, and I wanted to ask your opinion if there is a better and more efficient way to achieve this. Also, I have some segmentation fault in my code, that I cannot really figure out. I would appreciate any help. Here is a minimal example, using the code above, that doesn't work: https://godbolt.org/z/nKoo6e6ro.

I tend to use `float& operator()(size_t i, size_t j)` and `float const& operator()(size_t i, size_t j) const`, rather than `operator[]` — Eljay, Aug 07 '22 at 12:26
`const Row operator[](int i) const { return (*this)[i]; }` isn't this endless recursive loop? — KamilCuk, Aug 07 '22 at 12:29
I mean you could just use `float* operator[](size_t rowIndex) { return m + 4 * rowIndex; } float const* operator[](size_t rowIndex) const { return m + 4 * rowIndex; }`, if you're willing to give up on the assertions... — fabian, Aug 07 '22 at 12:38
@fabian I like the simple solution, but unfortunately it would not be sage enough, since you could do something like this m[0][4] and would have undefined behaviour — DevX10, Aug 07 '22 at 12:50
@Eljay yes, this was my first thought too, but since I was using the initial solution I mentioned I have a big codebase that uses the subscript operator to access elements. This would mean refactoring the whole codebase to use m(i,j). Which is not too bad, but I was interested to see if there is a good solution with the subscript operator (edit: to correct m(i, j)) — DevX10, Aug 07 '22 at 12:52
`Row` doesn't need to store a pointer and an index: just the pointer to the first element of that row (that is, `&m[i * 4]`) is enough. — Igor Tandetnik, Aug 07 '22 at 13:37
The segmentation fault is in fact a stack overflow: `const` versions of your `operator[]` call themselves recursively. `m.matrix[3][3]` works because `m` is not `const`. `m.ToString()` fails because `toString` is declared `const`, and so inside it `*this` is `const`. — Igor Tandetnik, Aug 07 '22 at 13:38
@IgorTandetnik how would you implement the const version? The field in Row is not const, so I'm not sure how I could do this — DevX10, Aug 07 '22 at 13:52
You could have another class, `ConstRow`; or make `Row` a template and have the operators return `Row` vs `Row`. The standard library does something similar with e.g. `std::vector::iterator` vs `std::vector::const_iterator` — Igor Tandetnik, Aug 07 '22 at 13:57
Thanks for the answer. I will provide an answer to the question to show the template version. — DevX10, Aug 07 '22 at 14:16
Starting in C++17, `std:array` must allocate elements in contiguous memory. — Raymond Chen, Aug 07 '22 at 15:45
*"I understood there is no real guarantee that the elements will be stored contiguously."* -- are you sure you're not confusing `std::array` with `std::vector`? — JaMiT, Aug 07 '22 at 17:43
I was referring to this @JaMiT: https://stackoverflow.com/questions/47120994/does-stdarray-of-stdarray-have-contiguous-memory. — DevX10, Aug 08 '22 at 22:36
@RaymondChen The problem is that the standard does not specify that `std::array` does not have any additional members or padding. So an array of array doesn't have to be contiguous. — Goswin von Brederlow, Aug 09 '22 at 06:46
I would just use an array or arrays with a static_assert that the size of the array matches the size of the data. I find it highly unlikely that `std::array` does have some padding or extra member so I would ignore that case until you get it. — Goswin von Brederlow, Aug 09 '22 at 06:48
@DevX10 Oh, you're worried about a little padding? Minor, but I guess it could be an issue when operating under tight constraints. It's a much smaller issue than when dealing with a vector-of-vectors, where each inner vector's data could be in a different memory page than the others'. The array-of-arrays at least maintains the performance of memory locality, even if it might waste a few bytes per row with padding. (I'd expect no padding in your example because 4 elements x 4 bytes per element gives a multiple of 8. Then again, it is just an example.) — JaMiT, Aug 10 '22 at 04:24

score 0 · Answer 1 · answered Aug 07 '22 at 14:21

Thanks to the comments I fixed the recursive call:

struct RawMatrix4 {
    float m[16] = { 0.0f, 0.0f, 0.0f, 0.0f, 
                    0.0f, 0.0f, 0.0f, 0.0f, 
                    0.0f, 0.0f, 0.0f, 0.0f, 
                    0.0f, 0.0f, 0.0f, 0.0f };

    template<typename T>
    struct Row { 
        T *m;

        const float &operator[](int j) const { 
            assert(j >= 0 && j < 4);
            return m[j];
        }
        float &operator[](int j) {
            assert(j >= 0 && j < 4);
            return m[j];
        }
    };

    const Row<const float> operator[](int i) const { 
        assert(i >= 0 && i < 4);
        return Row<const float>{&m[i * 4]};
    }
    Row<float> operator[](int i) {
        assert(i >= 0 && i < 4);
        return Row<float>{&m[i * 4]};
    }
};

However, as suggested in the comments, It might be easier to overload float& operator()(size_t i, size_t j) and float const& operator()(size_t i, size_t j) const, if you're starting a new project.

This does not really answer the question, since the question is not about the recursive call. It probably should have been, but it's not. Maybe you could convince yourself to fix up the question to what it should be so that this answer matches? — JaMiT, Aug 07 '22 at 17:45

Contiguous matrix with double subscript operator [][] in c++

1 Answers1