By Robin Hsu


2019-05-14 15:07:05 8 Comments

I want to achieve something like the pseudo-code below:

string foo;  // or vector<int> foo;
auto itr = bar?  foo.begin() : foo.rbegin();
auto end = bar?  foo.end() : foo.rend();
for (  ; itr != end; ++itr) {
// SomeAction ...
}

That is, I want to set itr to be either a forward iterator or the reverse iterator, depending on some condition bar, to scan in forward or reverse direction.

Apparently code like that won't work, since forward iterator and reverse iterator has different type.

Note that I don't want to split into two loops, as those code like // SomeAction will be duplicated.

How can I do that? Answers using C++11 and/or before are preferred.

Also, please elaborate if string and vector have different solutions.

5 comments

@eerorika 2019-05-14 15:33:18

One option is to to write a function template for the loop that works with any iterator. Then conditionally call one instance of the template or another. The other answers already show examples of how to do that.

By the way, the loop template might already exist in <algorithm> header depending on what you're doing. You could possibly use (but are not limited to) either std::for_each, std::accumulate or std::remove for example:

auto body = [captures,needed,by,some,action](char c) {
    // SomeAction ...
};
if (bar)
    std::for_each(foo.begin(),  foo.end(),  body);
else
    std::for_each(foo.rbegin(), foo.rend(), body);

If the body of the loop is reusable beyond this context, then you could use a named function as well, but only if you don't need captures. With captures, you can use a named functor type, but that involves quite a bit boilerplate.


Another option is to use a type erasing iterator adaptor. It comes with a small runtime cost, and is probably not necessary here. But it is useful to mention in case people have a closely related problem where it is a better fit.

Essentially, such adaptor is to templated iterator what std::function is to a templated functor argument. It removes the need for templates, which can be useful for abstract interfaces in particular. Unfortunately though, the standard library doesn't provide such iterator adaptor.

An alterantive for an iterator adaptor is a range adaptor (also not in standard library):

using t_erase = boost::adaptors::type_erased<>;
auto range = bar
    ? boost::make_iterator_range(foo.begin(),  foo.end())  | t_erase()
    : boost::make_iterator_range(foo.rbegin(), foo.rend()) | t_erase();
for(char c : range) {
    // SomeAction ...
}

@J. Antonio Perez 2019-05-14 21:20:24

Use an iterator class that abstracts this funtionality.

An iterator has 3 basic functions:

  • Increment
  • Dereference
  • Check for equality

We can use these as guidelines in creating an interface which abstracts this behavior. This interface is a bit cumbersome to use on it's own, but we can use it to build a wrapper class, GenericIterator, that can automatically be assigned any other iterator type.

GenericIterator: A ready-made general purpose solution

It's possible to write a GenericIterator class that can be assigned iterators from pretty much any collection, including the reverse iterators.

int main() {
    bool iterate_forward;
    std::cin >> iterate_forward; 

    std::vector<int> values { 1, 2, 3 };

    GenericIterator<int&> begin, end; 

    if(iterate_forward) {
        begin = values.begin(); 
        end = values.end(); 
    } else {
        begin = values.rbegin();
        end = values.rend(); 
    }

    // Print out the values
    for(; begin != end; ++begin) {
        std::cout << *begin << " ";
    }
}

You can download the entirety of the code from this github repo, which I'll be updating and improving as needed.

Remarks on performance GenericIterator

In terms of functionality, GenericIterator gives you everything you could possibly ask for. It's light-weight; and it's convenient; and it's easy to re-purpose if your code needs to read from a std::list or something other than a vector.

However, due to the fundamental limitations of runtime polymorphism, it's significantly more difficult for the compiler to inline the virtual method calls. This means that GenericIterator carries more runtime overhead than other solutions.

It's a good idea to favor static polymorphism and templates over runtime polymorphism when possible. If you're able to do so, use something like Mark B's solution, which will ultimately be more performant.

Appendix

Iterator interface definition. This class is used to implement GenericIterator. A GenericIterator contains a pointer to IteratorBase, which is used to achieve the runtime polymorphism. Thanks to the clone() method, GenericIterator remains both copyable and movable as expected.

template <class Value>
class IteratorBase
{
   public:
    virtual Value         operator*() const                     = 0;
    virtual IteratorBase& operator++()                          = 0;
    virtual bool          operator!=(IteratorBase const&) const = 0;
    virtual bool          operator==(IteratorBase const&) const = 0;

    // We need this function for making copies of the iterator
    virtual IteratorBase* clone() const = 0;
    virtual ~IteratorBase()             = default;
};

Concrete class implementing IteratorBase. This class implements the behavior defined in IteratorBase. The iterator it contains is the actual iterator returned by the collection you're iterating over. In your case, it'd be either std::vector::iterator or std::vector::reverse_iterator.

template <class Iter, class Value>
class IteratorDerived : public IteratorBase<Value>
{
    Iter it;

   public:
    IteratorDerived() = default;
    IteratorDerived(Iter it) : it(it) {}
    IteratorDerived(IteratorDerived const&) = default;
    IteratorDerived(IteratorDerived&&)      = default;

    Value                operator*() const override { return *it; }
    IteratorBase<Value>& operator++() override
    {
        ++it;
        return *this;
    }

    bool operator!=(IteratorBase<Value> const& other) const override
    {
        auto* derived = dynamic_cast<IteratorDerived const*>(&other);
        return derived == nullptr || it != derived->it;
    }
    bool operator==(IteratorBase<Value> const& other) const override
    {
        auto* derived = dynamic_cast<IteratorDerived const*>(&other);
        return derived != nullptr && it == derived->it;
    }
    IteratorBase<Value>* clone() const override
    {
        return new IteratorDerived(*this);
    }
};

