C++ 新经典笔记 - 这篇文章属于一个选集。

P18 STL标准模板库大局观

知识点
#

19.1 STL 总述、发展史、组成与数据结构谈
#

@ STL基础概念图 ![[白板/P59 STL组成结构.canvas|STL组成结构]]

19.1.1 几个概念与推荐书籍
#

[!tip] STL相关概念
C++标准库：安装C++编译器后自带，提供各种可复用功能（如 vector）
标准模板库（STL）：C++标准库的核心组成部分，包含在标准库中
泛型编程：使用模板为主要编程手段，STL就是用泛型编程方式编写的库

& 推荐书籍：《C++标准库》（字典式查阅）、《STL源码剖析》（侯捷）

19.1.2 算法和数据结构谈
#

[!tip] 数据结构基础
栈：后进先出（LIFO），如上公交车
队列：先进先出（FIFO），如排队买饭
链表：每个节点有数据部分和 next 指针，多个节点串在一起
树、图、散列表：了解基本概念即可
==STL内部使用树、哈希表等数据结构，但程序员不需要关心这些==

! 90%的开发者不需要深入学习红黑树左旋右旋等细节

19.1.3 STL 发展史和各个版本
#

[!tip] STL版本
HP STL：惠普STL，所有STL实现版本的始祖
SGI STL：Linux下的GNU C++（gcc、g++）使用
P.J. Plauger STL：Visual C++（Visual Studio）使用

19.1.4 标准库的使用说明
#

[!tip] 标准库使用
所有标识符定义在 std 命名空间内：using namespace std;
头文件无扩展名：#include <iostream>、#include <string>
C语言头文件加 c 前缀：#include <cstdlib>（对应 <stdlib.h>）

19.1.5 STL 的组成部分
#

[!tip] STL五大组成部分
容器：保存数据，管理元素（如 vector、map、list）
迭代器：遍历/访问容器中的元素，类似指针
算法：STL提供的函数，如查找（find）、排序（sort）、复制（copy）
分配器：内存分配器，服务于容器，一般使用默认分配器
其他：适配器、仿函数（函数对象）等

19.2 容器分类与 array、vector 容器精解
#

@ 容器分类图 ![[白板/P59 STL组成结构.canvas|STL组成结构]]

19.2.1 容器的分类
#

[!tip] 容器三大分类
顺序容器：元素放进去时排在哪里，就在哪里
array、vector、deque、list、forward_list
关联容器：每个元素是键值对，通过 key 找 value 特别快
内部用树（红黑树）实现
set、map、multiset、multimap
无序容器（C++11）：元素位置不重要，内部用哈希表实现
unordered_set、unordered_multiset、unordered_map、unordered_multimap

[!tip] 哈希表工作原理
有多个篮子（桶），元素通过算法计算后挂到对应篮子上
元素个数 >= 篮子个数时，扩充篮子数量（如2倍），重新分配元素
同一篮子上挂的元素越多，查找效率越低

19.2.2 容器的说明和简单应用
#

array 容器
#

[!tip] array容器
顺序容器，固定大小数组
空间连续，大小固定，不能增加
元素之间紧挨着（地址间隔等于元素大小）
#include <array>
array<string, 5> mystring = {"1", "Love", "China"};
cout << mystring.size() << endl;  // 5

vector 容器
#

[!tip] vector容器特点
顺序容器，一端（尾端）开口
尾端插入/删除快，中间插入/删除慢（需移动元素）
内存空间连续
有 size()（元素数量）和 capacity()（空间容量）

! capacity >= size，空间增长时会重新分配内存，导致元素搬迁

[!tip] vector效率陷阱
频繁插入元素时，capacity 增长导致：
老元素析构
新内存中重新构造
效率极低
解决方案：预先预留空间
vector<A> myveca;
myveca.reserve(10);  // 预留10个空间

[!tip] vector删除/插入元素
erase()：删除元素，后续元素往前移动（析构一次）
insert()：插入元素，后续元素往后移动（析构+重新构造）

19.3 容器的说明和简单应用例续
#

19.3.1 deque 和 stack
#

[!tip] deque容器
双端队列（双向开口），动态数组
头部和尾部插入/删除都快
中间插入/删除效率低
==分段连续内存==（每段内存连续，整体不连续）

[!tip] stack容器
栈/堆栈，后进先出（LIFO）
只有一端开口，只支持栈顶操作
不支持中间插入/删除（不同于 vector）
deque 包含 stack 功能

19.3.2 queue
#

[!tip] queue容器
普通队列，先进先出（FIFO）
元素从一端入，从另一端出
deque 也包含 queue 功能

19.3.3 list
#

[!tip] list容器
双向链表，内存不连续
任意位置插入/删除非常快（只需改变指针）
查找效率不高（需沿链逐个查找）
不支持高效随机存取

[!tip] vector vs list（面试常考）
特性 vector list
内存连续不连续
插入/删除低效高效
随机存取高效低效
内存不足时重新分配+搬迁无此问题

特性	`vector`	`list`
内存	连续	不连续
插入/删除	低效	高效
随机存取	高效	低效
内存不足时	重新分配+搬迁	无此问题

