Suppose I have a set<int> S;

I want to know how many members of S are less than x. Naively I could do
set<int>::iterator it;
it = S.lower_bound(x);
distance(S.begin(), it);

However, distance() is linear time. Is there a way to find this quanity using STL in log time? I could write an AVL binary tree too, but I'm hoping for a simple way to do it.

std::set does not support this operation. You must reimplement BST by your own.