第4章: 容器与算法

    4.0 建议
        1 用 push_back() 和 back_inserter() 给 容器 添加元素
        2 在 vector 上用 push_back() 优于 数组上用 realloc()

4.1 字符串

1 6大操作

    (1/2) 连接 + += 
        将 string对象 / 字符串字面常量 / C 风格字符串 / 1个 字符 连接到 string(左操作数) 上
        
        void f(string& s1, string& s2)
        {
            s1 = s1 + '\n';
            s2 += '\n';
        }
    
    (3) 下标
        
    (4) 子串
        substr(startPos, len)
        
        len: 不算 编译器 自动添的 '\0'
        
    (5) 替换
        replace(startPos, len, targetStringObj)
        
        替换的内容 与 被替换的内容 不必一样长
        
    (6) 比较
        string 与 string/字符串字面常量
    
    string str = "hello Xi'an";
    
    void f()
    {
        string s = str.substr(6, 5); // s = "Xi'an"
        str.replace(0, 5, "how are you"); // str = "how are you Xi'an"
        str[0] = toupper(name[0]); // str = "How are you Xi'an"
    }
    
    void f(const string& answer)
    {
        if(answer == "yes") { /*  */ }
    }       

4.2 I/O 流

1 << ("放到")

    默认下, 放到 std::cout 的 `值(如 10) 被转换为 字符序列` (先后将 字符'1' 和 '0' 放到 cout )

        int b = 'b';
        cout << 'a' << b; // 输出: a98

2 >> ("从...获取")

    (1) 读 字符序列
        最简单
            读入 1个 string

    (2) 默认下, 空白符 会终止输入
    
    (3) 可用 getline() 
        读取一整行(包括 尾部 换行符)
        尾部换行符 被丢弃, 接着 再 cin 的话, 从下一行开始
        
        string str;
        cin >> str;
        
        getline(cin, str);
        cout << str << "!\n";

3 用户自定义类型 I/O

    struct Entry
    {
        string name;
        int number;
    };
    ostream& operator<<(ostream& os, const Entry& e)
    {
        return os << "{\"" << e.name << "\", " << e.number << "}"; //  {\"...\", ...}
    }

4.3 容器

1 vector
    
    (1) vector 所有元素 构成1个 范围 -> 可对其用 `范围 for 循环`

    (2) 初始化/赋值 时, vector 可被 copy
        vector<Entry> book2 = book1;
        
        要想用 移动
            需 显式指定( std::move() ) / 隐式发生 (1侧为 右值)
    
2 list

    list<Entry> phone_book = {
        {"book1", 123},
        {"book2", 456}
    }
    
    (1) 添加/删除 时 无须移动 other 元素
    
    (2) list 是 序列 => 在 list 中 `搜索` 具有给定值的元素
    
        int getNum(const string& s)
        {
            for(const auto& x: phone_book)
                if(x.name == s)
                    return x.number;
            return 0; 
        }   
        
        // <=> 
        
        int getNum(const string& s)
        {
            for(auto= = phone_book.begin(); p!= phone_book.end(); ++p)
                if(p->name == s)
                    return p->number;
            return 0; 
        }   
        
    (3) 在 list 中 定位 元素
        用 迭代器 begin() end()
    
    (4) 添加/删除
        void f(const Entry& e, list<Entry>::iterator p, list<Entry>::iterator q)
        {
            phone_book.insert(p, e); // e 插入 p 所指元素前
            phone_book.erase(q); 
        }
    
    (5) 上述例子 都可以写成 等价的使用 vector 的版本
    
        且 出乎意料 的是, 数据量较小时, vector 版本的性能 由于 list
    
3 map / 关联数组 / 字典

    (名字, 数值) 对
      key   值/映射类型
      
    map<string, int> phone_book = {
        {"book1", 123},
        {"book2", 456}
    }
    
    (1) 下标 []           
        搜索 
            找到
            没找到 -> 插入: 给定 key, 关联的值为 value 类型 的 默认值(整型: 0)
            
    (2) 避免插入无效元素
        find() 和 insert() 代替 下标
    
    (3) T(n) = O(log (n) )
    
4 unordered_map

    (1) 比 map 性能更好
        基于 (某种) 序函数 的 比较                
        
    (2) 哈希容器
        `无序` 容器: 无需 `序函数`
        
        针对 key(通常是 字符串) 搜索 进行 优化
            用 哈希表 
    
