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

Question

I mean, aside from its obligating name (the Standard Template Library)...

C++ initially intended to present OOP concepts into C. That is: you could tell what a specific entity could and couldn't do (regardless of how it does it) based on its class and class hierarchy. Some compositions of abilities are more difficult to describe in this manner due to the problematics of multiple inheritance, and the fact that C++ supports the concept of interfaces in a somewhat clumsy way (compared to java, etc), but it's there (and could be improved).

And then templates came into play, along with the STL. The STL seemed to take the classical OOP concepts and flush them down the drain, using templates instead.

There should be a distinction between cases when templates are used to generalize types where the types themeselves are irrelevant for the operation of the template (containers, for examples). Having a vector<int> makes perfect sense.

However, in many other cases (iterators and algorithms), 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.

For example, you can tell the function:

void MyFunc(ForwardIterator<...> *I);

Update: As it was unclear in the original question, ForwardIterator is ok to be templated itself to allow any ForwardIterator type. The contrary is having ForwardIterator as a concept.

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

template <typename Type> void MyFunc(Type *I);

Two claims I can make in favor of using templates: compiled code can be made more efficient, by tailor-compiling the template for each used type, instead of using vtables. And the fact that templates can be used with native types.

However, I am looking for a more profound reason why abandoning classical OOP in favor of templating for the STL? (Assuming you read that far :P)

Solution 1

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?

Solution 2

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.

Solution 3

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.

Solution 4

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.

Solution 5

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 :)

View more solutions

Comments

[James McMahon]

You might to check out stackoverflow.com/questions/31693/…. The accepted answer is an excellent explanation of what templates offer you over generics.

[Jonas Kölker]

"compiled code can be made more efficient, by tailor-compiling the template for each used type, instead of using vtables." Yeah, but you get redundant code filling up the instruction cache. In modern CPU architectures, you're typically constrained on (cache) memory rather than clock cycles. But don't trust me: do the experiment. Err, well, except that it takes reimplementing g++ ;-)

[josesuero]

@Jonas: That doesn't make sense. The constraint on cache costs clock cycles, which is why it is important. At the end of the day, it is clock cycles, not cache, that defines performance. Memory, and cache is only important in so far as it affects the clock cycles spent. Moreover, the experiment can be done easily. Compare, say, std::for_Each called with a functor argument, with the equivalent OOP/vtable approach. The difference in performance is staggering. Which is why the template version is used.

[josesuero]

and there is no reason why the redundant code would be filling up the icache. If I instantiate vector<char> and vector<int> in my program, why should the vector<char> code be loaded into icache while I'm processing the vector<int>? In fact, the code for vector<int> is trimmed because it doesn't have to include code for casting, vtables and indirection.

[fredoverflow]

Alex Stepanov explains why inheritance and equality don't play well together.

[Andrey Vihrov]

Related: en.wikipedia.org/wiki/Concepts_%28C%2B%2B%29

[rabada123]

@jalf: Uhm, close, but no. The constraint on cache costs time, which is subtly different to clock cycles. If you could double the clock rate you'd also double the number of stalled cycles when pulling a new cache line. Also, memory cycles spent pulling in new instructions are cycles not spent doing IO. This phenomenon is why sometimes code compiled with -Os is faster than the same code compiled with -O2. Sometimes you're using vector<char> and vector<int> at the same time - they might not both fit into the icache.

[josesuero]

@BerndJendrissek: Uhm, close, but no yourself. Yes, more code costs in terms of memory bandwidth and cache usage if it is ever actually used. But there is no particular reason to expect a vector<int> and vector<char> to be used at the same time. They might, sure, but you might use any two pieces of code at the same time. That has nothing to do with templates, C++ or the STL. There is nothing in the instantiation of vector<int> which requires vector<char> code to be loaded or executed.

[josesuero]

And for all practical purposes, time == clock cycles. Yes, different CPUs have different clock rates, but given any specific CPU, something which can be done in 1 cycle will always be faster than something which takes 2 cycles. Both are measures of time, they just use different units.

[josesuero]

What, Taj Mahal is small and elegant, and your house is the size of a mountain, and a complete mess? ;)

[Rob K]

Good answer. I would add that templates depend on object oriented programming. Generic programming depends on being able to treat all types equally, whether intrinsic or user defined.

[josesuero]

Interesting interview. Pretty sure I've read it before some time ago, but was definitely worth going through again. :)

[lhahne]

you can just use the <, > and = operators of the type and not know what those are (though this might not be what you meant)

[Tanktalus]

Depending on the context, those may not make any sense, or they may work fine. Hard to tell without knowing more about MyType, which, presumable, the user does, and we don't.

[Igor Krivokon]

