這其實不是一個真正的答案本身，作爲對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