Алгоритм сортировки вектора, сортировка только элементов больше 0

Question

Я должен отсортировать вектор структур.Допустим, структура имеет двух членов:

Struct game
{
  string name;
  int rating;
};

Итак, я создал std::vector<game> игр и просто отсортировал их по рейтингу.

std::sort(games.begin(),games.end(), [](game& info1, game& info2)
{
    return info1.rating > info2.rating;
});

Все естьпока все в порядке.Проблема в том, что если все игры имеют рейтинг 0, они смешиваются.Проще говоря, я должен сортировать только элементы с рейтингом больше нуля.Давайте приведем пример:

Все игры помещаются в векторе по именам в алфавитном порядке и с рейтингом 0, когда сортировка запускается, порядок алфавита нарушается.

Пример перед сортировкой:

"A_Game", "B_Game", "C_Game", "E_Game", "G_Game" и т. Д. (Продолжить со всеми последующими буквами)

после сортировки (все игры с рейтингом 0):

"G_Game", "S_Game", "P_Game", "M_Game", "L_Game", "I_Game" и т. Д.

Мне нужно отсортировать только те игры, которые имеют рейтингбольше 0. Спасибо заранее.

Answer 1

std::sort действительно не гарантирует какого-либо порядка, когда элементы сравниваются одинаково.std::stable_sort гарантирует, что исходный порядок сохраняется, если он сравнивается равным.(См. Другие ответы)

Если вы сомневаетесь в исходном порядке, я хочу явно отсортировать по всем критериям:

std::sort(games.begin(),games.end(), [](game const & info1, game const & info2)
{
    if (info1.rating != info2.rating)
        return info1.rating > info2.rating;

    return info1.name < info2.name;
});

В приведенном выше, я предпочитаю использовать следующееpattern

if member1 different
    return compare member1
if member2 different
    return compare member2

return compare member<last> OR compare pointers

Этот шаблон легко узнаваем и легко расширяем при добавлении дополнительных элементов.

В идеале, когда вы хотите использовать эту сортировку в других местах, вы делаете это функцией соднозначное имя.(Не используйте operator<, так как это может привести к путанице, поскольку названия игр также могут использоваться в качестве логического способа сортировки)

Answer 2

Вы можете использовать stable_sort вместо sort.Это был бы лучший вариант для вопроса.

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

std::sort(games.begin(),games.end(), [](game& info1, game& info2)
{
    if (info1.rating == info2.rating)
        return info1.name.compare(info2.name);

    return info1.rating > info2.rating;
});

Answer 3

std::sort() is not a stable алгоритм сортировки , т. Е. Элементы с эквивалентными ключами могут не сохранять исходный порядок междупосле сортировки.

---

Вы можете использовать std::stable_sort() вместо std::sort():

std::stable_sort(games.begin(),games.end(), [](game& info1, game& info2)
{
    return info1.rating > info2.rating;
});

Как следует из названия, std::stable_sort()реализует алгоритм стабильной сортировки.

Answer 4

Вы можете использовать std::stable_sort().

Однако вы можете продолжать использовать std::sort() и вернуть компаратору true для игр с одинаковым рейтингом (так что относительный порядок сохраняется), изменивусловие до

return !(info1.rating < info2.rating)

Answer 5

Вы можете использовать std::stable_sort, чтобы предотвратить перемещение элементов, на которые не влияют критерии сортировки.

std::stable_sort(games.begin(),games.end(), [](game& info1, game& info2)
{
    return info1.rating > info2.rating;
});