It's a good writeup, but I'd like to highlight one detail. The STL is not a "product" of C++. In fact, STL, as a concept, existed before C++, and C++ just happened to be an efficient language having (almost) enough power for generic programming, so STL was written in C++.

[Johannes Schaub - litb]

@Igor, i've given up telling people that "STL" is an ambiguous term :) STL seems to have become the de-facto name for all templates in the standard library nowadays

[Jonas Kölker]

"and with C++0x some things can even be programmed functionally" -- it can be programmed functionally without those features, just more verbosely.

[Felixyz]

One of the most interesting interviews about programming that I've ever read. Although it leaves me thirsting for more detail...

[Женя Борісевіч]

@Tyler Indeed if you constrained C++ to pure OOP, you'd be left with Objective-C.

[KitsuneYMG]

The STL in its entirety isn't in the standard library. slist and rope are two containers that aren't off the top of my head. I would also say that hash_set/map/multiset/multimap aren't, but 0x plans on fixing that (albeit with a stupid name. Yes I know why, it's still stupid)

[KitsuneYMG]

Concepts aren't part of c++0x anymore. Some of the error messages can be pre-empted using static_assert perhaps.

[josesuero]

Since comments keep bringing it up, yes, I'm aware that the STL name is ambiguous. But I can't think of a better name for "the part of the C++ standard library that is modelled on the STL". The de-facto name for that part of the standard library is just "the STL", even though it is strictly inaccurate. :) As long as people don't use STL as the name for the entire standard library (including IOStreams and the C stdlib headers), I'm happy. :)

[David Stone]

GCC 4.6 has improved template error messages, and I believe that 4.7+ are even better with it.

[Paulo Pinto]

You failed to mention that STL was developed by Alexander Stepanov for Ada, and later on ported to C++ when the language got generics.

[josesuero]

@PauloPinto that's because it (1) is irrelevant, and (2) is inaccurate. Stepanov worked on what would one day become the STL over a period of several years, and yes, he initially did this work in Ada. But that does not mean that the STL ever existed for Ada, and it was not "ported" to C++. The switch to C++ was much more than just a port, and it happened long before the library was complete (and before it had the STL name)

[andygavin]

Agreed that interfaces are not just OO. But the ability polymorphism in the type system is (it was in Simula in the 60s). Module interfaces existed in Modula-2 and Ada, but these operated in the type system differently I think.

[Paulo Pinto]

@jalf I remember reading about it in the "The C/C++ Users Journal" and "C++ Report" before C++ even got templates, maybe with age I got some facts wrong.

[einpoklum]

I'm sorry, but I have to disagree with this answer! I was just referred to this question from here, where I inquired about how to do something pretty basic in an OOP language: Expressing the fact that my class is a kind of set. Well, it turns out - I can't really do that, at least with the Standard Library. Of course this is just an example of a bigger issue. In my very humble opinion it seems to me that while C++ may be multi-paradigmatic, its standard library simply doesn't support Object-Oriented Programming.

[einpoklum]

@TylerMcHenry: Having just asked this, I find I've just uttered the same answer as you! Just one point. I wish you would add the fact that the Standard Library cannot be used to write Object-Oriented code.

[einpoklum]

Well, I either: 1. Don't try to get it, since I'm writing generic code. Or, 2. Get it using whatever reflection mechanism C++ offers these days.

[fredoverflow]

@einpoklum Your class is a set if it follows a certain protocol.

[einpoklum]

@FredOverflow: And in an OOP spirit, I would expect this protocol to be embodied in an interface (= abstract base class), so that certain functions or methods can take SetInterface& arguments.

[fredoverflow]

@einpoklum And what exactly would you gain from an abstract base class? Take std::set as an example. It does not inherit from an abstract base class. How does that limit your usage of std::set? Is there anything you cannot do with a std::set because it does not inherit from an abstract base class?

[josesuero]

@einpoklum please take a look at the Smalltalk language, which Alan Kay designed to be an OOP language when he invented the term OOP. It didn't have interfaces. OOP is not about interfaces or abstract base classes. Are you going to say that "Java, which is nothing like what the inventor of the term OOP had in mind is more OOP than C++ which also is nothing like what the inventor of the term OOP had in mind"? What you mean to say is "C++ is not Java-like enough for my taste". That is fair, but it has nothing to do with OOP.

[einpoklum]

@FredOverflow: It would let me write code which works on sets, abstractly; and I can (probably) share a lot more code; and I don't need to make source code visible between modules (unlike the case with templates). And there's probably more, but I'm not much of a language lawyer.

[josesuero]

@einpoklum the source code that is being made visible between modules is the standard library. Your complaint is not "C++ doesn't allow me to use abstract base classes as interfaces" (because it does), but "the standard library does not define an abstract base class for sets". And so far you have not explained why that would be an advantage. You can write code which works on sets, abstractly.

