Блог

Главная - Вопросы по программированию - Как получить указатель на элемент списка, который остается после сортировки в C

Как получить указатель на элемент списка, который остается после сортировки в C

#c #list #pointers #vector #std

#c #Список #указатели #вектор #std

Вопрос:

Я держу в списке несколько двумерных точек с координатами x-y. У меня есть метод, который сортирует массив в соответствии с расстояниями, которые точки имеют с курсором, и метод возвращает указатель на точку, которая находится ближе всего к курсору.

Однако я использую amp;points.first(), и это всегда указывает на первый элемент списка. Однако указатель меняется после того, как я обращаюсь к списку. Как мне получить указатель, который указывает на конкретный ЭЛЕМЕНТ, а не на первый элемент списка.

Я пробовал: amp;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), [amp;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 amp;points.first();
}

Каждый раз, когда я вызываю этот метод рядом с новой точкой, указатель просто перемещается на первый элемент списка, что он и должен ДЕЛАТЬ, я это знаю. Но как мне сделать это так, как мне нужно?

Комментарии:

1. Не забывайте , что C настоятельно рекомендует использовать nullptr вместо NULL .

2. не используйте списки, если это не является абсолютно необходимым. Они если не злые, то адские.

3. элемент в списке — это элемент. В контейнерах хранятся значения, а не ссылки, поэтому, если вы хотите, чтобы ваши объекты имели некоторые идентификаторы вне списка, вы могли бы хранить указатели в списке, но это часто не очень хорошая идея, поэтому лучше использовать то, что было предложено в ответах

Ответ №1:

Вероятно, вам следует выполнить линейный поиск, чтобы найти этот элемент, потому что сортировка обходится дороже.

Линейный поиск O(N) .

Сортировка есть O(N*log2(N)) .

Например.:

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

Ответ №2:

Поскольку ваш список в конечном итоге отсортирован, вы можете найти исходную первую точку log2(n) поэтапно, используя двоичный поиск:

 #include <algorithm>

Point2 *DrawingWidget::closestToCursor() {
    if (points.isEmpty())
        return NULL;
    Point2 pos(m_x, m_y);
    auto cmpfun = [amp;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 amp;*std::lower_bound(std::begin(points), std::end(points),
                              firstPoint, cmpfun);
}

Существуют и другие подходы, такие как decorate-sort-undecorate для сортировки указателей и действительно сохранения исходной точки, но они, вероятно, в конечном итоге будут значительно дороже выполняться.

Метки: