C++ 进阶基础之五

大纲

• C++ 进阶基础之一、C++ 进阶基础之二、C++ 进阶基础之三
• C++ 进阶基础之四、C++ 进阶基础之五、C++ 进阶基础之六
• C++ 进阶基础之七、C++ 进阶基础之八、C++ 进阶基础之九
• C++ 进阶基础之十、C++ 进阶基础之十一

基本概念

模板的基本概念

模板是实现代码重用机制的一种重要工具，其本质是类型参数化，即把类型定义为参数。C++ 提供了类模板和函数模板，详细的使用可参考教程：C++ 进阶基础之二

类模板的简介

• 类模板的本质就是建立一个通用类，其成员变量的类型、成员函数的返回类型和参数类型都可以不具体指定，而用虚拟的类型来替代
• 当使用类模板建立对象时，编译器会根据实参的类型取代类模板中的虚拟类型，从而实现不同类的功能

函数模板的简介

• 函数模板就是建立一个通用的函数，其函数返回类型和形参类型不具体指定，而是用虚拟的类型来替代
• 凡是函数体相同的函数都可以用函数模板来代替，不必定义多个函数，只需在模板中定义一次即可
• 在调用函数时，编译器会根据实参的类型来取代模板中的虚拟类型，从而实现不同函数的功能

STL 的基本概念

STL 的简介

STL（Standard Template Library，标准模板库）是惠普实验室开发的一系列软件的统称。现然主要出现在 C++ 中，但在被引入 C++ 之前该技术就已经存在了很长的一段时间。STL 的从广义上讲分为三类：Algorithm（算法）、Container（容器）和 Iterator（迭代器），容器和算法通过迭代器可以进行无缝地连接。几乎所有的 STL 代码都采用了类模板和函数模板的方式编写，这相比于传统的由类和函数组成的库来说提供了更好的代码重用机会。从逻辑层次来看，在 STL 中体现了泛型化程序设计的思想（Generic Programming），在这种思想里，大部分的基本算法被抽象和被泛化，独立于与之对应的数据结构，用于以相同或相近的方式处理各种不同情形。从实现层次看，整个 STL 是以一种类型参数化（Type Parameterized）的方式实现的，本质是基于模板（Template）。在 C++ 标准中，STL 被组织为下面的 13 个头文件：<algorithm>、<deque>、<functional>、<iterator>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack> 、<utility>。

STL 的优势

• STL 是 C++ 的一部分，因此不用额外安装什么就可以直接使用，因为它被内建在编译器之内
• STL 的一个重要特点是数据结构和算法的分离，尽管这是个简单的概念，但是这种分离使 STL 变得非常通用
• 开发人员一般可以不用思考 STL 具体的实现过程，只要能够熟练使用 STL 就可以了，这样可以把精力放在程序开发的其他方面
• STL 具有高可重用性、高性能、高移植性、跨平台的优点
  • 高移植性：如在项目 A 上使用 STL 编写的模块，可以直接移植到项目 B 上
  • 跨平台：如用 Windows 的 Visual Studio 编写的代码，可以在 Mac OS 的 XCode 上直接编译
  • 高性能：如 map 可以高效地从十万条记录里面查找出指定的记录，因为 map 是采用红黑树的变体实现的（红黑树是平横二叉树的一种）
  • 高可重用性：STL 中几乎所有的代码都采用了类模板和函数模板的方式实现，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会

STL 的六大组件

• 容器（Containers）：各种数据结构，如 vector、list、deque、set、map 用来存放数据，STL 容器是一种类模板。
• 算法（Algorithms）：各种常用算法如 sort、search、copy、erase，从实现的角度来看，STL 算法是一种函数模板。
• 迭代器（Iterators）：扮演容器与算法之间的胶合剂，是所谓的 泛型指针，共有五种类型，以及其它衍生变体。从实现的角度来看，迭代器是一种将 Operators*、Operator->、Operator++、Operator-- 等相关操作予以重载的类模板。所有 STL 容器都附带有自己专属的迭代器，原生指针（Native pointer）也是一种迭代器。
• 仿函数（Functors）：也叫函数对象，行为类似函数，可作为算法的某种策略（Policy），从实现的角度来看，仿函数是一种重载了 Operator() 的类或者类模板。一般函数指针可视为狭义的仿函数。
• 适配器（Adapters）：一种用来修饰容器（Containers）或仿函数（Functors）或迭代器（Iterators）接口的东西，例如：STL 提供的 Queue 和 Stack，虽然看似容器，但只能算是一种容器适配器，因为它们的底层完全借助 Deque，所有操作都由底层的 Deque 提供。改变 Functor 接口者，称为 Function Adapter；改变 Container 接口者，称为 Container Adapter；改变 Iterator 接口者，称为 Iterator Adapter。适配器的实现技术很难一言蔽之，必须逐一分析。
• 空间配置器（Allocators）：负责空间配置与管理，从实现的角度来看，配置器是一个实现了动态空间配置、空间管理、空间释放的类模板。

