CODEWITHSUNDEEP
c++iterator
Crazor
Crazor

Reputation: 328

How to choose iterator direction at runtime

I'd like to choose the direction to iterate over a container at runtime, like in the following sample code:

#include <iostream>
#include <vector>

void iterate(bool forward, std::vector<int> v) {
  auto start = v.begin();
  auto end = v.end();
  if (!forward) {
    start = v.rbegin(); // this doesn't
    end = v.rend();     // work
  }

  for (auto it = start; it != end; ++it) {
    std::cout << *it << " -> " << *std::next(it) << std::endl;
  }
  std::cout << std::endl;
}

int main() {
  std::vector<int> v{1, 2, 3, 4, 5};
  iterate(true, v);
  iterate(false, v);
}

How can I change the iterator direction at runtime, without duplicating the for loop?

Imagine the loop being a rather complex algorithm that you don't want to duplicate to avoid future maintenance issues. Note that I need access to the std::next/std::previous element in the loop body.

Upvotes: 1

Views: 402

Answers (3)

Crazor
Crazor

Reputation: 328

I'd like to show what I came up with after @Botje mentioned 'polymorphic lambdas'. I recently watched CppCon 2019: Arthur O'Dwyer “Back to Basics: Lambdas from Scratch” and I'm not quite sure if Arthur's 'Generic Lambdas' are what @Botje means, but the following code works just fine and is rather elegant IMHO:

#include <iostream>
#include <vector>

void iterate(bool forward, std::vector<int> v) {
  auto l = [](auto start, auto end){
    for (auto it = start; it != end; ++it) {
      std::cout << *it << " -> " << *std::next(it) << std::endl;
    }
  };

  if (forward) {
    l(v.begin(), v.end());
  } else {
    l(v.rbegin(), v.rend());
  }

  std::cout << std::endl;
}

int main() {
  std::vector<int> v{1, 2, 3, 4, 5};
  iterate(true, v);
  iterate(false, v);
}

Upvotes: 0

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275800

Some boilerplate. Some of the helper stuff has implementations in / std library. Parts of this implementation requires .

template<class It>
struct range_t {
  It b, e;
  It begin() const { return b; }
  It end() const { return e; }
  bool empty() const { return begin() == end(); }

  // in a real implementation, this should check if the iterators are
  // random access, and if so do the simple implementation.  I don't
  // want to use std::distance, because if n is small compared to the
  // distance from begin to end, that could get expensive.
  range_t except_last( std::size_t n = 1 ) const {
    if (n==0 || empty()) return *this;
    if (n==1) return { begin(), std::prev(end()) };
    return except_last((n-1)/2).except_last(1+(n-1)/2);
  }
};

template<class C>
auto range( C&& c ) {
  using std::begin; using std::end;
  return range_t{ begin(c), end(c) };
}

template<class C>
auto backwards( C&& c ) {
  using std::rbegin; using std::rend;
  return range_t{ rbegin(c), rend(c) };
}

template<class T>
struct index_iterator {
  using difference_type = std::ptrdiff_t;
  using value_type = T;
  using reference = T;
  T t;
  T operator*() const { return t; }
  T const* operator->() const { return std::addressof(t); }
  index_iterator& operator++() { ++t; return *this; }
  index_iterator operator++(int) { auto r = *this; ++t; r; }
  friend bool operator==(index_iterator const& lhs, index_iterator const& rhs) {
    return lhs.t==rhs.t;
  }
  friend bool operator!=(index_iterator const& lhs, index_iterator const& rhs) {
    return lhs.t!=rhs.t;
  }
};

template<class C>
auto iterators_into( C&& c ) {
  using std::begin; using std::end;
  return range_t{ index_iterator{begin(c)}, index_iterator{end(c)} };
}

template<class R, class Op>
void foreach_adjacent( R&& r, Op&& op ) {
  for( auto it : iterators_into( r ).except_last() ) {
    op( *it, *std::next(it) );
  }
}

This is the result of having that boilerplate around:

void iterate(bool forward, std::vector<int> v) {
  auto op = [](auto&& first, auto&& second) {
    std::cout << first << " -> " << second << std::endl;
  };
  if (forward) 
    foreach_adjacent( v, op ):
  else
    foreach_adjacent( backwards(v), op );
}

what is going on:

range_t is a wrapper for a non-owning range of elements using iterators.

backwards and range create forward and backwards range_ts based off an input container or range.

index_iterator is an input iterator over a range of iterators. With iterators_into, it lets you simply loop over a range of a container with a for(:) loop, but get the iterators not the elements at each step. (Note that index_iterator can also accept std::size_t instead of iterators; that is what I usually use it for. Both iterators and integers model the concepts it requires for its type argument.)

.except_last is a helper method on range_t that drops the last n (default 1) elements from the range.

foreach_adjacent iterates over the iterators of its input, dropping the last element, then calls op on each element and the one after it (which is guaranteed to exist, because we dropped the last element).

In our iterate function, we first write the body of the loop op, then we either visit adjacent elements forwards or backwards, calling op.

Upvotes: 2

NathanOliver
NathanOliver

Reputation: 180955

With a little bit of indirection, ie, using a helper function you can make a call to a template function that accepts the iterator types you want to loop with like

template<typename Iterator>
void iterate_helper(Iterator start, Iterator end)
{
    for (auto it = start; it != end; ++it) 
    {
        std::cout << *it << " -> " << *std::next(it) << std::endl;
    }
    std::cout << std::endl;
}

void iterate(bool forward, std::vector<int> v)
{
        if (!forward)
            iterate_helper(v.rbegin(), v.rend());
        else
            iterate_helper(v.begin(), v.end());
}

Just in case this example code is real code, do note that *std::next(it) in the for loop is going to go one past the end of the container. Your end condition needs to stop one before end to use it.

Upvotes: 7

Related Questions