std::set has logarithmic complexity (red-black tree). The complexity of std::hash_set depends heavily on the implementation of the hashing function, but it is tried to be selected in such way that the element is accessed with constant complexity.