19

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.

13
  • 3
    You can implement a filtering iterator quite easily in C++ without the iterator exposing any external polymorphism (Boost provides a generic filter iterator). Jan 31, 2011 at 15:37
  • 5
    @7vies: Matthie M's answer on that question uses smart pointers, but as an implementation detail, not in the interface. So I don't think your objection about simple/general interfaces applies. Btw, if you prefer polymorphic iterators over duck-typing with templates, can I recommend Java? ;-p Jan 31, 2011 at 15:48
  • 2
    @7vies: it exists, however the STL has enforced a very strict model of Iterator that is quite incompatible with the GOF model :/ Jan 31, 2011 at 15:58
  • 4
    @7vies: if you want mark-sweep GC then, again, can I recommend Java? Or you could try Boehm's GC for C++. C++ iterators are designed with value semantics, and Matthieu's answer over on that other question is the "correct" idiom to bridge between value semantics and runtime polymorphism. Smart pointers in that case manage the allocated resource exactly as required. I don't really know what "lame" is supposed to mean - smart pointers handle this case fine. So what's the problem? Jan 31, 2011 at 16:04
  • 3
    @7vies: "why would I need to use STL iterators for my containers if I'm not planning to use STL algrotihms on them anyway" - you don't have to use STL iterators. But you say you want to return by value, which means you have to implement value semantics. Which btw means using shared_ptr rather than unique_ptr, so that it's copyable, if you are starting from Matthieu's answer. Jan 31, 2011 at 16:06

6 Answers 6

10

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, " "));
}
20
  • Don't you find it clunky that we need "two" iterators to implement any "smart" behavior ? I feel that Stepanov confused the "pointer" concept with the "iterator" one, and having to pass two items to be able to iterate safely makes for messed up interfaces :/ Jan 31, 2011 at 16:01
  • Only if that "smart" behaviour involves skipping elements. Jan 31, 2011 at 16:09
  • @Matthieu: Yeah, it's pretty clunky. In my current project, I compose five filter, transform, and accumulation iterators in one place, and it makes me sad having to introduce a bunch of variables just to make the code readable (I don't have any runtime polymorphism, though; just lots and lots of compile-time polymorphism). Jan 31, 2011 at 16:10
  • 1
    @James McNellis: I'm also afraid that the things you "don't care" about will become a bottleneck in a big project - templates (at least in their current implementation) lead to quickly growing compilation dependencies, e.g. N*M cases for N algorithms on M types. With runtime polymorphism, it's only N cases applied to an interface which can be implemented by M types. And no implementation details.
    – Roman L
    Jan 31, 2011 at 17:26
  • 1
    @James McNellis: I guess that with 1M+ lines of code the top-level code is not template-based, or is it? Do you still have some non-templated abstractions, or is "everything a template"? I just don't understand how you manage to stop the "template snowball" so that it does not require to include 1M lines of code to compile a single expression?
    – Roman L
    Jan 31, 2011 at 18:01
4

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.