[pyon]

On explicitly declared interfaces, two words: type classes. (Which are already what Stepanov means by "concept".)

[Kos]

Nice gem; Do you know what year is it from?

[André]

That "someone" has a name: Alexander Stepanov. I think he deserves some recognition for his work.

[alfC]

@Kos, according to the web.archive.org/web/20000607205939/http://www.stlport.org/… the first version of the linked page is from June 7 2001. The page itself at the bottom says Copyright 2001-2008.

[Mason Wheeler]

-1 for writing a bunch of blatant nonsense and flat-out lies about OOP. If it "didn't really promote reusable code or modularity", you wouldn't see literally millions of developers around the world re-using modules developed in OO languages. If it didn't work, it wouldn't have taken over the world the way it has; such revisionist comments are sour-grapes nonsense from people who don't understand why their language, which is clearly so much better despite not having OO support, hasn't taken over the world. (See also: Paul Graham.) Just because C++'s OOP sucks doesn't mean OOP sucks.

[josesuero]

Right, it can't be bad if it's popular. So Coca Cola is healthy too, I assume? And Win32 is a well-designed API? You see literally millions of developers around the world reusing libraries developed in procedural languages and functional languages. Millions of developers using something proves nothing. As for sour grapes, have you looked in the mirror recently?

[Christian Hackl]

@MasonWheeler: Those "OO languages" often do not use much OOP at all, or they are only now slowly discovering the power of functional and generic programming. Code does not become OOP when you put it into a class. Not in C++, not in Java, nor in C# or any other language I am aware of.

[panda-34]

@MasonWheeler if this answer was a bunch a blatant nonsense you wouldn't see literally hundreds of developers around the world voting +1 on this with only three people doing otherwise

[davidhigh]

@panda-34: although that's of course just another argument in the way the author disregarded in one of his comments. Many upvotes reveal a consensus, not the truth. Still I'm among those +1 voters :-)

[Mihai Danila]

"Simpler and more concise"? Java beats C++ in conciseness hands-down. C++ is a monster. I was unpleasantly surprised when I picked it back up after a ten year long hiatus. What a joke of a language. :)

[Some Guy]

Most claims about OO here incorrectly assume that the only way to do OO is similar to the way that C++ did it. Other OO languages don't have C++'s limitations. For instance, "Would you be able to include just the vector header, without also getting iterator or even iostream pulled in?" first assumes that header files are the only way to share interfaces (they suck: textual inclusion hugely increases compile times.), and then assumes that sharing an entire iterator class or iostream class (instead of a tiny base class with only pure virtual methods, similar to a Java interface) would be needed.

[Some Guy]

A lot of the complaints he makes about languages like Java ("You can't write a generic max() in Java that takes two arguments of some type and has a return value of that same type") were only relevant to very early versions of the language, before generics were added. Even from the beginning, it was known that generics would eventually be added added, though (once a viable syntax/semantics was figured out), so his criticisms are largely baseless. Yes, generics in some form are needed to preserve type safety in a statically typed language, but no, that does not make OO worthless.

[Some Guy]

A Concept is essentially the "interface" that the OP was asking for. The only difference is that "inheritance" from a Concept is implicit (if a class has all the right member functions, it is automatically a subtype of the Concept) rather than explicit (a Java class has to explicitly declare that it implements an interface). However, both implicit and explicit subtyping are valid OO, and some OO languages have implicit inheritance which works just like Concepts. So what is being said here is basically "OO sucks: use templates. But templates have problems, so use Concepts (which are OO)."

[Yakk - Adam Nevraumont]

"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." -- that is false. Passing in something to the std library that fails to match a concept is usually "ill-formed, no diagnostic required".

[melpomene]

@SomeGuy They're not complaints about Java per se. He's talking about "the "standard" OO programming of SmallTalk or, say, Java". The interview is from the late 90s (he mentions working at SGI, which he left in 2000 to work at AT&T). Generics were only added to Java in 2004 in version 1.5 and they are a deviation from the "standard" OO model.

[melpomene]

@Kos Stepanov mentions working at SGI in the first answer. He left SGI in May 2000, so presumably the interview is older than that.

[Steve Jessop]

True, I was playing fast and loose with the term "valid". I just meant if the compiler can't compile one of the required expressions, then it will report something.

[Peregring-lk]

The big adventage of OOP is invariant protection by means of public/private. It's an unvaluable resource and in my opinion its best feature. Inheritance and polymorphism are just ways of implementing data or behaviour reuse, without being the only ones.

[MSalters]

If Stepanov got anything wrong, it would be making iterators first-class, instead of treating them as a building block for ranges.