Wednesday, September 14, 2011

Using reverse iterators with c++11 range-based "for" loops

The range-based for loop is a handy c++11 language construct that allows you to simply iterate over, well, anything iterable :


void makeSnaflu(const std::vector<int>& vec) {
  for(int x : vec)
    doFooBar(x);
}

Unfortunately, a sheer number of STL classes and containers allow iterating in a reverse order using reverse_iterators, but there is no support for them in the range-based for loop.


However, this could be fixed easily by creating a proxy template which uses some c++11 features. This template proxy assumes the class provides reverse iterators via rbegin() and rend(), in the same manner that the range-based for loop assumes the object passed provides begin() and end():


template<class Cont>
class const_reverse_wrapper {
  const Cont& container;

public:
  const_reverse_wrapper(const Cont& cont) : container(cont){ }
  decltype(container.rbegin()) begin() const { return container.rbegin(); }
  decltype(container.rend()) end() const { return container.rend(); }
};

template<class Cont>
class reverse_wrapper {
  Cont& container;

public:
  reverse_wrapper(Cont& cont) : container(cont){ }
  decltype(container.rbegin()) begin() { return container.rbegin(); }
  decltype(container.rend()) end() { return container.rend(); }
};

template<class Cont>
const_reverse_wrapper<Cont> reverse(const Cont& cont) {
  return const_reverse_wrapper<Cont>(cont);
}

template<class Cont>
reverse_wrapper<Cont> reverse(Cont& cont) {
  return reverse_wrapper<Cont>(cont);
}

Here decltype() is super handy when it comes to allow the rbegin() and rend() to return pretty much anything they like.


Now you can easily iterate to string in a reverse order:

std::string stressed = "stressed no tips";
for(char c : reverse(stressed))
  std::cout << c;
std::cout << std::endl;

You may want to follow me on twitter.



9 comments:

  1. This looks very elegant. I would like to use this code but I need a license from you. Can you please attach some non-GPL FOSS license?
    Cheers!

    ReplyDelete
  2. Hi Steve, sorry for the late answer. I added a "about" page with licensing information. The code snippets are now in public domain.

    ReplyDelete
  3. Visual C++ 2012 gives the error "C2228: left of '.rbegin' must have class/struct/union."

    Dang.

    ReplyDelete
    Replies
    1. change decltype( container.rbegin() ) to decltype( Cont().rbegin() )

      Delete
  4. In const_reverse_wrapper,
    decltype(container.rend()) end() { return container.rend(); }
    should be:
    decltype(container.rend()) end() const { return container.rend(); }

    ReplyDelete
  5. This change seems to work in VS 2012

    auto begin()-> decltype(container.rbegin()) { return container.rbegin(); }
    auto end() -> decltype(container.rend()) { return container.rend(); }
    --david

    ReplyDelete
  6. Warning, you can end up with a dangling reference if you use a temporary! Try replacing

    std::string stressed = "stressed no tips";
    for(char c : reverse(stressed))

    with

    for(char c : reverse(std::string("stressed no tips")))

    then it won't work (the string will be destructed before the first iteration, undefined behavior). That's annoying, since

    for(char c : std::string("stressed no tips"))

    is valid. The fix is not easy, I guess you must treat rvalue references differently and store a container object (move from source)... Maybe boost::adaptors::reverse handles that...

    ReplyDelete