<C++>11 STL

本文最后更新于：2023年3月30日 下午

11 STL

长久以来，软件界一直希望建立一种可重复利用的东西。C++ 的面向对象和泛型编程的思想，目的就是代码复用性的提升。

多数情况下，数据结构和算法都未能有一套标准，这导致了大量的重复工作。

STL（Standard Template Library）的诞生就是为了建立数据结构和算法的一套标准。

STL 从广义上分为：容器（container）、算法（algorithm）、迭代器（iterator）。容器和算法间通过迭代器进行无缝连接。STL 几乎所有代码都采用了模板类或模板函数。

STL 的六大组件是：

  • 容器：各种数据结构，如 vector、list、deque、set、map 等，用以存放数据

    容器就是运用最广泛的一些数据结构（数组、链表、树、栈、队列、集合、映射表等）的实现

    容器分为两种：

    • 序列式容器：强调值的排序。序列式容器中每个元素都有固定的位置
    • 关联式容器：二叉树结构，各元素间没有严格的物理上的顺序关系

  • 算法：各种常用算法，如 sort、find、copy、for_each 等

    用有限的步骤，解决逻辑或数学上的问题，这样的学科称为算法

    算法分为两种：

    • 质变算法：运算过程中会改变区间内元素的内容。如拷贝、替换、删除等
    • 非质变算法：运算过程不会改变区间内的元素内容。如查找、计数、遍历、寻找极值等

  • 迭代器：扮演了容器和算法间的胶合剂

    提供一种方法，使之能依序寻访某个容器所含的各个元素，而无需暴露该容器的内部表示方式

    每个容器都有自己的迭代器

    迭代器分为五种：

    • 输入迭代器：对数据的只读访问。支持 ++、==、!、=
    • 输出迭代器：对数据的只写访问。支持 ++
    • 前向迭代器：读写操作，并能向前推进迭代器。支持 ++、==、!、=
    • 双向迭代器：读写操作，并能向前、后操作。支持 ++、–
    • 随机访问迭代器：读写操作，可以跳跃访问任意数据。支持 ++、–、[n]、-n、<、<=、>、>=

  • 仿函数：行为类似函数，可以作为算法的某种策略

  • 适配器：一种用来修饰容器或仿函数或迭代器接口的东西

  • 空间配置器：负责空间的配置与管理

11.1 STL 常用容器

容器就是运用最广泛的一些数据结构（数组、链表、树、栈、队列、集合、映射表等）的实现

11.1.1 string 容器

string 是 C++ 风格的字符串。string 的本质是一个类

使用前应该包含头文件：#include<string>

string 与 char* 的区别：

  • char* 是一个指针
  • string 是一个类，其内部封装了 char*，管理字符串，是一个 char* 型的容器

构造方法：

  • string()：创建空串
  • string(const char* s)：以指定字符串初始化
  • string(const string& str)：用另一个 string 初始化
  • string(int n, char c)：用 n 个 c 进行初始化

string 赋值操作：

  • string& operator=(const char* s)：把 s 赋给当前 string。重载了 = 操作符

    string& operator=(const string& s)

    string& operator=(char s)

  • string& assign(const string& s)：把 s 赋给当前 string。

    string& assign(const char* s)

    string& assign(const char* s, int n)：把 s 的前 n 个字符赋给当前 string

    string& assign(int n, char c)：把 n 个 c 赋给当前 string

string 拼接操作：

  • string& operator+=(const char* s)：在当前 string 末尾拼接 s。重载了 += 操作符

    string& operator+=(const char c)

    string& operator+=(const string& s)

  • string& append(const char* s)：在当前 string 末尾拼接 s。

    string& append(const string& s)

    string& append(const char* s, int n)：拼接 s 的前 n 个字符

    string& append(const string& s, int pos, int n)：拼接 s 的 [pos, pos + n) 范围的字符

string 查找和替换：

  • int find(const string& s, int pos = 0)：从 pos 位置开始，查找 s 第一次出现的位置

    返回那个找到位置的起始下标。没有找到的场合，返回 -1

    int find(const char* s, int pos = 0)

    int find(const char c, int pos = 0)

    int find(const char* s, int pos, int n)：从 pos 位置开始，查找 s 中前 n 个字符第一次出现的位置

  • int rfind(const string& s, int pos = npos)：从 pos 位置开始，查找 s 最后一次出现的位置

    int rfind(const char* s, int pos = npos)

    int rfind(const char c, int pos = npos)

    int rfind(const char* s, int pos, int n)：从 pos 位置开始，查找 s 中前 n 个字符最后一次出现的位置

  • string& replace(int pos, int n, const string& s)：把 [pos, pos + n) 处字符串替换为 s

    string& replace(int pos, int n, const char* s)

  • int size()：获取 string 的长度

