C ++ STL implementation

Question

Why is the C ++ set implemented as a binary tree and not as a hashset, which can provide the average complexity of the O (1) case compared to the O (log n) provided by the binary tree?

Answer 1

Since C ++ sets are ordered by the comparison operator T , which allows you to program iteration over the elements. If you know that all you will do with this set is insert, test membership and / or delete elements, then std::unordered_set , which implements hashset, exists for this with C ++ 11.

Answer 2

According to John Nagle, from a 2006 publication on comp.lang.c ++. Moderated :

The actual reason is that the person who wrote the hash table part of the specification did not finish on time. It's all.

The standardization processes are as follows.

Answer 3

There are two factors here:

• both binary treelike and hash associative sets are useful
• the original STL only implemented the first due to lack of time to work through the “policy” of Standarisation; SGI, GNU, MS, boost and others have been providing non-standard hash versions for many years, and C ++ 11 represents unordered_set

These points are discussed below.

BOTH USEFUL

There are many pros and cons, and both are available (as in C ++ 11) to allow the programmer to choose. Hash sets were not available because they simply did not agree to implement, so that they would be included in earlier standards.

set iteration is in sorting order, while the hashed container unsorted_set efficiently randomized - order traversal

• set supports lower_bound , upper_bound , which are impractical to provide on unsorted_set

set uses a comparison function (by default it contains type operator< , while unordered_set requires hashing (some types are provided by default, but they can be quite mediocre depending on your actual keys and quality hashing can take a lot of time) and the key equality function either being faster for lower N values ​​is not for everyone dealing with billions of elements, so it’s wise to offer choices even in terms of performance.There may be significant differences in memory usage and small objects, even though I'm not sure what general advice would be true for implementations, so you can just offer measurement in the program, if you care as elements are added to the existing iterators std::unordered_set may be declared null and void (see. 23.2.5p14, to be exact), while iterators in std::map will never be invalidated by inserts (pointers and references to unordered_set elements remain valid, though).

Why before in C ++ standards there was no set based on hashes

From an interview with Stepanov:

Question: I find two hash table implementations on the D.Musser website, and they both work and are pretty smart - much smarter than the hash tables commonly found in class libraries. Why are hash tables not included in the STL?

Answer: Policy. They should be. Our new STL implementation contains them. In general, we need to develop a mechanism for adding things to the STL. After all, STL is an extensible structure; it requires expansion. There are many data structures that are missing, such as singly linked lists, matrices, and graphs. SGI is ready to lead the distribution of STL.

(full interview http://www.stlport.org/resources/StepanovUSA.html )