Iterating Streams in Reverse

Question

I would like to use std::find_if to traverse the contents of an std::streambuf in reverse. This involves constructing an std::reverse_iterator from an std::istream_iterator or std::istreambuf_iterator. Unfortunately, trying to do this, as shown in the code sample below, results in a compilation error. How can I get this to work? If necessary, solutions using Boost would be great.

#include <cstddef>
#include <fstream>
#include <iterator>

template <class Iterator>
static std::reverse_iterator<Iterator>
make_reverse_iterator(Iterator i)
{
    return std::reverse_iterator<Iterator>(i);
}

int main()
{
    std::ifstream is{"foo.txt", std::ios::binary};
    std::istreambuf_iterator<char> i{is};
    auto r = make_reverse_iterator(i);
    // Error =(
    *r;
    return EXIT_SUCCESS;
}

Here is the compilation error reported by g++-4.8.1:

In file included from /opt/local/include/gcc48/c++/bits/stl_algobase.h:67:0,
                 from /opt/local/include/gcc48/c++/bits/char_traits.h:39,
                 from /opt/local/include/gcc48/c++/ios:40,
                 from /opt/local/include/gcc48/c++/istream:38,
                 from /opt/local/include/gcc48/c++/fstream:38,
                 from ri.cpp:9:
/opt/local/include/gcc48/c++/bits/stl_iterator.h: In instantiation of 'std::reverse_iterator<_Iterator>::reference std::reverse_iterator<_Iterator>::operator*() const [with _Iterator = std::istream_iterator<char>; std::reverse_iterator<_Iterator>::reference = const char&]':
ri.cpp:24:3:   required from here
/opt/local/include/gcc48/c++/bits/stl_iterator.h:163:10: error: no match for 'operator--' (operand type is 'std::istream_iterator<char>')
  return *--__tmp;
          ^

Thanks for your help!

Answer 1

As far as I know input iterators (such as those of ifstreams) are not capable of going backwards which is why the reverse iterator is not available. Which makes sense because if you think about it, the forward of the reverse_iterator (i.e. operator ++) is the backwards of the normal iterator (i.e. operator --) and so if the normal iterator doesn't provide operator --, then it stands to reason that the reverse_iterator should not exist.

As I recall there are 3 types of iterators: forward, bidirectional and random access. Forward can only go in one direction (guess which :P), bidirectional can go forward and backwards by 1 and random access can go forwards and backwards by whatever increment.

As you can see random access iterators offer all the operations of bidirectional iterators (and more) who themselves offer all the operations of forward iterators (and more). Which means random access iterators can be used where forward iterators are require but not the other way around.

As you may have guessed from this explanation make_reverse_iterator most likely requires either bidirectional or random access iterators and ifstream most likely offers only forward which is why the template instantiation fails.