Почему std::vector смежный?

Кроме того, что стандарт определяет, что он смежный, почему std::vector смежный?

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

Что, если это не было смежным? Когда хранилище заполняется, оно просто выделит новый блок и сохранит старый блок. При доступе через итератор он выполнял бы просто > , < проверяет, в каком блоке находится индекс и возвращает его. Таким образом, он не должен копировать массив каждый раз, когда он заканчивается.

Будет ли это действительно работать/быть лучше? или я что-то пропустил?

Ответ 1

Если std::vector не гарантировало смежности, был бы изобретен новый контейнер.

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

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

Ответ 2

Стандартная библиотека С++ также определяет непересекающийся контейнер, подобный массиву: std::deque<T>. Итерация над std::deque<T> намного медленнее, чем итерация по std::vector<T>. Если операция довольно тривиальная, это может быть примерно в 5 раз медленнее: это фактические времена, которые я получаю при сравнении накоплений последовательности целых чисел. Это стоимость, которую вы платите за несмежное представление!

Причиной этого довольно крутого замедления является то, что gcc знает, как векторизовать цикл по std::vector<int>, но не для std::deque<int>. Даже без векторизации итерация примерно на 30% медленнее. То есть довольно небольшая стоимость перераспределения std::vector<T> на самом деле не имеет большого значения!

Ответ 3

Есть несколько причин для этого:

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

Во-вторых, там написано много кода на С++, который должен взаимодействовать с C-кодом, и многие из этого кода ожидают непрерывное пространство памяти при приеме массива/буфера, поскольку эта реализация наименьшей структуры данных -зависимый способ сделать это. Когда вы взаимодействуете с кодом, который постоянно ожидает буферы/массивы, накладные расходы на преобразование вашего std::deque в массив берут свои потери по сравнению с практически мгновенным прохождением std::vector в массив (который может в основном просто давать указатель на внутренний массив).

Все это оправдывает существование непрерывного контейнера. Как говорили другие, когда вам не нужна либо быстрая итерация, либо смежность памяти, вы всегда можете использовать std::deque.

Ответ 4

Сделав std::vector смежным, его можно рассматривать как массив. Тем не менее, он также изменяется. Его размер определяется во время выполнения, а не времени компиляции. Кроме того, вектор может использоваться для выделения памяти для функций, для которых требуется буфер. Преимущество этого заключается в том, что память будет свободна от vector, когда она выходит за рамки. Например, при использовании ReadFile вектор может быть использован для создания буфера.:

unsigned int bytesRead = 0;
std::vector<char> buffer(fileSize);
// open file, etc.
ReadFile(hFileIn, buffer.data(), buffer.size(), &bytesRead, nullptr);

Обратите внимание, что data является новым в С++ 11. В более раннем коде вы, вероятно, увидите эквивалент &(buffer.at(0)) или &(buffer[0]), который возвращает адрес первого элемента.

A std::deque будет лучше соответствовать тому, что вы описываете.

Ответ 5

В дополнение к другим ответам (они достаточно полные), есть одна ситуация, когда вы предпочитаете, чтобы векторы не были смежными: когда вам нужно одновременно изменять размер вектора. Вот почему Intel Thread Building Block предоставляет tbb:: concurrent_vector, что более или менее то, что вы сказали, что вы ожидаете

"Когда хранилище заполнится, оно просто выделит новый блок и сохранит старый блок. При доступе через итератор он выполнил бы simple > , < check, чтобы увидеть, в каком блоке находится индекс, и вернуть его."

Затем сравнение между tbb:: concurrent_vector и std::vector даст вам лучшее представление о преимуществах (скорости) и недостатках (не может одновременно расти std::vector) непрерывной памяти. Я ожидаю, что tbb:: concurrent_vector будет лучше оптимизирован, чем std:: deque, и именно поэтому tbb:: concurrent_vector vs std::vector является более справедливым сравнением.