Как стать автором
Обновить

C++ и копирование перекрывающихся областей памяти

Время на прочтение 3 мин
Количество просмотров 24K
Программируя на Си многие сталкивались с такими функциями как memcpy() и memmove(), по сути, функции делают одно и тоже, но вторая корректно отрабатывает ситуацию, когда области памяти перекрываются (на что появляются дополнительные накладные расходы).

В мире С++ никто не запрещает пользоваться этими функциями (часто эти функции используют различные механизмы оптимизации и могут статься быстрее своих собратьев из мира C++), но есть и более родное средство, работающее через итераторы: std::copy. Это средство применимо не только к POD типам, а к любым сущностям, поддерживающим итераторы. О деталях реализации в стандарте ничего не сказано, но можно предположить, что разработчики библиотеки не настолько глупы, что бы не использовать, оптимизированные memcpy()/memmove() когда это возможно.

Но по наитию, хочется посмотреть, а что там с пересекающимися областями (overlapping memory blocks)? Ведь задача, на самом деле, не такая уж редкая. К примеру, хотим мы читать MPEG-TS пакеты (размер каждого 188 байт, каждый пакет начинается с 0x47 /sync byte/) из какого-то потока, и есть вероятность, что первое (а может и последующее: например, имеем дело с M2TS контейнером, размер блока которого 192 байт и лишние 4 байта в большинстве случаем мы можем игнорировать /timestamp/) чтение может попасть на середину пакета. В таких случаях обычно делается так: вычитываем блок 188 байт, далее ищем байт синхронизации, если он в нулевой позиции — всё отлично, если нет, то данные от него и до конца, нужно переместить в начало блока, в освободившееся место нужно дочитать недостающую порцию, после чего пакет считается вычитанным и можно отдавать его на обработку.

Наглядно процесс копирования данных в начало блока можно показать этой картинкой:
image

Т.е. видим, что есть перекрытие. Логично было бы применить какой-то аналог memmove(), но в стандартной библиотеке есть только std::move который делает совершенно не то (тут нужно улыбнуться). Но при этом, читая описание для std::copy видим следующую строчку:
The ranges shall not overlap in such a way that result points to an element in the range [first,last).


т.е. на самом деле, если начало области (result) куда копировать, лежит вне области [first,last), то всё должно быть ок. И это реально так.

Но посмотрим такую схему копирования с перекрытием:
image

пока не обращаем внимание на то, что result тут в конце. Смысл картинки в том, что блок памяти нужно сдвинуть от начала на какое-то смещение вперёд, соответственно, если это смещение меньше размера сдвигаемого блока, то адрес назначения у нас будет лежать в пределах [first,last), таким образом условие применимости std::copy не соблюдаются. И если применить его, мы просто затрём данным в перекрывающейся области.

Но тут на помощь нам приходит его собрат, как раз решающий эту проблему: std::copy_backward, всё отличие этой функции в том, что он осуществляет копирование с конца. Т.е. для случая изображённой на второй картинке, он возьмёт (далее очень грубо) элемент из last и ложится в result, далее из last-1 в result-1, далее из last-2 в result-2 и так далее.

Видно, что при такой схеме копирования, когда мы начнём писать в перекрывающуюся область, данные в ней уже будут обработаны. Т.е. для нас всё хорошо. Забавно, что условие применимости при перекрывающийся областях для std::copy_backward слово в слово повторяет данное условие для std::copy.

Итак, резюмируя, простое правило:
  1. Если result < first («сдвиг блока к началу /или влево/»), то применяем std::copy, в качестве result указываем начало блока-назначения.
  2. Если result > first («сдвиг блока к концу /или вправо/»), то применяем std::copy_backward, в качестве result указываем конец блока-назначения.


Текст является творческим переосмыслением англоязычной статьи: www.trilithium.com/johan/2006/02/copy-confusion, картинки взяты от туда же, пример из собственного опыта.

Референс:
  1. www.cplusplus.com/reference/algorithm/copy
  2. www.cplusplus.com/reference/algorithm/copy_backward
Теги:
Хабы:
+30
Комментарии 16
Комментарии Комментарии 16

Публикации

Истории

Работа

QT разработчик
13 вакансий
Программист C++
122 вакансии

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн