1.algorithm 裡的sort()隻接收RandomAccessIterator
用于像vector,dequeue的排序
2.像set,map,這種關聯式容器,本身就由RBTree維護了有序,隻要周遊一遍就行了。
3.而list比較特殊一點,由于隻有BidirectionalIterator。而又不本身有序。
是以該容器自帶了一個用來排序的函數。
list.sort() //預設排序,如果是指針則按位址大小排序
list.sort(greater<int>()) //升序 比較符号為 >
list.sort(less<int>()) //降序 比較符号為 <
//其他如 >= <= 為greater_equal, less_equal...
list.sort()裡面也可以是自定義函數:
#include <iostream>
#include <list>
#include <string.h>
#include <iterator>
using namespace std;
char *ss[] = { "bb" , "aa" , "cc" , "ee" , "dd" } ;
bool mycmp( char *&s1 , char *&s2)
{
return strcmp(s1 , s2) == -1 ;
}
int main()
list<char*> l(ss , ss + sizeof(ss) / sizeof(char*)) ;
ostream_iterator<char*> oit(cout , " ") ; //構造輸出疊代器
copy( l.begin() , l.end() , oit) ;cout<<endl; //輸出原序列
l.sort() ; //預設的排序,其實是按指針大小排序
copy( l.begin() , l.end() , oit) ;cout<<endl; //輸出1
l.sort(mycmp); //傳入函數指針的排序
copy( l.begin() , l.end() , oit) ;cout<<endl; //輸出2
system("pause");
return 0 ;
輸出:
bb aa cc ee dd
aa bb cc dd ee
可見不帶參數的是按指針從小到大排序的。
而這段在VC6裡就會報錯,即使把mycmp加上ptr_fun的修飾也不行。
主要是list的sort參數實在太奇怪了。
STL裡面有很多函數提供兩個版本,其中一個以預設方式進行比較,
另一個版本可以允許傳入一個functor,以該functor進行比較。
而這個list.sort直接限定死了傳進去的是greater<T>
比如,我們直接設計一個functor
struct c{
operator()(char *&s1 , char *&s2){
return strcmp(s1,s2) == -1 ;
}
};
後面調用:l.sort(c());
編譯器會給出下面的資訊:
cannot convert parameter 1 from 'struct c' to 'struct std::greater<char *>'
No constructor could take the source type, or constructor overload resolution was ambiguous
其實就是類型不比對。。。-_-編譯器隻認greater這個functor。
就是這裡糾結了很久。。後來終于不小心搞定了,用特化!!
像下面這樣:(代碼直接從泛化的greater複制過來,做相應修改就可以了)
struct greater<char*> : binary_function<char*, char*, bool> {
bool operator()(const char*& _X, const char*& _Y) const
{return (strcmp(_X,_Y) == -1); }
};
在DEV裡面,全特化要求加入 template<>開頭,VC裡面可以不加。
那麼後面直接這樣調用就可以了:l.sort(greater<char*>()) ;
這時編譯器選擇的就不是前面泛化的greater了,就是我們量身定做的char* 的greater。
且慢,在VC6裡面還要報錯。
error C2934: 'greater<char *>' : template-class-id redefined as a nested 'struct' of '<Unknown>'
原來是namespace的問題。因為greater是定義在std裡面的。
下面這份代碼和前面的差不多。在VC6下運作正常:
相信通過前面的解釋能夠很容易明白。
#include <algorithm>
#include <vector>
namespace std
struct greater<char*> : binary_function<char*, char*, bool>
{
ostream_iterator<char*> oit(cout , " ") ;
copy( l.begin() , l.end() , oit) ;cout<<endl;
l.sort() ;
l.sort(greater<char*>()) ;