В этом посте мы обсудим, как сортировать vector в порядке убывания в C++.
1. Используйте std::sort (или же std::stable_sort)
Эффективным решением является использование std::sort алгоритм, определенный в <algorithm> заголовок. Обычно это высокоэффективная реализация Алгоритм интросортировки, который начинается с быстрая сортировка и переключается на сортировка кучей когда рекурсия идет слишком глубоко.
The std::sort алгоритм не поддерживает относительный порядок равных элементов. Чтобы получить стабильную сортировку, используйте std::stable_sort, который использует Сортировка слиянием алгоритм.
Версия с двумя аргументами std::sort алгоритм сортирует vector в порядке возрастания, используя operator<. Чтобы получить порядок убывания, позвоните по номеру std::reverse после std::sort.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> vec = { 7, 3, 5, 1, 9 }; std::sort(vec.begin(), vec.end()); std::reverse(vec.begin(), vec.end()); // Делать что-нибудь return 0; } |
Приведенный выше код требует дополнительного прохода для обращения вектора. Можно избежать вызова std::reverse с помощью обратных итераторов.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> vec = { 7, 3, 5, 1, 9 }; std::sort(vec.rbegin(), vec.rend()); // Делать что-нибудь return 0; } |
2. Использование std::sort + компаратор
The std::sort функция имеет другую перегруженную версию, которая принимает компаратор. Компаратор — это двоичный предикат, который принимает два аргумента и возвращает логическое значение, определяющее, появляется ли первый аргумент перед вторым аргументом в выходной последовательности.
1. Мы можем использовать std::greater как компаратор, который возвращает true, если первый аргумент больше второго аргумента. Начиная с C++14, вы даже можете пропустить аргументы шаблона, т.е. std::greater<int>() становится std::greater<>().
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> vec = { 7, 3, 5, 1, 9 }; std::sort(vec.begin(), vec.end(), std::greater<>()); // Делать что-нибудь return 0; } |
2. Компаратором может быть простая бинарная функция, или вы можете передать свой собственный объект функции. Вам просто нужен экземпляр класса с operator() определенный.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include <iostream> #include <vector> #include <algorithm> // Двоичный предикат struct comp { template<typename T> bool operator()(const T &l, const T &r) const { return l > r; } }; /* bool fn(int i, int j) { вернуть я > j; } */ int main() { std::vector<int> vec = { 7, 3, 5, 1, 9 }; std::sort(vec.begin(), vec.end(), comp()); // или позвоните по телефону // std::sort(vec.begin(), vec.end(), fn); // Делать что-нибудь return 0; } |
3. С C++11 вы даже можете передать лямбда-функцию в std::sort функция.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> vec = { 7, 3, 5, 1, 9 }; std::sort(vec.begin(), vec.end(), [](const int &l, const int &r) { return l > r; }); // Делать что-нибудь return 0; } |
3. Пользовательская процедура сортировки
Наконец, вы также можете написать свою собственную эффективную процедуру для сортировки вектора в порядке убывания, используя быстрая сортировка, Сортировка слиянием алгоритмы и т.д.
Вот и все, что касается сортировки вектора по убыванию в C++.