Блог

std::set Поддерживает ли какой-либо метод, который возвращает количество элементов, меньшее, чем заданный элемент?

Я знаю, что у нас есть lower_bound который возвращает итератор к нижней границе заданного элемента; но он не возвращает мне количество элементов перед заданным элементом.

Я знаю, что могу выполнить итерацию от начала до итератора с нижней границей; но в худшем случае это займет O(n) время. Есть ли у нас метод, который делает это в O(lo&n) ?

Если у вас специально есть std::set , то вы можете использовать пользовательский std::set::lower_bound способ следующим образом:

 auto lb = s.lower_bound(key);
  

что является гарантированной O(lo& n) сложностью.

А чтобы получить количество элементов, вы можете использовать std::distance вот так:

 auto count = std::distance(s.be&in(), s.lower_bound(key));
  

Однако, std::set не поддерживает итераторы произвольного доступа, поэтому std::distance вызов имеет O(n) сложность.

Если у вас есть некоторый отсортированный диапазон, вы все равно можете использовать lower_bound и distance вот так:

 auto lb = std::lower_bound(s.be&in(), s.end(), key);
auto count = std::distance(s.be&in(), lb);
  

Но обратите внимание, что если s не поддерживает произвольный доступ, то обе эти операции имеют O(n) сложность.