0

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

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

如何在列表中找到距离大于 distance(19.0f) 的第一个元素？如何申请列表二分查找？（迭代效率不够，列表很长）？有更优雅的解决方案吗？

4

6 回答 6

3

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

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

于 2012-10-20T10:05:54.870 回答
2

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

于 2012-10-20T10:07:39.283 回答
2

您不能对链表进行二分搜索。考虑用vectoror替换它multiset。

于 2012-10-20T10:05:38.987 回答
2

您不能有效地对链表执行二进制搜索，因为随机访问时间是O(n)，而O(1)二进制搜索正常工作需要。

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

于 2012-10-20T10:06:05.047 回答
1

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

于 2012-10-20T13:32:30.210 回答
0

如何在列表中找到距离大于距离（19.0f）的第一个元素？如何应用于列表二分搜索？（迭代效率不够，list很长）

正如其他几个回答者所说，二分查找不适用于std::list; 但如果您将您的更改list为 a 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);
}
于 2019-02-16T18:06:29.340 回答