Программируя на Си многие сталкивались с такими функциями как
В мире С++ никто не запрещает пользоваться этими функциями (часто эти функции используют различные механизмы оптимизации и могут статься быстрее своих собратьев из мира C++), но есть и более родное средство, работающее через итераторы:
Но по наитию, хочется посмотреть, а что там с пересекающимися областями (overlapping memory blocks)? Ведь задача, на самом деле, не такая уж редкая. К примеру, хотим мы читать MPEG-TS пакеты (размер каждого 188 байт, каждый пакет начинается с 0x47 /sync byte/) из какого-то потока, и есть вероятность, что первое (а может и последующее: например, имеем дело с M2TS контейнером, размер блока которого 192 байт и лишние 4 байта в большинстве случаем мы можем игнорировать /timestamp/) чтение может попасть на середину пакета. В таких случаях обычно делается так: вычитываем блок 188 байт, далее ищем байт синхронизации, если он в нулевой позиции — всё отлично, если нет, то данные от него и до конца, нужно переместить в начало блока, в освободившееся место нужно дочитать недостающую порцию, после чего пакет считается вычитанным и можно отдавать его на обработку.
Наглядно процесс копирования данных в начало блока можно показать этой картинкой:
Т.е. видим, что есть перекрытие. Логично было бы применить какой-то аналог
т.е. на самом деле, если начало области (result) куда копировать, лежит вне области [first,last), то всё должно быть ок. И это реально так.
Но посмотрим такую схему копирования с перекрытием:
пока не обращаем внимание на то, что result тут в конце. Смысл картинки в том, что блок памяти нужно сдвинуть от начала на какое-то смещение вперёд, соответственно, если это смещение меньше размера сдвигаемого блока, то адрес назначения у нас будет лежать в пределах [first,last), таким образом условие применимости
Но тут на помощь нам приходит его собрат, как раз решающий эту проблему:
Видно, что при такой схеме копирования, когда мы начнём писать в перекрывающуюся область, данные в ней уже будут обработаны. Т.е. для нас всё хорошо. Забавно, что условие применимости при перекрывающийся областях для
Итак, резюмируя, простое правило:
Текст является творческим переосмыслением англоязычной статьи: www.trilithium.com/johan/2006/02/copy-confusion, картинки взяты от туда же, пример из собственного опыта.
Референс:
memcpy() и memmove(), по сути, функции делают одно и тоже, но вторая корректно отрабатывает ситуацию, когда области памяти перекрываются (на что появляются дополнительные накладные расходы).В мире С++ никто не запрещает пользоваться этими функциями (часто эти функции используют различные механизмы оптимизации и могут статься быстрее своих собратьев из мира C++), но есть и более родное средство, работающее через итераторы:
std::copy. Это средство применимо не только к POD типам, а к любым сущностям, поддерживающим итераторы. О деталях реализации в стандарте ничего не сказано, но можно предположить, что разработчики библиотеки не настолько глупы, что бы не использовать, оптимизированные memcpy()/memmove() когда это возможно. Но по наитию, хочется посмотреть, а что там с пересекающимися областями (overlapping memory blocks)? Ведь задача, на самом деле, не такая уж редкая. К примеру, хотим мы читать MPEG-TS пакеты (размер каждого 188 байт, каждый пакет начинается с 0x47 /sync byte/) из какого-то потока, и есть вероятность, что первое (а может и последующее: например, имеем дело с M2TS контейнером, размер блока которого 192 байт и лишние 4 байта в большинстве случаем мы можем игнорировать /timestamp/) чтение может попасть на середину пакета. В таких случаях обычно делается так: вычитываем блок 188 байт, далее ищем байт синхронизации, если он в нулевой позиции — всё отлично, если нет, то данные от него и до конца, нужно переместить в начало блока, в освободившееся место нужно дочитать недостающую порцию, после чего пакет считается вычитанным и можно отдавать его на обработку.
Наглядно процесс копирования данных в начало блока можно показать этой картинкой:
Т.е. видим, что есть перекрытие. Логично было бы применить какой-то аналог
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), то всё должно быть ок. И это реально так.
Но посмотрим такую схему копирования с перекрытием:
пока не обращаем внимание на то, что result тут в конце. Смысл картинки в том, что блок памяти нужно сдвинуть от начала на какое-то смещение вперёд, соответственно, если это смещение меньше размера сдвигаемого блока, то адрес назначения у нас будет лежать в пределах [first,last), таким образом условие применимости
std::copy не соблюдаются. И если применить его, мы просто затрём данным в перекрывающейся области. Но тут на помощь нам приходит его собрат, как раз решающий эту проблему:
std::copy_backward, всё отличие этой функции в том, что он осуществляет копирование с конца. Т.е. для случая изображённой на второй картинке, он возьмёт (далее очень грубо) элемент из 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 указываем конец блока-назначения.
Текст является творческим переосмыслением англоязычной статьи: www.trilithium.com/johan/2006/02/copy-confusion, картинки взяты от туда же, пример из собственного опыта.
Референс:
