A common class type for all bidirectional iterators, c++

Question

I have a bunch of classes which implement geometric objects based on vertices, such as TriangleMesh, PointClouds or Edgesets. They all inherit from VertexBasedGeometry. I now want all of them to return a bidirectional iterator on references of its vertices. This would allow to access the vertices of any VertexBasedGeometry in a non-templated way. Now, me not being very familiar with iterators, this turns out to be rather difficult. My try looks as follows:

class VertexBasedGeometry : public Geometry
{
public:

typedef std::iterator<std::bidirectional_iterator_tag,defines::Vector3 >  VertexIterator;

VertexBasedGeometry(){};

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

In TraingleMesh, which inherits from VertexBasedGeometry I now try to implement the function begin by returning the begin iterator of the std::vector which contains its vertices. This results in the following compiler error on gcc 4.2 (apple):

Mesh.cpp:25: error: conversion from '__gnu_cxx::__normal_iterator<defines::Vector<double, 3>*, std::vector<defines::Vector<double, 3>, std::allocator<defines::Vector<double, 3> > > >' to non-scalar type 'std::iterator<std::bidirectional_iterator_tag, defines::Vector<double, 3>, long int, defines::Vector<double, 3>*, defines::Vector<double, 3>&>' requested

My question are now: Why does this not work, and how should I change this to get it work? Reading more about iterators, I got the slight feeling that I won't be able to find a common type for any bidirectional iterator, is that right? Some of the classes might have their vertices stored in containers other than std::vector, others already provide (non-stl-conforming ) iterators which I want to adapt to my common type. I am open for any recommendations how to implement this.

Answer 1

std::iterator is only a tag class that you derive from, and the type of your iterator must be known at compile-time to the implementing class. If you want to hide the iterator implementation from the iterating code, you must add an indirection level, e.g. Thomas Becker's any_iterator.

Answer 2

Iterators are only a loose concept, and real-life iterator classes aren't related in any sense. In general, you don't get around writing a complete iterator class for your class.

Iterators do share certain commonalities, and you have to design them so they can be probed with std::iterator_traits. This means that any given iterator implementation will have a lot of similar-looking code (and something like Boost's iterator facade may help). Nonetheless, your class's interface (like begin(), end() and find()) will have to return your own iterator type, and you have to write the iterator's implementation (i.e. increment and dereference operators).

Answer 3

BidirectionalIterator is not a class, it is a concept. A concept consists of a set of requirements and expressions with specified semantics. If a class fulfills all requirements of a concept it is said to be a model of this concept. That means that there is no common class for iterators of some concept as the stdlib doesn't work based on subtype polymorphism but on concepts.

So what is std::iterator? It's a helper to ease defining the traits of a specific iterator but it doesn't supply functionality. It only enables compile time meta-programming.

There are a few tools that help you implement your own classes that model a specific iterator like the Boost.Iterators.