CODEWITHSUNDEEP
c++
Baz
Baz

Reputation: 13125

Reverse iterate over a std::vector with forward iterators

If I have a function which takes a std::vector<T>::const_iterator called begin and a std::vector<T>::const_iterator called end, is it possible for me to iterate over it in a backwards direction?

UPDATE

I can't change the function signature, which is like this:

void func(Foo::const_iterator begin, Foo::const_iterator end) 
{
   ...
}

and called with:

func(foo.begin(), foo.end());

which I also can't change

Upvotes: 1

Views: 1598

Answers (3)

ipc
ipc

Reputation: 8143

Yes, you can.

template <typename Foo>
void test(typename Foo::const_iterator begin,
          typename Foo::const_iterator end)
{
  std::reverse_iterator<typename Foo::const_iterator>
    rbegin(end),
    rend(begin);
  std::copy(rbegin, rend, std::ostream_iterator<typename std::iterator_traits<typename Foo::const_iterator>::value_type>(std::cout));
}

int main()
{
  std::vector<int> v{3,1,4,1,5,9,2,6};
  test<std::vector<int> >(v.begin(), v.end());
}

Upvotes: 5

Steve Jessop
Steve Jessop

Reputation: 279215

I may have misunderstood the question, but do you just need:

while (begin != end) {
    --end;
    // do something with *end
}

If you need an iterator that goes backwards, ipc's answer gives you one.

In practice with vector you could probably get away with while (begin != end--), but don't be tempted. It's undefined behavior to decrement an iterator in the case where it's at the start of the vector (i.e. when it's equal to the result of vector::begin()).

This code requires at least a BidirectionalIterator. Fortunately, vector has a RandomAccessIterator, which is even better.

If you genuinely only had a ForwardIterator, then you'd have to iterate over the range and store the iterator values somewhere (like a stack), and then use them in reverse order:

std::stack<Foo::const_iterator> iterators;
while (begin != end) {
    iterators.push(begin);
    ++begin;
}
while (!iterators.empty()) {
    Foo::const_iterator i = iterators.top();
    // do something with *i
    iterators.pop();
}

This code requires at least a ForwardIterator (it will not work with a mere InputIterator).

Upvotes: 3

pmr
pmr

Reputation: 59811

Yes, you can use std::reverse_iterator. It is also a good idea not to specify the type of the iterator explicitly. Use a template argument instead.

#include <vector>
#include <algorithm>
#include <iostream>
#include <iterator>

template <typename BidirectionalIterator>
void x(BidirectionalIterator b, BidirectionalIterator e) {
  std::reverse_iterator<BidirectionalIterator> rb(e), re(b);
  std::for_each(rb, re, 
                [](typename BidirectionalIterator::reference x) 
                { std::cout << x << std::endl;});
}

int main()
{
  std::vector<int> v{1,2,3,4};
  x(begin(v), end(v));
  return 0;
}

Upvotes: 2

Related Questions