C ++ and copying overlapping areas of memory

memmove() programming in C, many have come across such functions as memcpy() and memmove() , in fact, the functions do the same thing, but the second one correctly works out the situation when memory areas overlap (to which additional overheads appear).

In the C ++ world, no one forbids using these functions (often these functions use various optimization mechanisms and can be faster than their fellows from the C ++ world), but there is a more native tool that works through iterators: std::copy . This tool is applicable not only to POD types, but to any entities that support iterators. The implementation details in the standard say nothing, but it can be assumed that library developers are not so stupid as to not use optimized memcpy() / memmove() when possible.

But on a whim, I want to see, but what about overlapping memory blocks? After all, the task, in fact, is not so rare. For example, we want to read MPEG-TS packets (the size of each is 188 bytes, each packet starts with 0x47 / sync byte /) from some stream, and there is a possibility that the first (and maybe the next one: for example, we deal with M2TS a container with a block size of 192 bytes and an extra 4 bytes in most cases we can ignore / timestamp /) reading can get to the middle of the packet. In such cases, it is usually done this way: we read the block 188 bytes, then we look for the synchronization byte, if it is in the zero position - everything is fine, if not, the data from it to the end should be moved to the beginning of the block, the remaining portion needs to be read into the free space , after which the package is considered to be read and you can give it to processing.

Visually the process of copying data to the beginning of the block can be shown with this picture:

')
Those. see that there is an overlap. It would be logical to apply some analogue of memmove() , but in the standard library there is only std::move which does absolutely not the same thing (here you need to smile). But at the same time, reading the description for std :: copy we see the following line:

This is not the case. [First, last)

those. in fact, if the beginning of the region (result) where to copy, lies outside the region [first, last), then everything should be ok. And it really is.

But let's look at this overlapping copy scheme:


until we pay attention to the fact that the result is here at the end. The meaning of the picture is that the memory block needs to be shifted from the beginning by some kind of an offset forward, respectively, if this offset is less than the size of the shifted block, then the destination address will be within [first, last), thus the condition of applicability of std::copy not respected. And if we apply it, we simply wipe the data in the overlapping area.

But here his colleague comes to the rescue, just solving this problem: std::copy_backward , the whole difference of this function is that it performs copying from the end. Those. for the case depicted in the second picture, it takes (further roughly) an element from last and goes to result, then from last-1 to result-1, then from last-2 to result-2, and so on.

It can be seen that with such a copying scheme, when we start writing in an overlapping area, the data in it will already be processed. Those. everything is good for us It's funny that the condition of applicability with overlapping areas for std::copy_backward word for word repeats this condition for std::copy .

So, summarizing, a simple rule:

1. If result <first (“block shift to the beginning / or left /”), then use std::copy , and specify the beginning of the target block as result.
2. If result> first (“block shift to end / or right /”), then apply std::copy_backward , and specify end of std::copy_backward block as result.

The text is a creative reinterpretation of an English-language article: www.trilithium.com/johan/2006/02/copy-confusion , pictures taken from the same place, an example from my own experience.

Reference:

1. www.cplusplus.com/reference/algorithm/copy
2. www.cplusplus.com/reference/algorithm/copy_backward