What are the specific differences between the original STL and those parts of it that ended up in the C++ Standard Library?

Question

I'd like to know what the specific differences are between the STL as released by SGI and the ISO C++ standard library. Prompted by this question and not at all answered by this question.

Some differences are obvious, such as the slist and hash_set classes that never made it into the standard. I'm also looking for more subtle differences, such as return value/parameter differences on methods, or different complexity requirements, or different iterator invalidation conditions.

Answer 1

SGI STL stuff "missing" in the C++ standard includes

• slist
• bit_vector
• hash_set, hash_map, hash_multiset, hash_multimap and everything pertaining to hash functions
• rope
• iota
• lexicographical_compare_3way
• random_sample and random_sample_n
• the MonoidOperation and Trivial Iterator concepts
• a host of backward compat headers such as algo.h

... and I bet you can find a few more.

Answer 2

In addition to what larsmans already wrote:

• std::basic_string got equipped with an STL container interface.

• Some template features were added to the language to better support the STL, which the STL portion of the standard library can exploit, but weren't available for the orginal STL.

Answer 3

operator[] in std::map has the difference that in the standard it is defined as returning (*((insert(make_pair(x, T()))).first)).second, whereas in the STL m[k] is defined as equivalent to (*((m.insert(value_type(k, data_type()))).first)).second.

The difference is that conforming C++ implementations call make_pair whereas the STL constructs the pair directly. I can think of two differences this makes:

1) The standard permits an additional copy of the pair (and hence of the key and data objects), if RVO fails to kick in for the call to make_pair. As I read it, the STL does not permit this copy (although there is of course a further copy down the line, in insert). This matters if either the key or the value type have copy constructors with observable side-effects.

2) Users can specialize either std::make_pair or std::pair. If they specialize make_pair then their code is guaranteed to be called in standard C++, and guaranteed not to be called in the STL.

Such specializations cause UB if they don't satisfy the requirements of the template, though, and in the case of make_pair I think that if it has any observable effects other than those of creating the pair, then it doesn't satisfy the requirements. So it might be difficult or impossible in this case to write a specialization that's guaranteed to let you work out whether it has been called or not. In practice if the implementation has done the obvious thing and used the code from the standard, then you will easily see a difference...

Users can also ADL-overload make_pair, same caveat, with the extra complication that I'm never quite sure whether mentions in the standard of unqualified function calls require that the implementation make the same unqualified call. I'm sure I've heard that some implementations have made fully-qualified calls to std::whatever in such cases, perhaps erroneously.

Is this the sort of thing you're after?

Answer 4

In the STL, the four-argument version of std::list::splice is guaranteed to have constant time complexity, even when a portion of one list is being spliced into a different list. As a consequence, std::list::size is not guaranteed to have constant complexity, indeed is in effect guaranteed to be Omega(n) in at least some cases. I haven't checked whether the SGI implementation makes it Omega(n) in all cases.

In the C++03 standard, 4-arg splice is only guaranteed to have constant complexity when a section of a list is being moved to a different place in the same list. This means that the size of the list doesn't change, and hence allows for implementations in which size() is constant time. GNU stuck with the STL approach, but I believe Dinkum opted for constant-time size().

In the C++11 standard, size() is required to have constant time, and hence in effect splice is guaranteed to be Omega(n) in certain cases. The STL approach no longer conforms, and as a consequence there is a binary incompatibility in gcc when they added a size field to std::list.

Answer 5

The STL allows for the possibility that the C++ implementation doesn't support member function templates (in which case, all the member function templates and constructor templates are unavailable). Obviously the standard doesn't permit that.

Answer 6

STL also had some functional stuff that was sadly missed in stdlib, although C++0x fixes that.

To quote an example for composition fuctors from STL doc

Computes sin(x)/(x + DBL_MIN) for each element of a range.

transform(first, last, first,
          compose2(divides<double>(),
                   ptr_fun(sin),
                   bind2nd(plus<double>(), DBL_MIN)));

Or, for pair selectors:

transform(M.begin(), M.end(), ostream_iterator<double>(cout, " "),
          select2nd<map<int, double>::value_type>());

Answer 7

I'm not familiar with an exhaustive list. However, it is possible to get the original STL and compare it to the Standard, depending on how much time you have and how much detail you want.