Заменить вектор вектора с плоской структурой памяти

У меня есть следующий тип:

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

где размер внутреннего вектора всегда равен 2. Задача состоит в том, что векторы несмежные в памяти. Я хотел бы заменить внутренний вектор на нечто смежное, чтобы я мог спрятать сплющенный массив:

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

Было бы неплохо, если новый тип имеет оператор [], так что мне не нужно менять весь код. (Я мог бы сам реализовать его, если это необходимо). Мои идеи:

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

или

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

Как они выглядят в памяти? Я написал небольшой тест:

#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;
}

что приводит к:

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

В этом случае он работает. Это поведение в стандарте или просто удачное совпадение? Есть ли лучший способ сделать это?

Ответ 1

An array<int,2> будет структурой, содержащей массив int[2]; стандарт не дает прямого мандата, но на самом деле нет другого разумного и практичного способа сделать это.

См. 23.3.7 [массив] в стандарте. В стандарте, который я могу найти, нет ничего, что требует, чтобы sizeof(std::array<char, 10>)==1024 был ложным. Это было бы смехотворным QOI (качество реализации); каждая реализация, которую я видел, имеет sizeof(std::array<T,N>) == N*sizeof(T), и все остальное я считаю враждебным.

Массивы должны быть смежными контейнерами, которые являются агрегатами, которые могут быть инициализированы до N аргументов типов, конвертируемых в T.

Стандарт допускает заполнение после такого массива. Я знаю 0 компиляторов, которые вставляют такие дополнения.

Буфер смежных std::array<int,2> не гарантируется безопасным доступом в виде плоского буфера int. На самом деле правила псевдонимов почти наверняка запрещают такой доступ, как поведение undefined. Вы даже не можете сделать это с помощью int[3][7]! Смотрите этот вопрос и ответ, и здесь, и здесь.

Большинство компиляторов сделают то, что вы описываете, но оптимизатор может решить, что доступ через int* и через array<int,2>* не может получить доступ к одной и той же памяти и генерировать безумные результаты. Это не похоже на это.

Подходом, совместимым со стандартами, было бы написать тип вида массива (который принимает два указателя и формирует итерируемый диапазон с перегрузкой []). Затем напишите 2d-представление плоского буфера, нижний размер которого будет либо временем выполнения, либо значением времени компиляции. Его [] затем вернет представление массива.

В boost и других библиотеках стандартного расширения будет использоваться код для этого.

Объедините представление 2d с типом, которым владеет вектор, и вы получите свой 2d-вектор.

Единственное различие в поведении заключается в том, что когда старый вектор векторного кода копирует нижнее измерение (например, auto inner=outer[i]), он копирует данные, а вместо этого создает представление.

Ответ 2

Есть ли лучший способ сделать это?

Недавно я закончил еще одну версию Game-of-Life.

Игровая доска 2d, и да, вектор векторов потерял пространство в ней.

В моих недавних усилиях я решил попробовать 1-й вектор для 2-й игровой платы.

typedef std::vector<Cell_t*>  GameBoard_t;

Затем я создал простую функцию индексирования, поскольку при добавлении строки/столбца к читаемости кода:

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

Пример: доступ к строке 27, col 33:

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

Все Cell_t * в gameBoard теперь упакованы обратно назад (определение вектора) и тривиальны для доступа (инициализировать, отображать и т.д.) в порядке строки /col, используя gbIndx().

Кроме того, я мог бы использовать простой индекс для различных усилий:

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 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;
   }
}

Я был удивлен тем, как часто мне не нужно индексировать строку/кол.

Ответ 3

Насколько я знаю, std::vector смежны в памяти. Взгляните на эти вопросы:

Почему std::vector смежный?,

Являются ли элементы std::vector неотличимыми?

Если вам нужно изменить размер внутреннего вектора, у вас не будет цельной структуры, но внутренние векторы все равно будут. Если вы используете вектор векторов, тем не менее, у вас будет полностью смежная структура (и я редактирую здесь, извините, что неправильно понял ваш вопрос), что означает, что указатели, указывающие на ваши внутренние векторы, также будут смежными.

Если вы хотите реализовать структуру, которая всегда смежна, от первого элемента первого вектора до последнего элемента последнего вектора, вы можете реализовать его как пользовательский класс с vector<int> и elems_per_vector что указывает количество элементов в каждом внутреннем векторе.

Затем вы можете перегрузить operator(), поэтому для доступа к a(i,j) вы фактически обращаетесь к a.vector[a.elems_per_vector*i+j]. Однако, чтобы вставлять новые элементы и поддерживать постоянный размер внутренних векторов между ними, вам нужно будет сделать столько вложений, сколько у вас есть внутренние векторы.