Why is there no "Iterable" interface in the STL?

Question

The C++ STL does not seem to use purely abstract base classes (aka interfaces) very often. I know that most things can be achieved with the STL algorithms or clever template metaprogramming.

But still, for some use cases (for example, in an API, if I do not want to be specific about the type of container I get, just about the elements it contains), an interface of the following form would be nice:

template<typename T> struct forward_iterable {
    struct iterator {
        typedef T  value_type;
        typedef T& reference;
        typedef T* pointer;
        virtual reference operator*() const = 0;
        virtual pointer operator->() const = 0;
        virtual bool operator==(const iterator&) const = 0;
        virtual bool operator!=(const iterator&) const = 0;
        virtual operator const_iterator() const = 0;
        virtual iterator& operator++() = 0;
        virtual iterator  operator++(int) = 0;
    };
    struct const_iterator { ... };  // similar, but with const references

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

If the STL containers implement this class as non-virtual function, this would, in my opinion, not affect performance (if I use the containers directly and not via this interface). So why are there so few "interfaces" in the STL? Or am I just thinking too much in "Java" terms?

Answer 1

The reason you don't see a lot of "interface"-style abstract base classes in the STL is because it relies so heavily on C++ templates. When you use C++ templates, pretty much any class whatsoever, no matter what its parentage may be, will do as long as it supports all the methods the template tries to use.

There is sort of an implied interface, but actually writing it out is unnessecary. In my own coding I tend to write one anyway, just as a convenience to the user, but that isn't how the STL writers roll.

Answer 2

STL (which is a subset of the standard library) does not use OOP (as in runtime polymorphism) at all and that's by design.

With your design, wouldn't there be problems returning iterators by value (covariance doesn't work for value types)? That is, wouldn't inevitably the whole thing either have to rely on static members (that you can return by reference) or on heap-allocated iterators? The latter would seem rather awkward in a non-garbage-collected language.

What you are describing (an iterator templated on value type) can be achieved using a technique called type-erasure (and you can find any_iterator implementations out there) just like boost's function and any types.

The basic idea is:

 //less templated interface
 template <class T>
 class any_iterator_base
 {
     virtual void increment() = 0;
     /*...*/
 };

 //derived class templated on iterator type
 template <class Iter, class T>
 class any_iterator_impl: public any_iterator_base<T>
 {
     Iter it;
     virtual void increment() { ++it; }
     /*...*/
 };

 //and a class for the user which makes it all act like a regular value type
 template <class T>
 class any_iterator
 {
     shared_ptr<any_iterator_base<T> > it;
 public:
     template <class Iter>
     any_iterator(Iter iterator): it(new any_iterator_impl<Iter, T>(iterator)) {}
     any_iterator& operator++() { it->increment(); return *this; }
     //...
 };

 int main()
 {
      std::vector<int> vec;
      any_iterator<int> it = vec.begin();
      //...
 }

It may be more complicated than that (e.g need to do something about describing and enforcing iterator category?, how would comparing two any_iterators work (double dispatch/RTTI?)).

Answer 3

STL structures are not defined with inheritance in mind. It's not easy to make a good case for subclassing any of the stl collections. with that in mind, the stl does not make you 'pay' any cost that might have been associated with normal class inheritance. If virtual methods were to be used, then they could not be inlined by the optimizer.

Also, STL wants to be compatible with things that could not possibly inherit from a top-level abstract base class, like arrays.