C++ Iterator, Why is there no Iterator base class all iterators inherit from

Question

I am learning for an exam and I have a question which I am struggling to give and answer for.

Why does no iterator base class exist all other iterators inherit from?

My guess my teacher is referring to the hierarchical structure from the cpp reference "http://prntscr.com/mgj542" and we have to provide a other reason than why should they?

I know what iterators are (sort of) and that they are used to work on containers. From what I understand because of the different possible underlying datastructures, different containers have different iterators because you can randomly access an array, for example, but not a linked list and different containers require different ways of moving through them.

They are probably specialized templates depending on the container, right?

Answer 1

You've already gotten answers pointing to why it's not necessary for all iterators to inherit from a single Iterator base class. I'd got quite a bit further though. One of the goals of C++ is abstraction with zero run-time cost.

If iterators worked by all of them inheriting from a common base class, and used virtual functions in the base class to define the interface, and the derived classes provided implementations of those virtual functions, that could (and often would) add substantial run-time overhead to the operations involved.

Let's consider, for example, a simple iterator hierarchy that does use inheritance and virtual functions:

template <class T>
class iterator_base { 
public:
    virtual T &operator*() = 0;
    virtual iterator_base &operator++() = 0;
    virtual bool operator==(iterator_base const &other) { return pos == other.pos; }
    virtual bool operator!=(iterator_base const &other) { return pos != other.pos; }
    iterator_base(T *pos) : pos(pos) {}
protected:
    T *pos;
};

template <class T>
class array_iterator : public iterator_base<T> {
public: 
    virtual T &operator*() override { return *pos; }
    virtual array_iterator &operator++() override { ++pos; return *this; }
    array_iterator(T *pos) : iterator_base(pos) {}
};

Then let's give it a quick test:

int main() { 
    char input[] = "asdfasdfasdfasdfasdfasdfasdfadsfasdqwerqwerqwerqrwertytyuiyuoiiuoThis is a stringy to search for something";
    using namespace std::chrono;

    auto start1 = high_resolution_clock::now();
    auto pos = std::find(std::begin(input), std::end(input), 'g');
    auto stop1 = high_resolution_clock::now();

    std::cout << *++pos << "\n";

    auto start2 = high_resolution_clock::now();
    auto pos2 = std::find(array_iterator(input), array_iterator(input+sizeof(input)), 'g');
    auto stop2 = high_resolution_clock::now();

    std::cout << *++pos2 << "\n";

    std::cout << "time1: " << duration_cast<nanoseconds>(stop1 - start1).count() << "ns\n";
    std::cout << "time2: " << duration_cast<nanoseconds>(stop2 - start2).count() << "ns\n";
}

[note: depending on your compiler, you may need to do a bit more, such as defining the iterator_category, difference_type, reference, and so on, for the compiler to accept the iterator.]

And the output is:

y
y
time1: 1833ns
time2: 2933ns

[Of course, if you run the code, your results won't match these exactly.]

So, even for this simple case (and doing only about 80 increments and comparisons) we've added around 60% overhead to a simple linear search. Especially when iterators were originally added to C++, quite a few people simply wouldn't have accepted a design with that much overhead. They probably wouldn't have been standardized, and even if they had, virtually nobody would use them.

Answer 2

The difference is between What something is, and How something behaves.

A lot of languages try to conflate the two together, but they are quite distinct things.

If How is What, and What is How...

If everything inherits from object then some benefits occur like: any variable of object can hold any value ever. But that is also the rub, everything must behave (the how) like an object, and look like (the what) an object.

But:

• What if your object does not have a meaningful definition of equality?
• What if it does not have a meaningful hash?
• What if your object cannot be cloned, but objects can be?

Either the object type becomes essentially useless - due to object providing no commonality across all the possible instances. Or there will exist objects that have a broken/shoe-horned/absurd definition of some presumed universal property found on object which provies almost universal behaviour except for a number of gotchas.

If What is not bound up with How

Alternately you can keep the What and the How separate. Then several different Types (with nothing in common at all the what) can all behave in the same way as seen from the collaborator the how. In this sense the idea of an Iterator is not a specific what, but a how. Specifically How do you interact with a thing when you do not yet know What you are interacting with.

Java (and similar) allow approaches to this by using interfaces. An interface in this regard describes the means of communication, and implicitly a protocol of communication and action that is followed. Any What which declares itself to be of a given How, states that it supports the relevant communication and action outlined by the protocol. This allows any collaborator to rely on the How and not get bogged down by specifying exactly which What's can be used.

C++ (and similar) allow approaches to this by duck typing. A template does not care if the collaborating type declares that it follows a behaviour, just that within a given compilation context, that the object can be interacted with in a particular manner. This allows C++ pointers, and Objects over-riding specific operators to be used by the same code. Because they meet the check-list to be considered equivalent.

• supports *a, a->, ++a, and a++ -> input/forward iterator
• supports *a, a->, ++a, a++, --a, and a-- -> bidirectional iterator

The underlying type does not even have to be iterating a container, it could be any what. Additionally it allows some collaborators to be even more generic, imagine a function only needs a++, an iterator can satisfy that, so can a pointer, so can an integer, so could any object implementing operator++.

Under and Over Specification

The problem with both approaches is under and over specification.

Using an interface requires the object to declare it supports a given behaviour, which also means that the creator must imbue that from the beginning. This causes some What's to not make the cut, as they did not declare it. It also means that ever What has a common ancestor, the interface representing the How. This does circle back to the initial problem of object. This causes collaborators to over-specify their requirements, while simultaneously causing some objects to be either unusable due to a lack of declaration, or be hidden gotchas as an expected behaviour is poorly defined.

Using a template requires that the collaborator works with a completely unknown What, and through its interactions it defines a How. To some extent this makes writing collaborators harder, as it must analyse the What for its communication primitives (functions/fields/etc) while avoiding compilation errors, or at least point out how a given What does not match its requirements for the How. This allows the collaborator to require the absolute minimum from any given What, allowing the broadest range of what's to be used. Unfortunately this has the downside of allowing nonsensical uses of objects which technical provide the communication primitives for a given How, but do not follow the implied protocol allowing all sorts of bad things to occur.

Iterators

In this case an Iterator is a How it is shorthand for a description of interaction. Anything that matches that description is by definition an Iterator. Knowing How allows us to write general algorithms and have a short list of 'How's given a specific What' that need to be provided in order to make the algorithm work. That list are the function/properties/etc, their implementation takes into account the specific What that is being dealt with by the algorithm.

Answer 3

Because C++ doesn't need to have (abstract) base classes to do polymorphism. It has structural subtyping as well as nominative subtyping.

Confusingly in the particular case of Iterators, previous standards defined std::iterator as (approximately)

template <class Category, class T, class Distance = std::ptrdiff_t, class Pointer = T*, class Reference = T&>
struct iterator {
    using iterator_category = Category;
    using value_type = T;
    using difference_type = Distance;
    using pointer = Pointer;
    using reference = Reference;
}

I.e. as merely a provider of the required member types. It didn't have any runtime behaviour, and was deprecated in C++17

Note that even this can't be a common base, as a class template is not a class, each instantiation stands alone from the others.

Answer 4

One reason is that iterators don't have to be instances of a class. Pointers are perfectly good iterators in many cases, for example, and since those are primitives they can't inherit from anything.