5 容器

    (1) 容器 `接口 的 一致性` 便于 设计与 容器类型无关的 `算法`
    
    (2) 下标 和 遍历 vector 高效简单
        但 插/删 时, 每次都移动元素, 效率低
        
        list 恰好有 相反特性
        
    (3) 序列较短 且 元素尺寸较小 时, vector 通常比 list 高效 (insert() erase() 也是如此 )
        默认选 vector, 除非有充分的理由, 再选其他容器

4.4 算法

    (1) 排序 vector + 将 不重复的 vector 元素 copy 到 list
        bool operator<(const Entry& x, const Entry& y)
        {
            return x.name < y.name; // Entry 对象的 序 由其 名字确定
        }
        
        void f(vector<Entry>& vec, list<Entry>& lst)
        {
            sort(vec.begin(), vec.end() ); // 用 < 确定元素的 序
            unique_copy(vec.begin(), vec.end(), lst.begin() );
        }
    
    (2) 把 不重复元素 存入 新容器, 而不是覆盖 容器中旧元素
    
        1) back_insert(标准库容器) 
        
            把元素 追加到 容器末尾, 追加过程中 `扩容`
            
            不必再用 C风格显式内存管理 realloc()
            
        2) 标准库容器 
            具有 `移动` 语义
            => `传值返回` 高效
            
        list<Entry> f(vector<Entry>& vec)
        {
            list<Entry> res;
            sort(vec.begin(), vec.end() ); 
            unique_copy(vec.begin(), vec.end(), back_inserter(res) ); // 1) 追加到 res
            return res; // 2) 移动 
        }

1 迭代器

(1) 作用
    
    分离 算法 和 容器, 使 两者 对对方 一无所知
    算法 通过 迭代器 处理 (容器中的) 数据
    
    => `数据存储 和 算法分离 的 模型` 催生出 通用、灵活的软件
    
    1) 算法 向 容器 请求 迭代器
    
    2) 容器 给 算法 提供 迭代器 begin()/end()
    
    3) 算法 通过 操作 迭代器 -> 间接 操作 容器中元素
    
(2) 在 字符串 中 查找 1个字符 出现的所有位置
        |
        | 泛化
        |/
    在 容器 c 中搜索 值 v 出现的所有位置  
    
    vector<sring::iterator> find_all(string& s, char c)
    {
        vector<sring::iterator> res;
        for(auto p = s.begin(); p!= s.end(); ++p)
            if(*p == c)
                res.push_back(p);
        return res;
    }
    
    void test()
    {
        string m{"Mary had a little lamb"};
        for(auto p: find_all(m, 'a') )
            if(*p != 'a')
                cerr << "a bug!\n"
    }
        |
        | 泛化 find_all
        |/
    template<typename C, typename V>
    vector<typename C::iterator> find_all(C& c, V v) 
    {   
        vector<typename C::iterator> res;
        for(auto p = c.begin(); p!= c.end(); ++p)
            if(*p == v)
                res.push_back(p);
        return res;
    }
            |
            |   引入 类型别名
            |/
    
    #include <vector>
    using namespace std;

    template<typename C>
    using Iterator = typename C::iterator;

    template<typename C, typename V>
    vector<Iterator<C> > find_all(C& c, V v)
    {
        vector<Iterator<C> > res;
        for (auto p = c.begin(); p != c.end(); ++p)
            if (*p == v)
                res.push_back(p);
        return res;
    }

    int main()
    {
        vector<int> vec{1, 2, 3, 3, 5};

        vector< Iterator<vector<int> > > iteVec = find_all(vec, 3);
    }

2 迭代器 类型

    每种迭代器 都与 特定类型的容器 关联

