泛型算法中的定制操作
許多算法都會比較輸入序列中的元素以達到排序的效果,通過定制比較操作,可以控制算法按照程式設計者的意圖工作。
- 普通排序算法:
template<class RandomIterator>
void sort(RandomIterator first,RandomIterator last){
if(first >= last || first + 1 == last)
return;
if(last - first <= 20)
return bubble_sort(first,last,pred);
auto mid = mid3(first,last-1,pred); //mid3 is unknow,is a function for calculating the mid?
while(p1 < p2){
while(pred(*p1,mid)&&(p1<p2)) ++p1;
while(!pred(*p2,mid)&&(p1<p2)) --p2;
if(p1 < p2){
swap(*p1,*p2);
}
}
swap(*p1,*(last-2)); //what is sort ?
sort(first,p1,pred);
sort(p1+1,last,pred);
}
- 排序算法的定制操作
排序算法隻能由小到大。
二排序算法的定制操作,多了一個類型BinaryPredicate,可以用來定制規則。
template<class RandomIterator,class BinaryPredicate>
void sort(RandomIterator first,RandomIterator last,BinaryPredicate){
if(first >= last || first + 1 == last)
return;
if(last - first <= 20)
return bubble_sort(first,last,pred);
auto mid = mid3(first,last,pred);
auto p1 = first, p2 = last - 2;
while(p1 < p2){
while(pred(*p1,mid) && (p1 < p2)) ++p1;
while(!pred(*p1,mid) && (p1 < p2)) --p2;
if(p1 < p2){
swap(*p1,*p2);
}
}
swap(*p1,*(last-2));
sort(first,p1,pred);
sort(p1+1,last,pred);
}
謂詞:相當于一個動作,比如一個需求,希望從大到小,則可以先定義一個謂詞(函數)
bool cmp(const int& v1,const int &v2){
return v1 > v2;
}
sort(v.begin(),v.end(),cmp);
将該函數傳遞給sort算法時,就可以從小到大排序了。
lambda表達式:
在前面的例子中,定義了一個函數傳遞給sort算法,這個函數可以重複使用還好,如果使用一次的話就很麻煩。
這種情況下lambda就可以用上了,它相當于謂語,沒有定義函數。
sort(v.begin(),v.end(),[]cmp(const int& int v1,const int& v2){