C++中的sort函數使用自定義比較函數的具體運行過程是怎麼樣的呢?

比如我現在定義一個比較函數

int cmp（int a，int b）return a&>b；

然後數組 int num［5］=｛1，4，3，5，2｝

sort（num，num+5，cmp）

這樣就實現了降序排列，但是具體的實現過程是怎麼樣的呢？
假設sort函數使用冒泡排序的方法，它是怎麼利用cmp的呢？

C++ 的 std::sort 是用模板實現的，其參數為隨機迭代器（RandomAccessIterator）和 Compare 函數對象。

冒泡排序只需要雙向迭代器（BidirectionalIterator），可實現為：

#include &

int main() {
int num[] = { 1, 4, 3, 5, 2 };
bubble_sort(num, num + 5, cmp);
for (size_t i = 0; i &< 5; i++) std::cout &<&< num[i] &<&< " "; }

更新：只用 ForwardIterator 也可：

template &
void bubble_sort(ForwardIt first, ForwardIt last, Compare comp) {
while (first != last) {
ForwardIt current = first;
for (ForwardIt next = first; ++next != last; ++current)
if (!comp(*current, *next))
std::swap(*current, *next);
last = current;
}
}


#include &
#include & /* (c99) add bool type */

int main() {
int num[5] = {1, 4, 3, 5, 2};
sort(num, num+5, cmp);
for (int i = 0; i &< 5; ++i) printf("%d ", num[i]); return 0; } void swap(int *a, int *b) { int tmp; tmp = *a; *a = *b; *b = tmp; } /* * bubble sort * pass pointer to function */ void sort(int* a, int* b, bool (*compare)(int, int)) { for (int *p = a; p &< b; ++p) for (int *q = p+1; q &< b; ++q) if (!compare(*p, *q)) swap(p, q); } bool cmp(int a, int b) {return a &> b;}


首先，sort不會用到冒泡排序，時間複雜度過高導致性能太差。SGI STL版本的sort在數據量很大時採用Quick Sort進行分段遞歸排序。如果分段之後的數據量小於某個門檻值，會改用Insertion Sort這種在數據量很小時性能很好的排序演算法。

其次，sort接受一個用戶指定的函數，要求：對於排序後的每兩個相鄰元素都要滿足使cmp結果為TRUE。也就是說，在進行比較運算的時候拿用戶定義的比較函數來替代原有的比較運算符。

所以具體實現就是：在快排分割成的小子序列中進行插入排序。

建議去閱讀《STL源碼剖析》。

以VS2015自帶的那份STL為例

template& inline
void sort(_RanIt _First, _RanIt _Last, _Pr _Pred)
{ // order [_First, _Last), using _Pred
_DEBUG_RANGE(_First, _Last);
_Sort_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred);
}

// TEMPLATE FUNCTION sort
template& inline
void sort(_RanIt _First, _RanIt _Last)
{ // order [_First, _Last), using operator&< _STD sort(_First, _Last, less&<&>());
}


Pred可以是一個函數對象，普通函數，函數指針，lambda表達式。現在假設你什麼都不傳，那默認就調用最底下的那個，相當於是傳一個less&<&>()這個函數對象進去，來看下less這個模板的定義

// TEMPLATE STRUCT less
template&
struct less
{ // functor for operator&< typedef _Ty first_argument_type; typedef _Ty second_argument_type; typedef bool result_type; constexpr bool operator()(const _Ty _Left, const _Ty _Right) const { // apply operator&< to operands return (_Left &< _Right); } }; // TEMPLATE STRUCT SPECIALIZATION less template&<&>
struct less&
{ // transparent functor for operator&< typedef int is_transparent; template&
constexpr auto operator()(_Ty1 _Left, _Ty2 _Right) const
-&> decltype(static_cast&<_Ty1&>(_Left)
&< static_cast&<_Ty2&>(_Right))
{ // transparently apply operator&< to operands return (static_cast&<_Ty1&>(_Left)
&< static_cast&<_Ty2&>(_Right));
}
};


從上面我們可以看到less就是個簡單的調用operator&<的操作而已

現在我們再來看下sort的實現

template& inline
void _Sort_unchecked1(_RanIt _First, _RanIt _Last, _Diff _Ideal, _Pr _Pred)
{ // order [_First, _Last), using _Pred
_Diff _Count;
while (_ISORT_MAX &< (_Count = _Last - _First) 0 &< _Ideal) { // divide and conquer by quicksort pair&<_RanIt, _RanIt&> _Mid =
_Partition_by_median_guess_unchecked(_First, _Last, _Pred);
_Ideal /= 2, _Ideal += _Ideal / 2; // allow 1.5 log2(N) divisions

if (_Mid.first - _First &< _Last - _Mid.second) { // loop on second half _Sort_unchecked1(_First, _Mid.first, _Ideal, _Pred); _First = _Mid.second; } else { // loop on first half _Sort_unchecked1(_Mid.second, _Last, _Ideal, _Pred); _Last = _Mid.first; } } if (_ISORT_MAX &< _Count) { // heap sort if too many divisions _Make_heap_unchecked(_First, _Last, _Pred); _Sort_heap_unchecked(_First, _Last, _Pred); } else if (2 &<= _Count) _Insertion_sort_unchecked(_First, _Last, _Pred); // small }

那麼在這份實現裡面sort沒有冒泡排序，而是快排+堆排+插入排序的混合，但是還是沒看到pred是怎麼調用的，點進去_Partition_by_median_guess_unchecked看下

可以看到_Partition_by_median_guess_unchecked裡面有一段是這樣的

while (_First &< _Pfirst !_DEBUG_LT_PRED(_Pred, *(_Pfirst - 1), *_Pfirst) !_Pred(*_Pfirst, *(_Pfirst - 1))) --_Pfirst;

可以看到如果我們傳入的是less&<&>()，相當於調用less&的函數重載運算符，這裡就是簡單的判斷*_Pfirst &< *(_Pfirst - 1)的操作而已，結合代碼其實快排裡面從右往左找第一個違反規則的元素的操作

題主是不清楚cmp怎樣起作用的嗎？

你可以先把sort()內的排序演算法認為成你會的任意一個演算法，比如你會的冒泡排序演算法。你在實現一個具體的排序演算法的時候，肯定用到了比較兩個元素大小的操作，比如大於小於等。

cmp()函數的作用就是提供這個比較操作。

為什麼要提供cmp()這類函數(當然不是必須)呢？

sort()作為一個模板函數，可以作用在任意類型上。對於自定義類型來說，sort()不知道如何判斷兩個量的大小，所以需要傳入用來提供比較操作的(仿)函數。