string 的比较：

  • int compare(const string& s)：与字符串进行比较

    相同的场合返回 0。不同的场合，根据 出现的第一处不同的字符的 ASCII 码的差值 返回 1 或 -1

    int compare(const char* s)

string 字符存取：

  • char& operator[](int n)：通过下标获取字符。重载了 [] 操作符

    因为获取的是 char&，所以获取以后可以修改

  • char& at(int n)：通过下标获取字符

  • string substr(int pos = 0, int n =npos)：截取 [pos, pos + n) 范围的子串，返回其构成的 string

string 插入和删除

  • string& insert(int pos, const char* s)：在 pos 位置插入 s

    string& insert(int pos, const string& s)

    string& insert(int pos, int n, const char c)：在 pos 位置插入 n 个 c

  • string& erase(int pos, int n = npos)：删除 [pos, pos + n) 范围的字符

11.1.2 vector 容器

vector 是可变容量的单端数组，能从尾部执行插入和删除元素

使用前应该包含头文件：#include<vector>

vector 与 数组 的区别：

  • 数组是静态空间，其容量大小固定

  • vector 可以动态扩展空间。

    动态扩展是找到一块更大的空间，之后拷贝原数据到新空间，并释放原空间。

构造函数：

  • vector<T>()：采用模板实现类实现的空的默认 vector
  • vector<T>(iterator begin, iterator end)：初始加入 由迭代器所指示的 [begin, end) 范围内元素的 vector
  • vector<T>(int n, T element)：初始加入 n 个 element 元素的 vector
  • vector<T>(const vector& v)：拷贝构造函数

迭代器：

vector 容器的迭代器是：随机访问迭代器

  • const_iterator& begin()：返回一个指向第一个元素的迭代器
  • reverse_iterator& rbegin()：返回一个指向最后一个元素的迭代器
  • const_iterator& end()：返回一个指向最后一个元素后方空间的迭代器
  • reverse_iterator& rend()：返回一个指向第一个元素前方空间的迭代器

赋值操作：

  • vector& operator=(const vector& v)：用另一个 vector 赋值。重载了 = 操作符

  • assign(iterator begin, iterator end)：用 由迭代器所指示的 [begin, end) 范围内的元素 赋值

    assigne(int n, T element)：用 n 个 element 元素赋值

容量和大小：

  • bool empty()：判断是否为空

  • int capacity()：返回容器的容量

  • int size()：返回容器包含的元素数量

  • void resize(int num)：重新指定容器容量。

    容量变大的场合，以默认值填充多余位置。变小的场合，末尾的多余元素会被丢弃。

    void resize(int num, T element)：重新指定容器容量。如有需要，以 element 填充多余位置

插入和删除：

  • push_back(T element)：尾部插入元素 element

  • pop_back()：删除最后一个元素

  • const_iterator insert(iterator pos, T element)：在迭代器的指示位置插入 element

    返回值是该插入位置（的迭代器）

    const_iterator insert(iterator pos, int n, T element)：在迭代器的指示位置插入 n 个 element

    const_iterator insert(iterator pos, iterator start, iterator end)：在迭代器的指示位置插入 迭代器所指示的 [begin, end) 范围内的元素

  • erase(iterator pos)：删除迭代器指示位置的元素

    erase(iterator start, iterator end)：删除迭代器所指示的 [begin, end) 范围内的元素

  • clear()：用 圣光 净化这个容器

数据存取：

  • T& operator[](index)：获取指定下标位置的元素。重载了 [] 运算符
  • T& at(int index)：获取指定下标位置的元素。
  • T& front()：获取容器中第一个元素
  • T& back()：获取容器中最后一个元素

互换容器：

  • swap(vector& v)：互换……就是互换。

    巧妙地使用 swap 可以收缩内存空间。哇哦 ~

预留空间：

  • reserve(int len)：容器预留 len 个位置。预留位置不初始化，元素不可访问

    这样，能减少 vector 容器动态扩展时的扩展次数

遍历 vector：

void print(const vector<int>& v) {
	for (vector<int>::const_iterator i = v.begin(); i < v.end(); i++) {
		cout << *i << '\t';
	}
	cout << endl;
}

