std :: vector of std :: vectors смежность

Я знаю, что std::vector<T> внутренне хранит данные непрерывно (если это не std::vector<bool>) как в старом C++03 стандарте, так и в новом C++11.

Хорошие вопросы о stackoverflow, которые касаются этого и цитируют стандарт: ответ, ответ.

А как насчет данных внутри вложенных векторов std::vector <std::vector <T> >? Как это хранится?

Если каждый внутренний вектор должен хранить свои данные непрерывно, как это может быть правдой, что &v[n] == &v[0] + n for all 0 <= n < v.size().

Выражаясь несколько иначе, можно ли получить доступ к всем элементам, хранящимся в такой вложенной структуре, «просто» и последовательно (с помощью указателя или подобного) так же, как это можно сделать для одномерного вектор?


c++ vector stdvector
person penelope    schedule 05.06.2012    source источник
comment
хранить данные непрерывно и хранить данные внутри - это не одно и то же.   -  person Mooing Duck    schedule 28.12.2020

Ответы (4)


arrow_upward
30
arrow_downward

Нет. Элементы vector хранятся в динамически выделяемом блоке памяти; в противном случае емкость vector не могла бы увеличиться. Объект vector просто содержит указатель на этот блок.

Требование, чтобы элементы хранились последовательно, применяется только к самим элементам, а не к каким-либо динамически выделяемым членам этих элементов.

person Ernest Friedman-Hill    schedule 05.06.2012

arrow_upward
8
arrow_downward

Чтобы ответить на ваш последний вопрос: Нет. Элементы вектора векторов не хранятся непрерывно.

Рассмотрим следующий код:

std::vector<std::vector<int> > vv;
.... fill in v[0], v[1], v[2], etc
std::vector <int> & v = vv[1];
v.push_back (23);

Если бы они все хранились непрерывно, то это привело бы к перемещению каждого элемента в vv [2], vv [3] и т. Д. Как это могло бы сработать, если вы воздействуете только на один вектор 'v'?

person Marshall Clow    schedule 05.06.2012
comment
Я не имел смысла, чтобы это работало. С другой стороны, требование непрерывности сбивало меня с толку в комбинации. - person penelope; 05.06.2012

arrow_upward
5
arrow_downward

std::vector< std::vector<T> > - это вектор объектов, которые хранятся в непрерывном блоке памяти. Однако тот факт, что эти объекты тоже являются векторами, не имеет значения.

Хотя элементы вектора хранятся в непрерывном блоке памяти, память, в которой находятся элементы, не является частью самого векторного объекта.

"можно ли получить доступ ко всем элементам, хранящимся в такой вложенной структуре" просто "и последовательно (с помощью указателя или подобного), так же, как это можно сделать для одномерного вектора?"
Для доступа к элементам std::vector лучше использовать метод operator[] или at(), чем получение адреса первого элемента и использование арифметики указателя. Для многомерных массивов, представленных в виде вектора векторов, я предлагаю вам остановиться на operator[], который прост в использовании и легко читается: myVector[i][j]. Также стоит увидеть vector :: at и vector :: operator [] :)

person LihO    schedule 05.06.2012

arrow_upward
3
arrow_downward

возможно ли получить доступ ко всем элементам, хранящимся в такой вложенной структуре, «просто» и последовательно (через указатель или что-то подобное) так же, как это можно сделать для одномерного вектора?

Да, если:

  • вам нужно только добавить что-то в конец вашего вектора векторов, и

  • вы хотите заменить вектор векторной конструкции на пользовательскую структуру данных

Что вы можете сделать, так это объединить все эти субвекторы в один непрерывный буфер с другим индексным буфером, используемым для доступа к нему по индексу входа верхнего уровня.

См. мою статью здесь для более подробного обсуждения этого, а также пример «свернутого вектора. реализация класса vector ..

person Thomas Young    schedule 26.11.2013