算法方面的改进
标准库的算法部分进行了如下改进:新增了一些算法函数;通过新语言特性改善了一些算法实现并且更易于使用。下面分别来看一些例子:
新算法:
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.
N1377=02-0035.