part5 算法

本章2个目标

1 介绍几个鲜为人知但很实用的算法

(1) 忽略大小写的字符串比较

(2) 有效查找容器中最合适的n个对象

(3) 容器中一个区间内元素的统计处理

(4) 实现一功能类似copy_if的算法

    最初的HP STL中实现了copy_if, 但在标准化过程中被删除了

2 提示3类错误, 及其避免方法

(1) 必须非常清楚 remove/remove_if/unique做了什么(及没做什么), 尤其是删除区间包含了指针时

(2) 要求排序的区间的算法: 有哪些? 为什么要求

(3) STL算法将结果写到并不存在的地方 -> 错误

item30: 确保目标区间足够大, 且正确使用了插入语义

总结: 希望算法(transform/copy等)把对源区间(第1/2参数)操作(第4参数)的结果插入到目标容器, 则必须用插入型迭代器(第3参数, 3种插入型迭代器生成器返回的迭代器 + 输出流迭代器), 还可以用 reserve避免不必要的空间重新分配

1 新元素插入到容器: 必须用 插入型迭代器

; 否则, 只使用 reserve 扩容到足够大容量, 也无法实现正确插入到容器

原因: reserve只增加了容器的容量, 容器不知道 算法(如transform)在执行过程中在它的unused空间中插入了新对象 => 容器size不变
=> 插入失败时导致不确定的行为; 插入成功时, 破坏容器的数据一致性

2 新元素覆盖容器已有元素: 不需要插入型迭代器

3 transform: 逐元素 赋值(插入/覆盖)算法

(1) 配合插入型迭代器, 执行插入语义

(2) 不配合插入型迭代器: 执行赋值/覆盖语义

(3) 内部实现: 调赋值运算符(assignment), 循环每次迭代操作 *result = op(*first1) 完成后, srcfirstIter 和 dstInsertIter 均自动自增(++result; ++first1;)(=>移到指向next元素)

(4) 第3实参是 插入型迭代器时, 是 伪 输出区间迭代器

真正的输出区间迭代器见第4 小节

(5) transform 执行逐元素赋值(插入/覆盖) 时, 没有相应的更高效的 区间成员函数(item5)可替代 transform

4 插入型迭代器及其生成器

(1) 3种插入型迭代器 生成器: 是函数模板, 返回插入型迭代器

[1] back_inserter + 提供 push_back 的容器

bits/stl_iterator.h 
    template <class Container>  
        inline back_insert_iterator<Container> 
    back_inserter (Container& c);
    { 
        return back_insert_iterator<_Container>(c); 
    }
    
    https://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a19527_source.html

    std::copy (bar.begin(), bar.end(), back_inserter(foo) ); 
    
    vector<int> dstVec;
    transform(dstVec.begin(), dstVec.end(),
              back_inserter(dstVec), // 伪输出区间迭代器
              Operator() );

[2] front_inserter + 提供 push_front 的容器(排除 vector)

    // 输出结果在dst区间与src区间顺序相同
    transform(dstVec.rbegin(), dstVec.rend(),
              front_inserter(dstVec), 
              Operator() );

[3] inserter + 提供 insert 容器

    transform(dstVec.begin(), dstVec.end(),
              inserter(dstVec, dstVec.begin() + dstVec.size()/2 ), 
              Operator() );

[4] ostream_iterator

第1模板形参是 所要输出的对象类型

    // 第1模板形参是 所要输出的对象类型
    template <class T, ...>              
    class ostream_iterator;

    // Ctor: 第2参数为分隔符
    ostream_iterator (ostream_type& s 
                      [,const char_type* delimiter]); 

    transform(stringPtrSet.begin(), stringPtrSet.end(),
              ostream_iterator<string>(std::cout, "\n"), // 伪输出区间迭代器
              Dereference() );

(2) 3种插入型迭代器生成器 & 插入型输出流迭代器 的 Ctor 第1(, 2)实参为

[1] 容器的引用

[2] 容器的引用

[3] 容器的引用, 容器的迭代器

[4] 输出流 std::cout, 分隔符

(3) 插入型迭代器分析: 以back_insert_iterator 为例

Note: 对插入型迭代器, 解引用和自增均 doNothing; 然后返回自身(*this)的引用, 不会再次触发解引用

