For random access iterators, std::distance is O(1). Unfortunately set iterator does not support random access, so the std::distance algorithm has to iterate over the pointers to compute distance, and worst case is O(n). You can achieve O(1) distance calc in sets if you use order-statistic balanced BST (there is some post in Codeforces teaching how to build this data structure using some hidden C++ libraries)