как проверить, есть ли в наборе элементы в определенном диапазоне на С++

Мне нужно проверить, содержит ли 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 является логарифмическим, верно?


c++ set search stl stdset
person Qiang Li    schedule 25.01.2012    source источник

Ответы (2)


arrow_upward
6
arrow_downward

Вы можете использовать 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)

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

person James McNellis    schedule 25.01.2012

arrow_upward
1
arrow_downward

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

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

person ruakh    schedule 25.01.2012