Сортировка вектора по убыванию

310

Должен ли я использовать

std::sort(numbers.begin(), numbers.end(), std::greater<int>());

или

std::sort(numbers.rbegin(), numbers.rend());   // note: reverse iterators

отсортировать вектор в порядке убывания? Есть ли какие-либо преимущества или недостатки с одним подходом или другим?

fredoverflow
источник
2
+1 Думаю, ответ очевиден, но в этом вопросе есть интересная мелочь. :)
wilhelmtell
3
Я бы проголосовал за первый вариант, просто потому, что тогда мне не придется иметь дело с этим reverse_iterator.
evandrix
2
@wilhelmtell Нубский вопрос, но почему второй должен сортироваться в порядке убывания? Мы даем тот же массив в качестве входных данных для метода сортировки. Просто мы даем его в обратном порядке, так почему он должен быть отсортирован по убыванию, а не по возрастанию, как это было бы в случае с ar.begin () и ar.end.
Шшнк
6
@shshnk std::sort(b, e);ставит минимум на b(в нашем случае rbegin, так что последний элемент) и максимум на e(в нашем случае rend, так что первый элемент).
fredoverflow

Ответы:

114

На самом деле, первая - плохая идея. Используйте либо второй , либо этот:

struct greater
{
    template<class T>
    bool operator()(T const &a, T const &b) const { return a > b; }
};

std::sort(numbers.begin(), numbers.end(), greater());

Таким образом, ваш код не будет молча ломаться, когда кто-то решит, что он numbersдолжен храниться longили long longвместо int.

user541686
источник
1
@FredOverflow: Вы сделали почести в своем комментарии;)
user541686
2
Или придерживаться первого. Используйте typedef для numberContainer - хорошая идея, чтобы кто-то мог поменяться на long long - и напишите: std :: sort (numbers.begin (), numbers.end (), std :: большее <numContainer :: value_type> ( ));
Ричард Хауэллс
1
+1 Первый действительно сбивает с толку. Что то, greaterчем другие? rbeginи rendбыли сделаны для конкретной цели.
Абхишек Дивекар
6
Почему не просто std::greater<typename decltype(numbers)::value_type>()или что-то?
einpoklum
1
Этот ответ устарел - вы можете использовать std::greater<>()начиная с C ++ 14.
Николай
70

Используйте первое:

std::sort(numbers.begin(), numbers.end(), std::greater<int>());

Это явно что происходит - меньше шансов искажения , rbeginкак begin, даже с комментарием. Это ясно и понятно, что именно то, что вы хотите.

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

Pubby
источник
68

С C ++ 14 вы можете сделать это:

std::sort(numbers.begin(), numbers.end(), std::greater<>());
mrexciting
источник
30

Как насчет этого?

std::sort(numbers.begin(), numbers.end());
std::reverse(numbers.begin(), numbers.end());
shoumikhin
источник
13
Причина может состоять в том, чтобы избежать дополнительной сложности: O (n * log (n)) + O (n) против O (n * log (n))
greg
32
@greg O (n * log (n)) = O (n * log (n) + n). Это два способа определения одного и того же набора. Вы хотите сказать: «Это может быть медленнее».
pjvandehaar
4
@pjvandehaar Грег в порядке. Он явно не сказал, O (n * log (n) + n), он сказал O (n * log (n)) + O (n). Вы правы, что его формулировка неясна (особенно его неправильное использование слова сложность), но вы могли бы ответить более добрым способом. Например: возможно, вы хотели использовать слово «вычисление» вместо слова «сложность». Реверсирование чисел является ненужным шагом O (n) по сравнению с идентичным в остальном шагом O (n * log (n)).
Офек Гила
3
@OfekGila Насколько я понимаю, нотация big-O касается наборов функций, а нотация включает в себя =и +просто означает значение и удобство . В таком случае O(n*log(n)) + O(n)это удобное обозначение, для O(n*log(n)) ∪ O(n)которого так же, как O(n*log(n)). Слово «вычисление» является хорошим предложением, и вы правы в отношении тона.
pjvandehaar
22

Вместо функтора, как предложил Mehrdad, вы можете использовать функцию Lambda.

sort(numbers.begin(), numbers.end(), [](const int a, const int b) {return a > b; });
Джулиан Деклерк
источник
16

Согласно моей машине, сортировка long longвектора [1..3000000] с использованием первого метода занимает около 4 секунд, в то время как использование второго занимает примерно вдвое больше времени. Это говорит о чем-то, очевидно, но я тоже не понимаю почему. Просто думаю, что это было бы полезно.

То же самое сообщается здесь .

Как сказал Xeo, с ними -O3они используют примерно одно и то же время, чтобы закончить.

