查找集合中具有特定第一个坐标的任何元素<pair>> [英] Finding any element with specific first coordinate in set<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).

这篇关于查找集合中具有特定第一个坐标的任何元素<pair>>的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！