如何找到距离大于19.0f的排序列表中的第一个元素？

Question

在std :: pair的排序列表中，按原点的距离按升序排序

pair<float,float> origin;
list<pair<float,float> > points;
float distance=19.0f;

如何找到距离大于距离（19.0f）的列表中的第一个元素？如何申请列表二进制搜索？ （迭代效率不高，列表很长）？有更优雅的解决方案吗？

Answer 1

列表不适合二进制搜索。这是因为您只能按顺序访问列表中的元素（您只能从元素k访问元素k-1），所以如果必须使用列表，除了线性搜索第一个元素之外别无选择比distance大。

如果你想进行二进制搜索，可以使用vector这样的容器，允许直接访问元素（如myvector[i]）

Answer 2

您不能在链接列表上进行二进制搜索。考虑用vector或multiset替换它。

Answer 3

您无法有效地在链表上执行二进制搜索，因为随机访问时间是O(n)，而O(1)是二进制搜索正常工作所必需的。

除非选择不同的数据结构，否则您需要遍历列表，没有其他方法。

Answer 4

使用find_if。如前所述，binary_search不能用于std::list，因为你无法访问列表中的随机元素。

Answer 5

您可以使用boost::flat_set在常规向量之上实现有序容器的语义。

Answer 6

如何找到距离大于距离（19.0f）的列表中的第一个元素？如何申请列表二进制搜索？ （迭代效率不高，列表很长）

正如其他几位回答者所说，二分搜索不适用于std::list;但如果你将你的list改为vector，那么你正在寻找的算法拼写为std::partition_point。

using Point = std::pair<float, float>;
float distance_between(Point, Point);

Point origin(0, 0);
std::vector<Point> points = { some stuff... };

// sort in ascending order by distance from origin point
std::sort(
    points.begin(), points.end(),
    [&](const auto& p1, const auto& p2) {
        return distance_between(origin, p1) < distance_between(origin, p2);
    }
);

现在这是你想知道的部分：

// find first element with distance bigger than 19.0f
auto it = std::partition_point(
    points.begin(), points.end(),
    [&](const auto& pt) {
        return distance_between(origin, pt) < 19.0f;
    }
);

返回的迭代器将是这样的：

if (it > points.begin()) {
    assert(distance_between(origin, *(it-1)) < 19.0f);
}
if (it < points.end()) {
    assert(distance_between(origin, *it) >= 19.0f);
}