Is there "magic" in the STL?

Question

Let me start with explaining what I mean with "magic". I will use two examples from Java:

1. Every class inherits (directly or indirectly) the Object class.
2. Operator overloading is not supported by Java but the + operator is defined for String objects.

This means that it is impossible to make an implementation of the Object and String classes in pure(*) Java. Now this is what I mean with "magic": to make an implementation of these classes, you will need some special support from the compiler.

What I always liked about C++ is that, as far as I know, there is no such "magic" going on in the STL, i.e. it is possible to implement the STL in pure C++.

Now my question is: is this true? Or are there parts of the STL that cannot be implemented in pure C++ and need some "magic"/special compiler support?

---

(*) With "pure" I mean without using any class libraries.

Answer 1

in other words, has anything been done to the compiler to allow for a 'special case' the STL needed to work?

No.

It was all implemented as 'pure' C++ code, using the magic of templates.

There has been some work done to compilers to improve the STL (I'm thinking about various optimisations) but otherwise, no, you could write the entire STL if you really wanted. Some people did - STLPort is an implementation that didn't have the backing of any compiler manufacturer.

Answer 2

STL is standard (Standard Template Library). The standard specifies the requirements for STL implementations. From the usage point of view, there is no "magic", no special dependencies you have to take care of. It can be used on any major C++ compilers, on all platforms supported by those compilers.

Answer 3

As "gbjbaanb" rightly said, there is no magic involved in the implementation of STL. It is written in pure C++. You could implement it yourself but has been made readily available as a library to make your life simpler.

Answer 4

Like gbjbaanb correctly said, the STL can be implemented in plain C++, without relying on any kind of compiler "magic".

However, if you go digging in the STL source code for your compiler, you'll probably see code that either isn't standard, or which you're not supposed to write yourself.

The STL can be implemented entirely in standard C++, but that doesn't mean compiler writers aren't allowed to improve it occasionally, using compiler-specific extensions. For example, they might insert non-standard code that ensures better error messages, or perhaps works around some flaw in their compiler, or maybe enables special optimizations by using extra features of that specific compiler.

They also consistently use names that you're not allowed to use. For example, template parameters are typically named something like _Type, which, since it starts with an underscore followed by a capital letter, is reserved for the implementation. The standard library is allowed to use them, but you and I are not. So if you were going to write your own STL implementation, you would have to make some minor changes, but that's not because of any magic, just a way to avoid name clashes between the standard library and user code.

Answer 5

As others have said, the STL is implementable in pure standard C++98. What hasn't been said is that the development of the STL was concurrent with the development of the C++ template mechanism, and largely drove the inclusion of certain features. I believe that Argument Dependent Lookup (ADL, aka Koenig Lookup), template template parameters, and default template arguments all came to C++ to serve Stepanov's STL development.

So, with STL, they moved the magic into the language itself. Nice that the standards committee recognized that if those features were useful for what would become the standard library, they might be useful for the rest of us as well!

Answer 6

I'm pretty sure some type_traits require compiler magic, for example has_trivial_constructor, has_virtual_destructor or is_pod.

Answer 7

If by STL you mean only the template portion of the C++ standard library, then it is perfectly possible to implement it without any "magic". Whether each given implementation actually uses any "magic" is a different question (there are portions of STL, where "magic" would help, but not absolutely required).

Now, if you are talking about the entire C++ Standard Library, then it does indeed have a bit of "magic" in it. The classic example would be the library-provided ::operator new and ::operator delete implementations. We often call them "overloadable" in everyday language, while formally they are replaceable. C++ language does not offer such functionality to the user. The user cannot write a replaceable function.

Another example would be the offsetof macro (inherited from C Standard Library). While it is usually implemented in "pure C", the popular implementation is actually illegal form the pedantic point of view (causes undefined behavior). I haven't seen any formally legal implementations of offsetof, so I'm not sure whether they are even possible.

Another example would be (again, inherited from C) the macros for working with variable arguments. They obviously cannot be implemented in pure C or C++.

Answer 8

std::initializer_list needs compiler support and cannot be reimplemented as another class (as far as I know), though I'm not sure if it counts since it's in c++0x.