Why did the designers of the STL introduce reverse iterators? I don't need a reverse integer to iterate backwards over an array; so why do I need a reverse iterator to iterate backwards over an STL container? What's wrong with good ol' operator--()? Instead they introduce a whole new iterator type (two types really: reverse_iterator and const_reverse_iterator)? Seems like this results in lots of replicated code for folks implementing container classes, many more test cases, and causes problems (or at least complexity) if, for example, you want to invoke some method that takes a regular iterator when what you have handy is a reverse iterator. No doubt this is an artifact of some fundamental design goal in the STL; but I'd really like to understand what was so important to warrant introducing all the complexity.
Thanks for your gracious and thoughtful response. My comments to each of your suggestions:
1) I suspect this may very-well have something to do with it. Some containers you simply can't iterate over in the backwards direction; so requiring all iterators to implement operator--() would cause problems. Hence we have both forward and bi-directional iterators in the C++ specification. Still, any container that supports both forward and reverse iterators will certainly support a bi-directional iterator; so it's still not completely clear to me why we need reverse iterators.
2) Why is that useful? From a purely aesthetic point of view, I find the presence of the "--" makes it more clear that we are indeed iterating through the container backwards. And it also makes it look more like the case of iterating through a classical array backwards with an integer iteration variable.
3) Quite true, but there's nothing to keep you from eliminating reverse_iterators but still include rbegin() and rend() and have them simply return a normal iterator:
for(iterator iter = s.rbegin(); iter != s.rend(); --iter)
3) Quite true, but there's nothing to keep you from eliminating reverse_iterators but still include rbegin() and rend() and have them simply return a normal iterator:
for(iterator iter = s.rbegin(); iter != s.rend(); --iter)
Why should I have to use a reverse iterator *AND* an operator--(), what if I decide I need to change the order of iterations then there's 2 things I need to change instead of just 1.
I'd imagine that it would be a maintenance nightmare for large libraries which make extensive use of iterators.
Mainly, this is for standardization with algorithms. For example, std::foreach will use ++ to go over all the iterators in it, however if reverse iterators used your example, std::foreach would somehow have to figure out which type of iterator it was using. If you want, you could think of ++ not really meaning "increment" but being more like "next".
I think a big reason for reverse iterators is so that you can apply generic functions in reverse without writing a reverse-specific function.
Consider:
1 2 3 4 5 6
template<class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f)
{
for ( ; first!=last; ++first ) f(*first);
return f;
}
That function is only going to increment the iterator that it is given.
If you want to use that function in reverse all you have to do is supply it with reverse iterators, rather than writing a new function.
It's for genericity. A std::reverse_iterator is an implementation of the reverse iterator category. The categories are used to describe the minimum requirements for particular algorithms.
There are a number of good books that cover this information and I'm sure it is also available online. I recommend reading Generic Programming and the STL.
Your concrete example shows the usefulness to firedraco's second observation: "It makes the code more similar". I had actually considered this myself, but wanted to see if anybody knew of any other practical benefit to the existence of reverse iterators. I still know of none. Perhaps this single benefit is enough, but I wonder if reverse versions of the algorithms wouldn't have been a better choice than doubling the number of iterator types for all the different containers. E.g., replicating find into find_first and find_last, promotes clarity. Most of the STL algorithms are little more than a single for loop anyway and I suspect most still go unused by most C++ programmers. In contrast, a full iterator implementation is usually quite extensive and iterators are obviously heavily used by anyone using the STL. I would have opted for simplifying the exposed interface for those classes that everybody uses, but I'm no expert and of course this is all moot now anyway.
I think it makes a bit more sense to give the container reverse iterators because then for your one container you can write a million algorithm's to process its data elements rather than 2 million. It just seems more likely to me that the number of algorithms would reasonably outnumber the number of containers.
EDIT:
Also from a conceptual viewpoint an algorithm is concerned with processing a sequence of data. It should not really need to care about how that sequence is ordered in its implementation, only the order in which it receives the elements from the interface it is given. It seems to me that it is the more container's job to provide an interface to access to the data in different ways.
EDIT 2:
Also I, as a third party, can write my own iterator to access the container's elements in yet a different order. let's say for example I write a random_iterator. I do not need to write a new algorithm to deal with the elements in random order, I can simply supply the current algorithm with my random_iterator. Another example might be a skip_iterator that provides a sequence of every second or third element, missing out the others.