STL 组件之间的关系如下图所示：

• 1）STL 的容器通过类模板技术，实现数据类型和容器模型的分离。
• 2）STL 的迭代器技术实现了遍历容器的统一方法，也为 STL 的算法提供了统一性。
• 3）STL 的函数对象（仿函数）实现了自定义数据类型的算法运算。
• 4）具体例子：transform 算法的输入，通过迭代器 first 和 last 指向的元算作为输入；通过 result 作为输出；通过函数对象来做自定义数据类型的运算。

容器的基本概念

在实际的开发过程中，数据结构本身的重要性不会逊于操作数据结构的算法的重要性，当程序中存在着对执行效率要求很高的部分时，数据结构的选择就显得更加重要。经典的数据结构数量有限，但是常常重复着一些为了实现向量、链表等结构而编写的代码，这些代码都十分相似，只是为了适应不同数据的变化而在细节上有所不同。STL 容器为此提供了这样的方便，它允许重复利用已有的实现构造自己的特定类型下的数据结构，通过设置一些模板，STL 容器对最常用的数据结构提供了支持，这些模板的参数允许指定容器中元素的数据类型，可以将许多重复而乏味的工作简化。容器部分主要由头文件 <vector>、<list>、<deque>、<set>、<map>、<stack>、<queue> 组成。对于常用的一些容器和容器适配器（可以看作由其它容器实现的容器），可以通过下表总结不同容器与相应头文件的对应关系。

容器	描述	实现头文件
向量 (vector)	连续内存的元素	<vector>
列表 (list)	由节点组成的双向链表，每个结点包含着一个元素	<list>
双队列 (deque)	连续内存的指向不同元素的指针所组成的数组	<deque>
集合 (set)	由节点组成的红黑树，每个节点都包含着一个元素，节点之间以某种作用于元素对的谓词排列，没有两个不同的元素能够拥有相同的次序	<set>
多重集合 (multiset)	允许存在两个次序相等的元素的集合	<set>
栈 (stack)	先进后出的值的排列	<stack>
队列 (queue)	先进先出的执的排列	<queue>
优先队列 (priority_queue)	元素的次序是由作用于所内存的值对上的某种谓词决定的一种队列	<queue>
映射 (map)	由 {键，值} 对组成的集合，以某种作用于键对上的谓词排列	<map>
多重映射 (multimap)	允许键对有相等的次序的映射	<map>

容器的简介

容器可以用来管理一组元素，如下图所示：

容器的分类

• 序列式容器（Sequence Containers）：每个元素都有固定的位置，取决于插入时机和地点，与元素的值无关，如 vector、deque、list
• 关联式容器（Associated Containers）：元素位置取决于特定的排序规则，与插入的顺序无关，如 set、multiset、map、multimap

算法的基本概念

算法的简介

函数库对数据类型的选择对其可重用性起着至关重要的作用。举例来说，一个求方根的函数，在使用浮点数作为其参数类型的情况下的可重用性肯定比使用整型作为它的参数类性要高。而 C++ 通过模板的机制允许推迟对某些类型的选择，直到真正想使用模板或者说对模板进行特化的时候，STL 就利用了这一点提供了相当多的算法。它是在一个有效的框架中完成这些算法的 —— 可以将所有的类型划分为少数的几类，然后就可以在模板的参数中使用一种类型替换掉同一种类中的其他类型。

算法的头文件

