Быстрый способ «резервного копирования» (копирования) большого вектора STL пользовательских объектов

Question

Я использую вектор STL для хранения большого (~ 10 ^ 6) числа пользовательских объектов (sizeof () дает 368 байт для одного из этих объектов). Структура моей программы требует от меня частого создания резервных копий этого вектора, поскольку изменения, внесенные на определенном этапе, возможно, придется развернуть при определенных условиях. Примерно это выглядит как

std::vector<myClass> vecA( largeNumber );
std::vector<myClass> vecB;

do
{
  vecB = vecA;

  //do lots of stuff to vecA

  if ( restoreBackup ) { vecA = vecB; }

} while (someCondition)

Выполняя какое-то профилирование, операция копирования vecB = vecA на самом деле является существенной проблемой. Мне действительно нужно ускорить эту часть. Какие стратегии вы бы предложили?

Примечания:

• По некоторым причинам я хотел бы сохранить векторную структуру STL.
• Я знаю, что в большинстве случаев обновляется только небольшая часть элементов в vecA. Таким образом, я мог бы попытаться сохранить дополнительный список этих элементов, а затем копировать эти элементы только туда-сюда, перебирая этот список. Будет ли это адекватной стратегией?
• Вопрос, безусловно, связан с этим вопросом , однако предложенные там решения на самом деле не помогают.

Answer 1

Хм, это не тривиальная вещь, и я не думаю, что вы можете избежать этого копирования, если вам действительно нужно использовать только (и один) std::vector.

Лучшим решением будет использование Персистентная структура данных .

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

Если вам нужна только предыдущая версия ..
Легкая вещь, которая приходит мне в голову и кажется, что она будет работать для вас, заключается в резервном копировании только элементов, которые вы измените. Вы можете использовать std::list (или std::vector) с std::pair< int, myClass >. Таким образом, first пары будет индексом элемента, который вы изменяете, а second - резервной версией. Итак, в конце концов, если вам нужно восстановить резервную копию, вам нужно просто пройти через этот контейнер и «вернуть» старые данные.

Ситуация с удалением / добавлением элементов будет более сложной, но не неразрешимой. Вам нужно будет иметь больше контейнеров - один для удаленных элементов, один для добавленных элементов, один для измененных элементов и один для последовательности изменений. Таким образом, это даст вам возможность выполнить «отмену» шагов.

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

Другая вещь, которая приходит мне в голову - вы могли бы сначала проверить размер контейнера. А если он маленький, сделайте целую копию Если он большой - выполните «выборочное резервное копирование» или как там это называется.

Обратите внимание, что это не лучшее решение (я полагаю), а просто идея, которая у меня появилась прямо сейчас (мне никогда не нужна была такая вещь)

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

Answer 2

Я знаю, что вы хотите сохранить существующий std :: vector.Но эта проблема звучит так, как будто она была создана для STM (программная транзакционная память). Возможно, стоит изучить.

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

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

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

Answer 3

Если myClass является POD, и если оба вектора уже имеют подходящий размер, вы можете использовать memcpy:

memcpy(&dstVec[0], &srcVec[0], sizeof(myClass)*srcVec.size());

Answer 4

Альтернативой советам Кирилла является создание полных копий, но swap (или перемещение) в фазе «восстановления резервной копии».

То есть, замените

if ( restoreBackup ) { vecA = vecB; }

с

if ( restoreBackup ) { std::swap(vecA, vecB); }

Тогда часть «восстановления резервной копии» становится практически бесплатной, и вам остается беспокоиться только о (полной) резервной копии.Конечно, это делает невозможной любую стратегию «частичного резервного копирования».

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