19.3.4 其他容器
#

[!tip] forward_list容器
C++11新增，单向链表
比 list 少一个方向的指针，节省4字节
只有 push_front，适合往前头插入

[!tip] map容器
关联容器，内部用红黑树
每个元素是键值对（key/value）
通过 key 查找 value 极快
key 不允许重复（重复插入无效）
key 可重复时用 multimap
#include <map>
map<int, string> mymap;
mymap.insert(std::make_pair(1, "老王"));
mymap.insert(pair<int, string>(3, "老赵"));
auto iter = mymap.find(3);  // 查找key为3的元素

[!tip] set容器
关联容器，每个元素就是一个 value
元素值不允许重复
值可重复时用 multiset
插入时容器自动安排位置

[!tip] unordered_set等无序容器
C++11新增，内部用哈希表
unordered_map、unordered_set：键/值不允许重复
unordered_multimap、unordered_multiset：允许重复
bucket_count()：篮子数量
元素超过篮子数量时，篮子数量会扩充

19.4 分配器简介、使用与工作原理说
#

@ 分配器图 ![[白板/P59 STL组成结构.canvas|STL组成结构]]

19.4.1 分配器简介
#

[!tip] 分配器概念
内存分配器：服务于容器，为容器中的元素分配内存
默认分配器：std::allocator<T>
vector<int> 等价于 vector<int, std::allocator<int>>
==引入分配器的主要目的：减少 malloc 调用次数，减少内存浪费==

! 标准库的默认 allocator 底层可能直接调用 malloc，未使用内存池技术

19.4.2 分配器的使用
#

[!tip] 分配器使用范例

#include <memory>
allocator<int> aalloc;
int *p = aalloc.allocate(3);  // 分配3个int的原始内存
int *q = p;
*q = 1; q++;
*q = 2; q++;
*q = 3;
aalloc.deallocate(p, 3);  // 释放时需记住分配了多少

! 分配器一般不直接使用，用 new/delete 更方便

19.4.3 其他的分配器与原理说
#

[!tip] 内存池分配器原理
使用多个内存池，不同编号对应不同大小内存块
1号针对8字节，2号针对16字节…
申请7字节时，往8字节靠拢，从1号分配
一次分配一大块，小块分配给程序员
==减少 malloc 调用，减少内存浪费==

! 分配器申请的内存很难真正归还给操作系统（除非整块全部回收）

19.5 迭代器的概念和分类
#

@ 迭代器分类图 ![[白板/P60 迭代器与算法.canvas|迭代器与算法]]

19.5.1 迭代器基本概念
#

[!tip] 迭代器概念
迭代器：可遍历STL容器全部或部分元素的对象
行为类似于指针的对象
由容器提供，表现容器中的某一个位置
*iter 读取迭代器指向的内容

[!tip] 迭代器经典用法

vector<int> iv {100, 200, 300};
for (vector<int>::iterator iter = iv.begin(); iter != iv.end(); ++iter)
    cout << *iter << endl;

19.5.2 迭代器的分类
#

[!tip] 迭代器五大分类
输出型迭代器（output_iterator_tag）：向前写入
输入型迭代器（input_iterator_tag）：向前读取一次
前向迭代器（forward_iterator_tag）：向前读取/写入
双向迭代器（bidirectional_iterator_tag）：向前和向后读取
随机访问迭代器（random_access_iterator_tag）：随机读取，可跳跃多个元素

[!tip] 迭代器分类继承关系

output_iterator_tag（最低）
input_iterator_tag
forward_iterator_tag
bidirectional_iterator_tag
random_access_iterator_tag（最高）

[!tip] 各容器支持的迭代器类型
迭代器类型容器
随机访问 array、vector、deque、string、C风格数组
双向 list、set、multiset、map、multimap
前向 forward_list、unordered_*容器
输入 istream
输出 ostream

迭代器类型	容器
随机访问	`array`、`vector`、`deque`、`string`、C风格数组
双向	`list`、`set`、`multiset`、`map`、`multimap`
前向	`forward_list`、`unordered_*`容器
输入	`istream`
输出	`ostream`

! stack、queue 不提供迭代器（后进先出/先进先出，不需要遍历）

[!tip] 随机访问迭代器特点
支持最多操作：iter[n]、iter+=n、iter-=n、iter+n、iter-n
可计算距离：iter1 - iter2
支持关系运算：iter1 < iter2、iter1 > iter2
支持随机访问的容器多数内存连续

19.6 算法简介、内部处理与使用范例
#

@ 算法图 ![[白板/P60 迭代器与算法.canvas|迭代器与算法]]

19.6.1 算法简介
#

[!tip] 算法概念
算法：理解为函数模板，全局函数
不针对某个容器，对大部分容器都适用
参数一般是迭代器，表示元素区间
区间是==前闭后开== [begin(), end())

[!tip] 前闭后开区间的好处
判断迭代器等于 end() 表示迭代结束
begin() == end() 表示空区间

! 算法违背了面向对象封装性，但增加了灵活性

19.6.2 算法内部处理
#