STL 提供了大约 100 个实现算法的函数模板，比如算法 for_each 将为指定序列中的每一个元素调用指定的函数，stable_sort 以调用者所指定的规则对序列进行稳定性排序等等。这样一来，只要熟悉了 STL 之后，许多代码可以被大大地简化，只需要通过调用一两个算法模板，就可以完成所需要的功能。算法主要由头文件 <algorithm>、<numeric>、<functional> 组成。<algorithm> 是所有 STL 头文件中最大的一个，它是由一大堆函数模板组成的，可以认为每个函数在很大程度上都是独立的，其中常用到的功能范围涉及到比较、交换、查找、遍历、复制、修改、移除、反转、排序、合并操作等。<numeric> 的体积很小，只包括几个在序列上面进行简单数学运算的函数模板，包括加法和乘法在序列上的一些操作。<functional> 中则定义了一些类模板，用来声明函数对象。

迭代器的基本概念

• 迭代器是一个 “可遍历 STL 容器内全部或部分元素” 的对象。
• 迭代器指出容器中的一个特定位置。
• 迭代器就如同一个指针。
• 迭代器提供对一个容器中的对象的访问方法，并且定义了容器中对象的范围。

迭代器的简介

迭代器从作用上来说是最基本的部分。软件设计有一个基本原则，所有的问题都可以通过引进一个间接层来简化，这种简化在 STL 中就是用迭代器来完成的。概括来说，迭代器在 STL 中用来将算法和容器联系起来，起着一种黏和剂的作用。几乎 STL 提供的所有算法都是通过迭代器存取元素序列进行工作的，每一个容器都定义了其本身所专有的迭代器，用以存取容器中的元素。迭代器主要由头文件 <utility>、<iterator>、<memory> 组成。其中 <utility> 是一个很小的头文件，它包括了贯穿使用在 STL 中的几个模板的声明，<iterator> 中提供了迭代器 使用的许多方法，而对于 <memory> 描述起来则十分的困难，它以不同寻常的方式为容器中的元素分配内存空间，同时也为某些算法在执行期间产生的临时对象提供管理机制，<memory> 中最主要的是类模板 allocator，它负责产生所有容器的默认空间配置器（分配器）。

迭代器的分类

• 输入迭代器：也有叫法称之为 只读迭代器，它从容器中读取元素，只能一次读入一个元素向前移动，只支持一遍算法，同一个输入迭代器不能两遍遍历一个序列。
• 输出迭代器：也有叫法称之为 只写迭代器，它往容器中写入元素，只能一次写入一个元素向前移动，只支持一遍算法，同一个输出迭代器不能两遍遍历一个序列。
• 正向迭代器：组合输入迭代器和输出迭代器的功能，还可以多次解析一个迭代器指定的位置，可以对一个值进行多次读 / 写。
• 双向迭代器：组合正向迭代器的功能，还可以通过 -- 操作符向后移动位置。
• 随机访问迭代器：组合双向迭代器的功能，还可以向前向后跳过任意个位置，可以直接访问容器中任何位置的元素。

提示

• list、set、multiset、map、multimap 容器支持双向迭代器。
• vector，deque 支持随机访问迭代器。

初识容器的使用

指针是一种迭代器

#include <iostream>

using namespace std;

int main() {
    int array[5] = {1, 2, 3, 4, 5};
    int length = sizeof(array) / sizeof(int);
    int *p = array;

    for (int i = 0; i < length; i++) {
        cout << *(p++) << " ";
    }
    return 0;
}

程序运行输出的结果如下：

1 2 3 4 5 

容器存放基础数据类型

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void m_print(const int num) {
    cout << num << " ";
}

int main() {
    // 定义容器
    vector<int> v;

    // 插入数据
    v.push_back(11);
    v.push_back(12);
    v.push_back(13);
    v.push_back(14);
    v.push_back(15);

    // 第一种方式：遍历容器
    vector<int>::iterator itBegin = v.begin();
    vector<int>::iterator itEnd = v.end();
    while (itBegin != itEnd) {
        cout << *(itBegin++) << " ";
    }
    cout << endl;

    // 第二种方式：遍历容器
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;

    // 第三种方式：遍历容器
    for_each(v.begin(), v.end(), m_print);

    return 0;
}

程序运行输出的结果如下：

11 12 13 14 15 
11 12 13 14 15 
11 12 13 14 15 

容器存放自定义数据类型

#include <iostream>
#include <vector>

using namespace std;

