Moving Ranges Around with STL Algorithms
We’ve seen various ways to achieve complex operations on ranges with STL algorithms along the posts of the STL Learning Resource.
Let’s now see how to just move collections around. A much simpler topic…
…or is it?
Heaving ranges around
There are essentially 3 STL algorithms that allow to move several elements of a collection in bulk: std::copy, std::move and std::swap_ranges.
std::copy
std::copy is probably the simplest algorithm in the STL inventory. It takes an input range (in the form of two iterators, with the interface of the STL as it is today), and an output iterator:
template<typename InputIterator, typename OutputIterator > OutputIterator copy(InputIterator first, InputIterator last, OutputIterator out);
And it simply copies each element of the input range over to the output iterator, incrementing it at each step.
It can become a little more subtle when one of its input or output is not bound to a container. For example, consider the following case where the output iterator is bound to a stream:
std::vector<int> v = {1, 2, 3, 4, 5};
std::copy(begin(v), end(v), std::ostream_iterator<int>(std::cout));
Which displays on the console:
12345
If you’d like to read more on streams and iterators on streams, we’ve seen them in detail in How to split a string in C++.
Another subtlety of std::copy is that, if the copy constructor of the type of the elements of the ranges satisfies certain conditions (if it std::is_trivially_copyable, to be more accurate), std::copy could call a std::memmove to haul the chunk of memory in bulk rather than calling a copy constructor on every element.
But all in all, it isn’t a very subtle algorithm.
Note that std::copy has a “_n” counterpart: std::copy_n. It takes its input range in the form of a begin iterator and a size, as opposed to a begin and an end:
template<typename InputIterator, typename Size, typename OutputIterator> OutputIterator copy_n(InputIterator first, Size count, OutputIterator out);
Also, to copy a range into an STL container, note that there are other ways of inserting several elements into an STL container efficiently.
std::move
You know std::move, right? It’s one of the most fundamental standard functions brought along by C++11 (if you don’t, now is a good time to look it up. Effective Modern C++ covers it in its Items 23 and 25, for example).
But did you know that std::move also had an overload for ranges?
Like std::copy, it takes two input iterators and one output iterator:
template<typename InputIterator, typename OutputIterator> OutputIterator move(InputIterator first, InputIterator last, OutputIterator out);
And as you can imagine, it moves every element of the input ranges over to the output iterator:
It is another way than move iterators to allow the STL to move elements around.
std::swap_ranges
Like its name suggests, std::swap_ranges swaps every element of a first range with its counterpart in the second range:
Note that the 2 ranges are not allowed to overlap.
It’s a little curious that std::swap_range and std::move have asymmetric names, perhaps std::move_ranges or an overload of std::swap would have been more consistent. Oh well.
Also note that std::swap_ranges is a “1.5 range” that is to say it doesn’t take the end of the second range:
template<typename ForwardIterator1, typename ForwardIterator2>
ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2);
It assumes that the second range will be at least as big as the first one, so you need to be sure that this assumption is true before calling std::swap_ranges.
Shuffling subranges inside a range
The three above algorithms allow to haul data from one range to another one. But what if those two ranges are in fact two subranges of a bigger one? And what if those subranges overlap?
Going forward
Let’s consider the case where we want to copy a subpart of a range over to a position further down the range. It could be that this new position is located before the end of the first subrange.
For instance, consider this 1 to 10 range:
Say that we’d like to move the 1 to 5 subrange 3 positions down:
Out first instinct may be to use std::copy:
std::copy(begin(v), begin(v) + 5, begin(v) + 3);
or rather, std::copy_n:
std::copy_n(begin(v), 5, begin(v) + 3);
But there are at least two reasons for which this is NOT the right algorithm for this operation:
The first reason is that it would not do the right thing. Consider the first thing that std::copy does:
Oops. We’ve lost the value of 4.
And the second reason is that the standard requires that the output iterator be NOT within [begin, end) (which means that begin is included but end is not). So if it is, std::copy actually has undefined behaviour. Which has the strange implication that it is forbidden to std::copy a range over itself.
So to copy values forward in a range, we’d need an algorithm that does the same thing as std::copy, but backward (which sounds a little odd, but oh well).
This is why we have… std::copy_backward!
std::copy_backward is like std::copy, except that it starts by copying the last element of the input range over to the last element of the output range:
Then it works its way up from there and to the beginning of the input range:
This implies that the output iterator pointing to the output range must be its end:
template<typename BidirectionalIterator1, typename BidirectionalIterator2> BidirectionalIterator2 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 outLast);
So in our case the code would be:
std::copy_backward(begin(v), begin(v) + 5, begin(v) + 8);
Note that there is also std::move_backward, that moves the elements of a range starting from its end and working its way up to its beginning.
Going backward
With a similar reasoning as above, to go backward you would use std::copy (or std::move).
Indeed, it is undefined behaviour if the output iterator of std::copy_backward is inside the (begin, end] of the input range.
Swapping subranges
You can swap two subranges inside of a range by using std::swap_ranges, as long as they don’t overlap.
All this is complicated
Using copy_backward to shift elements forward, making sure to get all the begin and end iterators right to avoid stepping out of the range… All seems is complicated, isn’t it?
Well, it is. For this reason there has been a proposal by Dan Raviv for the standard to add a std::shift_left and a std::shift_right functions in C++20. They would have the following prototypes:
template<typename ForwardIterator>
ForwardIterator shift_left(ForwardIterator first, ForwardIterator last,
typename std::iterator_traits<ForwardIterator>::difference_type n);
template<class ForwardIterator>
ForwardIterator shift_right(ForwardIterator first, ForwardIterator last,
typename std::iterator_traits<ForwardIterator>::difference_type n);
What the last parameter means is the number of steps to shift the elements, so:
std::shift_right(begin(v), begin(v) + 5, 3);
would move the first 5 elements of our range 3 positions down the range. Careful: those two functions would move, and not copy the elements.
Will this actually get into C++20? The answer in 2020.
Where to find an implementation of those functions? Here is the sample implementaton supporting the proposal.
Until then? Happy backwarding!
Related articles:
- The STL Learning Resource
- How to insert several elements into an STL container efficiently
- How to split a string in C++
Share this post!
