Почему вектор вектора не может быть смежным? (или это?)

Question

Я знаю, что std::vector элементы гарантированы непрерывными в памяти.

Итак, почему вы не можете ожидать, что вектор, содержащий другие векторы, будет иметь общую совокупность?

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

Но, по-видимому, есть некоторые разногласия по этому вопросу относительно того, действительно ли это так. Можно ли надежно полагаться на это или нет? Некоторым людям кажется go out of their way для достижения этого, хотя я думаю, что это гарантировано.

Answer 1

Каждый из ваших векторов внутри вектора векторов является индивидуальным объектом и как таковой несет ответственность за его хранение. Итак, нет, отнюдь не гарантировано быть смежным, на самом деле я не могу увидеть ситуацию, когда может случиться так, что данные, хранящиеся во внешнем векторе, и его внутренние векторы - это один непрерывный блок памяти.

Answer 2

Вектор - это объект, содержащий указатель на фактический массив.

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

Answer 3

Давайте посмотрим на (логический) раскладке памяти вектора:

[size:4/8 bytes] 
[capacity:4/8 bytes] 
[other datamembers:n bytes] 
*[elements:size*sizeof(element) bytes] << one contiguous memory (pointer to heap) 

С вектором векторов выглядит следующим образом:

[size:4/8 bytes] 
[capacity:4/8 bytes] 
[other datamembers:n bytes] 
* [ 
    [Vector:0] 
     [size:4/8 bytes] 
     [capacity:4/8 bytes] 
     [other datamembers:n bytes] 
     *[elements:size*sizeof(element) bytes] << pointer to contiguous memory for elements 
    [Vector:1] 
     [size:4/8 bytes] 
     [capacity:4/8 bytes] 
     [other datamembers:n bytes] 
     *[elements:size*sizeof(element) bytes] 
    [Vector:2] 
     [size:4/8 bytes] 
     [capacity:4/8 bytes] 
     [other datamembers:n bytes] 
     *[elements:size*sizeof(element) bytes] 
    ... 
    ... 
] << contiguous memory of vectors 

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

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

В зависимости от вашего прецедента вы можете использовать универсальный блок памяти памяти для вектора вектора или просто сделать это старым способом ручного распределения и освобождения одного непрерывного блока памяти.

Answer 4

Проблема заключается в том, что векторный шаблон не содержит данных, которые он обрабатывает «inline» или напрямую. Другой способ сказать, что векторный класс блокирует массив данных, который он удерживает: класс vector содержит указатель на область памяти, содержащую массив элементов. Это структурно эквивалентно: (. Т.е. constexpr)

template <typename T> 
struct vector_eq { 
    T *ptr; 
}; 

и не

template <typename T> 
struct vector_neq { 
    T arr[SIZE]; 
}; 

, который потребует SIZE быть известно во время компиляции, для arr элементов, которые будут включены в структурах.

Я представляю Тары должно быть возможностью специализироваться vector<vector<T>> содержать указатель на один блок памяти, и имеют свои методы возвращают СПЕЦИАЛЬНУЮ экземпляры vector<T> совместных ломтиков этого блока памяти, хотя логика позади него, вероятно, будет немного волосатый.

Answer 5

Проще говоря - std :: vector гарантирует, что элементы хранятся смежно. Но это включает только элементы данных элемента, в случае вектора, который будет его размером, емкостью и т. Д., А также указателем на фактические векторные данные.

Итак, вектор векторов даст вам смежный вектор векторов, но эти векторы будут иметь свои данные, динамически распределенные по произвольным адресам памяти.

Поскольку размер объекта должен быть известен во время компиляции, вы не можете иметь объекты с разным размером, единственный способ сделать это - использовать распределение динамической памяти. Если у вас есть пользовательский вектор фиксированного размера, который не использует динамическое распределение памяти внутри, то std::vector<customVector> будет хранить пользовательские векторы смежно, но у вас все еще будут дополнительные вспомогательные элементы, которые «прервут» фактическую смежность данных элемента customVector.

Answer 6

Я думаю, что самый правильный формальный способ ответа на это (в отличие от описания существующих реализаций) основан на §23.3.6.1/1:

[...] Элементы вектора сохраняются смежно, а это означает, что если v является vector<T, Allocator> где T некоторый тип кроме BOOL, то он подчиняется тождественность

&v[n] == &v[0] + n 

для всех 0 <= n < v.size().

Обратите внимание, что это говорит об адресах &v[i] отдельных элементов вектора и следует, в частности, что каждый элемент вектора имеет постоянный размер sizeof(T) (потому что это как указатель арифметика работает).

Это означает, что элементы вектора не могут изменять размер во время выполнения. Если vector<vector<T>> был реализован как один непрерывный блок памяти, членам внешнего вектора, являющимся самими векторами, будет разрешено изменять размер.

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