zw324
источник
12
Возможно, вы просто не скомпилировали с включенными оптимизациями? Звучит очень похоже на то, что reverse_iteratorоперации не были встроены, и, учитывая, что они являются просто оберткой вокруг реальных итераторов, неудивительно, что они удваивают время без вставки.
Xeo
@Xeo Даже если они были встроены, некоторые реализации используют сложение для разыменования.
Пабби
@ildjarn: потому что это так? base()Функция состоит, например , возвращает обернутую итератор.
Xeo
1
@Xeo Теперь они оба заканчивают в секунду. Спасибо!
zw324
3
@Xeo: я забираю это; стандарт на самом деле обязывает, что std::vector<>::reverse_iteratorреализуется с точки зрения std::reverse_iterator<>. Необычный; сегодня я узнал. :-P
ildjarn
11

Первый подход относится к:

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

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

rashedcs
источник
Это тот же ответ, что и у mrexciting. Замечание о сложности также мне непонятно.
Филипп Классен
7
bool comp(int i, int j) { return i > j; }
sort(numbers.begin(), numbers.end(), comp);

источник
4
чтобы быть верным ответом, вам следует подумать о том, чтобы написать что-то о преимуществах / недостатках ваших методов против упоминания OP
Stefan Hegny
3

TL; DR

Используйте любой. Они почти одинаковые.

Скучный ответ

Как обычно, есть плюсы и минусы.

Используйте std::reverse_iterator:

  • Когда вы сортируете пользовательские типы и не хотите реализовывать operator>()
  • Когда тебе лень набирать std::greater<int>()

Используйте std::greaterкогда:

  • Когда вы хотите иметь более явный код
  • Когда вы хотите избежать использования неясных обратных итераторов

Что касается производительности, оба метода одинаково эффективны. Я попробовал следующий тест:

#include <algorithm>
#include <chrono>
#include <iostream>
#include <fstream>
#include <vector>

using namespace std::chrono;

/* 64 Megabytes. */
#define VECTOR_SIZE (((1 << 20) * 64) / sizeof(int))
/* Number of elements to sort. */
#define SORT_SIZE 100000

int main(int argc, char **argv) {
    std::vector<int> vec;
    vec.resize(VECTOR_SIZE);

    /* We generate more data here, so the first SORT_SIZE elements are evicted
       from the cache. */
    std::ifstream urandom("/dev/urandom", std::ios::in | std::ifstream::binary);
    urandom.read((char*)vec.data(), vec.size() * sizeof(int));
    urandom.close();

    auto start = steady_clock::now();
#if USE_REVERSE_ITER
    auto it_rbegin = vec.rend() - SORT_SIZE;
    std::sort(it_rbegin, vec.rend());
#else
    auto it_end = vec.begin() + SORT_SIZE;
    std::sort(vec.begin(), it_end, std::greater<int>());
#endif
    auto stop = steady_clock::now();

    std::cout << "Sorting time: "
          << duration_cast<microseconds>(stop - start).count()
          << "us" << std::endl;
    return 0;
}

С этой командной строкой:

g++ -g -DUSE_REVERSE_ITER=0 -std=c++11 -O3 main.cpp \
    && valgrind --cachegrind-out-file=cachegrind.out --tool=cachegrind ./a.out \
    && cg_annotate cachegrind.out
g++ -g -DUSE_REVERSE_ITER=1 -std=c++11 -O3 main.cpp \
    && valgrind --cachegrind-out-file=cachegrind.out --tool=cachegrind ./a.out \
    && cg_annotate cachegrind.out

std::greater demo std::reverse_iterator demo

Сроки такие же. Valgrind сообщает о том же количестве пропусков кеша.

ivaigult
источник
2

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

Я бы выступил за следующее, так как оно выглядит как стандартная библиотечная функция и проясняет ее намерения:

#include <iterator>

template <class RandomIt>
void reverse_sort(RandomIt first, RandomIt last)
{
    std::sort(first, last, 
        std::greater<typename std::iterator_traits<RandomIt>::value_type>());
}
Мартин Бродхерст
источник
2
Это в тысячу раз больше сбивает с толку, чем просто использование std::greaterкомпаратора ....
Аполлис поддерживает Монику
@Apollys Я согласен, что начиная с C ++ 14, std :: больше <> выглядит как предпочтительное решение. Если у вас нет C ++ 14, это может быть полезно, если вы хотите исключить какие-либо сюрпризы с помощью std :: большее <int> (например, когда типы в какой-то момент меняются с int на long).
Филипп Классен
2

Вы можете использовать первый или попробовать приведенный ниже код, который одинаково эффективен

sort(&a[0], &a[n], greater<int>());
Криш мунот
источник