不难懂吧

11.1.3 deque 容器

双端数组。可以从头端或尾端进行插入删除操作

deque 内部有一个中控器，维护每段缓冲区中的内容。缓冲区中存放真实数据

中控器维护的是每个缓冲区的地址，使得使用 deque 时貌似是一片连续的内存空间

（deque 中控器图_11.1.3）

deque 与 vector 的区别：

  • vector 从头部插入删除的效率低（需要移动元素）。数据量越大，效率越低
  • deque 相对而言，对头部插入、删除的速度比 vector 快
  • vector 访问元素的速度比 deque 快

迭代器：

和 vector 一样

构造器：

和 vector 一样，欸嘿 ★~

常用方法：

大部分和 vector 一样

注意 deque 容器 没有容量（其容量无限。原因见 [deque 中控器图_11.1.3]），所以也不能获取容量。但可以改变容量。效果和 vector 相似

此外，还有这些额外的方法：

  • push_front(T element)：头部插入元素 element
  • pop_front()：删除容器第一个数据

11.1.4 stack 容器

stack 栈容器是一种 先进后出 的数据结构。它只有一个出口。只有栈顶的数据能被访问。

栈容器不允许有遍历行为。栈中进入数据称为 入栈，弹出数据称为 出栈。

（stack 栈图_11.1.4）

构造函数：

  • stack<T>()：默认构造
  • stack<T>(const stack<T>& s)：拷贝构造函数

赋值操作：

  • stack& operator=(const stack& s)：重载 = 操作符

数据存取：

  • push(T element)：向栈顶添加元素
  • pop()：从栈顶移除第一个元素
  • T& top()：从栈顶获取第一个元素

容量操作：

  • bool empty()：是否为空
  • int size()：返回栈的大小

11.1.5 queue 容器

queue 队列容器是一种 先进先出 的数据结构。有两个出口，只有队首与队尾能被访问。

队列容器不允许遍历行为。进数据称为 入队，出数据称为 出队。

（queue 队列图_11.1.5）

构造函数：

  • queue<T>()：默认构造函数
  • queue<T>(const queue<T>& q)：拷贝构造函数

赋值操作：

  • queue& operator=(const queue& q)：重载 = 操作符

数据存取：

  • push(T ele)：向队尾添加元素

  • pop()：从队首移除一个元素

  • T& back()：返回最后一个元素。

    既然是先进先出，那么最后显然指的是队尾（后进）元素

  • T& front()：返回第一个元素

容量操作：

  • bool empty()：你猜这个方法是用来干什么的？
  • int size()：你再猜一个？

11.1.6 list 容器

list 链表是一种存储单元上非连续的数据结构。

链表由一系列节点串联组成。每个节点中包含 数据域 和 指针域。

由于存储方式是不连续的内存空间，其迭代器只能前移或后移，属于 双向迭代器

（list 链表图_11.1.6）

list 的特点：

  • 采用动态存储分配，不会造成内存浪费和溢出
  • 插入和删除操作方便，只需要修改指针，而不需要移动大量元素
  • 其空间（占用额外指针域）和时间（遍历速度慢）消耗较大

构造函数：

  • list<T>()：默认构造
  • list<T>(iterator start, iterator end)：用 迭代器指示的 [start, end) 区间的元素 进行初始化
  • list<T>(int n, T ele)：用 n 个 ele 进行初始化
  • list<T>(const list<T>& list)：拷贝构造

常用方法：

大部分和 deque 一样。你往上翻翻嘛

不能用 <、> 来对 list 提供的双向迭代器进行比较，也不能进行 +、- 操作。但是 ++、-- 操作符是有效的

list 不支持随机访问。只能通过 front() 或 back() 访问第一个或最后一个元素。其余时候，使用迭代器遍历元素

此外，还有以下方法：

  • remove(T ele)：删除链表中所有与 ele 匹配的元素

11.1.7 set / multiset 容器

set 关联式容器（集合容器）底层结构是用 二叉树 实现。所有元素在插入时会被自动排序。

set 不允许重复元素。multiset 允许重复元素

构造函数：

  • set<T>()：这是啥呀，这是一个无参构造器呀
  • set<T>(const set<T>& s)：拷贝构造

常用方法：

set / multiset 容器没有 push_xxx 方法 或 pop_xxx 方法。

set / multiset 容器插入元素只能使用 insert 方法，删除元素只能使用 erase 方法

set 插入元素时会返回一个 pair<iterator, bool> 对象，以表示插入成功或失败。multiset 不会有返回值

