polymorphic iterators in C++

Question

I'm trying to implement a polymorphic iterator in C++. Basically, I need this to be able to apply a filter, so that the iterator would skip some items depending on the associated condition. So I made a GoF-like iterator with an abstract interface, this allows me to derive a filtered iterator from it and implement the required logic. I also prefer interface-based iterators over templated ones as they allow to hide implementation without leading to a mess of duck-typed templates.

However, polymorphic iterators cannot be returned by value (as opposed to STL iterators), so I have to pass pointers around, and this can easily become dangerous like in this case, which seems logical but leads to a memory leak:

Iter* Collection::GetIter() {...} // new IterImpl
DoSomething(Iter*) {...} // doesn't do delete

DoSomething(Collection.GetIter()); // convenient, but wrong :\

The obvious solution is to use some kind of smart pointers to control iterators lifetime, but people often say that interfaces should be as simple and as general as possible, so smart pointers should probably be avoided there?

If you have worked with polymorphic iterators in C++, how was this issue resolved? Or are template-based iterators the only "good" way of iteration in C++? Thanks.

Answer 1

The usual approach is to use compile-time polymorphism instead of runtime polymorphism; this allows the compiler many more opportunities to optimize code using the iterator and generally is more idiomatic in modern C++.

If you do need runtime polymorphic behavior, it's probably easiest to encapsulate the polymorphism within the iterator itself and not expose it externally. You can accomplish this using a polymorphic function wrapper like function, found in Boost, C++ TR1, and C++0x. I've provided an example here based on a filter iterator from one of my hobby projects:

template <typename ForwardIt>
class filter_iterator
    : public std::iterator<
          std::forward_iterator_tag, 
          typename std::iterator_traits<ForwardIt>::value_type>

{
public:

    typedef typename std::iterator_traits<ForwardIt>::value_type ValueType;
    typedef typename std::function<bool(ValueType)> FunctionType;

    filter_iterator() { }

    explicit filter_iterator(ForwardIt end)
        : it_(end), end_(end) 
    {
    }

    filter_iterator(ForwardIt it, ForwardIt end, FunctionType is_filtered) 
        : it_(it), end_(end), is_filtered_(is_filtered)
    { 
        skip_filtered_elements(); 
    }

    const ValueType& operator*()  const { return it_.operator*();  }
    const ValueType* operator->() const { return it_.operator->(); }

    filter_iterator& operator++()   
    { 
        ++it_; skip_filtered_elements(); return *this; 
    }

    filter_iterator operator++(int) 
    { 
        filter_iterator it(*this); ++*this; return it; 
    }


    friend bool operator==(const filter_iterator& lhs,
                           const filter_iterator& rhs)
    {
        return lhs.it_ == rhs.it_;
    }

    friend bool operator!=(const filter_iterator& lhs,
                           const filter_iterator& rhs)
    {
        return !(lhs == rhs);
    }

private:

    void skip_filtered_elements()
    {
        while (it_ != end_ && is_filtered_(*it_))
            std::advance(it_, 1);
    }

    ForwardIt it_;
    ForwardIt end_;

    std::function<bool(const ValueType&)> is_filtered_;
};

template <typename ForwardIt>
filter_iterator<ForwardIt> make_filter_iterator(ForwardIt end)
{
    return filter_iterator<ForwardIt>(end);
}

template <typename ForwardIt, typename Function>
filter_iterator<ForwardIt> make_filter_iterator(ForwardIt it, 
                                                ForwardIt end, 
                                                Function f)
{
    return filter_iterator<ForwardIt>(it, end, f);
}

Usage is straightforward. This example (using a C++0x lambda expression as the function type) demonstrates filtering odd numbers from a range:

int main()
{
    std::array<int, 4> x = { 1, 2, 3, 4 };

    std::copy(make_filter_iterator(x.begin(), x.end(), [](int i) { return i % 2; }),
              make_filter_iterator(x.end()),
              std::ostream_iterator<int>(std::cout, " "));
}

Answer 2

There are two issues here:

• syntax: the STL assumes that iterators provide traits (value_type, reference for example) which need match the actual item.
• semantics: the iterators shall be copyable.

Remember that (in C++) an iterator is not a range, and therefore the ++ operation quickly gets messy, because you need to skip over some items, but (with a traditional implementation) you cannot know how many items are at your disposal...

Therefore, if you want polymorphic iterators which follow the GOF interface, you'll have to forgo the use of STL algorithms.

That said, it's perfectly feasible to implement polymorphic iterators:

struct IterBase
{
  virtual void increment() = 0;
  virtual void decrement() = 0;

  // others
};

class Iter
{
public:
  Iter& operator++() { base->increment(); return *this; }
  Iter operator++(int) { Iter tmp(*this); base->increment(); return tmp; }

  // others

private:
  std::unique_ptr<IterBase> base;
};

And then you'll need to write all the copy constructors, assignment operators and destructors to do the right thing...

Without template polymorphism though, it's only worth it if your iterator is only ever meant to be used on the same type...