Why isn't there a common base for the standard library containers?

Question

Just out of interest...

If I were to design a library of containers, I would surely derive them from a common base class, which would have (maybe abstract) declarations of methods like size() and insert() .

Is there a strong reason for the standard library containers not to be implemented like that?

Answer 1

In C++, inheritance is used for run-time polymorphy (read: run-time interface reuse). It comes with the overhead of a redirection via the vtable at runtime.

In order to have the same interface for multiple container classes (so that the API is predictable and algorithms can make assumptions), there's no need for inheritance. Just give them the same methods and you're done. The containers (and algorithms) in C++ are implemented as templates, which means that you get compile-time polymorphy.

This avoids any run-time overhead, and it is in line with the C++ mantra "Only pay for what you need".

Answer 2

Java collections (which you probably have in mind) have a bunch of common methods implemented in AbstractCollection, that sit on top of the size() and iterator() methods implemented in the concrete class. Then IIRC there are more such methods in AbstractList and so on. Some subclasses override most of those methods, a few can get away with implementing little more than the required abstract methods. Some of the methods genuinely are implemented in common across most or all collections sharing an interface. For example the one that gives you a non-modifiable view is a total PITA to write, in my bitter experience.

C++ containers have a few member functions in common to all containers, pretty much none of which could be implemented the same way for all containers[*]. Where there are common algorithms that can be performed using an iterator (like find), they are free functions in <algorithm>, far from anywhere that inheritance gets a look-in.

There are also member functions common to all sequences, to all associative arrays, etc. But again for each of those concepts there isn't much in common between the implementations for different concrete data structures.

So ultimately in comes down to a question of design philosophy. Both Java and C++ have some code reuse in respect of containers. In C++ this code reuse comes through function templates in <algorithm>. In Java some of it comes through inheritance.

The main practical difference probably is that in Java your function can accept a java.util.Collection without knowing what kind of collection it is. In C++ a function template can accept any container, but a non-template function cannot. This affects the coding style of users, and is also informed by it - Java programmers are more likely to reach for runtime polymorphism than C++ programmers.

From an implementer's point of view, if you're writing the library of C++ containers then there is nothing to stop you from sharing private base classes between different containers in std, if you feel that will help reuse code.

[*] Now that size() is guaranteed O(1) in C++11, empty() could probably be implemented in common. In C++03 size() merely "should" be O(1), and there were implementations of std::list that took advantage of this to implement one of the versions of splice in O(1) instead of the O(n) it would take to update the size.