We recently switched a C++ application from using a sorted std::vector and std::binary_search to using boost::unordered_set. The performance improvement on lar

We recently switched a C++ application from using a sorted std::vector and std::binary_search to using boost::unordered_set. The performance improvement on large sets (millions) was dramatic. unordered_set really does average O(1) time complexity. However, it was slightly slower than binary_search on smaller sets, but not so much slower to matter.