distance between std::set begin() and std::set iterator in O(logn)

You can use the function std::set<>::find to search for an element x and compute the distance to the first iterator of the set.

std::distance(s.begin(), s.find(x))

However, as comments indicate the runtime of distance depends on the type of iterator used. In the case of a set this is a bidirectional iterator and distance is O(n).

You can use sorted std::vector<int>. If it is sorted, you can find element in O(log n). And you can find distance in constant time O(1).

By sorted vector I mean that after every insertion (or after many insertions) you do std::sort(v.begin(), v.end());

If your type inside std::set<T> is not as light like int - you can keep both - std::set<T> and sorted vector of iterators std::vector<std::set<T>::iterator>. But it could not trivial to keep these structures in sync. Maybe you can add some like position to T? Or keep std::set<std::pair<T,int>, comp_first_of_pair<T>> where comp_first_of_pair is just to have set sorted only by T and the second int is for keeping position in set?

Just a few ideas - to have even O(1) distance time...

You can find the index of an element in a set in O(log(N)) with an ordered set: https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/ . This is implemented as a red-black tree. I know this topic is very old, but it might help readers in the future.