cpp iterator inheritance

Question

My requirements are same to the question asked Using Iterators to hide internal container and achieve generic operation over a base container[1] at stackoverflow. I have a generic pure virtual base container class, which needs to provide an iterator which should be STL complaint so I can use them with cpp algorithm's #include <algorithm>. My implementation uses only an single class instead of two classes as in [1] solution.

Base pure virtual class

class BaseItr
{
  public:
    class iterator : public std::iterator<std::input_iterator_tag, int>
    {
      public:
        iterator() : _in(NULL) {}
        inline iterator(const iterator& org) : _in(org._in) {}
        inline iterator& operator=(const iterator& other) { _in = other._in; return *this; }
        virtual inline int operator * () { return _in->operator*(); }
        virtual inline iterator& operator++() { (*_in)++; return *this; }
        virtual inline iterator& operator++(int unused) { (*_in)++; return *this; }
        virtual inline bool operator==(const iterator& other) 
        {
          return *(*_in) == *(*(other._in));
        }
        virtual inline bool operator!=(const iterator& other)
        {
          return *(*_in) != *(*(other._in));
        }
        // would use shared pointer insted of this
        //~iterator() { if(_in) { delete _in; } }
        static inline iterator New(iterator *in) { return iterator(in); }
      private:
        iterator(iterator *in) : _in(in) {}
        iterator *_in;
    };

    virtual iterator begin() = 0;
    virtual iterator end() = 0;
};

Implementation

class Itr : public BaseItr
{
  private:
    class iterator : public BaseItr::iterator
    {
      public:
        iterator(int val) : _val(val), BaseItr::iterator() {}
        int operator * () { return _val; }
        inline iterator& operator++() { ++_val; return *this; }
        inline iterator& operator++(int unused) { _val++; return *this; }
      private:
        int _val;
    };
    BaseItr::iterator _begin;
    BaseItr::iterator _end;
  public:
    inline Itr(int start, int end)
    {
      _begin = BaseItr::iterator::New(new iterator(start));
      _end = BaseItr::iterator::New(new iterator(end));
    }

    BaseItr::iterator begin() { return _begin; }
    BaseItr::iterator end() { return _end; }
};

My implementation works was need, I want to know are there any drawbacks with this implementation, Please help me decide with my design to use the appropriate implementation. I have add my full working example code in github:gist https://gist.github.com/3847688

Ref:

score 5 · Accepted Answer · answered Oct 07 '12 at 11:04

5

The most glaring issue: your iterator does not have value semantics.

The STL algorithms are free to copy an iterator if they wish. For example suppose:

template <typename It>
It find(It b, It e, typename std::iterator_traits<It>::const_reference t) {
    for (; b != e; ++b) {
        if (*b == t) { return b; }
    }
    return e;
}

The problem is that if you invoke this algorithm with BaseItr&, then the result is of type BaseItr, and you are thus exposed to Object Slicing, which is undefined behavior.

In order to give value semantics to you iterator, you need to create a wrapper class around an abstract implementation and have the wrapper correctly manage the copy through a virtual clone method. If your iterator ends up with virtual methods, you are doing it wrong.

answered Oct 07 '12 at 11:04

Matthieu M.

287,565
48
449
722

If the iterator is a wrapper for the abstract implementation don't we still face the _Object Splicing_?. As we can initialize the wrapper without an instance of the abstract class in it, if so how to prevent it. Can we use `std::unique_ptr` instead of a virtual `clone`. – Kam Oct 07 '12 at 15:00
2

"*If your iterator ends up with virtual methods, you are doing it wrong.*" I'd +1 this more than once if I could. – ildjarn Oct 07 '12 at 16:38
1

@Kam: `std::unique_ptr` deals with ownership, `clone` deals with copying. You can use both in conjunction. – Matthieu M. Oct 08 '12 at 06:14

cpp iterator inheritance

1 Answers1