C ++ набор: подсчет элементов меньше значения
Предполагая, у меня есть STLset <int> s
иint x
Как я могу посчитать количество элементов вs
которые меньше чемx
?
Я ищуO(log n)
(или что-то похожее;O(n)
) решение;
Я уже знаю оstd::distance(s.begin(), s.lower_bound(x))
, но этоO(n)
Я верю, потому чтоset
с не случайным доступом.