插入型迭代器 绑定/内部维护 容器(引用)的指针, client 对插入型迭代器做 赋值 operator= 操作 时, 会被导引调用 插入迭代器内部所含容器的 push_back/push_front/insert/输出(operator<<) 操作,该操作内部自动更新容器相应的迭代器(如 vector的finish), 即 真正的输出区间迭代器

Note: ostream 是1种流容器

    template <class Container>
    class back_insert_iterator: public iterator<output_iterator_tag,void,void,void,void>
    {
    protected:
        Container* container;
    public:
        typedef Container container_type; // 给外部用
        
        // (1) Ctor: 取容器(引用)指针
        explicit back_insert_iterator (Container& x) 
            : container(&x) {}

        // (2) 赋值 operator=: (通过容器指针)`调容器的 push_back 成员函数`, 参数按 `const 引用` 传递
        back_insert_iterator<Container>& 
        operator= (typename Container::const_reference value)
        { 
            container->push_back(value); // 更新容器自身的相应迭代器
            return *this; // Note: return *this不调解引用操作符 operator*, 仅仅是返回自身的引用
        }

        // (3) Note: 对插入型迭代器, 解引用和自增均 doNothing, 然后返回自身的引用
        back_insert_iterator<Container>& 
        operator* ()
        { return *this; }

        back_insert_iterator<Container>& 
        operator++ ()       
        { return *this; }
    };

std::iterator 类

    无成员数据
    只 typedef 了5个相应型别

容器的 push_back 函数: 内部会更新容器自身的相应迭代器(指向next可能的元素位置)

vector
    void push_back(const T& x)
    {
        if(finish != end_of_storage)
        {
            construct(finish, x); // finish 迭代器所指位置上构造新元素
            ++finish;             // 更新finish 迭代器
        }
        else
            insert_aux(end(), x);
    }

item31: 了解各种与排序有关的选择

1 nth_element/partial_sort

结论: 前n(1~n)个排列顺序在后面元素之前, 但前n+1个/[raFirst, raMid)中没排序/也排序了

(1) 部分排序 + 前n+1个内部无序: 以 第 n+1个元素为界

    nth_element(raFirst, raNth, raLast[, comp])

新区间 nth(第 n+1 个) 元素 与 sort 完整排序结果 nth 元素 值相同, nth 左、右子区间之间 整体有序(< / comp) 但各自内部无序

(2) 部分排序 + [raFirst, raMid) 内部排序, 其余无序

    partial_sort(raFirst, raMid, raLast[, comp])

(3) 能解决的问题: 对能描述出 部分区间排序语义的整体区间进行部分排序(相对于后半部分)

如: 将最好的20个Widget放到wVec前部/送给最重要的20位顾客

[1] 不关心哪个Widget送给哪位顾客 -> nth_element

[2] 前20个Widget也按顺序 送给 按重要性排序的顾客 -> partial_sort

例: 把最好的20个Widget放到wVec前部

bool 
qualityCmp(const Widget& lhs, const Widget& rhs)
{
    // Widget 的 Quality 成员提供 小于 operator< 操作符
    return lhs.getQuality() < rhs.getQuality();
}

nth_element(wVec.begin(), 
            wVec.begin() + 19, // Note: 前n=20个 => begin()+ (n - 1)
            wVec.end(),
            qualityCmp);
            
partial_sort(wVec.begin(), 
             wVec.begin() + 20,
             wVec.end(),
             qualityCmp);

2 nth_element 适用场景

(1) 找 前n个 元素

(2) 找 某个位置上 的元素

(3) 类似 nth_element 的功能, 如 找所有一级品和二级品

1) 方法1

[1] 整体排序 sort

[2] 找某个位置上的元素: 哪个位置？质量比二级还差的第1个位置: nth_element

=> 从起始处到该位置间的元素 正是所需

bool
hasBetterQualityThan3Lev(const Widget& w)
{
    Widget w3Lev(...);
    
    return  w3Lev.getQuality() < w.getQuality();
}

auto lessEqual3LevPos = 
    find( wVec.begin(), wVec.end(),
          not1( ptr_fun( hasBetterQualityThan3Lev) ) );
          
    区间 [wVec.begin(), lessEqual3LevPos) 为所求

