How to parametrize on iterator direction?

Question

Basically I'm doing the following:

std::set<int> indices;
// ..fill indices

if (flag)
{
   // we need to process in ascending order
   BOOST_FOREACH (int i, indices) 
   {
      process(i);
   }
}
else
{
   // we need to process in descending order
   BOOST_REVERSE_FOREACH (int i, indices) 
   {
      process(i);
   }
} 

I wonder if there's a way to write the same thing in C++03 with just one call to process(i), somehow parametrizing on the processing order? Like this (which obviously doesn't work even in C++0x because begin() and rbegin() return different types):

   auto iter = flag ? indices.begin() : indices.rbegin();
   auto end =  flag ? indices.end() : indices.rend();

   BOOST_FOREACH (int i, std::make_pair(iter, end)) 
   {
      process(i);
   }

Answer 1

What you want can be implemented with Boost.Variant.

The idea is to define a new type of iterator which stores a variant (think of it like a C union on steroids) containing either a forward or reverse iterator:

template<class InputRange>
struct any_dir_iterator
: std::iterator_traits<typename boost::range_iterator<InputRange>::type> {

    typedef typename boost::range_iterator<InputRange>::type forward_iterator;
    typedef typename 
        boost::range_reverse_iterator<InputRange>::type reverse_iterator;

    typedef boost::variant<forward_iterator, reverse_iterator> iterator_type;

    iterator_type current_it, end_it;

    any_dir_iterator(InputRange & input_range, 
                     bool fwd = true, 
                     bool end = false) 
    {
        end_it = fwd ? iterator_type(boost::end(input_range)) 
                     : iterator_type(boost::rend(input_range));

        if(end)
            current_it = end_it;
        else
            current_it = fwd ? iterator_type(boost::begin(input_range)) 
                             : iterator_type(boost::rbegin(input_range));
    }

    reference operator*() const {
        return boost::apply_visitor(dereference_visitor<any_dir_iterator>(), 
                                    current_it);
    }

    any_dir_iterator & operator++() {
        boost::apply_visitor(increment_visitor<any_dir_iterator>(), 
                             current_it);
        return *this;
    }

    bool operator==(any_dir_iterator const & rhs) {
        return boost::apply_visitor(equals_visitor<any_dir_iterator>(), 
                                    current_it, rhs.current_it);
    }    
};

This is similar to Adobe's any iterator but much less general, which means that it will have virtually no performance overhead when compared to a plain iterator.

As you can see in the code above, all the logic is delegated to static visitors which we define as follows:

template<class AnyDirIterator>
struct dereference_visitor 
: boost::static_visitor<typename AnyDirIterator::iterator_type> {

    typedef typename AnyDirIterator::reference result_type;

    template<class FwdOrRevIterator>
    result_type operator()(FwdOrRevIterator const & it) const { 
        return *it; 
    }
};

template<class AnyDirIterator>
struct increment_visitor 
: boost::static_visitor<typename AnyDirIterator::iterator_type> {

    typedef void result_type;

    template<class FwdOrRevIterator>
    result_type operator()(FwdOrRevIterator & it) const {
        ++it;
    }
};

template<class AnyDirIterator>
struct equals_visitor 
: boost::static_visitor<typename AnyDirIterator::iterator_type>
{
    typedef bool result_type;

    template <typename FwdOrRevIterator>
    bool operator()(FwdOrRevIterator const & lhs, 
                    FwdOrRevIterator const & rhs) const {
        return lhs == rhs;
    }

    template <typename T, typename U>
    bool operator()( const T &, const U & ) const {
        return false; // comparing fwd to rev or vice-versa
    }
};

That was the tricky part. But we still have to make this more convenient to use, for which we define a helper function that relies on the functionality provided by the Boost.Range library:

template<class InputRange>
boost::iterator_range<any_dir_iterator<InputRange> > 
make_any_dir_range(InputRange & range, bool forward=true) {
    typedef any_dir_iterator<InputRange> iterator;
    return boost::make_iterator_range(iterator(range, forward),
                                      iterator(range, forward, true));
}

And that is all. Now you can write:

int main() {

    int items[] = { 1, 2 };
    typedef std::vector<int> container_type;
    container_type container(items, items + sizeof(items)/sizeof(items[0]));

    BOOST_FOREACH(int i, make_any_dir_range(container, true))
        std::cout << i << " ";

    std::cout << "\n";
    BOOST_FOREACH(int i, make_any_dir_range(container, false))
        std::cout << i << " ";

    return 0;
}

Which prints:

1 2
2 1

This works with const containers as well, although I haven't shown that possibility in the main function.

Another nice thing which results from using Boost.Range is that this works with arrays out of the box. So you can do this:

int items[] = { 1, 2 };

BOOST_FOREACH(int i, make_any_dir_range(items, true)) // Prints "1 2"
    std::cout << i << " ";

Too keep this answer short I've left a few things unimplemented (but they're all boilerplate, not requiring new visitors):

• The postfix increment operator
• The != operator
• The -> operator

Here's all the code in Codepad. Due to the "treat warnings as errors" policy Codepad won't swallow it but both VS2008 and GCC 4.4 compile it OK in my local machine.

UPDATE

I've made some tests and apparently boost::variant does introduce some runtime overhead: a BOOST_FOREACH-based loop like the one in the main function runs about 4 times slower (when compiled in release mode) than the equivalent version using a plain iterator. It would be interesting to check whether this is best or worst than the overhead introduced by Adobe's any_iterator.

Answer 2

Well the obvious one is to make a class which handles the logic of this situation, either through storing a flag, or using polymorphism. However, it would at best be "hiding" the if statement.