Сортировка структуры точек с помощью sort

368
27 января 2017, 06:39

У меня есть структура точки:

struct Point  
{  
    double x;  
    double y;  
};

У меня есть два массива этих точек, один из которых (ans) нужно отсортировать сначала по иксу, потом по игреку:

 Point p[51],ans[400000];

По аналогии с примером, который нашел здесь для целочисленных значений структуры, попробовал написать для своего случая:

sort(ans,ans+sochcnt+1, [&](Point &a, Point &b){ return RealLessEq(a.x,b.x) });
sort(ans,ans+sochcnt+1, [&](Point &a, Point &b){ return RealLessEq(a.y,b.y) });

где RealLessEq - процедура сравнения двух вещественных чисел (возвращает true, если a<=b):

bool RealLessEq(double a, double b)
{
    if ((a-b)<=Eps)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

где double Eps=1e-6; Компилятор на строку sort(ans,ans+sochcnt+1, [&](Point &a, Point &b){ return RealLessEq(a.x,b.x) }); выдает ошибку expected ';' before '}' token|

Подскажите, как это сделать корректно.

Answer 1

Ну, вам ответили вполне понятно - вы забыли точку с запятой:

sort(ans,ans+sochcnt+1, [&](Point &a, Point &b){ return RealLessEq(a.x,b.x); });
                                                                           ^

Но есть еще замечания. Даже не знаю, с какого начать...
отсортировать сначала по иксу, потом по игреку - это как? Просто отсортировать по x, поработать, а потом еще раз - по y, потеряв сортировку по x? Или при равных x должны быть отсортированы по y? Вы решаете задачу в первом понимании, но не во втором! Чтобы решать во втором варианте - должна быть функция, сравнивающая x, а при равенстве - y. Примерно

[](const Point&a, const Point&b) 
    { return (a.x < b.x) ? true : (a.x > b.x) ? false : (a.y < b.y); }

Далее, если у вас sochcnt элементов в массиве, то и вызывать сортировку надо как

sort(ans,ans+sochcnt, ...

Конечно, если их sochcnt+1, то у вас все верно, тут я просто не знаю.

И еще - компаратор возвращает результат сравнения меньше, а не меньше или равно. Строго меньше. Если ему понадобится проверка на равенство, алгоритм ее выполнит сам, как !((a<b)||(b<a)).

Answer 2

В обоих этих предложениях

sort(ans,ans+sochcnt+1, [&](Point &a, Point &b){ return RealLessEq(a.x,b.x) });
                                                                          ^^      
sort(ans,ans+sochcnt+1, [&](Point &a, Point &b){ return RealLessEq(a.y,b.y) });
                                                                          ^^    

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

Данная функция неверная

bool RealLessEq(double a, double b)
{
    if ((a-b)<=Eps)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

так как сравнение должно удовлетворять условию (так называемое strict weak ordering), при котором, например, выражение !RealLessEq( x, x ) должно иметь значение true. То есть должна иметь проверка на строгое неравенство.

Поэтому по крайней мере эту функцию, если она используется в сортировке, следует написать как

bool RealLessEq(double a, double b)
{
    return a < b;
}

Для получения указателей на начало массива и на конец массива, то есть на место после последнего элемента массива, чтобы задать диапазон итераторов, можно использовать стандартные функции std::begin и std::end, которые объвоены в заголовке <iterator>.

Вызов стандартного алгоритма будет выглядеть следующим образом

std::sort(std::begin(ans), std::end(ans),
    [](const Point &a, const Point &b) 
    { 
        return RealLessEq(a.x, b.x); 
    });

или для сортировки по вторым координатам

std::sort(std::begin(ans), std::end(ans),
    [](const Point &a, const Point &b) 
    { 
        return RealLessEq(a.y, b.y); 
    });

Вот демонстрационная программа

#include <iostream>
#include <algorithm>
#include <iterator>
bool RealLessEq(double a, double b)
{
    return a < b;
}
int main()
{
    struct Point
    {
        double x;
        double y;
    };
    Point ans[] = { { 2, 3 }, { 1, 4 }, { 3, 0 } };
    std::sort(std::begin(ans), std::end(ans),
        [](const Point &a, const Point &b) 
        { 
            return RealLessEq(a.x, b.x); 
        });
    for (const auto &p : ans)
    {
        std::cout << p.x << ' ' << p.y << std::endl;
    }
    std::cout << std::endl;
    std::sort(std::begin(ans), std::end(ans),
        [](const Point &a, const Point &b)
        {
            return RealLessEq(a.y, b.y);
        });
    for (const auto &p : ans)
    {
        std::cout << p.x << ' ' << p.y << std::endl;
    }
    return 0;
}

Ее вывод на консоль

1 4
2 3
3 0
3 0
2 3
1 4

В принципе функция RealLessEq для такого простого сравнения чисел с плавающей запятой не нужна. Вы могли бы записать лямбда вырадение, например, в виде

    std::sort(std::begin(ans), std::end(ans),
        [](const Point &a, const Point &b) 
        { 
            return a.x < b.x; 
        });

Если вам нужно отсортировать точки по x, а затем внутри этой сортировки по y, то делается это просто с помощью стандартной функции std::tie, объявленной в заголовке <tuple>. Например,

std::sort(std::begin(ans), std::end(ans),
    [](const Point &a, const Point &b)
    {
        return std::tie( a.x, a.y ) < std::tie( b.x, b.y );
    });
READ ALSO
Рекурсия вызваная из базового класса

Рекурсия вызваная из базового класса

Все мы знаем обычную рекурсию, например:

365
Размер массива string

Размер массива string

Есть массив типа string, в который может быть записано как 1, так и 200 значений

348
Получение директории из argv

Получение директории из argv

В argv[0] находится полный путь до до исполняемого файла, а как получить директорию, в которой находится файл?

364
Преобразование огромных чисел

Преобразование огромных чисел

Преобразую значения из string в long long

426