The Difference Between std::copy_backward and std::copy with Reverse Iterators
A couple of months ago, I made a talk at the ACCU conference about learning every algorithm there is in the STL. Amongst them, we covered std::copy_backward, that makes a copy of a source range to a destination range, starting from its end and working its way back to the beginning.
In the questions session at the end of the talk, attendant Oscar Forner rose an interesting point: is there any difference between performing a std::copy_backward versus performing a simple std::copy on the reverse iterators from the source collection?
Here are Oscar’s exact words:
Question I asked to @JoBoccara at @ACCUConf that might be interesting for the #cplusplus #cpp communities:
Is there any difference between using std::copy_backward or using std::copy with reverse iterators?
— Oscar Forner (@oscar_forner) April 11, 2018
Indeed, the two options sound sort of similar. Do you see a difference between them? Let’s find out what it is.
std::copy_backward
Here is a reminder about std::copy_backward. If you’re already familiar with this algorithm you can skip to the next section.
std::copy-backward is one of the STL algorithms that allows moving ranges around. A simple way to illustrate the point of std::copy_backward is to start from an example.
Consider the following collection containing the numbers from 1 to 10:
How can we copy the sub-range going from 1 to 5 three positions to the right inside the collection? That is, how to get from the above state to that one:
A option that sounds reasonable at first is to use std::copy. If we call our collection numbers, we could attempt to write:
std::copy(begin(numbers), begin(numbers) + 5, begin(numbers) + 3);
But contrary to what this line of code looks like, it doesn’t copy the first 5 elements three positions down. Not at all. Indeed, the first thing std::copy does is to copy the first element of the source range over to the destination range. The first element in the source is 1, and the first location in the destination holds the 4:
Huh-oh. Not good, we’ve lost the 4.
What we would like is to start copying from the end of the source range and work our way backwards. Starting with 5, the last element of the source range:
So we need to copy, but backwards. This is what std::copy_backward does:
std::copy_backward(begin(numbers), begin(numbers) + 5, begin(numbers) + 8);
Note the output iterator: it is at the end of the destination collection, since this is where std::copy_backward has to start writing its results.
After the call to std::copy_backward, the collection is in the following state:
So this is std::copy_backward.
Reverse iterators
The initial question was to compare std::copy_backward with using reverse iterators. So let’s leave std::copy_backward aside for a moment to make a quick recap on reverse iterators. If you’re already familiar with reverse iterators, you can skip to the next section.
The simplest way to traverse a collection is by using a pair of iterators that go from its first element to its last. In the STL containers, such as std::vector and std::map, those iterators are accessible via the begin and end functions.
But if the structure of the collection allows an iterator to go backwards (bidirectional iterators), it can also provide reverse iterators. This is the case of almost all STL containers. For example, std::vector and std::map provide rbegin and rend.
To illustrate, consider the following program:
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
int main()
{
std::vector<std::string> words = { "so", "long", "and", "thanks", "for", "all", "the", "fish" };
std::for_each(rbegin(words), rend(words), [](std::string const& word){ std::cout << word << ' '; });
}
Its output is:
fish the all for thanks and long so
Reverse iterators offer an operator++ just like their forward counterparts, but theirs move backwards in the collection instead of forwards.
std::copy_backward VS reverse iterators
Both std::copy_backward and reverse iterators allow to traverse a collection in reverse order. Are they equivalent?
Let’s take our initial usage of std::copy_backward that took the collection from this state:
To that one:
Here is the full program:
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
int main()
{
std::vector<int> numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
std::copy_backward(begin(numbers), begin(numbers) + 5, begin(numbers) + 8);
for (int number : numbers) std::cout << number << ' ';
}
It indeed outputs:
1 2 3 1 2 3 4 5 9 10
How could we write a program that achieve the same result, but with reverse iterators?
If we start from the end of the collection, the subrange to copy (the one going from 1 to 5) goes from rbegin + 5 to rbegin + 10 (which by coincidence happens to be rend in this case). So that would be our source: from rbegin + 5 to rbegin + 10.
What about the destination? If we pass a reverse iterator as an output to std::copy, then the starting point from the destination is its last element, so the one that holds 8. Indeed, std::copy applies operator++ to advance its output iterators, which effectively goes backwards into the collection, since we’re using a reverse iterator in output. And counting from the end, the position of 8 is rbegin + 2.
Here is the corresponding program:
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
int main()
{
std::vector<int> numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
std::copy(rbegin(numbers) + 5, rbegin(numbers) + 10, rbegin(numbers) + 2);
for (int number : numbers) std::cout << number << ' ';
}
It also outputs:
1 2 3 1 2 3 4 5 9 10
Copying forwards, copying backwards, and the reverse of the backwards
As we saw with the STL algorithms that move ranges around, to copy a sub-range further right we should use std::copy_backward, and to copy a sub-range further left we should use std::copy, which sounds kind of weird.
Now that reverse iterators enter the picture, we see that we can also copy a sub-range further right by using std::copy and reverse iterators. And, similarly, we can copy a sub-range further left with std::copy_backward and reverse iterators.
Here is an example of program that illustrate that last statement, “copying a sub-range further left with std::copy_backward and reverse iterators”:
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
int main()
{
std::vector<int> numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
std::copy_backward(rbegin(numbers), rbegin(numbers) + 5, rbegin(numbers) + 7);
for (int number : numbers)
{
std::cout << number << ' ';
}
}
It outputs:
1 2 3 6 7 8 9 10 9 10
We’ve copied the last 5 elements two positions left inside the collection.
It seems to mo me that using std::copy and std::copy_backward with forward iterators results in more natural code than using them with reverse iterators. But the resulting English statements may sound more logical: “we can copy a sub-range further left with std::copy_backward and reverse iterators”. What do you think?
In any case an even simpler solution would be to encapsulate everything behind a nice interface, like Dan Raviv has been proposing to the C++ committee with the shift operations.
Thanks Oscar for this great question. If, like Oscar, you’d like to discuss a topic about the STL algorithms, you can reach out to me by email at jonathan@fluentcpp.com.
You may also like
Don't want to miss out ? Follow:
Share this post!
