Returning an 'any kind of input iterator' instead of a vector::iterator or a list::iterator

Question

Suppose I want to implement in C++ a data-structure to store oriented graphs. Arcs will be stored in Nodes thanks to STL containers. I'd like users to be able to iterate over the arcs of a node, in an STL-like way.

The issue I have is that I don't want to expose in the Node class (that will actually be an abstract base class) which STL container I will actually use in the concrete class. I therefore don't want to have my methods return std::list::iterator or std::vector::iterator...

I tried this:

class Arc;

typedef std::iterator<std::random_access_iterator_tag, Arc*> ArcIterator;  // Wrong!

class Node {
public:
  ArcIterator incomingArcsBegin() const {
    return _incomingArcs.begin();
  }
private:
  std::vector<Arc*> _incomingArcs;
};

But this is not correct because a vector::const_iterator can't be used to create an ArcIterator. So what can be this ArcIterator?

I found this paper about Custom Iterators for the STL but it did not help. I must be a bit heavy today... ;)

Answer 1

If you really don't want the client's of that class to know that it uses a vector underneath, but still want them to be able to somehow iterate over it, you most likely will need to create a class that forwards all its methods to std::vector::iterator.

An alternative would be to templatize Node based on the type of container it should use underneath. Then the clients specifically know what type of container it is using because they told them to use it.

Personally I don't think it usually makes sense to encapsulate the vector away from the user, but still provide most (or even some) of its interface. Its too thin of an encapsulation layer to really provide any benefit.

Answer 2

I want to think there should be a way to do this through straight STL, similar to what you are trying to do.

If not, you may want to look into using boost's iterator facades and adaptors where you can define your own iterators or adapt other objects into iterators.

Answer 3

Try this:

class Arc;
class Node {
private:
  std::vector<Arc*> incoming_;
public:
  typedef std::vector<Arc*>::iterator iterator;
  iterator incoming_arcs_begin()
  { return incoming_.begin(); }
};

And use Node::iterator in the rest of the code. When/if you change the container, you have to change the typedef in a single place. (You could take this one step further with additional typedef for the storage, in this case vector.)

As for the const issue, either define vector's const_iterator to be your iterator, or define double iterator types (const and non-const version) as vector does.

Answer 4

I looked in the header file VECTOR.

vector<Arc*>::const_iterator

is a typedef for

allocator<Arc*>::const_pointer

Could that be your ArcIterator? Like:

typedef allocator<Arc*>::const_pointer ArcIterator;

Answer 5

I asked a similar question awhile back

Answer 6

To hide the fact that your iterators are based on std::vector<Arc*>::iterator you need an iterator class that delegates to std::vector<Arc*>::iterator. std::iterator does not do this.

If you look at the header files in your compiler's C++ standard library, you may find that std::iterator isn't very useful on its own, unless all you need is a class that defines typedefs for iterator_category, value_type, etc.

As Doug T. mentioned in his answer, the boost library has classes that make it easier to write iterators. In particular, boost::indirect_iterator might be helpful if you want your iterators to return an Arc when dereferenced instead of an Arc*.

Answer 7

You could templatize the Node class, and typedef both iterator and const_iterator in it.

For example:

class Arc {};

template<
  template<class T, class U> class Container = std::vector,
  class Allocator = std::allocator<Arc*>
>
class Node
{
  public:
    typedef typename Container<Arc*, Allocator>::iterator ArcIterator;
    typedef typename Container<Arc*, Allocator>::Const_iterator constArcIterator;

    constArcIterator incomingArcsBegin() const {
      return _incomingArcs.begin();
    }

    ArcIterator incomingArcsBegin() {
      return _incomingArcs.begin();
    }
  private:
    Container<Arc*, Allocator> _incomingArcs;
};

I haven't tried this code, but it gives you the idea. However, you have to notice that using a ConstArcIterator will just disallow the modification of the pointer to the Arc, not the modification of the Arc itself (through non-const methods for example).

Answer 8

C++0x will allow you do this with automatic type determination.

In the new standard, this
for (vector::const_iterator itr = myvec.begin(); itr != myvec.end(); ++itr
can be replaced with this
for (auto itr = myvec.begin(); itr != myvec.end(); ++itr)

By the same token, you will be able to return whatever iterator is appropriate, and store it in an auto variable.

Until the new standard kicks in, you would have to either templatize your class, or provide an abstract interface to access the elements of your list/vector. For instance, you can do that by storing an iterator in member variable, and provide member functions, like begin() and next(). This, of course, would mean that only one loop at a time can safely iterate over your elements.

Answer 9

Have a look at Adobe's any_iterator: this class uses a technique called type erase by which the underyling iterator type is hidden behind an abstract interface. Beware: the use of any_iterator incurs a runtime penalty due to virtual dispatching.

Answer 10

Well because std::vector is guaranteed to have contiguous storage, it should be perfect fine to do this:

class Arc;
typedef Arc* ArcIterator;

class Node {
public:
    ArcIterator incomingArcsBegin() const {
     return &_incomingArcs[0]
    }

    ArcIterator incomingArcsEnd() const {
     return &_incomingArcs[_incomingArcs.size()]
    }
private:
    std::vector<Arc*> _incomingArcs;
};

Basically, pointers function enough like random access iterators that they are a sufficient replacement.

Answer 11

Consider using the Visitor Pattern and inverting the relationship: instead of asking the graph structure for a container of data, you give the graph a functor and let the graph apply that functor to its data.

The visitor pattern is a commonly used pattern on graphs, check out boost's graph library documentation on visitors concepts.