The complexity of the distance function depends on the type of the iterators supplied: in general it only required to take linear time in the distance but, in the special case in which the input iterators are random access iterators, the worst-case running time is linear. (I believe this is accounting for the time spent in the function in itself, and assumes that the time needed to advance iterators is constant).
The C++ specification do not mandate any particular implementation as long as it conforms to the required complexity so your question cannot be answered without inspecting the particular implementation that you are using.
However, just to convey the intuition, here are two possible implementations that would conform to the requirements:
- Given random access iterators $x$ and $y$, distance($x$, $y$) returns $y-x$.
- For general iterators increment $x$ until it equals $y$. Return the number of increments performed.
std::set does not return a random access iterator, therefore
std::distance can take linear time and the second implementation above can be used. Now your question reduces to "how can the standard library iterate over the elements of a
std::set in sorted order?"
The answer to this question depends once again on the implementation as there is no particular data structure mandated by the standard to implement
Since you mention red-black trees, which are a special kind of BSTs, this can easily be done by noticing that the order of iteration coincides with the order in which the vertices of a BST are visited by an in-order visit.
Notice that the concept of distance completely abstracts from the data structure used to store the elements of the set. Instead it only refers to the positions in which two elements appear when using an iterator to access the collection's contents.
In the case of
std::set the elements appear in sorted order. This also means that the distance between an iterator pointing to the beginning of the collection and an iterator pointing to an element $x$ is exactly the number of elements that are smaller than $x$.