C ++ set: contando elementos menores que um valor
Assumindo que eu tenho um STLset <int> s
e umint x
, como posso contar o número de elementos ems
que são menos quex
?
Estou procurando umO(log n)
(ou similar; qualquer coisa que seja razoavelmente melhor queO(n)
) solução;
Eu já conheçostd::distance(s.begin(), s.lower_bound(x))
, Mas isso éO(n)
, Acredito, porqueset
s não são acesso aleatório.