std :: vector и смежная память многомерных массивов

Question

Я знаю, что стандарт не заставляет std::vector выделять смежные блоки памяти, но, тем не менее, все реализации подчиняются этому.

Предположим, я хочу создать вектор многомерного статического массива. Для простоты рассмотрим 2 измерения и вектор длины N. То есть я хочу создать вектор с N элементами, скажем, int[5].

Могу ли я быть уверен, что все N * 5 целых чисел теперь непрерывны в памяти? Чтобы я в принципе мог получить доступ ко всем целым числам, просто зная адрес первого элемента? Зависит ли эта реализация?

Для справки, в настоящее время я создаю двумерный массив в непрерывном блоке памяти путем создания (динамического) массива с плавающей запятой * длины N, выделения всех N * 5 с плавающей запятой в одном массиве и последующего копирования адреса каждого 5-й элемент в первом массиве float*.

Answer 1

Стандарт требует , чтобы память std::vector была смежный. С другой стороны, если вы напишите что-то вроде:

std::vector<std::vector<double> > v;

Глобальная память (все v[i][j]) не будет смежной. Обычный способ создания двумерных массивов - использовать один

std::vector<double> v;

и рассчитайте индексы в точности так, как вы предлагаете сделать с float. (Вы также можете создать второй std::vector<float*> с адресами если ты хочешь. Однако я всегда только пересчитывал индексы.)

Answer 2

Элементы вектора гарантированно являются смежными согласно стандарту C ++.
Цитаты из стандарта следующие:

От n2798 (черновик C ++ 0x):

23.2.6 Вектор шаблона класса [вектор]

1 Вектор - это контейнер последовательности, который поддерживает итераторы произвольного доступа. Кроме того, он поддерживает (амортизируется) операции вставки и удаления с постоянным временем в конце; вставить и стереть в середине взять линейное время. Управление хранилищем осуществляется автоматически, хотя могут быть даны советы для повышения эффективности. Элементы вектора хранятся непрерывно, а это означает, что если v является вектором, где T - это какой-то тип, отличный от bool, то он подчиняется тождеству & v [n] == & v [0] + n для всех 0 <= n <v .size (). </em>

Стандарт C ++ 03 (23.2.4.1):

Элементы вектора хранятся смежно, что означает, что если v является вектором, где T является другим типом, отличным от bool, то он подчиняется тождеству & v [n] == & v [0] + n для всех 0 <= n <v.size (). </em>

Кроме того, смотрите здесь то, что взгляды Херба Саттера на то же самое.

Answer 3

Как уже указывал @Als, да, std::vector (сейчас) гарантирует непрерывное распределение.Однако я бы не имитировал бы двумерную матрицу с массивом указателей.Вместо этого я бы рекомендовал один из двух подходов.Более простым (на сегодняшний день) является использование operator() для подписки и умножение для преобразования двумерного ввода в линейный адрес в вашем векторе:

template <class T>
class matrix2D { 
     std::vector<T> data;
     int columns;
public:
     T &operator()(int x, int y) {
         return data[y * columns + x];
     }

     matrix2D(int x, int y) : data(x*y), columns(x) {}
};

Если по какой-либо причине выЕсли вы хотите использовать matrix[a][b] стиль адресации, вы можете использовать прокси-класс для обработки преобразования.Хотя это было для 3D матрицы вместо 2D, я опубликовал демонстрацию этой техники в предыдущем ответе .

Answer 4

Для справки, в настоящее время я создаю двумерный массив в непрерывном блоке памяти путем создания (динамического) массива с плавающей точкой * длины N, выделения всех N * 5 с плавающей точкой в ​​одном массиве, а затем копирования адреса каждого 5-й элемент в первом массиве с плавающей точкой *.

Это не двумерный массив, это массив указателей. Если вам нужен настоящий 2D массив, вот как это делается:

float (*p)[5] = new float[N][5];

p [0] [0] = 42;   // access first element
p[N-1][4] = 42;   // access last element

delete[] p;

Обратите внимание, что существует только одно распределение. Могу ли я предложить больше узнать о с использованием массивов в C ++ ?

Answer 5

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

template <class T> 2DArray {
private:
    T *m_data;
    int m_stride;
public:
    2DArray(int dimY, int dimX) : m_stride(dimX) : m_data(new[] T[dimX * dimY]) {}
    ~2DArray() { delete[] m_data; }
    T* operator[](int row) { return m_data + m_stride * row; }
}

Можно использовать это как:

2DArray<int> myArray(30,20);

for (int i = 0; i < 30; i++)
    for (int j = 0; j < 20; j++)
        myArray[i][j] = i + j;

Или даже передать &myArray[0][0] в качестве адреса низкоуровневым функциям, которые принимают некие «плоские буферы».

Но, как вы видите, это превращает наивные ожидания в то, что это myarray[y][x].

Как правило, если вы взаимодействуете с кодом, который требует какого-то классического плоского массива в стиле C, то почему бы просто не использовать это?

Редактировать: Как уже говорилось, выше просто .Никаких попыток проверки границ вообще.Прямо как «массив».

Answer 6

Под капотом вектор может выглядеть примерно так (p-код):

class vector<T> {
    T      *data;
    size_t  s;
};

Теперь, если вы сделаете vector<vector<T> >, будет макет, подобный этому

vector<vector<T>> --> data {
    vector<T>,
    vector<T>,
    vector<T>
};

или в «встроенной» форме

vector<vector<T>> --> data {
    {data0, s0},
    {data1, s1},
    {data2, s2}
};

Да, вектор-вектор использует непрерывную память, но нет, не так, как вам бы хотелось. Скорее всего, он хранит массив указателей (и некоторых других переменных) на внешние места.

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