qsort vs std::sort
朋友問我疆液，qsort和std::sort有什么區(qū)別，我沒有專門查過，但還是嘗試答了幾條：
- qsort是C標(biāo)準(zhǔn)庫函數(shù)相艇，位于<stdlib.h>；sort是STL中的函數(shù)模板纯陨，位于<algorithm>
- qsort的參數(shù)用指針表示范圍坛芽；sort的參數(shù)用迭代器表示范圍
- qsort肯定是快排，sort應(yīng)該是根據(jù)迭代器類型來判斷是否采用快排翼抠，如果是前向迭代器的話應(yīng)該就不是快排
第三條是我猜的咙轩，后來查過資料之后，發(fā)現(xiàn)我第三條確實(shí)答錯(cuò)了阴颖，事實(shí)上：
- sort的迭代器參數(shù)只能是Mutable RandomAccessIterator活喊。
- sort的排序算法不是快排，而是IntroSort和InsertionSort的結(jié)合量愧。（內(nèi)省排序 和 插入排序）
下面說一下std::sort的源碼钾菊，以及記錄一下閱讀中遇到的不懂的東西（不懂的實(shí)在有點(diǎn)多，可能有點(diǎn)啰嗦）侠畔。
std::sort
std::sort有兩個(gè)重載：
template<typename _RAIter>
void
sort(_RAIter, _RAIter);
template<typename _RAIter, typename _Compare>
void
sort(_RAIter, _RAIter, _Compare);
分別點(diǎn)進(jìn)去：
template<typename _RandomAccessIterator>
inline void
sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_function_requires(_LessThanComparableConcept<
typename iterator_traits<_RandomAccessIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
}
template<typename _RandomAccessIterator, typename _Compare>
inline void
sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
typename iterator_traits<_RandomAccessIterator>::value_type,
typename iterator_traits<_RandomAccessIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
}
殊途同歸结缚，調(diào)用了同一個(gè)函數(shù)std::__sort，只是第三個(gè)參數(shù)不同软棺。
接下來先不看std::__sort的源碼红竭，先搞懂調(diào)用該函數(shù)前的那一堆代碼是什么。
__glibcxx_function_requires
上面代碼里面，__glibcxx_function_requires是宏定義茵宪，涉及到c++ concept checking的概念最冰。
顯然concept checking不是C++11標(biāo)準(zhǔn)的一部分，它是Boost的一部分稀火，是Boost Concept Checking Library的內(nèi)容暖哨，然后GNU將其整合到了 GNU C++ library中。gcc里面凰狞，concept checking默認(rèn)是關(guān)閉的篇裁，可以通過 #define _GLIBCXX_CONCEPT_CHECKS 來打開它，但是沒有任何必要赡若，因?yàn)镃++11的特性會(huì)完成concept checking的功能达布。更具體的解釋見文末的引用[6][7]。
簡而言之逾冬，這個(gè)concept check的作用是“限制某類型的特定的操作是合法的”黍聂。比如說，__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIterator>)就是要限制你傳入的迭代器類型得是Mutable RandomAccessIterator身腻，得支持++ -- [] * += -= 等運(yùn)算符操作产还。如果不滿足的話，編譯就不通過嘀趟。
上面的sort(__first, __last)里的兩條__glibcxx_function_requires就限制了：
- 迭代器類型得是Mutable RandomAccessIterator
- 迭代器所指類型得是支持<運(yùn)算符的
之前我只清楚iterator的五種類型脐区，即std::input_iterator_tag等代表的五種，然后我就有了以下疑問：
- 為什么用concept check來檢查迭代器類型去件？像std::advance那樣用__iterator_traits檢查迭代器類型不行嗎坡椒？
- 迭代器類型中有mutable iterator嗎？五種迭代器類型好像沒有提到坝攘铩？
針對(duì)問題查了cppreference.com [4]：
There are five (until C++17)six (since C++17) kinds of iterators: InputIterator, OutputIterator, ForwardIterator, BidirectionalIterator, RandomAccessIterator, and ContiguousIterator (since C++17).
All of the iterator categories (except OutputIterator and ContiguousIterator) can be organized into a hierarchy, where more powerful iterator categories (e.g. RandomAccessIterator) support the operations of less powerful categories (e.g. InputIterator). If an iterator falls into one of these categories and also satisfies the requirements of OutputIterator, then it is called a mutable iterator and supports both input and output. Non-mutable iterators are called constant iterators.
mutable iterator指的支持write和increment的迭代器汗唱。因此宫莱，iterator_catogory是random_access_iterator_tag的迭代器并不一定可寫，random_access_iterator_tag并不能保證迭代器是mutable還是constant哩罪，只有mutable iterator才是可寫的授霸。所以上面的兩個(gè)問題有答案了。
那么concept check是怎么實(shí)現(xiàn)的呢际插？接下來接著看源碼碘耳。
點(diǎn)進(jìn)去__glibcxx_function_requires：
#ifndef _GLIBCXX_CONCEPT_CHECKS
#define __glibcxx_function_requires(...)
#else // the checks are on
#define __glibcxx_function_requires(...) \
__gnu_cxx::__function_requires< __gnu_cxx::__VA_ARGS__ >();
#endif // enable/disable
因此，如果想要使用concept check框弛，就需要自己在include相關(guān)頭文件之前定義宏_GLIBCXX_CONCEPT_CHECKS辛辨，或者修改c++config.h中的宏定義。
接下來看 __gnu_cxx::__function_requires。
template <class _Concept>
inline void __function_requires()
{
void (_Concept::*__x)() _IsUnused = &_Concept::__constraints;
}
_IsUnused是宏定義斗搞，展開后是__attribute__((unused))指攒，表示該函數(shù)或變量可能不使用，這個(gè)屬性可以避免編譯器產(chǎn)生警告信息僻焚。如果看不懂__function_requires里面的語法允悦，請(qǐng)參考引用[2][3]。
所以虑啤，最初std::sort里的第一個(gè)__glibcxx_function_requires展開之后就是：
__gnu_cxx::__function_requires< __gnu_cxx::_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>>();
然而這做了什么隙弛？
首先，這句話導(dǎo)致實(shí)例化并調(diào)用了__function_requires模板函數(shù)狞山。該函數(shù)里全闷，定義了一個(gè)函數(shù)指針，指向模板參數(shù)表示的類的__constraints成員函數(shù)铣墨，進(jìn)而導(dǎo)致實(shí)例化了__gnu_cxx::_Mutable_RandomAccessIteratorConcept<_RandomAccessIterator>::__constraints室埋。在__constraints函數(shù)中會(huì)對(duì)迭代器進(jìn)行某些運(yùn)算符操作，編譯時(shí)編譯器會(huì)檢查這些操作的有效性伊约，因此姚淆，就達(dá)到了檢查迭代器性質(zhì)的作用。
貼出來_Mutable_RandomAccessIteratorConcept的源碼屡律，加以印證：
template <class _Tp>
struct _Mutable_RandomAccessIteratorConcept
{
void __constraints() {
__function_requires< _RandomAccessIteratorConcept<_Tp> >();
__function_requires< _Mutable_BidirectionalIteratorConcept<_Tp> >();
__i[__n] = *__i; // require element access and assignment
}
_Tp __i;
typename std::iterator_traits<_Tp>::difference_type __n;
};
現(xiàn)在std::__sort之前的那一大坨我們已經(jīng)弄清楚了腌逢，接下來進(jìn)入std::__sort。
std::__sort
接下來std::__sort的實(shí)現(xiàn)和侯捷的《STL源碼剖析》中講的std::sort的實(shí)現(xiàn)基本一樣了超埋。我看的這個(gè)STL版本是gcc 5.3.1使用的版本搏讶，其std::sort的實(shí)現(xiàn)只是在侯捷書中講的版本上套了個(gè)殼子，加了concept checking（也就是前面大費(fèi)周章講的東西）霍殴。如果有這本書的話可以去看這本書媒惕，書上講的詳細(xì)多了，這里只簡單介紹一下實(shí)現(xiàn)来庭。
std::__sort的排序算法是IntroSort和InsertionSort的結(jié)合妒蔚，先說一下什么是IntroSort。
這個(gè)排序算法類似于快排月弛，在快排的基礎(chǔ)上肴盏，當(dāng)遞歸深度超過一定深度（深度為排序元素?cái)?shù)量的對(duì)數(shù)值）時(shí)轉(zhuǎn)為堆排序。偽代碼如下：
procedure sort(A : array):
let maxdepth = ?log(length(A))? × 2
introsort(A, maxdepth)
procedure introsort(A, maxdepth):
n ← length(A)
p ← partition(A) // assume this function does pivot selection, p is the final position of the pivot
if n ≤ 1:
return // base case
else if maxdepth = 0:
heapsort(A)
else:
introsort(A[0:p], maxdepth - 1)
introsort(A[p+1:n], maxdepth - 1)
接下來貼出來std::__sort源碼帽衙，我把代碼加上了注釋菜皂，不再單獨(dú)解釋代碼了。
template<typename _RandomAccessIterator, typename _Compare>
inline void
__sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
if (__first != __last)
{
// __introsort_loop先進(jìn)行一遍IntroSort厉萝，但是不是嚴(yán)格意義上的IntroSort恍飘。
//因?yàn)閳?zhí)行完之后區(qū)間并不是完全有序的榨崩，而是基本有序的。
//__introsort_loop和IntroSort不同的地方是常侣，__introsort_loop會(huì)在一開始會(huì)判斷區(qū)間的大小蜡饵，當(dāng)區(qū)間小于16的時(shí)候，就直接返回胳施。
std::__introsort_loop(__first, __last,
std::__lg(__last - __first) * 2,
__comp);
// 在區(qū)間基本有序的基礎(chǔ)上再做一遍插入排序溯祸，使區(qū)間完全有序
std::__final_insertion_sort(__first, __last, __comp);
}
}
__introsort_loop和__final_insertion_sort代碼：
enum { _S_threshold = 16 };
template<typename _RandomAccessIterator, typename _Size, typename _Compare>
void
__introsort_loop(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Size __depth_limit, _Compare __comp)
{
// 若區(qū)間大小<=16就不再排序。
while (__last - __first > int(_S_threshold))
{
// 若遞歸次數(shù)達(dá)到限制舞肆，就改用堆排序
if (__depth_limit == 0)
{
std::__partial_sort(__first, __last, __last, __comp);
return;
}
--__depth_limit;
_RandomAccessIterator __cut =
std::__unguarded_partition_pivot(__first, __last, __comp); // 分割
std::__introsort_loop(__cut, __last, __depth_limit, __comp); // 右半?yún)^(qū)間遞歸
__last = __cut;
// 回到while循環(huán)焦辅，對(duì)左半?yún)^(qū)間進(jìn)行排序，這么做能顯著減少__introsort_loop的調(diào)用的次數(shù)
}
}
template<typename _RandomAccessIterator, typename _Compare>
void
__final_insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
if (__last - __first > int(_S_threshold)) // 區(qū)間長度大于16
{
// 插入排序
std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
// 也是插入排序椿胯，只是在插入排序的內(nèi)循環(huán)時(shí)筷登，不再判斷邊界條件，因?yàn)橐呀?jīng)保證了區(qū)間前面肯定有比待插入元素更小的元素
std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
__comp);
}
else // 區(qū)間長度小于等于16的話
std::__insertion_sort(__first, __last, __comp); // 插入排序
}
__unguarded_insertion_sort和__insertion_sort和__unguarded_partition_pivot不再贅述哩盲。
總結(jié)
感覺講了一堆廢話前方，C++11中concept checking都不用了，感覺白看了......
Reference
- how does __glibcxx_function_requires and __glibcxx_requires_valid_range macros work?
- Function pointer to member function
- function pointers in c++ : error: must use '.' or '->' to call pointer-to-member function in function
- https://en.cppreference.com/w/cpp/iterator
- https://en.wikipedia.org/wiki/Introsort
- Compile Time Checks
- Using Concept Checks
