Home > C++ > The Emergence Of The STL

The Emergence Of The STL

In the preface to the 2006 Japanese translation of “The Design and Evolution of C++“, Bjarne Stroustrup writes about how the C++ STL containers/iterators/algorithms approach to generic programming came into being. Of particular interest to me was how he struggled with the problem of “intrusive” containers:

The STL was a revolutionary departure from the way we had been thinking about containers and their use. From the earliest days of Simula, containers (such as lists) had been intrusive: An object could be put into a container if and only if its class had been (explicitly or implicitly) derived from a specific “Link” or “Object” class containing the link information needed by the compiler (to traverse the container). Basically, such a container is a container of references to Links. This implies that fundamental types, such as ints and doubles, can’t be put directly into containers and that the array type, which directly supports fundamental types, must be different from other containers. Furthermore, objects of really simple classes, such as complex and Point, can’t remain optimal in time and space if we want to put them into a container. It also implies that such containers are not statically type safe. For example, a Circle may be added to a list, but when it is extracted we know only that it is an Object and need to apply a cast (explicit type conversion) to regain the static type.

The figure below illustrates an “intrusive” container. Note that container users (like you and me) must conform to the container’s requirement that every application-specific, user-defined class (Element)  inherits from an “overheadObject class in order for the container to be able to traverse its contents.

As the figure below shows, the STL’s “iterator” concept unburdens the user’s application classes from having to carry around the extra overhead burden of a “universal“, “all-things-to-all people”, class.

The “separation of concerns” STL approach unburdens the user by requiring each library container writer to implement an Iterator class that knows how to move sequentially from user-defined object to object in accordance to how the container has internally linked the objects (tree, list, etc) and regardless of the object’s content. The Iterator itself contains the container-specific equivalent navigational information as the Object class in the “intrusive” container model. For contiguous memory type containers (array, vector), it may be implemented as a simple pointer to the type of objects stored in the container. For more complex containers (map, list) the Iterator may contain multiple pointers for fast, container-specific, traversal/lookup/insertion/removal.

I don’t know about you, but I think the STL’s implementation of containers and generic programming is uber cool. It is both general AND efficient – two desirable properties rarely found together in a programming language library:

…the performance of the STL is that it – like C++ itself – is based directly on the hardware model of memory and computation. The STL notion of a sequence is basically that of the hardware’s view of memory as a set of sequences of objects. The basic semantics of the STL maps directly into hardware instructions allowing algorithms to be implemented optimally. The compile-time resolution of templates and the perfect inlining they support is then key to the efficient mapping of high level expression of the STL to the hardware level.

  1. August 11, 2011 at 12:44 am

    C++ Templates and generics are far from perfect. If you are not careful, you will end up with serious code bloat.

    I have been working with C++, Java and C# on a daily basis. I find that STL syntax are clumsy and outdated, and it really hurts productivity.

    … Alan

    • August 11, 2011 at 3:00 am

      Nothing is perfect, right? C++ doesn’t have “Generics” and you’re right in that if you’re not careful, code bloat can occur. But at runtime, each app doesn’t require a JVM to be co-running with it in memory. Writing production code in C++ isn’t for novices and it definitely requires a higher learning curve in order to not blow one’s foot off.

      Yepp, the syntax is clumsy and requires more typing than not using the STL, but it doesn’t hurt productivity if you know the language well. I think it increases productivity relative to rolling your own containers and algorithms.

      If Java or C# can meet the latency and throughput requirements of an application, then that’s the way to go. But if they can’t, then all the time and money is gone and the software is useless. Now that’s a real productivity killer. 🙂 I work on computationally intensive, soft real-time sensor systems with high and bursty input sample rates. Over the years, despite the angst of thinking that C++ is not as efficient as C, we’ve been leveraging the abstract power of C++ to increase productivity for enhancements and new product development. A lot of our peripheral, non-mission-critical support tools are written in Java and C#.

      BTW, thanks for stopping by again Alex. I appreciate the feedback.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: