Very interesting. This makes it sound like there should be a way to control `std::lower_bound` to switch to linear probing once it's narrowed the range down enough. (In the specific example, "enough" is about 125 elements.)

Likewise for a hash table with separate chaining, wouldn't one better-than `std::unordered_set` way to do it be to keep the separate chains as a `std::vector` that is kept sorted, and then use `std::lower_bound` (or the above better version of it) to probe the table? Those separate tables are O(1) in size, so lookup and insertion are still O(1) on average. Worst case goes to O(n log n), but that doesn't seem too bad.

Related: Is there a widely-used "frozen set" C++ data structure? I'm picturing something that is constructed from a sequence but that internally is a sorted `std::vector<T>` that provides a set-like API but that uses `std::lower_bound` to find data. It's easy enough to write, but it seems like it should be in the standard or at least Boost.