查找集合中具有特定第一个坐标的任何元素<pair>>
我正在尝试找出以下问题.
I'm trying to figure out the following problem.
假设我在 C++ 中有以下容器:
Suppose I have the following container in C++:
std::set<std::pair<int, int> > my_container;
这个集合(字典)按照 std::pair 上的顺序 < 排序，这是字典顺序.我的任务是在 my_container 中找到第一个坐标等于 x 的 any 元素，并将迭代器返回给它.显然，我不想使用 find_if，因为我需要在对数时间内解决这个问题.
This set (dictionary) is sorted with respect to the order < on std::pair<int, int>, which is the lexicographic order. My task is to find any element in my_container that has the first coordinate equal to, say x, and return the iterator to it. Obviously, I don't want to use find_if, because I need to solve this in logarithmic time.
我会很感激任何关于如何做到这一点的建议
I would appreciate any advice on how this can be done
推荐答案
你可以使用??lower_bound 为此:
You can use lower_bound for this:
auto it = my_container.lower_bound(std::make_pair(x, std::numeric_limits<int>::min());
这会给你一个迭代器到第一个元素 e 其中 e <std::pair(x, -LIMIT) 不成立.
This will give you an iterator to the first element e for which e < std::pair(x, -LIMIT) does not hold.
这样的元素要么具有它的第一个组件 > x(在这种情况下，集合中没有 x)，或者具有等于 x 的第一个组件 并且是第一个这样的.(请注意，根据定义，所有第二个组件都大于或等于 std::numeric_limits<int>::min().
Such an element either has its first component > x (in which case there's no x in the set), or has the first component equal to x and is the first such. (Note that all second components are greater than or equal to std::numeric_limits<int>::min() by definition).
相关文章