Skip to main content

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

10
  • 5
    @Noein, I sort of sketched a solution without prescribing a particular one. More detail might look like: class Matrix { int* array; int m_width; public: Matrix( int w, int h ) : m_width( w ), array( new int[ w * h ] ) {} ~Matrix() { delete[] array; } int at( int x, int y ) const { return array[ index( x, y ) ]; } protected: int index( int x, int y ) const { return x + m_width * y; } }; If you straighten out that code it might make sense, and might shed light on the answer above.
    – Jeff Wofford
    Commented May 26, 2015 at 19:51
  • 4
    I like this solution a lot, is it applicable to 3 dimensions array too ? I'm thinking something like this : (x + m_width * y) + (m_width * m_height * z)
    – Ulrar
    Commented Nov 26, 2016 at 20:57
  • 6
    The major problem with this solution is that there is extra computation for every index. It becomes worse if you put the index calculation in a function which adds extra overhead. At least, consider using macros or inline functions to reduce overhead. An example macro for C++: #define ROW_COL_TO_INDEX(row, col, num_cols) (row*num_cols + col) Then you can use it as int COLS = 4; A[ ROW_COL_TO_INDEX(r, c, COLS) ] = 75; The overhead really affects when we do matrix multiplications which are of complexity O(n^3) or O(n^2.81) for Strassen's algorithm.
    – Ash Ketchum
    Commented Apr 27, 2017 at 16:49
  • 8
    @AshKetchum Inlining (or maybe macro substitution) makes sense to optimize, but how is the compiled computation more complex than what needs to be done to resolve the address of a[x][y] ?
    – Dronz
    Commented May 26, 2018 at 4:22
  • 8
    @Dronz With a[x][y], what you are actually doing is *(*(a + x) + y): two additions and two memory fetches. With a[index(x, y)], what you are actually doing is *(a + x + w*y): two additions, one multiplication, and one memory fetch. The latter is often preferable, for the reasons exposed in this answer (i.e., trading the extra memory fetch with a multiplication is worth it, especially because the data isn't fragmented and therefore you don't cache-miss).
    – Boris Dalstein
    Commented Feb 3, 2020 at 11:54