


This is the algo:

4. Store the distance in another array Lets say CountSmaller.
4. Print that array



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.

The type 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 std::set. 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$.

  • $\begingroup$ Thats a lot for your answer. Brings a lot more perspective to this. However, I would be lil' more comforted if I understand/ get to visualize the distance function as it works for a set (internally). Any resources? $\endgroup$ – user248884 Jul 5 '20 at 18:24
  • 1
    $\begingroup$ The distance function doesn't do anything particular for a set, as you can see here. It just increments an iterator $x$ until it reaches $y$. What you want to inspect is the function that advances the iterator. For gcc's implementation you want the function local_Rb_tree_increment from here. $\endgroup$ – Steven Jul 5 '20 at 18:47

Your Answer

