April 7, 2014 at 11:29C ++ and copy overlapping memory areas
- From the sandbox
- Tutorial
When programming in C, many came across such functions as,
In the world of C ++, no one prohibits the use of these functions (these functions often use a variety of mechanisms to optimize and may well be faster than their counterparts from the C ++ world), but there are more native agent running through iterators:
But on a hunch, I want to see what is there with overlapping areas (overlapping memory blocks)? After all, the task, in fact, is not so rare. For example, we want to read MPEG-TS packets (each 188 bytes in size, each packet starts with 0x47 / sync byte /) from some stream, and there is a possibility that the first (and maybe the following: for example, we deal with M2TS a container whose block size is 192 bytes and an extra 4 bytes in most cases we can ignore / timestamp /) reading can fall in the middle of the packet. In such cases, this is usually done as follows: we subtract the block of 188 bytes, then we look for the synchronization byte, if it is in the zero position - everything is fine, if not, then the data from it to the end must be moved to the beginning of the block, the missing portion needs to be read into the vacated space ,
Clearly the process of copying data to the top of the unit can show this picture:
That is, we see that there is an overlap. It would be logical to apply some kind of analogue
those. in fact, if the beginning of the area (result) where to copy lies outside the [first, last) area, then everything should be ok. And it is really so.
But let's see such a copying scheme with overlapping: for
now, we do not pay attention to the fact that 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 shift forward, respectively, if this shift is less than the size of the shifted block, then the destination address will lie within [first, last), so the applicability condition is
But here his brother comes to the rescue, just solving this problem:
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 is funny that the condition of applicability for overlapping areas for
So, in summary, a simple rule:
The text is a creative rethinking of the English-language article: www.trilithium.com/johan/2006/02/copy-confusion , the pictures are taken from the same place, an example from my own experience.
Reference:
memcpy()and memmove(), in fact, the functions do the same thing, but the second correctly fulfills the situation when the memory areas overlap (which causes additional overhead). In the world of C ++, no one prohibits the use of these functions (these functions often use a variety of mechanisms to optimize and may well be faster than their counterparts from the C ++ world), but there are more native agent running through iterators:
std::copy. This tool is applicable not only to POD types, but to any entities that support iterators. Nothing is said about the implementation details in the standard, but it can be assumed that the developers of the library are not so stupid as to not use optimized memcpy()/ memmove()when it is possible.But on a hunch, I want to see what is there with overlapping areas (overlapping memory blocks)? After all, the task, in fact, is not so rare. For example, we want to read MPEG-TS packets (each 188 bytes in size, each packet starts with 0x47 / sync byte /) from some stream, and there is a possibility that the first (and maybe the following: for example, we deal with M2TS a container whose block size is 192 bytes and an extra 4 bytes in most cases we can ignore / timestamp /) reading can fall in the middle of the packet. In such cases, this is usually done as follows: we subtract the block of 188 bytes, then we look for the synchronization byte, if it is in the zero position - everything is fine, if not, then the data from it to the end must be moved to the beginning of the block, the missing portion needs to be read into the vacated space ,
Clearly the process of copying data to the top of the unit can show this picture:
That is, we see that there is an overlap. It would be logical to apply some kind of analogue
memmove(), but in the standard library there is only one std::movethat does absolutely wrong (here you need to smile). But at the same time, reading the description for std :: copy we see the following line:The ranges shall not overlap in such a way that result points to an element in the range [first, last).
those. in fact, if the beginning of the area (result) where to copy lies outside the [first, last) area, then everything should be ok. And it is really so.
But let's see such a copying scheme with overlapping: for
now, we do not pay attention to the fact that 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 shift forward, respectively, if this shift is less than the size of the shifted block, then the destination address will lie within [first, last), so the applicability condition is
std::copynot met . And if you apply it, we simply overwrite the data in the overlapping area. But here his brother comes to the rescue, just solving this problem:
std::copy_backward, the whole difference of this function is that it carries out copying from the end. Those. for the case shown in the second picture, it will take (very roughly below) the element from last and go 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 is funny that the condition of applicability for overlapping areas for
std::copy_backwardword for word repeats this condition for std::copy. So, in summary, a simple rule:
- If result <first (“shift of the block to the beginning / or to the left /”), then we apply
std::copy, as the result we indicate the beginning of the destination block. - If result> first (“shift of the block to the end / or to the right /”), then we use
std::copy_backward, as the result we indicate the end of the destination block.
The text is a creative rethinking of the English-language article: www.trilithium.com/johan/2006/02/copy-confusion , the pictures are taken from the same place, an example from my own experience.
Reference: