Facts about STL

This is an excerpt from an advanced C++ training that I gave at my office couple of months back.

Most of our text books give a feeling that the standard template library (STL) in C++ is implemented as a shared library that is linked with your code by the C++ compiler / linker automatically. Templates by declaration dont hold any memory for its definition unless a specific instance of the template needs to be expanded by the compiler. For example a List class is defined to contain elements of a templated type, then a separate class will be created by the compiler for each of the instantiation of the class. That is, if an integer list is declared, then the tempplated List class will be expanded into List class containing integer data. If a string list is declared then the compiler will expand the templated List class into another List class containing string data.

So if the STL implementation is a dynamically linked library with your code, then how is it possible for the STL library writer to have defined an instantiation for all possible data types for all the STL classes. For example if you want to declare a list of your own data structure, you declare it as

std::list yourlist;

When this piece of code is hit by the compiler, it will create a new class called yourstruct_list by expanding the templated declaration of std::list class. But if the STL were to be a predefined shared library it is not possible to have the author of std::list class to have compiled it for the symbol yourstruct_list since, the author has no way of knowing how user defined data structures will look like. If the complete STL were a pre-compiled .so library and if you simply link it then the .so will never have the class instantiations for your data types.

So how is this problem solved by STL?

In STL only the basic functionalities which are independent of templates are compiled as libstdc++.so library. All the STL templated classes like list, vector, map etc.,. are coded in the header files which we include. For example /usr/include/c++//vector -->includes /usr/include/c++//bits/vector.tcc. The *.tcc files have the complete definition of the templated classes. When your C++ code uses STL the following is what happens

1. You define an instantiation of a templated class (eg: vector) for your data type
2. Compiler gets the blue print of the vector class from the included vector-->/usr/include/c++//bits/vector.tcc file
3. Compiler creates an instance of the vector class for your data type as per the definition of its blue print in /usr/include/c++//bits/vector.tcc

For a better understanding of the STL classes look at the source code in /usr/include/c++//bits/*.tcc files.