2) 方法2: 完全排序不必要, 一种更好的策略: partition 算法

partition: 把满足 (任意, 而不仅仅是含区间语义的)特定条件的元素放在区间前部 => 当特定条件具有排序语义时, partition 具有部分排序语义

    pred(*first)

partition(wVec.begin(), wVec.end(), 
          hasBetterQualityThan3Lev);

    partial_sort/nth_element/sort: 非稳定

    stable_sort: 稳定(排序前后, 元素的相对前后关系不变)

3 list: list::sort / 借助 vector 间接排序

4 关联容器: 始终保持特定顺序

建议: 对排序算法的选择应该更多地基于所需功能, 而不是算法性能

item32: 删除元素: 需要 remove类似算法 + erase

remove类似算法: unique, 及其两者的 _if 版本

    v.erase( remove(v.begin(), v.end(), 99), 
             v.end() );

1 从容器中删除元素的唯一方法是调用该容器的成员函数

非成员的STL算法, 如 remove并 不知道 也推断不出它操作的元素所在的容器, 所以 不可能从容器中删除元素, 只能从容器中移除元素

2 remove移动了区间中的元素

(1) "不用被删除"的元素移到了区间前部(保持原相对顺序)

(2) 返回的迭代器指向最后1个"不用被删除"的元素之后的元素, 以指示 "新的 逻辑结尾", 而非容器的真正结尾

(3) remove结束后, 区间中被移除的元素可能在也可能不在区间

因为可能被 覆盖/赋值了

(4) 实现

要被移除的第1个元素 被标记为1个洞, 迭代器后移找到其后 非被移除的元素(可能与洞不相邻, 中间间隔了多个要被移除的元素), 填原洞位置 并 更新新洞位置为原洞的next位置

3 对 list, 用remove成员函数比用erase-remove习惯用法更高效(item44)

4 remove类似算法之unique

容器中移除(相邻 且 重复值 的)元素

5 remove 实现过程 & remove前、后的 容器内存布局

remove后的容器内存布局.png

remove后的容器内存布局.png

=>

被移除的元素可能在区间中(last 99), 也可能不在区间(倒数2/3):被覆盖

=>

覆盖者残留 到 容器的非逻辑区间, 若容器元素为指针, 则残留指针也指向有效对象 => 不应该 delete 残留指针, 而容器的成员函数 container::erase() / list::remove()等也不会导致 delete 容器的(指针)元素

item33: 指针容器用remove类似算法 时要特别小心

1 2个原因:

(1) 根本原因: remove 后, 很可能(若 被移除的元素最终不在区间中)已经资源泄漏了

(2) 次要原因: (erase /list::remove等 )"删除(从...去除) 容器中的指针 并 不能删除该指针所指的对象"(item7)

=> 若 被移除的元素最终仍指向自己原先所指对象, 则 也发生内存泄漏

case1: remove前 指针容器的内存布局.png

remove后 指针容器的内存布局.png

case2: 被"删除"的指针有的最终仍指向自己原先所指对象

            ——————————
begin - - ->|         | - - - - - - ->  A               
            ——————————                  
            |         |\                B
            ——————————  \              
            |         |\ \              C
            ——————————  \  \_ _ _ _ _ _              
remove_if ->|         | -\ - - - - - -- D
return      ——————————    \_ _ _ _ _ _              
            |         |- - - - - - - -  E
            ——————————                  
            |         | - - - -- - - -  F 
            ——————————                            
end() - - -> 

解决

(1) 方法1: partition算法(item31)

(2) 方法2: remove类算法前, 先手工删除指针并将它们置空

    void delAndNullifyTargetObj(Widget* & pWidget) // 指针的引用 作参数
    {
        if(! pWidget->isTargetObj() )
        {
            delete pWidget;
            pWidget = 0;
        }
    }
    
    for_each(v.begin(), v.end(),
             delAndNullifyTargetObj);
             
    v.erase( remove(v.begin(), v.end(),
                    static_cast<Widget*>(0) ),
            v.end() );

(3) 方法3: 手工循环

2 RC智能指针容器, 无remove相关问题, 但想正确用 erase-remove类似算法, 需注意几点

