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

Question

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

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

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

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

Answer 1

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

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

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

Answer 2

Применяя 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 нового в C++ 11. В более раннем коде вы, вероятно, увидите эквивалент &(buffer.at(0)) или &(buffer[0]), который возвращает адрес первого элемента.

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

Answer 3

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

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

Answer 4

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

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

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

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

Answer 5

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

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

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