Replace vector of vector with flat memory structure

Question

I have the following type:

std::vector<std::vector<int>> indicies

where the size of the inner vector is always 2. The problem is, that vectors are non-contiguous in memory. I would like to replace the inner vector with something contiguous so that I can cast the flattened array:

int *array_a = (int *) &(a[0][0])

It would be nice if the new type has the [] operator, so that I don't have to change the whole code. (I could also implement it myself if necessary). My ideas are either:

std::vector<std::array<int, 2>>

or

std::vector<std::pair<int, int>>

How do these look in memory? I wrote a small test:

#include <iostream>
#include <array>
#include <vector>
int main(int argc, char *argv[])
{
    using namespace std;

    vector<array<int, 2>> a(100);

    cout << sizeof(array<int, 2>) << endl;

    for(auto i = 0; i < 10; i++){
        for(auto j = 0; j < 2; j++){
            cout << "a[" << i << "][" << j << "] " 
                <<&(a[i][j]) << endl;
        }
    }
    return 0;
}

which results in:

8
a[0][0] 0x1b72c20
a[0][1] 0x1b72c24
a[1][0] 0x1b72c28
a[1][1] 0x1b72c2c
a[2][0] 0x1b72c30
a[2][1] 0x1b72c34
a[3][0] 0x1b72c38
a[3][1] 0x1b72c3c
a[4][0] 0x1b72c40
a[4][1] 0x1b72c44
a[5][0] 0x1b72c48
a[5][1] 0x1b72c4c
a[6][0] 0x1b72c50
a[6][1] 0x1b72c54
a[7][0] 0x1b72c58
a[7][1] 0x1b72c5c
a[8][0] 0x1b72c60
a[8][1] 0x1b72c64
a[9][0] 0x1b72c68
a[9][1] 0x1b72c6c

It seems to work in this case. Is this behavior in the standard or just a lucky coincidence? Is there a better way to do this?

Answer 1

An array<int,2> is going to be a struct containing an array int[2]; the standard does not directly mandate it, but there really is no other sane and practical way to do it.

See 23.3.7 [array] within the standard. There is nothing in the standard I can find that requires sizeof(std::array<char, 10>)==1024 to be false. It would be a ridiculous QOI (quality of implementation); every implementation I have seen has sizeof(std::array<T,N>) == N*sizeof(T), and anything else I would consider hostile.

Arrays must be contiguous containers which are aggregates that can be initialized by up to N arguments of types convertible to T.

The standard permits padding after such an array. I am aware of 0 compilers who insert such padding.

A buffer of contiguous std::array<int,2> is not guaranteed to be safely accessed as a flat buffer of int. In fact, aliasing rules almost certainly ban such access as undefined behaviour. You cannot even do this with a int[3][7]! See this SO question and answer, and here, and here.

Most compilers will make what you describe work, but the optimizer might decide that access through an int* and through the array<int,2>* cannot access the same memory, and generate insane results. It does not seem worth it.

A standards compliant approach would be to write an array view type (that takes two pointers and forms an iterable range with [] overloaded). Then write a 2d view of a flat buffer, with the lower dimension either a runtime or compile time value. Its [] would then return an array view.

There is going to be code in boost and other "standard extension" libraries to do this for you.

Merge the 2d view with a type owning a vector, and you get your 2d vector.

The only behaviour difference is that when the old vector of vector code copies the lower dimension (like auto inner=outer[i]) it copies data, afer it will instead create a view.

Answer 2

Is there a better way to do this?

I recently finished yet-another-version of Game-of-Life.

The game board is 2d, and yes, the vector of vectors has wasted space in it.

In my recent effort I chose to try a 1d vector for the 2d game board.

typedef std::vector<Cell_t*>  GameBoard_t;

Then I created a simple indexing function, for when use of row/col added to the code's readability:

inline size_t gbIndx(int row, int col)
  { return ((row * MAXCOL) + col); }

Example: accessing row 27, col 33:

Cell_t* cell = gameBoard[ gbIndx(27, 33) ];

All the Cell_t* in gameBoard are now packed back to back (definition of vector) and trivial to access (initialize, display, etc) in row/col order using gbIndx().

---

In addition, I could use the simple index for various efforts:

void setAliveRandom(const GameBoard_t& gameBoard)
{
   GameBoard_t  myVec(m_gameBoard); // copy cell vector

   time_t seed = std::chrono::system_clock::
        now().time_since_epoch().count();

   // randomize copy's element order
   std::shuffle (myVec.begin(), myVec.end(), std::default_random_engine(seed));

   int count = 0;
   for ( auto it : myVec )
   {  
      if (count & 1)  it->setAlive(); // touch odd elements
      count += 1;
   }
}

I was surprised by how often I did not need row/col indexing.