How to parameterize an iterator direction?

Question

I basically do 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 is a way to write the same thing in C ++ 03 with only one process call (i), somehow parameterizing in the processing order? How is it (which obviously does not 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 using Boost.Variant .

The idea is to define a new type of iterator that stores a variant (think of it as a C-connection on steroids) containing either a direct 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 any iterator , but much less general, which means that it will have virtually no overhead compared to a regular iterator.

As you can see in the above code, all 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 hard part. But we still need to make it more convenient for 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 it's 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; } 

What prints:

 1 2 2 1 

This also works with constant containers, although I have not shown this feature in the main function.

Another nice thing that results from using Boost.Range is that it 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 << " "; 

The answer to this question is too short. I left a few unrealized things (but they are all templates that do not require new visitors):

• Postfix increment operator
• Operator! = Operator
• Operator →

Here is all the code in the encoder . Due to the "warn about warnings as errors" policy, Codepad will not swallow it, but both VS2008 and GCC 4.4 will compile it in my local machine.

UPDATE

I did some tests, and apparently boost::variant introduces some overhead at runtime: a BOOST_FOREACH , based on a loop like the one in the main function, runs about 4 times slower (when compiled in release mode ) than the equivalent version using a simple iterator. It would be interesting to check if this is better or worse than the overhead paid by Adobe any_iterator .

Answer 2

Well, the obvious is to create a class that handles the logic of this situation, either by storing the flag, or using polymorphism. However, at best, this will “hide” the if .