Сравнение с stl sort () - PullRequest
Новая
       16

Сравнение с stl sort ()

1 голос
/ 17 ноября 2011

Я пытаюсь использовать stl sort () в функции класса.Я хотел бы отсортировать массив структур, которые выглядят следующим образом: 

struct foo{
    double num;
    std::string s;
};

с функцией сравнения, подобной этой: 

bool aGreaterThanb(foo a, foo b){
    if (a.num > b.num){
        if(a.num == b.num){
            if (anotherOutsideComparison(a.s, b.s)){
                return true;
            }
        }
        else
            return true;
    }
    else
        return false;
}

Но я не уверен, как я могу отформатировать эточтобы получить его для компиляции.Как мне отформатировать это, чтобы я мог позвонить sort(fooarray[0], fooarray[end], aGreaterThanb);?(Пример был бы великолепен)

Ответы [ 6 ]

4 голосов
/ 17 ноября 2011

Напишите функцию сравнения как operator() метод структуры, называемой функтором : 

struct aGreaterThanb
{
    bool operator() (const foo& a, const foo& b)
    {
        // return true iff a is strictly less than b according to your ordering
    }
};

Затем передайте экземпляр этого объекта функтора в std::sort: 

std::sort(fooarray.begin(), fooarray.end(), aGreaterThanb());
3 голосов
/ 17 ноября 2011

Если вы используете массив foo, например: 

foo fooarray[Foos];
...
sort(fooarray, fooarray + Foos, &aGreaterThanb);

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

Кроме того, чтобы избежать копирования большого количества foo -объектов просто для сравнения, объявите ваш компаратор в качестве аргументов const foo& вместо foo. 

bool aGreaterThanb(const foo& a, const foo& b) {
2 голосов
/ 17 ноября 2011

Вы должны передать итераторы - обобщенный расширенный набор указателей - в функцию STL sort: 

std::sort(fooarray, fooarray + end, &aGreaterThanb);
1 голос
/ 17 ноября 2011

Это работает так, как вы уже хотите: 

#include <algorithm>
int main()
{
    foo     data[10];
    std::sort(&data[0], &data[10], aGreaterThanb);
}

Но у вас есть синтаксическая ошибка.Вам не хватает скобки: 

        return true;
} // <--- Missing this line
else
    return false;

Для эффективности вы должны пройти по константной ссылке: 

bool aGreaterThanb(foo const& a, foo const& b){
0 голосов
/ 17 ноября 2011

Обратите внимание, что в худшем случае функция сортировки может содержать до N ^ 2 сравнений. А сложность stable_sort находится между N * logN и N * (LogN ^ 2)

0 голосов
/ 17 ноября 2011

Сделайте его оператором. 

struct foo {
    double num;
    std::string s;
};

bool operator>(const foo& a, const foo& b) {
    return (
        (a.num > b.num) ||
        ((a.num == b.num) &&
        anotherOutsideComparison(a.s, b.s))
    );
}

// note: std::sort expects operator<
bool operator<(const foo& a, const foo& b) {
    return b > a;
}

Если вы действительно хотите отсортировать, используя оператор>, передайте std::greater<foo>() в качестве функтора. 

std::sort(foos.begin(), foos.end(), std::greater<foo>());
...