算法方面的改进

标准库的算法部分进行了如下改进:新增了一些算法函数;通过新语言特性改善了一些算法实现并且更易于使用。下面分别来看一些例子:

  • 新算法:

    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());
    

参考: