Как проверить, есть ли набор элементов в определенном диапазоне в C ++ - PullRequest
Новая
       80

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

6 голосов
/ 25 января 2012

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

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

Ответы [ 2 ]

5 голосов
/ 25 января 2012

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

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

1 голос
/ 25 января 2012

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

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

...