(1) erase-remove 可安全正确使用

    v.erase( remove(v.begin(), v.end() ),
            v.end() );

(2) erase-remove_if + mem_fun, 要求 RC智能指针/RCSP<Widget> 要能隐式地转换为对应的 内置指针类型(即 Widget＊)

std::shared_ptr 不符合要求

    std::shared_ptr 没有 
    
    //  CRSP 隐式转换wei隐式转换为 内部裸指针支持, 类型转换运算符 X::operator T()
    operator T*() const
    {
        return ptr_;
    }

原因: mem_fun 的返回类型所保存的成员函数必须通过内置指针调用

    S operator() (T* p) const // operator() 的参数必须是裸指针
    { 
        return (p->*pmem)(); 
    }

(3) erase-remove_if + mem_fn, 无(2)中要求, RC智能指针即可

std::shared_ptr 符合要求

原因: std::mem_fn 的返回类型的 operator() 的参数可为任意类型, 不再像 std::mem_fun 那样要求为裸指针

std::mem_fn 的返回类型

未指定, 但其 operator() 的参数可为任意类型
    template<class... Args>
    /* see below */ 
    operator()(Args&&... args) /* cvref-qualifiers */
        noexcept(/* see below */);

=> 可用

    v.erase( remove_if(v.begin(), v.end(),
                       mem_fn(&Widget::isTarget) ),
            v.end() );

以下例子若用 std::mem_fn OK; 用 std::mem_fun, vs2019下报错:

    error C2664: “_Result std::mem_fun_t<_Result,Widget>::operator ()(_Ty *) const”: 
        无法将参数 1 从“std::shared_ptr<Widget>”转换为“_Ty *”

#include <iostream>
#include <memory> // std::shared_ptr
#include <vector>
#include <algorithm>
#include <functional> // std::mem_fun

class Widget
{
private:
    int data;
public:
    Widget(int data_)
        : data(data_) {}

    bool
    isTarget()
    {
        return data == 0;
    }
};

int main()
{

    std::vector< std::shared_ptr<Widget> > spWVec;
    spWVec.reserve(5);
    spWVec.push_back(std::shared_ptr<Widget>(new Widget(1)));
    spWVec.push_back(std::shared_ptr<Widget>(new Widget(0)));
    spWVec.push_back(std::shared_ptr<Widget>(new Widget(2)));

    auto iter =
        std::remove_if(spWVec.begin(), spWVec.end(),
                        std::mem_fn(&Widget::isTarget) );
    spWVec.erase(iter, spWVec.end());
    std::cout << "hello" << std::endl;
}

item35: 用 lexicographical_compare 实现简单的忽略大小写的 字符串比较

Note 对字符串比较而言, strcmp vs. operator<

strcmp 返回 负数/零/正数, operator< 返回true/false

int 
ciCharCompare(char c1, char c2)
{
    int lc1 = tolower(static_cast<unsigned char>(c1) );
    int lc2 = tolower(static_cast<unsigned char>(c2) );
    
    if(lc1 < lc2)
        return -1;
    
    if(lc2 < lc1)
        return 1;
        
    return 0;
}

1 忽略大小写的字符串比较 : 不考虑国际化

用 unsigned char 强转 -> 避免 char 为负值 -1 时, 与 EOF 的混淆问题: EOF 转化不到 unsigned char

忽略大小写的字符比较 : 不考虑国际化

bool
ciCharLess(char c1, char c2)
{
    return tolower(static_cast<unsigned char>(c1) ) < 
        tolower(static_cast<unsigned char>(c2) );
}

忽略大小写的字符串比较: 用 STL中名字第二长的算法 lexicographical_compare

bool 
ciStringCompare(const string& str1, const string& str2)
{
    return lexicographical_compare(s1.begin(), s1.end(),
                                   s2.begin(), s2.end(),
                                   ciCharLess);
}

2 牺牲一点移植性 + 字符串中间不含空字符 + 不考虑国际化

忽略大小写的字符串比较: 最高效的方法是 C 实现: 把 两个string转化成 const char* 指针(item16), 再调用strcmp

int 
ciStringCompare(const string& s1, const string& s2)
{
    return strcmp(s1.c_str(), s2.c_str() );
}