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.

Answer 3

As far as I know, std::vector are contiguous in memory. Take a look at this questions:

Why is std::vector contiguous?,

Are std::vector elements guaranteed to be contiguous?

In case you have to resize an inner vector, you wouldn't have the whole structure contiguous, but the inner vectors would still be it. If you use a vector of vectors, though, you'd have a fully contiguous structure (and I edit here, sorry I misunderstood your question) meaning that the pointers that point to your inner vectors will also be contiguous.

If you want to implement a structure that is always contiguous, from the first element of the first vector to the last element of the last vector, you can implement it as a custom class that has a vector<int> and elems_per_vector that indicates the number of elements in each inner vector.

Then, you can overload the operator(), so to access to a(i,j) you are actually accessing a.vector[a.elems_per_vector*i+j]. To insert new elements, though, and in order to keep the inner vectors at constant size between them, you'll have to make as many inserts as inner vectors you have.