class Person {

public:
    Person(int age, string name) {
        this->age = age;
        this->name = name;
    }

    int getAge() {
        return this->age;
    }

    string getName() {
        return this->name;
    }

private:
    int age;
    string name;

};

int main() {
    Person p1(23, "Jim");
    Person p2(26, "Tom");
    Person p3(29, "Peter");

    // 定义容器
    vector<Person> v;

    // 插入数据
    v.push_back(p1);
    v.push_back(p2);
    v.push_back(p3);

    // 遍历容器
    for (vector<Person>::iterator it = v.begin(); it != v.end(); it++) {
        cout << "age = " << it->getAge() << ", name = " << it->getName() << endl;
        // 或者
        // cout << "age = " << (*it).getAge() << ", name = " << (*it).getName() << endl;
    }
    return 0;
}

程序运行输出的结果如下：

age = 23, name = Jim
age = 26, name = Tom
age = 29, name = Peter

容器存放自定义数据类型的指针

#include <iostream>
#include <vector>

using namespace std;

class Person {

public:
    Person(int age, string name) {
        this->age = age;
        this->name = name;
    }

    int getAge() {
        return this->age;
    }

    string getName() {
        return this->name;
    }

private:
    int age;
    string name;

};

int main() {
    // 定义容器
    vector<Person *> v;

    // 插入数据
    v.push_back(new Person(23, "Jim"));
    v.push_back(new Person(26, "Tom"));
    v.push_back(new Person(29, "Peter"));

    // 遍历容器
    for (vector<Person *>::iterator it = v.begin(); it != v.end(); it++) {
        cout << "age = " << (*it)->getAge() << ", name = " << (*it)->getName() << endl;
        // 或者
        // cout << "age = " << (**it).getAge() << ", name = " << (**it).getName() << endl;
    }
    return 0;
}

程序运行输出的结果如下：

age = 23, name = Jim
age = 26, name = Tom
age = 29, name = Peter

容器之间的嵌套使用

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 定义容器
    vector<int> v1;
    vector<int> v2;
    vector<int> v3;
    vector<vector<int>> v;

    // 插入数据
    for (int i = 0; i < 5; i++) {
        v1.push_back(i + 1);
        v2.push_back(i + 6);
        v3.push_back(i + 11);
    }
    v.push_back(v1);
    v.push_back(v2);
    v.push_back(v3);

    // 遍历容器
    for (vector<vector<int>>::iterator it1 = v.begin(); it1 != v.end(); it1++) {
        for (vector<int>::iterator it2 = (*it1).begin(); it2 != (*it1).end(); it2++) {
            cout << *it2 << " ";
        }
        cout << endl;
    }
    return 0;
}

程序运行输出的结果如下：

1 2 3 4 5 
6 7 8 9 10 
11 12 13 14 15 

各类容器的对比

各类容器的特性对比

	vector	deque	list	set	multiset	map	multimap
数据结构	单端数组	双端数组	双向链表	二叉树	二叉树	二叉树	二叉树
可随机存取	是	是	否	否	否	对 Key 而言是	否
元素搜索速度	慢	慢	非常慢	快	快	对 Key 而言快	对 Key 而言快
快速插入与移除	尾端	头尾两端	任何位置	-	-	-	-

各类容器的使用场景

• deque 的使用场景：比如排队购票系统，对排队者的存储可以采用 deque，支持头端的快速移除，尾端的快速添加。如果采用 vector，则头端移除时，会移动大量的数据，速度很慢。
• list 的使用场景：比如公交车乘客的存储，随时可能有乘客上下车，支持频繁地对不确定位置的元素进行移除与插入操作。
• set 的使用场景：比如对手机游戏的个人得分记录的存储，存储要求从高分到低分地顺序排列。 
• map 的使用场景：比如按 ID 号存储十万个用户，想要快速地通过 ID 查找对应的用户，这时二叉树的查找效率就体现出来了。如果是使用 vector 容器，最坏的情况下可能要遍历完整个容器才能找到指定的用户。

vector 与 deque 对比

• vector.at() 比 deque.at() 效率高，比如 vector.at(0) 是固定的，而 deque 的开始位置却是不固定的。
• 如果有大量内存释放操作的话，vector 花的时间更少，这跟二者的底层实现有关。
• deque 支持头部的快速插入与快速移除，而 vector 则不支持。