How best to control iteration direction?

问题:

I have a container of large objects that are expensive to copy. I must sometimes iterate over the whole container normally, and sometimes in reverse. Once I determine the iteration direction, I don't need to change mid-flight, i.e. no random access needed.

I'm hoping to do something like this pattern:

#include <iostream>
#include <vector>
using namespace std;
int main( int argc, char** )
{
    // pretend this is a vector of expensive objects
    vector<int> foo = {1,2,3,4,5};

    // calculate forward or backward iteration direction
    bool backwards = (argc > 1);

    if( backwards )
        // prepare backward iteration, but don't copy objects
    else
        // prepare forward iteration, but don't copy objects

    for( auto& i : /* either forward or backward */ )
    {
        // my loop body
        cout << i;
    }

    return 0;
}

This is a C++11 program, but I don't think that really helps me here. I'm just not seeing the best way to do this. Thanks for any help.

回答1:

The C++ standard containers come with these things called "reverse iterators". Use std::vector::rbegin() and std::vector::rend() to get an iterator that iterates backwards through the vector. C++03 can do this easily:

#include <iostream> 
#include <vector>  

// Use const reference to pass expensive-to-copy types
void loop_body(const int& i)
{
    std::cout << i;
}

int main( int argc, char** ) 
{ 
    // pretend this is a vector of expensive objects 
    std::vector<int> foo = {1,2,3,4,5}; 

    // calculate forward or backward iteration direction 
    bool backwards = (argc > 1); 

    if( backwards ) { 
        std::for_each(foo.rbegin(), foo.rend(), &loop_body);
    } else { 
        std::for_each(foo.begin(), foo.end(), &loop_body);
    } 
    return 0; 
} 

You may be able to do this, using lambdas in C++11:

#include <iostream> 
#include <vector> 

int main( int argc, char** ) 
{ 
    // pretend this is a vector of expensive objects 
    std::vector<int> foo = {1,2,3,4,5}; 

    // calculate forward or backward iteration direction 
    bool backwards = (argc > 1); 

    // Use const reference to pass expensive-to-copy types
    auto loop_body = [](const int& i)
    {
        std::cout << i;
    };

    if( backwards ) { 
        std::for_each(foo.rbegin(), foo.rend(), loop_body);
    } else { 
        std::for_each(foo.begin(), foo.end(), loop_body);
    } 
    return 0; 
}

回答2:

Why don't you just put your algorithm into a template function? Then it's trivial to call it with begin/end or rbegin/rend.

template <class Iterator>
void do_stuff(Iterator first, Iterator last)
{
    // Your loop code here.
}

Or you can use lambda (since it is C++11) along with std::for_each as:

auto loop_body = [&](int &i) { std::cout << i << std::endl; } ;

if (backward)
  std::for_each(v.rbegin(), v.rend(), loop_body);
else
  std::for_each(v.begin(), v.end(), loop_body);

回答3:

Standard library containers have both normal and reverse iterators, which solves a big part of the problem.

Unfortunately, the are distinct types, so you can't create a single variable which can hold either a normal or a reverse iterator.

So what I'd do is wrap your loop in a separate function, and template it to work with both:

template <typename It>
void myloop(It first, It last) {
    for(It cur = first; cur != last; ++cur)
    {
        // my loop body
        cout << *cur;
    }
}

And then call it like this:

if( backwards )
    myloop(foo.rbegin(), foo.rend());
else
    myloop(foo.begin(), foo.end());

Of course, then you could probably just as well use one of the standard library algorithms instead of your loop:

if( backwards )
    std::for_each(foo.rbegin(), foo.rend(), [](int item){  cout << item;});
else
    std::for_each(foo.begin(), foo.end(), [](int item){  cout << item;});

(Note I'm using for_each here for simplicity. Very likely, std::transform or std::copy might be better fits to describe what you want to do.

I also used a lambda expression instead of the myloop function. You could do either, but the lambda is much shorter, and IMO easier to read.

回答4:

std::vector<int>::iterator begin = foo.begin();
std::vector<int>::iterator last = foo.end();
if (last != begin)
{
    --last;
    int direction = 1;
    if( backwards )
    {
        std::swap(begin, last);
        direction = -1;
    }
    for( auto& i = begin;  ; i += direction)
    {
        // do stuff
        if (i == last)
            break;
    }
}

回答5:

Even if this an old question I recently had the same problem and solved it this way:

Put this somewhere:

namespace mani {

    // an extension to std::for_each where you can choose the direction:
    template <class InputIterator, class Function> Function for_each_reverse(bool reverse, const InputIterator& first, const InputIterator& last, Function fn)
    {
        if (reverse) {
            return std::for_each(std::reverse_iterator<InputIterator>(last), std::reverse_iterator<InputIterator>(first), fn);
        }
        return std::for_each(first, last, fn);
    }

}

... then you can use it as simple as that:

auto start = ...
auto end = ...
bool reverse = ...
mani::for_each_reverse(reverse, start, end, [&](const MyItem& item) {
    ...
});

If reverse is false, it will iterate over the items in normal direction. If reverse is true, it will iterate backwards over the items.

回答6:

What you need is to make your own iterator wrapper. I can think of three approaches:

• One that acts like like a union of two iterator types; it has two iterator members of different types, and a flag choosing which one is active.

• One that contains a single bidirectional iterator, and a flag indicating whether to operate in the forward or reverse direction.

• Some sort of generic iterator thing with virtual functions. (inefficient, but probably straightforward to write)