[!tip] 算法内部根据迭代器类型优化
算法内部拿到迭代器分类，不同种类有不同处理
随机访问迭代器：直接加数字跳转，效率高
前向迭代器：不能执行向后读取操作
==从效率角度考虑不同迭代器的处理方式==

19.6.3 一些典型算法使用范例
#

[!tip] for_each算法
#include <algorithm>
void myfunc(int i) { cout << i << endl; }

vector<int> myvector {10, 20, 30, 40, 50};
for_each(myvector.begin(), myvector.end(), myfunc);
第三个参数是可调用对象（函数、lambda、重载 operator() 的类）

[!tip] find算法

vector<int>::iterator finditer = find(myvector.begin(), myvector.end(), 400);
if (finditer != myvector.end())
    cout << "找到" << endl;

返回迭代器，指向第一个匹配元素

! 容器有同名成员函数时，优先使用成员函数（如 map::find）

[!tip] find_if算法
auto result = find_if(myvector2.begin(), myvector2.end(),
    [](int val) { return val > 15; });
第三个参数是可调用对象，返回 true 时停止遍历

[!tip] sort算法
vector<int> myvector3 {50, 15, 80, 30, 46};
sort(myvector3.begin(), myvector3.end());  // 默认从小到大
sort(myvector3.begin(), myvector3.end(), greater<int>());  // 从大到小
只适用于随机访问迭代器
list 不支持 sort 算法，用 list::sort 成员函数
关联容器不适合排序（位置由容器内部算法决定）

19.7 函数对象回顾、系统函数对象与范例
#

@ 函数对象图 ![[白板/P60 迭代器与算法.canvas|迭代器与算法]]

19.7.1 函数对象/仿函数回顾
#

[!tip] 函数对象形式
函数：void func(int x) {...}
函数对象：重载 operator() 的类对象
class A {
public:
    bool operator()(int i, int j) { return i > j; }
};
lambda表达式：也是一种可调用对象
==调用方式统一：名字(参数列表)==

19.7.2 标准库中定义的函数对象
#

[!tip] 标准库函数对象分类
算术运算类：negate、plus、minus、multiplies、divides、modulus
关系运算类：equal_to、not_equal_to、less、greater、less_equal、greater_equal
逻辑运算类：logical_not、logical_and、logical_or
位运算类：bit_and、bit_or、bit_xor
使用前包含：#include <functional>

[!tip] 函数对象使用范例
cout << plus<int>()(4, 5) << endl;  // 9
plus<int>()：生成临时对象
(4, 5)：调用 operator()，传入两个参数

19.7.3 标准库中定义的函数对象范例
#

[!tip] 使用标准库函数对象排序

sort(myvector3.begin(), myvector3.end(), greater<int>());  // 从大到小
sort(myvector3.begin(), myvector3.end(), less<int>());     // 从小到大

19.8 适配器概念、分类、范例与总结
#

@ 适配器图 ![[白板/P59 STL组成结构.canvas|STL组成结构]]

19.8.1 适配器基本概念
#

[!tip] 适配器概念
适配器：类似于转接头，把既有东西进行适当改造
增加或减少一点东西，成为适配器
分为：容器适配器、算法适配器、迭代器适配器

19.8.2 容器适配器
#

[!tip] 容器适配器
stack：后进先出，是对 deque 的改造（减少一端）
queue：先进先出，是对 deque 的改造（减少一端）
stack 和 queue 归类为容器适配器

19.8.3 算法适配器
#

[!tip] 算法适配器（绑定器）
bind：C++11的绑定器，替代老的 bind1st、bind2nd
可以把函数对象的某些参数绑定固定值
#include <functional>
auto bf = bind(less<int>(), 40, placeholders::_1);
bf(19);  // 等价于 less<int>()(40, 19)，即 40 < 19
placeholders::_1：表示调用时传入的第一个参数

[!tip] bind配合count_if使用

int cishu = count_if(myvector.begin(), myvector.end(),
    bind(less<int>(), 40, placeholders::_1));  // 统计大于40的元素

19.8.4 迭代器适配器
#

[!tip] 迭代器适配器

反向迭代器（reverse_iterator）：反向遍历容器

vector<int> iv = {100, 200, 300};
for (vector<int>::reverse_iterator riter = iv.rbegin(); riter != iv.rend(); riter++)
    cout << *riter << endl;  // 输出 300, 200, 100

19.8.5 总结
#

[!tip] STL组成结构总结

STL组成
├── 容器（顺序、关联、无序）
├── 迭代器（输出、输入、前向、双向、随机访问）
├── 算法（for_each、find、find_if、sort等）
├── 分配器（std::allocator<T>）
└── 其他
    ├── 函数对象（标准库提供：plus、less等）
    ├── 适配器
    │   ├── 容器适配器（stack、queue）
    │   ├── 算法适配器（bind）
    │   └── 迭代器适配器（reverse_iterator）

Reply by Email

C++ 新经典笔记 - 这篇文章属于一个选集。

P16 并发与多线程

P17 内存高级话题

P18 STL标准模板库大局观

P19 高级话题与新标准