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

Question

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

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 

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

Answer 1

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. На самом деле правила псевдонимов почти наверняка запрещают такой доступ, как неопределенное поведение. Вы даже не можете сделать это с помощью int[3][7]! See this SO question and answer, and here, и here.

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

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

Будет создан код в boost и другие библиотеки «стандартного расширения», чтобы сделать это за вас.

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

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

Answer 2

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

Why is std::vector contiguous?,

Are std::vector elements guaranteed to be contiguous?

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

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

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

Answer 3

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

Я недавно закончил еще одну версию игры в жизни.

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

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

typedef std::vector<Cell_t*> GameBoard_t; 

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

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

Пример: доступ к строке 27, столбец 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'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; 
    } 
} 

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