For longish strings (length 64 qualifies), binary_search is missing an important optimization: it ends up walking the same prefix over and over. A better algor

For longish strings (length 64 qualifies), binary_search is missing an important optimization: it ends up walking the same prefix over and over. A better algorithm is called "radix quicksort with a three-way partition." Rather than the classical qsort < and >= partition, you maintain three regions of <, =, and >. Crucially, at each step, you sort based only on a single character: the whole range via the first char, then the = region via the second char, then that = region via the third char, etc. This allows for super-fast comparisons without re-walking prefixes. All of these data structures (std::binary_search, std::set, and and set::unordered_set) are quite sub-optimal. The design of unordered_set with closed-hashing separately-allocated buckets is especially distressing. For a much more efficient take, see LLVM's DenseSet which does NOT separately allocate buckets. This burdens the client with finding two values to represent empty and tombstone entries, but if perf is a concern that's much better than additional mallocs.