算法方面的改進 · C++11 FAQ 中文版

# 算法方面的改進標準庫的算法部分進行了如下改進：新增了一些算法函數；通過新語言特性改善了一些算法實現并且更易于使用。下面分別來看一些例子： * 新算法: ``` bool all_of(Iter first, Iter last, Pred pred); bool any_of(Iter first, Iter last, Pred pred); bool none_of(Iter first, Iter last, Pred pred); Iter find_if_not(Iter first, Iter last, Pred pred); OutIter copy_if(InIter first, InIter last, OutIter result, Pred pred); OutIter copy_n(InIter first, InIter::difference_type n, OutIter result); OutIter move(InIter first, InIter last, OutIter result); OutIter move_backward(InIter first, InIter last, OutIter result); pair<OutIter1, OutIter2> partition_copy(InIter first, InIter last, OutIter1 out_true, OutIter2 out_false, Pred pred); Iter partition_point(Iter first, Iter last, Pred pred); RAIter partial_sort_copy(InIter first, InIter last, RAIter result_first, RAIter result_last); RAIter partial_sort_copy(InIter first, InIter last, RAIter result_first, RAIter result_last, Compare comp); bool is_sorted(Iter first, Iter last); bool is_sorted(Iter first, Iter last, Compare comp); Iter is_sorted_until(Iter first, Iter last); Iter is_sorted_until(Iter first, Iter last, Compare comp); bool is_heap(Iter first, Iter last); bool is_heap(Iter first, Iter last, Compare comp); Iter is_heap_until(Iter first, Iter last); Iter is_heap_until(Iter first, Iter last, Compare comp); T min(initializer_list<T> t); T min(initializer_list<T> t, Compare comp); T max(initializer_list<T> t); T max(initializer_list<T> t, Compare comp); pair<const T&, const T&> minmax(const T& a, const T& b); pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp); pair<const T&, const T&> minmax(initializer_list<T> t); pair<const T&, const T&> minmax(initializer_list<T> t, Compare comp); pair<Iter, Iter> minmax_element(Iter first, Iter last); pair<Iter, Iter> minmax_element(Iter first, Iter last, Compare comp); // 填充[first,last]范圍內的每一個元素 // 第一個元素為value，第二個為++value，以此類ui // 等同于 // *(d_first) = value; // *(d_first+1) = ++value; // *(d_first+2) = ++value; // *(d_first+3) = ++value; ... // 注意函數名，是iota而不是itoa哦 void iota(Iter first, Iter last, T value); ``` * 更有效的move：more操作比copy操作更有效率（參看move semantics（譯注：實際上是一個右值(rval)問題，核心是減少創建不必要的對象））。基于move的std::sort()和std::set::insert()要比基于copy的對應版本快15倍以上。不過它對標準庫中已有操作的性能改善不多，因為它們的實現中已經使用了類似的方法進行優化了（例如string，vector使用了調優過的swap操作來代替copy了）。當然如果你自己的代碼中包含了move操作的話，就能自動從新標準庫中獲益了。試著用move操作來替代下邊這個sort函數中的智能指針（unique_ptr）吧（譯注：可以通過一個move版swap來搞定，參看之前move semantics文章）： ``` template<class P> struct Cmp<P> { //比較 *P 的值 bool operator() (P a, P b) const { return *a<*b; } } vector<std::unique_ptr<Big>> vb; // 用指向大對象的unique_ptr填充vb sort(vb.begin(),vb.end(),Cmp<Big>());// 不要像這樣使用時用auto_ptr ``` * 對lambda表達式的使用：對于為標準庫算法寫函數/函數對象（function object，推薦）這個事兒大家已經抱怨很久了（例如Cmp）。特別是在C++98標準中，這會令人更加痛苦，因為無法定義一個局部的函數對象。不過現在好多了，lambda表達式允許用”inline”的方式來寫函數了： ``` sort(vb.begin(),vb.end(), [](unique_ptr a, unique_ptr b) { return *a< *b; }); ``` 我希望大家盡量多用用lambda表達式（它真的是一種很好很強大的機制）（譯注：原文是：”I expect lambdas to be a bit overused initially (like all powerful mechanisms)”，非字面翻譯） * 對初始化列表（initializer lists）的使用：初始化表有時可以像參數那樣方便的使用。看下邊這個例子（x,y,z是string變量，Nocase是一個大小寫不敏感的比較函數）： ``` auto x = max({x,y,z},Nocase()); ``` 參考： * 25 Algorithms library [algorithms] * 26.7 Generalized numeric operations [numeric.ops] * Howard E. Hinnant, Peter Dimov, and Dave Abrahams: [A Proposal to Add Move Semantics Support to the C++ Language](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2002/n1377.htm). N1377=02-0035.