C++ set: counting elements less than a value
algorithm, c++, complexity-theory, performance, stl
Solution
What you need is an 'order-statistics tree'. It is essentially an augmented (binary search) tree that supports the additional operation `rank(x)` which gives you the number of elements with less or equal key as element `x`. Chapter 14 in Cormen, Leiserson, Rivest, Stein; "Introduction to Algorithms" should give you the algorithmic background.
There is also some implementation on the web.
Problem
Assuming a I have an STL `set <int> s` and an `int x`, how can I count the number of elements in `s` that are less than `x`? I'm seeking an `O(log n)` (or similar; anything that's reasonably better than `O(n)`) solution; I already know about `std::distance(s.begin(), s.lower_bound(x))`, but that's `O(n)`, I believe, because `set`s aren't random-access.