对一个向量进行降序排序

Question

我应该使用什么？

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

或者

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

如何将向量按降序排序？其中一种方法是否比另一种方法更有优势或劣势？

- fredoverflow

---

我认为答案很明显，但这个问题有一个有趣的琐事。 :) - wilhelmtell

我会选择第一个选项，因为这样我就永远不必再处理“reverse_iterator”了。 - evandrix

一个新手问题，为什么第二个例子应该按降序排序？我们将相同的数组作为输入传递给sort方法。只是我们是以相反的顺序传递它，那么为什么应该按降序排序而不是按升序排序，就像使用ar.begin()和ar.end()时一样。 - shshnk

@shshnk std::sort(b, e); 将最小值放在 b（在我们的情况下是 rbegin，即 最后 一个元素），将最大值放在 e（在我们的情况下是 rend，即 第一个 元素）。 - fredoverflow

这个回答解决了你的问题吗？将向量元素按降序排序 - Chnossos

Answer 1

实际上，第一个不是好主意。使用第二个或者这个：

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

---

@FredOverflow：你在评论中已经做了这个荣誉的事情 ;) - user541686

或者坚持使用第一个。为numberContainer使用typedef是个好主意，这样某人就可以切换到long long，并编写：std::sort(numbers.begin(), numbers.end(), std::greaternumContainer::value_type()); - RichardHowells

为什么使用Lambda不可能实现？ - yanpas

+1 第一个真的很令人困惑。什么比另一个“更大”？rbegin和rend是为特定目的而设计的。 - Abhishek Divekar

为什么不直接使用std::greater<typename decltype(numbers)::value_type>()或类似的东西？ - einpoklum

这个答案已过时 - 你可以在C++14中使用std::greater<>()。 - Nikolai

Answer 2

使用C++14，您可以这样做：

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

- mrexciting

---

C++17： std::sort(numbers.begin(), numbers.end(), std::greater{}); 对一组数字进行排序，使用的是C++17标准，排序方式为从大到小。C++20： std::ranges::sort(numbers, std::ranges::greater()); 对一组数字进行排序，使用的是C++20标准，排序方式为从大到小。在C++20中，可以使用ranges库来进行排序操作。 - Simon Eatwell

如果C++20可用，@SimonEatwell是否比前者更优秀？ - undefined

@roulette01 是的，后者更优越，因为C++20已经可用，所以在前者的情况下可能会错误地传递一对错误的迭代器。可能会意外地执行std::sort(numbers.end(), numbers.begin(), std::greater{})或std::sort(numbers.begin(), something_else.end(), std::greater{})。始终优先选择std::ranges。 - undefined

Answer 3

使用第一个：

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

这样做很明确，可以减少误读 rbegin 为 begin 的机会，即使有注释也是如此。清晰易读正是你想要的。

另外，考虑到反向迭代器的特性，第二种方法可能不如第一种方法高效，尽管你需要进行分析以确保。

- Pubby

Answer 4

这个怎么样？

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

- shoumikhin

---

可能的原因是为了避免额外的复杂度：O(n * log(n)) + O(n) 相对于 O(n * log(n))。 - greg

@Greg O(n * log(n)) = O(n * log(n) + n)，它们是定义相同集合的两种方式。你的意思是说“这可能会更慢。” - pjvandehaar

@pjvandehaar Greg没问题。他明确地没有说O(n * log(n) + n)，他说的是O(n * log(n)) + O(n)。你是对的，他的措辞不清楚（特别是他误用了“complexity”这个词），但你本可以以更友善的方式回答。例如：也许你的意思是使用词语“计算”而不是“复杂度”。将数字反转是一个不必要的O(n)步骤，对于一个完全相同的O(n * log(n))步骤而言。 - Ofek Gila

我理解的大O符号是关于函数集合的，而包含=和+符号的表达只是为了方便表示∈和∪。因此，O(n*log(n)) + O(n)是O(n*log(n)) ∪ O(n)的简便写法，等同于O(n*log(n))。关于“计算”，这是一个好建议，你的语气也是正确的。 - pjvandehaar

Answer 5

你可以使用Lambda函数，而不是像Mehrdad建议的那样使用一个函数对象。

sort(numbers.begin(), numbers.end(), [](const int a, const int b) {return a > b; });

- Julian Declercq

Answer 6

根据我的机器，使用第一种方法对 [1..3000000] 的 long long 向量进行排序大约需要 4 秒时间，而使用第二种方法需要的时间大约是前者的两倍。这显然说明了些什么，但我并不明白原因。只是认为这会有所帮助。 在这里 报告了同样的事情。

正如 Xeo 所说，使用 -O3 编译选项时它们用的时间基本相同。

- zw324

---

你是不是没有开启优化编译？听起来很像reverse_iterator操作没有进行内联，考虑到它们只是实际迭代器的包装器，所以没有内联就需要花费双倍的时间是很正常的。 - Xeo

@Xeo 即使它们被内联，某些实现也会在每次解引用时使用一个加法。 - Pubby

@ildjarn：因为就是这样？例如，base()成员函数返回封装的迭代器。 - Xeo

@Xeo 现在它们都在一秒钟内完成。谢谢！ - zw324

我收回之前的说法；实际上标准规定 std::vector<>::reverse_iterator 必须是以 std::reverse_iterator<> 为基础实现的。有点奇怪，今天我学到了。 :-P - ildjarn

迭代顺序可以根据预取和缓存优化而改变行为。https://dev59.com/gHI-5IYBdhLWcg3wPF12#1951271 - Abdurrahim

Answer 7

第一种方法如下：

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

您可以使用第一种方法，因为它比第二种方法更有效率。
第一种方法的时间复杂度小于第二种方法。

- rashedcs

---

这个回答跟mrexciting的回答一样。有关复杂性的评论对我也不太清楚。 - Philipp Claßen

Answer 8

简短概述

任选一种，它们几乎相同。

详细解释

像往常一样，各有优缺点。

使用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演示 std::reverse_iterator演示

时间相同。Valgrind报告缓存未命中数量相同。

- ivaigult

Answer 9

bool comp(int i, int j) { return i > j; }
sort(numbers.begin(), numbers.end(), comp);

- user7069426

---

为了成为一个有效的回答，您应该考虑写一些关于您的方法与OP提到的方法相比的优缺点。 - Stefan Hegny

Answer 10

您可以使用第一个，或者尝试下面的代码，它同样有效。

sort(&a[0], &a[n], greater<int>());

- Krish Munot