It's also O(lgn) on a sorted set, or O(1) on a hash set. So?
As araq points out this should be caught in profiling.Avoiding generality is not the best approach. A linear scan of a SIMD friendly array that is in cache may be a lot faster than your hash set.