10
  • GoF iterators know about the termination condition (eg IsDone). They are not STL-compatible, but I really don't see why would I need to run STL algorithms on them. Unfortunately there is no unique_ptr for me (C++03) ;( but I can try to emulate it. However, I still don't see if this is really better than just using a smart pointer, as this is by definition more complicated than a smart pointer - you have one as a member, and you can't hide its implementation as it's template-based, the only thing you can "hide" is its interface.
    – Roman L
    Jan 31, 2011 at 16:49
  • You can use a plain scoped_ptr in C++03 (as you won't need move semantics). The main advantage compared to a "single" smart pointer is that you can provide a reduced set of operations to override and then combine them in a lot of ways in the Iter class to provide a "true" interface (ie, usable by .). As for smart pointer being template-based... I think you're biaised ;) Jan 31, 2011 at 16:59
  • @Matthieu M.: In which sense am I biased? :) I don't hate templates if you mean that. I only mentioned that this option is not an alternative to smart pointers but more like a wrapper on top of smart pointers, so it implies all possible issues related to smart pointers, not less.
    – Roman L
    Jan 31, 2011 at 17:06
  • @7vies: It implies the technical issues of smart pointers... but hides the functional ones (since they're wrapped). I don't know which technical issues a scoped_ptr has, for example. Anyway, you can always recode the smart pointer logic if you wish. The Pimpl idiom does not require their use, it merely ease the task to employ them, because they work. Jan 31, 2011 at 17:36
  • @Matthieu M.: A possible "technical" issue of scoped_ptr is that you can't move it, only make a copy, while sometimes you actually want to move. I'm not sure what is a benefit of limiting access to the actual smart pointer that is used underneath, unless if this access somehow interfere with the functionality of the iterator itself... And by "recode" the smart pointer - do you mean creating my own smart pointers, instead of using the existing well-designed-and-tested ones?
    – Roman L
    Jan 31, 2011 at 17:48
3

It can be done using an iterator that contains a pointer in some form, and then passes on the functionality to the pointer.

You need to be very careful though doing this, and I have seen it done wrong many times (including falling for it myself once, then wondering why tests failed...)

  • Do not use shared_ptr!

Fortunately I have not seen anyone above make the mistake of using shared_ptr, but it has the wrong semantics as when you copy an iterator you have 2 separate copies. But if they contain a shared_ptr and you advance one of the iterators, the other one will move with it - unexpected behaviour...

Therefore you need to clone every time you copy, but fortunately with C++0x you can just move much of the time rather than clone.

You also need to know that operations will hit the v-table for each iteration which may cause it to run slower than if you made the "macro" methods polymorphic (and implement perhaps with a template so you don't need to rewrite the code).

1
  • Thanks for raising the shared_ptr issue, good to have it in mind.
    – opetroch
    Mar 22, 2017 at 23:49
2

A good solution I saw linked on Oli Charlesworth's question that didn't get much credit (at least, not as much as I thought it should).

class Iterator
{
public:
    SmartPointer<IteratorImplementation> ItrPtr;

    //Delegate methods to ItrPtr
}

You can then pass Iterator by value and defer methods to the contained smart pointer; It is basically an iterator that implements the 'Strategy' pattern, and the strategy exhibits the polymorphic behavior.

3
  • Looks like pimpl. The ugly thing about pimpl is the "delegate methods" part... And it is quite the same thing as a smart pointer.
    – Roman L
    Jan 31, 2011 at 15:50
  • @7vies: Right, but the user doesn't know they are dealing with a smart pointer, only an iterator. Seemed cleaner to me than just passing back smart pointers to iterators...
    – James
    Jan 31, 2011 at 15:57
  • @7vies: actually it's not the same. I've added more context in my own answer below, but the thing is that iterators have lots of redundancy in the methods they provide (variations on ++ for example) and thus you can actually reduce the number of methods to be overriden by the implementation of the IterImpl class. Jan 31, 2011 at 16:10
0

People do say that interfaces should be as simple and as general as possible. In your case, you describe a raw pointer as something that is not 'possible'. So, I'd suggest your obvious solution of using a smart pointer is the most simple and general technique that is possible.

To keep this smart pointer as simple and general as possible, I'd go with one of the stl provided smart pointers as they are the most ubiquitous.

0

Been there. Done that.

What you can do is hide your iterator interface behind another iterator. Suppose that you have several kind of iterators that all hide behind the IIterator interface.

Then write another Iterator-like class, e.g. MyIterator, which contains a pointer to IIterator, and which simply forwards all calls to IIterator, like this:

template <typename T>
class MyIterator
    {
    public:
       MyIterator() : m_iterator(nullptr) {}
       MyIterator(IIterator *it) : m_iterator(it) {}
       MyIterator &operator++()
          {
          if (m_iterator) m_iterator->operator++();
          return *this;
          }
       T &operator*() const
          {
          if (m_iterator) return m_iterator->operator*();
          else            throw an exception?
          }
    private
       IIterator *m_iterator;
    };

This example is far from complete, but you should get the idea.

1
  • 1
    It will have to manage lifetime somehow, so it's always the same smart pointer solution...
    – Roman L
    Jan 31, 2011 at 17:09

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.