STL - does every compiler implement it differently?

Question

It was said to me that the standard template library is differently implemented by every compiler, is this correct?

How can computational complexity (both in time and space) be observed if (for instance) the set container is implemented with a linked list rather than a red-black tree?

Did I miss something?

Answer 1

Short answer: it cannot, the author probably misunderstood. A red-black tree is implemented as a node-based containers (ie, nodes linked to each others in some way), as is a linked-list, but the way the nodes are linked together are different because they have different complexity requirements on their various operations.

---

Long answer: actually, there is a misunderstanding.

There are two (interleaved to a degree) components in the C++ Standard:

• the C++ language itself
• the C++ Standard Library

A compiler is only required to implement the C++ language. And indeed there is not necessarily a one-to-one matching between a compiler and an implementation of the standard library.

Examples:

• Dinkumware is a company providing its own implementation of the C++ Standard Library. It is sold to Microsoft which bundles it with its Visual Studio C++ compiler & IDE.
• Clang is a C++ compiler which on most Linux distributions will use the libstdc++ implementation, which is usually bundled with the gcc compiler. The LLVM project (which hosts Clang) has its own implementation (the libc++ library), but it is not ported to many linux distributions yet.

Any implementation of the Standard Library must meet a number of requirements, both in terms of interface (which classes/methods, which parameters, which types, ...) but also in terms of complexity. However the implementations do vary.

Example: std::string

• In libstdc++ (which comes with gcc), the std::string class only contains a single pointer to a shared class because it implements the Copy-On-Write idiom.
• In Dirkumware implementation, on the other hand, the std::string class is much fatter because it implements the Small-String-Optimization, which consists in storing small strings without dynamically allocating memory (via new) by reusing some space in the class.

Both implement the same interface, but widely differently.

Example: std::sort

The sort algorithm is only required to have a N*log(N) overall complexity, in average. However good implementations will implement either IntroSort algorithms or variations of TimSort, which have lower complexity in many common cases or less disastrous worst case complexity.

It is my understanding that libc++'s implementation is currently the best out of the three libraries I cited, for example.

Answer 2

How can computational complexity (both in time and space) be observed if (for instance) the set container is implemented with a linked list rather than a red-black tree?

SeaWorld San Antonio used to be owned by Anheuser-Busch. When Anheuser-Busch bought it, the weird liquor laws in Texas would have required Anheuser-Busch to sell only their competitors' beers at SeaWorld. It would have been illegal to sell Bud. Hence the Busch exception to those liquor laws. The Busch exception didn't name Anheuser-Busch or SeaWorld. That would have been a bit too blatant. But it nonetheless did allow SeaWorld to sell Bud, and it didn't apply anywhere else. Legislators are very adept at creating laws that target a very specific organization without naming that organization.

The same applies to standards writers. The standard doesn't say red black trees anywhere, but the requirements are heavily rigged in favor of them. I doubt that even an AVL tree could meet those stringent insertion requirements. AVL trees give up some performance on insertion so as to make lookup as fast as possible. AVL trees are even faster than red-black trees with regard to search.

Answer 3

Every C++ compiler comes with an implementation of the C++ standard library. Some implementations are based on others while some are independent.

However, they all must implement the standard. And the standard has certain complexity specifications that it requires from various functions. A set cannot be implemented purely as a linked-list and still meet those guarantees. Thus, if a C++ standard library implements set as a linked-list, then it is in violation of the standard. This is no different from a a C++ compiler implementing if wrong.

Answer 4

An example of the actual standard may be helpful to clarify, and unordered_* is a good one I think, since it was added specifically to get a hash table into the standard. This quote is from a draft but I expect the final version is substantially similar:

23.5.4.4 unordered_map modifiers

template <class P>
pair<iterator, bool> insert(P&& obj);

1. Requires: value_type is constructible from std::forward<P>(obj).
2. Effects: Inserts obj converted to value_type if and only if there is no element in the container with key equivalent to the key of value_type(obj).
3. Returns: The bool component of the returned pair object indicates whether the insertion took place and the iterator component points to the element with key equivalent to the key of value_type(obj).
4. Complexity: Average case O(1), worst case O(size()).
5. Remarks: This signature shall not participate in overload resolution unless P is implicitly convertible to value_type.

Other parts of the standard effectively require it be implemented as a hash table too, but I think the important part is that they make complexity requirements.

Answer 5

First things first, you probably mean the C++ standard library, not STL. The STL was a library written before C++ was standardised that heavily influenced the C++ standard library.

Now, the C++ standard provides rules and definitions that an implementation should conform to. In particular, the standard library is described as various partial class definitions and function declarations and the properties that they should have. The implementation is free to implement the library in any way it chooses, as long as it meets exactly what the standard says. Here's what the standard says about a conforming implementation (§1.4):

For classes and class templates, the library Clauses specify partial definitions. Private members (Clause 11) are not specified, but each implementation shall supply them to complete the definitions according to the description in the library Clauses.

For functions, function templates, objects, and values, the library Clauses specify declarations. Implementations shall supply definitions consistent with the descriptions in the library Clauses.

For example, to ensure the complexity of a std::list implementation is equal to that of a double-linked list, its member functions are given complexity requirements. For example, the std::list::insert functions are given the following requirement (§23.3.5.4, emphasis added):

Insertion of a single element into a list takes constant time and exactly one call to a constructor of T.

This doesn't necessarily mean that std::list must be implemented as a double-linked list. However, this is a common choice. An implementation must only act in such a way that the requirements are met (or that it appears that the requirements have been met; the as-if rule).