There may be a benchmark out there where std::set can beat std::unordered_set, but you'll be really hard pressed to find it
Java uses balanced trees instead of linked list in their chained-hashtable implementation, if I recall correctly.
I could go on, but it's very much detracting from the point of the paper to argue about the data structure choice when the paper isn't on this topic at all or trying to analyze any particular application to begin with.
std::unordered_set has some very difficult to reason about worst case scenarios that must factor in both the size of the collection and the hash function. Unless you are very careful about the type of hashing you use, you can easily be vulnerable to DDOS attacks that scale on the order of O(k * n) for key size k and container size n.
Aren't unordered_set and unordered_map quite new (IIRC, they came only with C++0x)? For most of C++'s history, if you preferred to use the standard library, what you had was only ordered sets and maps.
Also, in 2005 IIANM, Google published their dense and sparse hash map implementations, which were fast-ish and quite usable.
"Sorted" rather than ordered (an order can be arbitrary and I'd personally associate the word with insertion order).
> The formal data structure is unordered
The formal data structure doesn't have complexity bounds, the STL does.
If/when `std2::` happens, this is one of the things I assume would change.
2. The C++ standard library's maps and sets are known to be rather slow. See, for example:
https://stackoverflow.com/q/42588264/1593077
when you have string values, it's even worse, as you describe. But it's not clear that an overly-clever implementation, which caches numeric ranks of strings etc., is a good idea to have.