Программируя на Си многие сталкивались с такими функциями как memcpy() и memmove(), по сути, функции делают одно и тоже, но вторая корректно отрабатывает ситуацию, когда области памяти перекрываются (на что появляются дополнительные накладные расходы).
В мире С++ никто не запрещает пользоваться этими функциями (часто эти функции используют различные механизмы оптимизации и могут статься быстрее своих собратьев из мира C++), но есть и более родное средство, работающее через итераторы: std::copy. Это средство применимо не только к POD типам, а к любым сущностям, поддерживающим итераторы. О деталях реализации в стандарте ничего не сказано, но можно предположить, что разработчики библиотеки не настолько глупы, что бы не использовать, оптимизированные memcpy()/memmove() когда это возможно.
Но по наитию, хочется посмотреть, а что там с пересекающимися областями (overlapping memory blocks)? Ведь задача, на самом деле, не такая уж редкая. К примеру, хотим мы читать MPEG-TS пакеты (размер каждого 188 байт, каждый пакет начинается с 0x47 /sync byte/) из какого-то потока, и есть вероятность, что первое (а может и последующее, либо имеем дело с M2TS контейнером, размер блока которого 192 байта и лишние 4 байта в большинстве случаем мы можем игнорировать) чтение может попасть на середину пакета. В таких случаях обычно делается так: вычитываем блок 188 байт, далее ищем байт синхронизации, если он в нулевой позиции - всё отлично, если нет, то данные от него и до конца, нужно переместить в начало блока, в освободившееся место нужно дочитать недостающу порцию, после чего пакет считается вычитанным и можно отдавать его на обработку.
Наглядно процесс копирования данных в начало блока можно показать этой картинкой:
Т.е. видим, что есть перекрытие. Логично, было бы применить какой-то аналог memmove(), но в стандартной библиотеке есть только std::move который делает совершенно не то. Но при этом, читая описание для std::copy (
http://www.cplusplus.com/reference/algorithm/copy) видим следующую строчку:
The ranges shall not overlap in such a way that result points to an element in the range [first,last).
т.е. на самом деле, если начало области (result) куда копировать, лежит вне области [first,last), то всё должно быть ок. И это реально так.
Но посмотрим такую схему копирования с перекрытием:
пока не обращаем внимание на то, что result тут в конце. Смысл картинки в том, что блок памяти нужно сдвинуть с начала на какое-то смещение вперёд, соответственно если это смещение меньше размера сдвигаемого блока, то адрес назначения у нас будет лежать в пределах [first,last), таким образом условие применимости std::copy не соблюдаются. И если применить его, мы просто затрём данным в перекрывающейся области.
Но тут на помощь нам приходит его собрат, как раз решающий эту проблему: std::copy_backward, всё отличие этой функции в том, что он осуществляет копирование с конца. Т.е. для случая изображённой на второй картинке, он возьмёт (далее очень грубо, т.е. на самом деле last и result это указатели на конец блока, а ближайшие данные находятся по last-1 и result-1) элемент из last и ложится в result, далее из last-1 в result-1, далее из last-2 в result-2 и так далее.
Видно, что при такой схеме копирования, когда мы начнём писать в перекрывающуюся область, данные в ней уже будут обработаны. Т.е. для нас всё хорошо. Забавно, что условие применимости при перекрывающийся областях для std::copy_backward слово в слово повторяет данное условие для std::copy.
Итак, резюмируя, простое правило:
- Если result < first (“сдвиг блока к началу /или влево/”), то применяем
std::copy, в качестве result указываем НАЧАЛО блока-назначения. - Если result > first (“сдвиг блока к концу /или вправо/”), то применяем
std::copy_backward, в качестве result указываем КОНЕЦ блока-назначения.
Текст является творческим переосмыслением англоязычной статьи: http://www.trilithium.com/johan/2006/02/copy-confusion, картинки взяты от туда же, пример из собственного опыта.
Референс:
- http://www.cplusplus.com/reference/algorithm/copy
- http://www.cplusplus.com/reference/algorithm/copy_backward
PS Статья была опубликована на Habrahabr: http://habrahabr.ru/post/218451