Сам по себе это не столько ответ, сколько ответ на ответ АраК на мой комментарий о том, что сортировка с помощью функции вместо функтора может быть медленнее. Вот некоторый (по общему мнению, уродливый - слишком большой CnP) тестовый код, который сравнивает различные сортировки: qsort, std :: sort вектора с массивом и 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;
}
Компилируя это с VC ++ 9 / VS 2008, используя cl /O2b2 /GL sortbench3.cpp, я получаю:
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 вы будете обычно передавать по константной ссылке (на всякий случай, если это что-то более дорогое). скопировать).