GenericIterator implementation. This is the actual implementation of GenericIterator, based on IteratorBase and IteratorDerived. Any iterator given to GenericIterator is wrapped in the corresponding IteratorDerived, which is then assigned to the IteratorBase pointer.

template <class Value>
class GenericIterator
{
    std::unique_ptr<IteratorBase<Value>> iterator;

   public:
    using value_type = typename std::remove_reference<Value>::type; 
    using reference = Value;

    GenericIterator() = default;
    GenericIterator(GenericIterator const& it) : iterator(it.iterator->clone())
    {
    }
    GenericIterator(GenericIterator&&) = default;

    // Creates a GenericIterator from an IteratorBase
    explicit GenericIterator(IteratorBase<Value> const& it)
      : iterator(it.clone())
    {
    }

    // Creates a GenericIterator from an IteratorDerived
    template <class Iter>
    explicit GenericIterator(IteratorDerived<Iter, Value> const& it)
      : iterator(it.clone())
    {
    }

    // Creates a GenericIterator by wrapping another Iter
    template <class Iter>
    GenericIterator(Iter it) : iterator(new IteratorDerived<Iter, Value>(it))
    {
    }

    GenericIterator& operator=(GenericIterator const& it)
    {
        iterator = std::unique_ptr<IteratorBase<Value>>(it.iterator->clone());
        return *this;
    }
    GenericIterator& operator=(GenericIterator&&) = default;

    Value            operator*() const { return *(*iterator); }
    GenericIterator& operator++()
    {
        ++(*iterator);
        return *this;
    }
    void operator++(int) {
        ++(*iterator);
    }

    bool operator==(GenericIterator const& other) const
    {
        return *iterator == *other.iterator;
    }
    bool operator!=(GenericIterator const& other) const
    {
        return *iterator != *other.iterator;
    }
};

@HolyBlackCat 2019-05-14 15:15:12

I don't want to split into two loops, as those code like // SomeAction will be duplicated.

Put the action into a lambda.

auto lambda = [&](char &val) // `ElementType &`
{
    // ...
};

if (bar)
{
    for (auto &val : foo)
        lambda(val);
}
else
{
    for (auto it = foo.rbegin(); it != foo.rend(); it++)
        lambda(*it);
}

Alternatively, use indices rather than iterators. This will only work with containers that allow random access.

std::size_t i, end, step;
if (bar)
{
    i = 0;
    end = foo.size();
    step = 1;
}
else
{
    i = foo.size() - 1;
    end = -1;
    step = -1;
}

for (; i != end; i += step)
{
    // ...
}

@Fire Lancer 2019-05-14 15:17:59

Unfortunately, not a C++11 feature as the question was specifically tagged :(

@HolyBlackCat 2019-05-14 15:23:37

@FireLancer Forgot it was a C++14 thing, fixed.

@Fire Lancer 2019-05-14 15:14:45

The forward and reverse iterators are different types for most if not all containers, so unfortunately if it is a runtime decision, they can not simply be assigned to the same variable through the use of auto.

One option is to move the use of them into a template function:

template<class Iterator> void loop(Iterator begin, Iterator end)
{
    for (auto itr = begin; itr != end; ++itr) { ... }
}

if (bar) loop(foo.begin(), foo.end());
else loop(foo.rbegin(), foo.rend());

In newer versions of C++ (C++14 and newer, so not C++11) the loop function can be a lambda, by using auto as the parameter type.

auto loop = [](auto begin, auto end)
{
    for (auto itr = begin; itr != end; ++itr) { ... }
};

Another option, although somewhat more involved would be to make a wrapper type that can contain either an iterator or reverse iterator, and acts like an iterator itself with at least the comparison, increment and dereference operators.

@Mark B 2019-05-14 15:14:58

I would put the logic in a two-iterator function:

<template typename Iter>
void do_stuff(Iter first, Iter last)
{
    for(; first != last; ++first)
    {
        // Do logic
    }
}

bar ? do_stuff(foo.begin(), foo.end()) : do_stuff(foo.rbegin(), foo.rend());

@moooeeeep 2019-05-15 09:28:55

This function should probably be std::for_each().

@Mark B 2019-05-15 17:00:57

In simple cases that would definitely be better; I was (for no particular reason) assuming the logic was potentially more complicated where writing out the loop might make it clearer.

Related Questions

Sponsored Content

14 Answered Questions

[SOLVED] How can I profile C++ code running on Linux?

  • 2008-12-17 20:29:24
  • Gabriel Isenberg
  • 463099 View
  • 1639 Score
  • 14 Answer
  • Tags:   c++ unix profiling

76 Answered Questions

[SOLVED] How do I iterate over the words of a string?

  • 2008-10-25 08:58:21
  • Ashwin Nanjappa
  • 2103231 View
  • 2816 Score
  • 76 Answer
  • Tags:   c++ string split

13 Answered Questions

[SOLVED] What is the effect of extern "C" in C++?

28 Answered Questions

[SOLVED] Easiest way to convert int to string in C++

21 Answered Questions

[SOLVED] What is the "-->" operator in C++?

24 Answered Questions

[SOLVED] Why do we need virtual functions in C++?

10 Answered Questions

35 Answered Questions

1 Answered Questions

[SOLVED] The Definitive C++ Book Guide and List

  • 2008-12-23 05:23:56
  • grepsedawk
  • 2131432 View
  • 4248 Score
  • 1 Answer
  • Tags:   c++ c++-faq

Sponsored Content