提问人：student126 提问时间：4/16/2019 更新时间：4/16/2019 访问量：203
如何获取在 C++ 中排序后保留的列表元素指针
How to get a pointer of list element that stays after sorting in C++
问：
我在列表中保留了一些带有 x-y 坐标的 2D 点。我有一种方法，它根据点与光标的距离对数组进行排序，并且该方法将指针返回到最接近光标的点。
但是，我使用的是 &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();
}
每次我在新点附近调用此方法时，指针都会移动到列表的第一个元素，这是它应该做的，我知道这一点。但是我该怎么做呢？
答：
1赞
Maxim Egorushkin
4/16/2019
#1
您可能应该进行线性搜索以查找该元素，因为排序成本更高。
线性搜索是 。O(N)
排序是 。O(N*log2(N))
例如：
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;
0赞
user4815162342
4/16/2019
#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);
}
还有其他方法，例如装饰-排序-取消装饰来对指针进行排序并真正保留原始点，但这些方法最终可能会大大增加执行成本。
评论
nullptr而不是 .NULL