这其实不是一个真正的答案本身，作为对AraK回复我的评论的回复，即使用函数而不是函数进行排序可能会更慢。这里有一些（确实是丑陋的 - 太多的CnP）测试代码，比较各种排序：qsort，std ::向量与数组的排序，std :: sort使用模板类，模板函数或纯函数进行比较：
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
int compare(void const *a, void const *b) {
if (*(int *)a > *(int *)b)
return -1;
if (*(int *)a == *(int *)b)
return 0;
return 1;
}
const int size = 200000;
typedef unsigned long ul;
void report(char const *title, clock_t ticks) {
printf("%s took %f seconds\n", title, ticks/(double)CLOCKS_PER_SEC);
}
void wait() {
while (clock() == clock())
;
}
template <class T>
struct cmp1 {
bool operator()(T const &a, T const &b) {
return a < b;
}
};
template <class T>
bool cmp2(T const &a, T const &b) {
return a<b;
}
bool cmp3(int a, int b) {
return a<b;
}
int main(void) {
static int array1[size];
static int array2[size];
srand(time(NULL));
for (int i=0; i<size; i++)
array1[i] = rand();
const int iterations = 100;
clock_t total = 0;
for (int i=0; i<iterations; i++) {
memcpy(array2, array1, sizeof(array1));
wait();
clock_t start = clock();
qsort(array2, size, sizeof(array2[0]), compare);
total += clock()-start;
}
report("qsort", total);
total = 0;
for (int i=0; i<iterations; i++) {
memcpy(array2, array1, sizeof(array1));
wait();
clock_t start = clock();
std::sort(array2, array2+size);
total += clock()- start;
}
report("std::sort (array)", total);
total = 0;
for (int i=0; i<iterations; i++) {
memcpy(array2, array1, sizeof(array1));
wait();
clock_t start = clock();
std::sort(array2, array2+size, cmp1<int>());
total += clock()- start;
}
report("std::sort (template class comparator)", total);
total = 0;
for (int i=0; i<iterations; i++) {
memcpy(array2, array1, sizeof(array1));
wait();
clock_t start = clock();
std::sort(array2, array2+size, cmp2<int>);
total += clock()- start;
}
report("std::sort (template func comparator)", total);
total = 0;
for (int i=0; i<iterations; i++) {
memcpy(array2, array1, sizeof(array1));
wait();
clock_t start = clock();
std::sort(array2, array2+size, cmp3);
total += clock()- start;
}
report("std::sort (func comparator)", total);
total = 0;
for (int i=0; i<iterations; i++) {
std::vector<int> array3(array1, array1+size);
wait();
clock_t start = clock();
std::sort(array3.begin(), array3.end());
total += clock()-start;
}
report("std::sort (vector)", total);
return 0;
}
使用cl /O2b2 /GL sortbench3.cpp用VC++ 9/VS 2008的编译，我得到：
qsort took 3.393000 seconds
std::sort (array) took 1.724000 seconds
std::sort (template class comparator) took 1.725000 seconds
std::sort (template func comparator) took 2.725000 seconds
std::sort (func comparator) took 2.505000 seconds
std::sort (vector) took 1.721000 seconds
我相信这些落入相当干净地分成三组：使用排序与默认的比较，并使用模板类产生最快的代码。使用函数或模板函数显然比较慢。使用qsort（对某些人来说令人惊讶）是最慢的，大约是2：1的边距。
cmp2和cmp3之间的区别似乎完全在于通过引用与值传递 - 如果您更改cmp2以按值取其参数，则其速度与cmp3完全匹配（至少在我的测试中）。不同之处在于，如果您知道类型将为int，那么您几乎肯定会传递值，而对于通用T，您通常会传递const引用（以防万一它的复制成本更高）。
的C++ 0x具有lambda函数和TR1添加''头使这个少了很多不必要的冗长。 –
Omnifarious
2010-02-04 20:15:09
+1非常好的问及回答。这应该是未来的dups所关联的职位。 – 2010-02-04 20:33:51
@Omnifarious：你确定TR1/functional中有一些东西可以帮助你在这个例子中说明你已经可以在C++ 03中做些什么吗？ – Manuel 2010-02-04 20:44:57