在 set<pair> 中查找具有特定第一个坐标的任何元素 >

Question

我正在尝试解决以下问题。

假设我在 C++ 中有以下容器：

std::set<std::pair<int, int> > my_container;

这个集合（字典）是根据 std::pair<int, int> 上的 < 顺序排序的，这是字典顺序。我的任务是在 my_container 中找到 any 元素，其第一个坐标等于 x，return 是它的迭代器。显然，我不想使用find_if，因为我需要在对数时间内解决这个问题。

我将不胜感激有关如何完成此操作的任何建议

Answer 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()）。

Answer 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

在 set<pair> 中查找具有特定第一个坐标的任何元素 >

Finding any element with specific first coordinate in set<pair> >

c++

containers

stl