std :: вектор смежный смысл

Question

Я читал во многих местах, таких как here, что std::vector всегда соприкасается, но я не нашел объяснения смысла этого или почему это важно?

Означает ли это, что у них есть фиксированное место в памяти или что?

Answer 1

Смежный в этом контексте означает, что последовательно пронумерованные элементы вектора расположены рядом друг с другом в пространстве памяти. Например, если элемент i расположен по адресу a и имеет размер s, то элемент i+1 будет расположен по адресу a+s, элемент i+2 будет находиться в a+s+s и так далее.

Это важен по двум причинам:

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

Answer 2

Элементы в std::vector занимают непрерывный блок памяти. A std::vector - улучшенный массив.

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

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

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

Answer 3

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

Answer 4

Как ни один из ответов не упомянул:

Благодаря этой особенности std::vector вы можете сделать такие вещи, как

std::ifstream file("file.txt", std::ios::ate | std::ios::binary); 
std::vector<char> vec; 
if (!file) 
{ 
    file.seekg(0, std::ios_base::end); 
    auto fileSize = file.tellg(); 
    vec.resize(fileSize); 

    file.seekg(0, std::ios_base::beg); 

    // here we leverage contiguous memory in std::vector 
    file.read(&vec[0], fileSize); 
} 

где вы избежите чтения/записи поэлементно.

Это может быть использовано, так как C++, 03, как указано в (C++ 03) стандарт (23.2.4.1)

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

Answer 5

Это означает, что в представлении внутренней памяти std::vector нет отверстий. Похоже, что это в памяти:

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

Большинство других контейнеров не соприкасаются. Например, std::forward_list выглядит в памяти:

Здесь, опять же, оранжевые адреса содержат элементы контейнера. Но они разбросаны по памяти. Есть также серые элементы; они представляют дополнительную память, необходимую списку, чтобы каждый элемент знал, где находится следующий элемент. ^[*]

Как вы можете себе представить, четкое и сжатое представление памяти std::vector дает вам много преимуществ. Это объясняет, почему std::vector имеет некоторые операции с другими контейнерами, или почему эти операции выполняются в постоянное время. Например, чтобы перейти к n-му элементу, вы просто выполните одно добавление (базовый адрес + n). Это также объясняет, почему вы можете спокойно принять &v[0] и выполнить на нем указательную арифметику.

---

^{[*] Это немного упрощения, потому что пример есть char элементов, но указатели в списке занимают больше памяти, чем отдельные char с на типичных реализациях C++. Более реалистичная диаграмма будет использовать 4 или 8 серых квадратов для каждого элемента, потому что это размер одного указателя на типичных современных машинах.}