此外，还有以下方法：

  • iterator& find(T key)：查找 key 是否存在。

    存在的场合，返回指示那个位置的迭代器。不存在的场合，返回那个 end() 迭代器

  • int count(key)：统计 key 的个数

排序：

set / multiset 容器默认排序规则为从小到大。可以利用仿函数改变排序规则。

class OComparator {
public:
	bool operator()(const int o1, const int o2) {	// <———— 仿函数
		return o1 > o2;
	}
};

int main() {
	set<int, OComparator> s;						// <———— 这个场合，排序规则变为指定规则
}

对于自定义的数据类型，往往都会给定排序规则。

11.1.8 pair 对组

pair 是成对出现的数据。利用对组可以实现返回两个数据

构造方法：

  • pair<T, S>(T value1, S value2)：构造一个对组
  • make_pair<T, S>(T value1, S value2)：该方法返回一个对组

访问对组元素：

  • T& first()：访问第一个元素
  • S& second()：访问第二个元素

11.1.9 map / multimap 容器

map / multimap 也属于关联式容器。底层结构用二叉树实现，其中所有元素都是 pair。

pair 中第一个元素为 key（键），起索引作用。第二个元素为 value（值）

map / multimap 容器的所有元素按照键值排序。可以根据键值快速找到 value 值

map 不允许重复键值，multimap 允许重复键值

构造函数：

  • map<T, S>()：默认构造函数
  • map<T, S>(const map<T, S>& m)：拷贝构造函数

常用方法：

和 set 容器差不多

map / multimap 容器在使用 insert 插入时，插入的是一个 pair 对象：insert(pair<T, S>(t, s))

使用 erase 删除、find 查找、count 统计时，按照那个键值确定对象：erase(T& key)

排序：

和 set 一样，利用仿函数：map<T, S, OComparator> m;

11.2 STL 函数对象

重载函数调用操作符的类，其对象称为 函数对象

函数对象使用重载的 () 时，行为类似函数调用，也叫 仿函数

函数对象的本质是一个类，不是一个函数。

class AddInt{							// <———— 函数对象
public:
    int extra = 0;
    int operator(int n1, int n2) {		// <———— 仿函数
        return n1 + n2 + extra++;
    }
};

int main() {
    AddInt adding;
    int n = adding(1, 14);
}

特点：

  • 函数对象使用时，可以像普通函数那样调用。可以有参数和返回值
  • 函数对象超出普通函数的概念，可以有自己的状态
  • 函数对象可以作为参数传递

11.2.1 谓词

返回 bool 类型的仿函数称为 谓词

接受一个参数的仿函数被称为 一元谓词、接受两个参数的仿函数被称为 二元谓词

class CompareInt{
public:
    bool operator()(int n1, int n2 = 0) {
        return n1 > n2;
    }
};

11.2.2 内建函数对象

STL 内建了一些函数对象。这些函数对象用法和一般函数完全相同。

要使用这些函数对象，要包含头文件：#include<functional>

内建函数对象又分为三种：

  • 算数仿函数
  • 关系仿函数
  • 逻辑仿函数

算数仿函数：

主要功能是实现四则运算。

  • template<class T> plus<T>：加法仿函数

    plus<int> p;
cout << p(1, 15) << endl;					// <———— 输出 16

  • template<class T> minus<T>：减法仿函数

  • template<class T> multiplies<T>：乘法仿函数

  • template<class T> divides<T>：除法仿函数

  • template<class T> modulus<T>：取模仿函数

  • template<class T> negate<T>：取反仿函数（一元运算）

关系仿函数：

  • template<class T> bool equal_to<T>：等于

  • template<class T> bool not_equal_to<T>：不等于

  • template<class T> bool greater<T>：大于

    set<int, greater<int>> s;					// <———— 一个降序排序的 set

  • template<class T> bool greater_equal<T>：大于等于

  • template<class T> bool less<T>：小于

  • template<class T> bool less_equal<T>：小于等于

逻辑仿函数：

  • template<class T> bool logical_and<T>：逻辑与
  • template<class T> bool logical_or<T>：逻辑或
  • template<class T> bool logical_not<T>：逻辑非

11.3 STL 常用算法

算法主要由头文件 <algorithm>、<functional>、<numeric> 组成：

  • <algorithm>：所有 STL 头文件中最大的一个，涉及比较、交换、查找、遍历、复制、修改等
  • <numeric>：体积很小，只包括几个在序列上面进行简单数学运算的模板函数
  • <functional>：定义了一些模板类，以声明函数对象

