Поиск любого элемента с определенной первой координатой в наборе <pair>>

Предположим, что у меня есть следующий контейнер в С++:

Этот набор (словарь) сортируется относительно порядка < на std::pair<int, int>, который является лексикографическим порядком. Моя задача - найти любой элемент в my_container, который имеет первую координату, равную, скажем, x, и вернуть к ней итератор. Очевидно, я не хочу использовать find_if, потому что мне нужно решить это в логарифмическом времени.

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

Ответы

Ответ 1

Вы можете использовать lower_bound для этого:

auto it = my_container.lower_bound(std::make_pair(x, std::numeric_limits<int>::min());

Это даст вам итератор первому элементу e, для которого e < std::pair(x, -LIMIT) не выполняется.

Такой элемент либо имеет свой первый компонент > x (в этом случае в наборе нет x), либо имеет первый компонент, равный x, и является первым таким. (Обратите внимание, что все остальные компоненты по определению больше или равны std::numeric_limits<int>::min()).

Ответ 2

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

#include <set>
#include <iostream>

// for readability
typedef std::set<std::pair<int, int> > int_set;

void print_results(const int_set& s, int i)
{
    // first element not less than {i, 0}
    int_set::const_iterator lower = s.lower_bound(std::make_pair(i, 0));

    // first element not less than {i + 1, 0}
    int_set::const_iterator upper = s.lower_bound(std::make_pair(i + 1, 0));

    for(int_set::const_iterator iter = lower; iter != upper; ++iter)
        std::cout << iter->first << ", " << iter->second << '\n';
}

int main()
{
    int_set s;

    s.insert(std::make_pair(2, 0));
    s.insert(std::make_pair(1, 9));
    s.insert(std::make_pair(2, 1));
    s.insert(std::make_pair(3, 0));
    s.insert(std::make_pair(7, 6));
    s.insert(std::make_pair(5, 5));
    s.insert(std::make_pair(2, 2));
    s.insert(std::make_pair(4, 3));

    print_results(s, 2);
}

Вывод:

2, 0
2, 1
2, 2