What is an iterator in general?

Solution 1:

In C++ an Iterator is a concept, not a concrete (or abstract) type, but any type that obeys certain iterator like rules.

For example iterators generally can be incremented ++i. They can be accessed (dereferenced) *i to obtain the value they currently point to. They are essentially abstractions of a pointer.

In the Standard Library's containers & algorithms there are different kinds of iterators with different properties. Their properties are listed here:

https://en.cppreference.com/w/cpp/iterator

So when writing algorithms in C++ that accept iterators, generally just accept generic template parameters and use the appropriate iterator properties in the function. The compiler will complain if the user passes something to your function that doesn't obey the iterator rules:

template<typename Iterator>
void my_algorithm(Iterator begin, Iterator end)
{
    for(; begin != end; ++begin)
        std::cout << *begin << '\n';
}

You can add a whole bunch of specific checks to make sure the user passed something sensible, but that's too broad for this question.

Note:

Whilst currently concepts, such as Iterator, are merely a set of agreed upon semantic properties in the Standard that programmers must follow, a more comprehensive solution that will formalize such concepts (in code) is intended for the next version of the Standard, C++20.

Solution 2:

Iterators as a concept come from before C++ was a standard.

C++ started out as C with classes. More features where added, and an exponentially growing number of people got interested in the language.

One very important bit of work was called the STL -- the Standard Template Library -- originally written by Stepanov and Lee. in 1994 at Hewlett-Packard, later maintained by SGI.

This library used the template metaprogramming part of C++ in quite revolutionary ways. It was written to permit near bare-metal performance with abstracted types, with algorithm implementations divorced from container implementations, for nearly arbitrary types.

Iterators are a Concept -- a higher kind of type

In it, the iterator was a concept. A concept in C++ is a category of types (a type of types you could say). Concepts in C++ are not enforced by the compiler (at this time).

A type satisfies a concept if it has the required operations, and those operations respect the rules of the concept.

There is a heirarchy of concepts around iterators in the STL and later in the C++ standard. They go from the least restrictive (an iterator) to the most (a read-write random access contiguous iterator), and form a tree.

Template functions write functions

When a template algorithm asks for an Iterator, they are asking for a type that satisfies the Iterator concept (as described in the C++ standard). When they ask for a RandomAccessIterator, they are asking for a type that satisifies the RandomAccessIterator concept (which also includes the Iterator concept, the ForwardIterator concept, and a few others).

So template<class ForwardIterator> void std::sort( ForwardIterator, ForwardIterator ) is a template function that takes two instances of the same type which satisfy the ForwardIterator concept.

ForwardIterators have to support a number of operations (*it, ++it, bool b = it != it, bool b = it == it, etc), suport certain traits (iterator_traits<it>::iterator_category, iterator_traits<it>::reference, iterator_traits<it>::value_type, etc), and those operations have to follow certain rules.

If you feed it a type that satisfies RandomAccessIterator, std::sort guarantees better performance than if passed a ForwardIterator.

A raw pointer satisfies both Forward RandomAccess iterator without you doing anything. std::vector<?>::iterator also satisifes both, but often isn't a raw pointer (the std library did some work).

The two types -- the raw pointer, and std::vector<?>::iterator -- are usually unrelated types. C++'s template and traits system permits unrelated types to be understood by the same template algorithm with zero runtime overhead.

In c++2a there are plans to introduce in-language Concepts that actually check some of the requirements for things like RandomAccessIterator, and document in-langauge the other requirements that cannot practically be checked.

C++ is not an OO-language

You are possibly confused by being used to object oriented languages. C++ supports object oriented programming, but is not an object oriented language. It supports polymorphism -- treating multiple types the same -- without object based inheritance in a number of ways.

In an object oriented language, every iterator would inherit from an abstract iterator type. Algorithms would interact with the iterator via that abstract interface, often dispatching calls via a virtual function table of some kind. Values of the type wouldn't be possible, as the algorithm code would be compiled without knowing how many bytes the iterators take up, so extra indirection would occur.

In C++, the algorithm isn't a function until you pass it the type of the iterator. At that point, the function is custom-written for that iterator. The C++ standard states that if the iterator does certain things (obeys the Concept required), that the function written by the template will have certain behavior.

This template-written function knows how big the iterator is, what the operations do, can inline the operations and store instances of the iterator in buffers or on the stack as a value. Unless the iterator forces it, there is no virtual dispatch, and if the operations are visible, they can be inlined into the written function.

Tight loops can be examined by the compiler and vectorization can occur, just as if you wrote the function by hand.

The same template can sort database entries or strings or integers; each case a new function is written, and the compiler is told to try to make it go faster.

TL;DR

Iterators are not a type; they are a kind of type. Completely unrelated types can both be iterators. There is no base class for iterators; there is just certain ways they guarantee they behave.

C++ algorithms generates custom code for each type of iterator you pass to std::sort; if you sort a vector of int and a vector of strings, no binary code is shared between the two (except the possibility of comdat folding).

The concepts (kind of type) Iterator/ForwardIterator/RandomAccessIterator are documented requirements on the types passed to the C++ algorithms. No enforcing is done, other than that the compiler is free to do literally anything if you fail to meet the requirements.