不支持随机访问迭代器的容器，很多算法不支持。那个场合，应该使用那些容器内部内置方法

11.3.1 常用遍历算法

  • void for_each(iterator start, iterator end, consumer)：遍历。

    把 [start, end) 范围的元素依次进行 consumer 操作。不会改变原本对象。

    #include<algorithm>
#include<set>

void printInt(int n) {
	cout << n << endl;
}

class PrintInteger {
public:
	void operator()(int n) {
		cout << n << endl;
	}
};

int main() {
	set<int, greater<int>> s;
	PrintInteger p;
	s.insert(1);
	for_each(s.begin(), s.end(), printInt);			// <———— 传入函数
	for_each(s.begin(), s.end(), PrintInteger());	// <———— 传入函数对象（匿名初始化）
	for_each(s.begin(), s.end(), p);				// <———— 传入函数对象
}

  • void transform(iterator beg1, interator end1, iterator beg2, function)：搬运容器内容至另一个容器中

    把源容器的 [beg1, end1) 范围的元素，经过 function 处理后，添加到新容器的 beg2 位置。

    function 的返回值应该是新容器指定的泛型类型

    注意：新容器必须具备合适的容量，否则会报错

11.3.2 常用查找算法

  • iterator& find(iterator start, iterator end, T& ele)：查找元素

    在 [start, end) 范围内查找 ele 元素。找到的场合返回该元素初次出现的位置，否则返回 end

    那个泛型 T 是自定义类型的场合，需要重载运算符 == 以使算法能够进行对比

  • iterator& find_if(iterator start, iterator end, function)：按条件查找元素

    其中的 function 是一个一元谓词

  • iterator& adjacent_find(iterator start, iterator end)：查找相邻的重复元素

    找到的场合返回那组相邻元素中靠前元素的位置，否则返回 end

  • bool binary_search(iterator start, iterator end, T& ele)：用二分法查找元素是否存在

    找到的场合返回 true，否则返回 false。

    注意：该方法不能在无序序列中使用。在无序序列查找的场合，结果未知

  • int count(iterator start, iterator end, T& ele)：统计元素个数

  • int count_if(iterator start, iterator end, function)：按条件统计个数

    其中的 function 是一个一元谓词

11.3.3 常用排序算法

  • sort(iterator start, iterator end, consumer)：排序

    其中，consumer 是一个二元谓词。也可以不写，那个场合，默认使用内建函数的 less 仿函数

  • random_shuffle(iterator start, iterator end)：打乱

  • merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)：容器元素合并

    把 [beg1, end1) 和 [beg2, end2) 的元素合并，并放入 dest 位置

    源容器必须是有序的。

  • reserve(iterator start, iterator end)：反转

11.3.4 常用拷贝和替换算法

  • copy(iterator beg1, iterator end1, iterator dest)：拷贝

  • replace(iterator beg, iterator end, T& old, T& new)：替换

    将范围内的 old 元素替换为 new

  • replace_ifreplace(iterator beg, iterator end, consumer, T& new)：替换满足条件的元素

    其中 consumer 是一个一元谓词

  • swap(container c1, container c2)：互换两个容器的元素

    两种容器必须是同一类型

11.3.5 常用算术生成算法

算术生成算法是小型算法，其头文件为 include<numeric>

  • accumulate(iterator beg, iterator end, value)：计算容器元素累计总和

    计算 [beg, end) 范围的元素累加结果。累加初始值为 value

  • fill(iterator beg, iterator end, value)：向容器中填充元素

    [beg, end) 范围的元素变成 value

11.3.6 常用集合算法

  • set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)：求两个容器的交集

    将在 [beg1, end1) 和 [beg2, end2) 两个范围内都出现过的元素，放入 dest 位置

    不会出现多次匹配到另一范围内的某个单一元素。

    两个容器必须是有序排列的

  • set_union：求两个容器的并集

    将 [beg1, end1) 和 [beg2, end2) 两个范围内的元素放入 dest 位置。重复元素只添加一次

  • set_difference：求两个容器的差集

    将 [beg1, end1) 和 [beg2, end2) 两个范围内的元素放入 dest 位置。但是会去除那些重复出现过的元素

C++
#笔记 #C++
<C++>11 STL
https://i-melody.github.io/2022/05/05/C++/入门阶段/11 STL/
作者
Melody
发布于
2022年5月5日
许可协议