Как проверить, имеет ли набор элемент (ы) в определенном диапазоне в C++

Question

Мне нужно проверить, содержит ли элемент std::set элемент/элементы в диапазоне. Например, если набор равен set<int>{1, 2, 4, 7, 8} и задан интервал int[3, 5] (включая обе конечные точки), мне нужно знать, есть ли в нем элементы. В этом случае верните true. Но если интервал [5, 6], верните false. Интервал может быть [4, 4], но не [5, 3].

Похоже, я могу использовать set::lower_bound, но я не уверен, является ли это правильным подходом. Я также хочу, чтобы сложность была как можно ниже. Я считаю, что использование lower_bound является логарифмическим, правильно?

Answer 1

Вы можете использовать lower_bound и upper_bound вместе. Ваш пример тестирования элементов от 3 до 5 включительно, можно записать следующим образом:

bool contains_elements_in_range = s.lower_bound(3) != s.upper_bound(5); 

Вы можете сделать диапазон включительно или исключительно на обоих концах посредством коммутации, используемой функции (upper_bound или lower_bound):

s.upper_bound(2) != s.upper_bound(5); // Tests (2, 5] 
s.lower_bound(3) != s.lower_bound(6); // Tests [3, 6) 
s.upper_bound(2) != s.lower_bound(6); // Tests (2, 6) 

логарифмическое время лучшего, что вы можете достичь для этого, так как множество сортируются и вам необходимо найти элемент в отсортированном диапазоне, что требует дихотомического поиска.

Answer 2

Если вы уверены, что собираетесь использовать std::set, я согласен с тем, что его метод lower_bound - это путь. Как вы говорите, у него будет логарифмическая временная сложность.

Но в зависимости от того, что вы пытаетесь сделать, общая производительность вашей программы может быть лучше, если вы используете отсортированный std::vector и автономный алгоритм std::lower_bound (std::lower_bound(v.begin(), v.end(), 3)). Это также логарифмически, но с меньшей константой. (Недостатком, конечно же, является то, что вставка элементов в std::vector и хранение их сортировки обычно намного дороже, чем вставка элементов в std::set.)