如何获取在C ++中排序后保留的列表元素的指针

Question

我在列表中持有一些带有x-y坐标的二维点。我有一个方法，根据点与光标的距离对数组进行排序，该方法返回指向最接近光标的点的指针。

但是我正在使用＆points.first（），这总是指向列表的第一个元素。但是，在我使用列表后指针会发生变化。如何获得指向特定ELEMENT的指针，而不是列表的第一个元素。

我试过了：＆points.first（）

QList<Point2> points;


Point2 *DrawingWidget::closestToCursor(){
    // Current mouse position
    Point2 pos(m_x, m_y);

    // There are no points
    if(points.isEmpty()){
        return NULL;
    }

    // Sorts according to distance to the cursor
    std::sort(std::begin(points), std::end(points), [&pos](Point2 a, Point2 b) {
            return pos.distanceFrom(a) < pos.distanceFrom(b);
    });

    // We dont allow points closer than 50px appart
    if(pos.distanceFrom(points.first()) > 50){
        return NULL;
    }

    // Even after the resort, this always points to the first element of the vector. How do I get this elements pointer instead? 
    // Currently it seems that the pointer is basically LIST+0x0, however if the element shifts to whatever position, how do I still have its pointer?
    return &points.first();
}

每当我在新点附近调用此方法时，指针只会转移到列表的第一个元素，这就是它应该做的事情，我知道这一点。但是我该怎么做呢？

Answer 1

您应该进行线性搜索以找到该元素，因为排序更昂贵。

线性搜索是O(N)。

排序是O(N*log2(N))。

Ef。：

auto& found = *std::min_element(std::begin(points), std::end(points),
                                [&pos](Point a, Point b) { return pos.distanceFrom(a) < pos.distanceFrom(b); });
return pos.distanceFrom(found) > 50 ? 0 : &found;

Answer 2

由于您的列表最终排序，您可以使用二进制搜索在log2(n)步骤中找到原始的第一个点：

#include <algorithm>

Point2 *DrawingWidget::closestToCursor() {
    if (points.isEmpty())
        return NULL;
    Point2 pos(m_x, m_y);
    auto cmpfun = [&pos](Point2 a, Point2 b) {
            return pos.distanceFrom(a) < pos.distanceFrom(b);
    });
    auto firstPoint = points.first();

    std::sort(std::begin(points), std::end(points), cmpfun);
    if (pos.distanceFrom(points.first()) > 50)
        return NULL;

    // return a pointer to the original first point
    return &*std::lower_bound(std::begin(points), std::end(points),
                              firstPoint, cmpfun);
}

还有其他方法，例如decorate-sort-undecorate来对指针进行排序并真正保留原始点，但这些方法最终可能会更加昂贵。