Why is the C++ STL is so heavily based on templates? (and not on *interfaces*)

Question

The short answer is "because C++ has moved on". Yes, back in the late 70's, Stroustrup intended to create an upgraded C with OOP capabilities, but that is a long time ago. By the time the language was standardized in 1998, it was no longer an OOP language. It was a multi-paradigm language. It certainly had some support for OOP code, but it also had a turing-complete template language overlaid, it allowed compile-time metaprogramming, and people had discovered generic programming. Suddenly, OOP just didn't seem all that important. Not when we can write simpler, more concise and more efficient code by using techniques available through templates and generic programming.

OOP is not the holy grail. It's a cute idea, and it was quite an improvement over procedural languages back in the 70's when it was invented. But it's honestly not all it's cracked up to be. In many cases it is clumsy and verbose and it doesn't really promote reusable code or modularity.

That is why the C++ community is today far more interested in generic programming, and why everyone are finally starting to realize that functional programming is quite clever as well. OOP on its own just isn't a pretty sight.

Try drawing a dependency graph of a hypothetical "OOP-ified" STL. How many classes would have to know about each others? There would be a lot of dependencies. Would you be able to include just the vector header, without also getting iterator or even iostream pulled in? The STL makes this easy. A vector knows about the iterator type it defines, and that's all. The STL algorithms know nothing. They don't even need to include an iterator header, even though they all accept iterators as parameters. Which is more modular then?

The STL may not follow the rules of OOP as Java defines it, but doesn't it achieve the goals of OOP? Doesn't it achieve reusability, low coupling, modularity and encapsulation?

And doesn't it achieve these goals better than an OOP-ified version would?

As for why the STL was adopted into the language, several things happened that led to the STL.

First, templates were added to C++. They were added for much the same reason that generics were added to .NET. It seemed a good idea to be able to write stuff like "containers of a type T" without throwing away type safety. Of course, the implementation they settled on was quite a lot more complex and powerful.

Then people discovered that the template mechanism they had added was even more powerful than expected. And someone started experimenting with using templates to write a more generic library. One inspired by functional programming, and one which used all the new capabilities of C++.

He presented it to the C++ language committee, who took quite a while to grow used to it because it looked so strange and different, but ultimately realized that it worked better than the traditional OOP equivalents they'd have to include otherwise. So they made a few adjustments to it, and adopted it into the standard library.

It wasn't an ideological choice, it wasn't a political choice of "do we want to be OOP or not", but a very pragmatic one. They evaluated the library, and saw that it worked very well.

In any case, both of the reasons you mention for favoring the STL are absolutely essential.

The C++ standard library has to be efficient. If it is less efficient than, say, the equivalent hand-rolled C code, then people would not use it. That would lower productivity, increase the likelihood of bugs, and overall just be a bad idea.

And the STL has to work with primitive types, because primitive types are all you have in C, and they're a major part of both languages. If the STL did not work with native arrays, it would be useless.

Your question has a strong assumption that OOP is "best". I'm curious to hear why. You ask why they "abandoned classical OOP". I'm wondering why they should have stuck with it. Which advantages would it have had?

The most direct answer to what I think you're asking/complaining about is this: The assumption that C++ is an OOP language is a false assumption.

C++ is a multi-paradigm language. It can be programmed using OOP principles, it can be programmed procedurally, it can be programmed generically (templates), and with C++11 (formerly known as C++0x) some things can even be programmed functionally.

The designers of C++ see this as an advantage, so they would argue that constraining C++ to act like a purely OOP language when generic programming solves the problem better and, well, more generically, would be a step backwards.

My understanding is that Stroustrup originally preferred an "OOP-styled" container design, and in fact didn't see any other way to do it. Alexander Stepanov is the one responsible for the STL, and his goals did not include "make it object oriented":

That is the fundamental point: algorithms are defined on algebraic structures. It took me another couple of years to realize that you have to extend the notion of structure by adding complexity requirements to regular axioms. ... I believe that iterator theories are as central to Computer Science as theories of rings or Banach spaces are central to Mathematics. Every time I would look at an algorithm I would try to find a structure on which it is defined. So what I wanted to do was to describe algorithms generically. That's what I like to do. I can spend a month working on a well known algorithm trying to find its generic representation. ...

STL, at least for me, represents the only way programming is possible. It is, indeed, quite different from C++ programming as it was presented and still is presented in most textbooks. But, you see, I was not trying to program in C++, I was trying to find the right way to deal with software. ...

I had many false starts. For example, I spent years trying to find some use for inheritance and virtuals, before I understood why that mechanism was fundamentally flawed and should not be used. I am very happy that nobody could see all the intermediate steps - most of them were very silly.

(He does explain why inheritance and virtuals -- a.k.a. object oriented design "was fundamentally flawed and should not be used" in the rest of the interview).

Once Stepanov presented his library to Stroustrup, Stroustrup and others went through herculean efforts to get it into the ISO C++ standard (same interview):

The support of Bjarne Stroustrup was crucial. Bjarne really wanted STL in the standard and if Bjarne wants something, he gets it. ... He even forced me to make changes in STL that I would never make for anybody else ... he is the most single minded person I know. He gets things done. It took him a while to understand what STL was all about, but when he did, he was prepared to push it through. He also contributed to STL by standing up for the view that more than one way of programming was valid - against no end of flak and hype for more than a decade, and pursuing a combination of flexibility, efficiency, overloading, and type-safety in templates that made STL possible. I would like to state quite clearly that Bjarne is the preeminent language designer of my generation.

