C++ 按降序对向量进行排序
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/9025084/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Sorting a vector in descending order
提问by fredoverflow
Should I use
我应该使用
std::sort(numbers.begin(), numbers.end(), std::greater<int>());
or
或者
std::sort(numbers.rbegin(), numbers.rend()); // note: reverse iterators
to sort a vector in descending order? Are there any benefits or drawbacks with one approach or the other?
按降序对向量进行排序？一种方法或另一种方法有什么好处或缺点吗？
回答by user541686
Actually, the first one is a bad idea. Use either the second one, or this:
实际上，第一个是个坏主意。使用第二个，或者这个：
struct greater
{
template<class T>
bool operator()(T const &a, T const &b) const { return a > b; }
};
std::sort(numbers.begin(), numbers.end(), greater());
That way your code won't silently break when someone decides numbersshould hold longor long longinstead of int.
这样，当有人决定numbers应该持有long或long long代替int.
回答by Pubby
Use the first:
使用第一个：
std::sort(numbers.begin(), numbers.end(), std::greater<int>());
It's explicit of what's going on - less chance of misreading rbeginas begin, even with a comment. It's clear and readable which is exactly what you want.
它清楚地说明了正在发生的事情 -即使有评论，也减少了误读rbegin为 的机会begin。它清晰易读，这正是您想要的。
Also, the second one may be less efficient than the first given the nature of reverse iterators, although you would have to profile it to be sure.
此外，考虑到反向迭代器的性质，第二个可能比第一个效率低，尽管您必须对其进行分析才能确定。
回答by mrexciting
With c++14 you can do this:
使用 c++14 你可以这样做：
std::sort(numbers.begin(), numbers.end(), std::greater<>());
回答by shoumikhin
What about this?
那这个呢？
std::sort(numbers.begin(), numbers.end());
std::reverse(numbers.begin(), numbers.end());
回答by Julian Declercq
Instead of a functor as Mehrdad proposed, you could use a Lambda function.
您可以使用 Lambda 函数，而不是 Mehrdad 提出的函子。
sort(numbers.begin(), numbers.end(), [](const int a, const int b) {return a > b; });
回答by zw324
According to my machine, sorting a long longvector of [1..3000000] using the first method takes around 4 seconds, while using the second takes about twice the time. That says something, obviously, but I don't understand why either. Just think this would be helpful.
根据我的机器，long long使用第一种方法对 [1..3000000] 向量进行排序大约需要 4 秒，而使用第二种方法大约需要两倍的时间。显然，这说明了什么，但我也不明白为什么。只是认为这会有所帮助。
Same thing reported here.
同样的事情在这里报道。
As said by Xeo, with -O3they use about the same time to finish.
正如 Xeo 所说，-O3他们使用大约相同的时间来完成。
回答by rashedcs
First approach refers:
第一种方法是指：
std::sort(numbers.begin(), numbers.end(), std::greater<>());
You may use the first approach because of getting more efficiency than second.
The first approach's time complexity less than second one.
您可以使用第一种方法，因为比第二种方法效率更高。
第一种方法的时间复杂度小于第二种方法。
回答by rashedcs
bool comp(int i, int j) { return i > j; }
sort(numbers.begin(), numbers.end(), comp);
回答by ivaigult
TL;DR
TL; 博士
Use any. They are almost the same.
使用任何。它们几乎相同。
Boring answer
无聊的回答
As usual, there are pros and cons.
像往常一样，有利有弊。
Use std::reverse_iterator:
使用std::reverse_iterator：
- When you are sorting custom types and you don't want to implement
operator>() - When you are too lazy to type
std::greater<int>()
- 当您对自定义类型进行排序并且不想实现时
operator>() - 当你懒得打字时
std::greater<int>()
Use std::greaterwhen:
std::greater在以下情况下使用：
- When you want to have more explicit code
- When you want to avoid using obscure reverse iterators
- 当您想要更明确的代码时
- 当你想避免使用晦涩的反向迭代器时
As for performance, both methods are equally efficient. I tried the following benchmark:
至于性能，这两种方法同样有效。我尝试了以下基准测试：
#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;
}
With this command line:
使用此命令行：
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::greaterdemostd::reverse_iteratordemo
std::greaterdemostd::reverse_iteratordemo
Timings are same. Valgrind reports the same number of cache misses.
时间是一样的。Valgrind 报告相同数量的缓存未命中。
回答by Martin Broadhurst
I don't think you should use either of the methods in the question as they're both confusing, and the second one is fragile as Mehrdad suggests.
我认为您不应该使用问题中的任何一种方法，因为它们都令人困惑，而第二种方法正如 Mehrdad 所建议的那样脆弱。
I would advocate the following, as it looks like a standard library function and makes its intention clear:
我会提倡以下内容，因为它看起来像一个标准的库函数并且它的意图很明确：
#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>());
}