3 流 迭代器

    容器 并非容纳 元素序列 的 唯一场所
    
    1个 输入流/输出流 `产生/可放` 1个 值的序列  
        ifstream/ofstream: 可 绑定到 文件的 istream/ostream
        
    istream_iterator/ostream_iterator 允许我们将 输入流/输出流 当作 只读容器/可写容器
        istream_iterator<string> ii{cin};
        istream_iterator<string> eos{}; // 输入哨兵
        ostream_iterator<string> oi{cout};      
    
    (1) 向 标准输入 写入 的 新方法
        *oi = "hello"; // <=> cout << "hello";
        ++oi; 
    
    (2) 从文件 读 数据 -> 排序 读入的 单词 -> 对单词 去重 -> 结果写到 另一文件

        note: 认为 (文件)输入流 由 `空白符` 分隔出 各 单词
    
        1) 方法 1
            文件流 + 文件流迭代器 + vector 存 输入流中 的 `各 单词(string)`
            
        2) 方法 2
            将 string 保存到 set
            
            set 
                1> 不保留 重复值, 
                2> 自动维护 值的 顺序
            
    set<string> s{ii, eos};
    copy(vec.begin(), vec.end(), oi);
    
    #include <iostream>
    #include <fstream> // 
    #include <string>
    #include <vector>
    #include <algorithm>

    using namespace std;

    // 1) 
    int main()
    {
        string fromFileName, toFileName;
        cin >> fromFileName >> toFileName;

        // (1) 流 绑定到 文件 
        ifstream is{ fromFileName };
        ofstream os(toFileName);

        // (2) 流迭代器 初始化
        istream_iterator<string> ii(is);
        istream_iterator<string> eos{};
        ostream_iterator<string> oi{ os, "\n" };

        // (3) 算法
        vector<string> vec(ii, eos);
        sort(vec.begin(), vec.end() );
        unique_copy(vec.begin(), vec.end(), oi);

        return !is.eof() || !os; 
    }

    /* 
    D:\in.txt
    hello world
    ni hao!

    D:\out.txt
    hao!
    hello
    ni
    world
    */

4 谓词

    操作 作 算法 参数
    
    查找 满足特点要求元素 
        |
        |   更通用 的 方法
        |/
      谓词
        
        map<string, int> 中 搜索 第1个 大于42 的值
            |
            |   转化为
            |/
        在 map<string, int> 中 搜索 特定的 pair<const string, int>， 并要求其 int 部分 >  42
        
        void f(map<string, int>& m)
        {
            auto p = find_if(m.begin(), m.end(), Greater_than(42) );
            // ...
        }
        
        struct Greater_than
        {
            int val;
            Greater_than(int v): val(v) {}
            bool operator()(const pair<string, int>& p) { return p.second > val; }  
        };

5 算法

    (1) 是 操作 元素序列的 函数模板
    
    (2) <algorithm>
    
    (3) 7种 常用算法
    
    总结:
        (1) 相对于 `有/无 基准值` v 的版本, 策略版本 的 `策略对象 f 放 v 位置/最后`
        (2) 
            替换/排序 返回   = void
            
            搜索    返回值 = 目标 iterator
            
            copy/合并 返回值 = 尾   iterator, 构成结果的 迭代器区间[out, p)
    
        // 搜索: 第1个满足 *p == v / f(*p) == true 的 iterator
        p =    find(b, e, v)
        p = find_if(b, e, f)
        
        // 计数
        n =    count(b, e, v)
        n = count_if(b, e, f)
        
        // 替换: v2 时 dst
           replace(b, e, v, v2) 
        replace_if(b, e, f, v2)
        
        // copy
        p =        copy(b, e, out)
        p =     copy_if(b, e, out, f)
        p = unique_copy(b, e, out)
        p = unique_copy(b, e, out, f) // 连续重复元素, 只 copy 第1个
        
        // 排序
        sort(b, e)    // 默认 < 作 序函数
        sort(b, e, f)
        
        // 合并: 结果放 [out, p)
        p = merge(b, e, b2, e2, out)
        
        // 对 已排序序列 二分搜索, 子序列 元素值 都等于 v
        (p1, p2) = equal_range(b, e, v)

6 容器 算法

(1) 序列 
    用一对 迭代器 [begin, end) 定义
    
(2) 为 标准算法 加1层接口, 更简单

    算法 操作的序列 时 容器本身的内容 时
        sort(v.begin(), v.end() )
            |   冗长
            |
            |   简化
            |       将 容器版本 的 sort() 放到 自己的 namespace( Estd: 扩展std)
            |/
        sort(v)
        
    #include <algorithm>
    #include <vector>

    namespace Estd
    {
        using namespace std;

        template<typename C>
        void sort(C& c)
        {
            sort(c.begin(), c.end());
        }

        template<typename C, typename Pred>
        void sort(C& c, Pred p)
        {
            sort(c.begin(), c.end(), p);
        }
    }

    int main()
    {
        std::vector<int> vec{1, 3, 2};

        Estd::sort(vec);
    }

1.jpg 2.jpg 3.jpg