Std :: copy обрабатывает перекрывающиеся диапазоны?

Question

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

Я предполагаю, что std::copy работает как memcpy, поскольку не учитывает перекрытия между областями источника и назначения. Если вы попытаетесь сместить объекты «вниз» в std::vector с помощью std::copy, вы повредите данные. Есть ли аналог алгоритма STL memmove для обработки подобных ситуаций? Или я должен свернуть свой собственный с обратными итераторами?

Answer 1

Он не обрабатывает перекрывающиеся диапазоны, если начало выходного диапазона перекрывается с входным диапазоном.

К счастью, вы можете использовать std::copy_backward вместо этого (что требует, чтобы вы не перекрывали end диапазона вывода с диапазоном ввода) .

Answer 2

Предварительные условия для std::copy, запрещает перекрытие:

• Прототип

  template <class InputIterator, class OutputIterator>
  OutputIterator copy(InputIterator first, InputIterator last,
                      OutputIterator result);
  

• Предпосылки

  • [first, last) - допустимый диапазон.
  • Результат не является итератором в диапазоне [first, last).
  • Достаточно места для размещения всех копируемых элементов. Больше формально требование состоит в том, чтобы [result, result + (last - first)) является допустимый диапазон. [1]

Answer 3

C ++ 17 стандартная тяга

Стандартный черновик C ++ 17 n4659 *1006* говорит:

28.6.1 «Копировать»:

template<class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last,
                    OutputIterator result);

1 Требуется: результат не должен находиться в диапазоне [первый, последний).

2 Эффекты: копирует элементы в диапазоне [первый, последний) в диапазон [результат, результат + (последний - первый)) начиная с первого и заканчивая последним.

и

template<class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2
copy_backward(
    BidirectionalIterator1 first,
    BidirectionalIterator1 last,
    BidirectionalIterator2 result);

17 Требуется: результат не должен быть в диапазоне (первый, последний).

18 Эффекты: копирует элементы из диапазона [first, last) в диапазон [result - (last-first), результат) начиная с последнего - 1 и переходя к первому. (263) Для каждого натурального числа n <= (последний - первый), выполняет * (результат - n) = * (последний - n). </p>

В примечании объясняется, когда использовать copy_backward:

263) copy_backward следует использовать вместо copy, когда последний находится в диапазоне [результат - (последний - первый), результат)

Следовательно, для этих функций не требуется никаких перекрытий, и в отличие от memcpy, поведение перекрытий четко определено в разделах Effects.

Вы просто выбираете между ними, потому что вы обычно хотите std::copy для копирования влево и std::copy_backward для копирования влево.

C ++ также имеет ранжированную версию std::move в <algorithm>, которая перемещается вместо копирования.

Answer 4

Кажется, самый простой способ - создать временный вектор диапазона, который вы хотите скопировать:

std::vector copiedRange( srcVecIterBegin, srcVecIterEnd);
std::copy( copiedRange.begin(), copiedRange.end(), srcVecIterCopyLocIter);

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