The answer is found in this interview with Stepanov, the author of the STL:

Yes. STL is not object oriented. I think that object orientedness is almost as much of a hoax as Artificial Intelligence. I have yet to see an interesting piece of code that comes from these OO people.

Why a pure OOP design to a Data Structure & Algorithms Library would be better ?! OOP is not the solution for every thing.

IMHO, STL is the most elegant library I have seen ever :)

for your question,

you don't need runtime polymorphism, it is an advantage for STL actually to implement the Library using static polymorphism, that means efficiency. Try to write a generic Sort or Distance or what ever algorithm that applies to ALL containers! your Sort in Java would call functions that are dynamic through n-levels to be executed!

You need stupid thing like Boxing and Unboxing to hide nasty assumptions of the so called Pure OOP languages.

The only problem I see with STL, and templates in general is the awful error messages. Which will be solved using Concepts in C++0X.

Comparing STL to Collections in Java is Like comparing Taj Mahal to my house :)

templated types are supposed to follow a "concept" (Input Iterator, Forward Iterator, etc...) where the actual details of the concept are defined entirely by the implementation of the template function/class, and not by the class of the type used with the template, which is a somewhat anti-usage of OOP.

I think you misunderstand the intended use of concepts by templates. Forward Iterator, for example, is a very well-defined concept. To find the expressions which must be valid in order for a class to be a Forward Iterator, and their semantics including computational complexity, you look at the standard or at http://www.sgi.com/tech/stl/ForwardIterator.html (you have to follow the links to Input, Output, and Trivial Iterator to see it all).

That document is a perfectly good interface, and "the actual details of the concept" are defined right there. They are not defined by the implementations of Forward Iterators, and neither are they defined by the algorithms which use Forward Iterators.

The differences in how interfaces are handled between STL and Java are three-fold:

1) STL defines valid expressions using the object, whereas Java defines methods which must be callable on the object. Of course a valid expression might be a method (member function) call, but it doesn't have to be.

2) Java interfaces are runtime objects, whereas STL concepts are not visible at runtime even with RTTI.

3) If you fail to make valid the required valid expressions for an STL concept, you get an unspecified compilation error when you instantiate some template with the type. If you fail to implement a required method of a Java interface, you get a specific compilation error saying so.

This third part is if you like a kind of (compile-time) "duck typing": interfaces can be implicit. In Java, interfaces are somewhat explicit: a class "is" Iterable if and only if it says it implements Iterable. The compiler can check that the signatures of its methods are all present and correct, but the semantics are still implicit (i.e. they're either documented or not, but only more code (unit tests) can tell you whether the implementation is correct).

In C++, like in Python, both semantics and syntax are implicit, although in C++ (and in Python if you get the strong-typing preprocessor) you do get some help from the compiler. If a programmer requires Java-like explicit declaration of interfaces by the implementing class, then the standard approach is to use type traits (and multiple inheritance can prevent this being too verbose). What's lacking, compared with Java, is a single template which I can instantiate with my type, and which will compile if and only if all the required expressions are valid for my type. This would tell me whether I've implemented all the required bits, "before I use it". That's a convenience, but it's not the core of OOP (and it still doesn't test semantics, and code to test semantics would naturally also test the validity of the expressions in question).

STL may or may not be sufficiently OO for your taste, but it certainly separates interface cleanly from implementation. It does lack Java's ability to do reflection over interfaces, and it reports breaches of interface requirements differently.

you can tell the function ... expects a Forward Iterator only by looking at its definition, where you'd need either to look at the implementation or the documentation for ...

Personally I think that implicit types are a strength, when used appropriately. The algorithm says what it does with its template parameters, and the implementer makes sure those things work: it's exactly the common denominator of what "interfaces" should do. Furthermore with STL, you're unlikely to be using, say, std::copy based on finding its forward declaration in a header file. Programmers should be working out what a function takes based on its documentation, not just on the function signature. This is true in C++, Python, or Java. There are limitations on what can be achieved with typing in any language, and trying to use typing to do something it doesn't do (check semantics) would be an error.

That said, STL algorithms usually name their template parameters in a way which makes it clear what concept is required. However this is to provide useful extra information in the first line of the documentation, not to make forward declarations more informative. There are more things you need to know than can be encapsulated in the types of the parameters, so you have to read the docs. (For example in algorithms which take an input range and an output iterator, chances are the output iterator needs enough "space" for a certain number of outputs based on the size of the input range and maybe the values therein. Try strongly typing that.)

Here's Bjarne on explicitly-declared interfaces: http://www.artima.com/cppsource/cpp0xP.html

In generics, an argument must be of a class derived from an interface (the C++ equivalent to interface is abstract class) specified in the definition of the generic. That means that all generic argument types must fit into a hierarchy. That imposes unnecessary constraints on designs requires unreasonable foresight on the part of developers. For example, if you write a generic and I define a class, people can't use my class as an argument to your generic unless I knew about the interface you specified and had derived my class from it. That's rigid.

Looking at it the other way around, with duck typing you can implement an interface without knowing that the interface exists. Or someone can write an interface deliberately such that your class implements it, having consulted your docs to see that they don't ask for anything you don't already do. That's flexible.