Lecture 3:STL 与泛型编程
来源:
lec3_part2.pdf,共 32 页。本文按课件教学顺序整理,重点解释知识点、代码含义与实现方法。页码均指 PDF 页码。示例使用 C++;按本文写法组合运行时建议使用 C++14 或更新标准,因为链表结点示例同时使用了默认成员初始化与聚合初始化。课件中的明显代码笔误已修正,见文末说明。
泛型编程与 STL(第 1—5 页)
泛型编程的目标是让一份实现适用于多种类型和数据结构,减少重复代码。 本章用模板表示类型,用迭代器表示遍历位置,把算法需要的操作统一起来。
STL(Standard Template Library,标准模板库)在本章中包含四个部分:
| 部分 | 作用 | 课件中的例子 |
|---|---|---|
| 容器 | 保存和组织元素 | vector<int>、list<int> |
| 迭代器 | 表示元素位置,支持访问与移动 | begin()、end() 返回的位置 |
| 算法 | 对指定范围执行操作 | find、sort |
| 函数对象 | 提供可调用的操作或规则 | greater<int>{} |
课件提出三种独立关系:
- 数据结构与元素类型分离。
vector<int>与vector<double>采用相同的容器模板,保存不同类型的元素。 - 算法与数据结构分离。
find通过迭代器遍历,能够查找vector和list中的元素。 - 算法与元素类型分离。 函数模板根据实际类型生成相应的函数,但元素必须支持算法用到的操作。
| |
这里需要 <vector> 和 <algorithm>。values.begin() 与 values.end() 把待排序的范围交给算法。
| |
std::greater<int>{} 创建一个比较对象,比较规则相当于 a > b,需要 <functional>。{} 表示创建对象。
算法的通用性受迭代器能力限制。 std::sort 需要随机访问迭代器,即能直接跳到相隔若干元素的位置。vector 支持这类操作,list 不支持,所以链表排序使用成员函数:
| |
从指针到迭代器:逐步实现 my_find(第 6—14 页)
这一部分依次放宽查找函数的限制:先查找 vector<int>,再支持不同元素类型,然后支持数组,最后支持链表。每一步都围绕同一件事展开:怎样表达要查找的元素范围。
在 vector<int> 中查找(第 7 页)
要求:找到目标时返回元素地址,找不到时返回 nullptr。
| |
| 写法 | 含义 |
|---|---|
const std::vector<int>& vec | 用引用接收原容器,避免复制;函数不能通过它修改元素 |
vec[i] | 访问下标为 i 的元素 |
&vec[i] | 取得该元素的地址 |
const int* | 指向整数的指针,不能通过该指针修改整数 |
nullptr | 空指针,表示没有找到 |
查找按顺序进行,遇到第一个匹配元素就返回。若有 N 个元素,最坏需要检查全部元素,时间复杂度为 O(N);额外空间为 O(1)。
用函数模板支持不同元素类型(第 8 页)
把固定的 int 换成模板参数 T:
| |
template <typename T> 声明类型参数。传入 vector<int> 时,T 可推导为 int;传入 vector<string> 时,T 可推导为 string。const T& value 避免为传参复制目标对象。
模板仍有使用条件:vec[i] == value 必须合法。 自定义类型若没有可用的相等比较,这个查找函数就不能用于该类型。这个版本还要求能取得元素地址,适用于普通 vector<T>;vector<bool> 的特殊实现不适用这一指针接口。
这里有两处 typename,含义需要分清:
template <typename T>中的typename声明一个类型参数。typename std::vector<T>::size_type中的typename告诉编译器,这个依赖于T的成员名称表示类型。
此时函数已经支持不同元素类型,但参数仍固定为 vector<T>。
用“首地址 + 元素数量”支持数组(第 9—10 页)
数组与普通 vector<T> 都使用连续存储,可以统一提供首地址和元素数量:
| |
| |
data() 提供连续元素区的首地址。函数只按地址和数量遍历,不需要知道数据来自数组还是 vector。
上面的 int size 沿用课件写法;调用者必须提供正确数量,且转换到 int 时不能超出其表示范围。这个版本仍依赖连续存储,不能按相同方式遍历链表。
用两个指针表示左闭右开区间(第 11 页)
把元素数量换成尾后指针,形成范围 [first, last):
first指向范围内第一个元素。last指向最后一个元素之后的位置,不属于范围。first == last表示空范围。
| |
| |
*first 读取当前位置的元素,++first 移到下一个元素。a + 3 是合法的尾后位置,但不能解引用。
从这一版本开始,查找失败返回 last。 调用者先比较结果与尾后位置,确认找到后再解引用。尾后位置通常并非空指针。
用 begin() 和 end() 安全取得范围(第 12—13 页)
课件指出下面的取址方式有问题:
| |
operator[] 要求下标小于 size()。空容器没有第 0 个元素;words[words.size()] 也超出了有效下标范围。仅仅取地址不能使越界访问合法。
容器提供统一的范围接口:
| |
空容器的 begin() == end(),查找循环不会访问元素,结果直接等于 end()。
auto 让编译器根据右侧表达式推导变量类型,变量本身仍有确定类型。
| 取得范围的方式 | 适用对象 |
|---|---|
c.begin()、c.end() | 提供这些成员函数的容器 |
std::begin(c)、std::end(c) | 标准容器,也支持内置数组 |
| |
非成员形式的 std::begin 和 std::end 需要 <iterator>。对内置数组,它们得到首指针和尾后指针。标准接口没有要求空容器的迭代器必须是空指针。
链表为什么需要迭代器(第 14 页)
链表结点的位置不连续,不能靠地址加一找到下一个结点。
| 动作 | 数组或普通 vector 的指针 | 单链表内部的结点指针 |
|---|---|---|
| 读取元素 | *p | p->value |
| 前进一个位置 | ++p | p = p->next |
| 判断是否到达边界 | 比较指针 | 比较结点位置 |
迭代器把不同结构的遍历方式封装起来。 算法统一使用 *it 读取元素,用 ++it 前进,用 it != last 判断范围。具体怎样前进,由迭代器内部实现。
迭代器的实现与使用(第 15—25 页)
运算符重载与指针式访问(第 15 页)
C++ 允许类定义 operator* 和 operator->,让对象支持 *对象 与 对象->成员 的写法。这叫运算符重载。
课件先用智能指针说明这种语法:
| |
需要 <memory>。unique_ptr 拥有对象,销毁时负责释放对象;普通容器迭代器提供元素访问,销毁迭代器不会删除容器结点。
课件中自写的 Unique_ptr 只展示指针成员、析构函数及两个访问运算符。它没有完整处理复制与移动,不能直接当作完整智能指针使用。实际管理对象时使用标准库 std::unique_ptr。课件提到的旧类型 auto_ptr 已在 C++11 中弃用,并在 C++17 中移除。
实现单链表结点与迭代器(第 16—17 页)
下面合并课件分散在两页的实现:
| |
ptr_ 保存当前结点地址,Node<T> 保存元素和后继指针。在 Node 类定义内部,Node* 指向当前模板实例对应的结点类型。
| 成员 | 实现作用 | 返回值的含义 |
|---|---|---|
operator*() | 读取 ptr_->value | T& 引用原元素,允许修改 |
operator++() | 沿 next 前进 | 返回更新后的迭代器自身的引用 |
operator++(int) | 保存旧位置,再前进 | 返回前进之前的迭代器副本 |
operator== | 比较结点地址 | 判断两个迭代器是否指向同一位置 |
operator!= | 对相等判断取反 | 判断位置是否不同 |
后置 ++ 的参数 int 用来区分重载形式,使用 it++ 时不需要显式传参。
this 是指向当前迭代器对象的指针,*this 是当前迭代器对象。因此,ListIter old = *this; 复制迭代器,++(*this) 调用前置递增。代码中的 *this 与 *it 所在层次不同:前者取得当前对象,后者调用迭代器的解引用运算符取得元素。
operator*() const 中的 const 表示该函数不修改迭代器自身的位置;由于返回类型是 T&,仍可通过它修改元素。这与只读迭代器返回只读元素访问不同。
此模型用内部的 nullptr 表示结束。到达结束后,既不能解引用,也不能继续递增。它是教学用的最小实现,未包含完整标准迭代器的全部定义。
组织链表范围并查找(第 18 页)
| |
查找函数使用下文第 21 页的通用版本。结点顺序为 n1 → n2 → n3 → nullptr,范围仍写为 [first, last)。这些结点必须在迭代器使用期间保持有效。
本章采用 *it 返回元素值的引用。这里的自定义迭代器用于说明查找所需操作;若要直接交给标准库算法,还需满足相应算法与标准库实现对迭代器的完整要求。
容器内部的迭代器类型(第 19 页)
容器把自己的迭代器类型命名为 iterator,再提供取得首尾位置的函数:
| |
using iterator = ListIter<T>; 给已有类型起别名,也可写为课件中的 typedef ListIter<T> iterator;。这里仅展示类型别名与首尾接口,没有实现完整链表的插入、删除或资源管理。
| |
:: 表示在指定作用域中查找名称。std::vector<int>::iterator 就是 vector<int> 内部定义的迭代器类型。不同容器可用相同的名称提供各自不同的实现。
普通、只读与反向迭代器(第 20 页)
| 类型 | 能否通过它修改元素 | 遍历方向 | 常用范围接口 |
|---|---|---|---|
iterator | 本章的 vector、list 可以 | 正向 | begin()、end() |
const_iterator | 不可以 | 正向,仍能递增 | cbegin()、cend() |
reverse_iterator | 本章的可修改序列可以 | 反向 | rbegin()、rend() |
| |
*it 取得字符串,it->size() 调用该字符串的成员函数。对支持箭头访问的迭代器,可把后者理解为 (*it).size()。
const_iterator 限制元素修改,不限制迭代器前进。 const iterator 则限制迭代器对象自身被修改,这两个类型含义不同。set 等容器还会限制对键的修改,不能把表中的元素可修改性推广到所有容器。
最终版本:基于迭代器的通用查找(第 21—22 页)
| |
Iter 表示遍历位置的类型,T 表示查找值的类型。这个实现只要求能复制遍历位置、比较位置、读取元素、递增位置,以及比较元素与目标值。
| |
这三个调用共用同一份函数模板。数组以原生指针遍历,另外两个容器使用各自的迭代器。由于 1024 不存在,返回值分别等于数组尾后指针、v.end() 和 l.end()。
参数 first 按值传入,函数内部前进的是迭代器副本,不会改变调用者原先保存的起始位置。算法返回第一个匹配位置;最坏时间为 O(N),额外空间为 O(1)。
迭代器的类型兼容与有效范围(第 23 页)
| |
需要同时检查类型与所属范围:
vector<int>::iterator与vector<string>::iterator的元素类型不同,不能直接赋值。vector<int>::iterator与list<int>::iterator来自不同容器类型,不能直接赋值。vector<int>::iterator不保证就是int*,不能依赖它与data()的返回值直接互相赋值。- 即使迭代器类型相同,也不能据此把不同容器的首尾位置拼成有效范围。比较、求距离等操作须满足其范围要求。
vector 的遍历方法(第 24—25 页)
需要下标时,使用容器的大小类型:
| |
size_type 用于表示容器大小。直接用 int 与 size() 比较可能产生有符号和无符号类型不一致的问题,也可能无法表示较大容器的大小。v[i] 不做越界检查。
需要迭代器位置时:
| |
只需逐个处理元素时,使用 C++11 的范围 for:
| |
value_type 表示容器元素类型,例如 std::vector<int>::value_type 就是 int。课件中的字符串容器也可用 std::vector<std::string>::value_type 声明循环变量。
遍历期间若插入或删除元素,必须考虑迭代器是否失效:原位置可能因存储变化或元素删除而不能继续使用。循环语法正确并不能保证迭代器一直有效。
标准 STL 容器(第 26—30 页)
容器分类与常用接口(第 27 页)
| 类别 | 本章涉及的容器 | 元素组织方式 |
|---|---|---|
| 顺序容器 | vector、list、deque | 顺序由位置及插入删除操作决定 |
| 有序关联容器 | map、set、multimap、multiset | 按键的比较规则组织 |
本章归纳的常用接口包括:== 和 != 比较容器内容,= 赋值,empty() 判断是否为空,size() 获取元素数量,begin() 与 end() 获取范围,insert() 插入,erase() 删除,clear() 清空。
各容器的具体参数与操作代价不同。对非空容器才能直接读取 front() 或 back(),对空容器也不能直接执行弹出操作。
三种顺序容器的存储与选择(第 28 页)
先读复杂度记号:O(1) 表示操作量不随元素数量线性增长;O(N) 表示可能需要处理与元素数量成比例的元素。
| 容器 | 存储方式 | 随机访问 | 首尾操作 | 中间插入或删除 |
|---|---|---|---|---|
vector | 连续存储 | O(1),支持下标 | 尾部 push_back 均摊 O(1),pop_back 为 O(1) | O(N),可能移动后续元素 |
list | 双向链表 | 不支持下标,定位一般为 O(N) | 两端插入删除为 O(1) | 已有位置时,单个元素插入删除为 O(1) |
deque | 通常采用分段存储 | O(1),支持下标 | 两端插入删除为 O(1) | O(N) |
vector 的“均摊”表示把多次追加的总成本平均分摊后,每次为常数级。一次追加若触发扩容,仍可能移动已有元素,花费 O(N)。
list 的常数时间插入删除以已经拿到位置为前提;若需要先查找该位置,还要计入遍历时间。第 16 页的单链表用于演示迭代器,标准库 std::list 是双向链表。
需要下标访问、主要从尾部追加时可选 vector;已知位置且经常插入删除时可考虑 list;需要从两端操作且保留下标访问时可选 deque。课件据此指出:vector 可实现栈式操作,deque 可实现队列式操作。
构造与初始化(第 29 页)
| |
范围构造函数只需要一对合适的迭代器,来源可以是数组或其他兼容范围。复制构造创建独立的新容器;修改本例 e 中的字符串不会修改 c 中对应的字符串。
| 操作 | 含义 | vector | deque、list |
|---|---|---|---|
push_back(x) | 尾部插入 | 支持 | 支持 |
pop_back() | 删除尾部元素,不返回该元素 | 支持 | 支持 |
front()、back() | 访问首尾元素 | 支持 | 支持 |
push_front(x) | 头部插入 | 无此成员函数 | 支持 |
pop_front() | 删除头部元素 | 无此成员函数 | 支持 |
按位置插入与删除(第 30 页)
以下接口针对本节的顺序容器。insert 在 pos 之前插入;erase(first, last) 删除左闭右开范围。
| |
| |
vector 的迭代器支持 + 2,list 的迭代器需要逐步递增。erase(pos) 要求 pos 指向有效元素,不能用 end();在尾部插入时则可以把 end() 作为插入位置。
本节这些 insert 重载在现代 C++ 中返回插入位置;插入多个元素时返回第一个插入元素的位置,空插入返回 pos。erase 返回删除范围之后的位置,删除到末尾时返回新的 end()。
补充一个与返回值直接相关的实现方法:遍历中删除元素时,用 erase 的返回值继续遍历。
| |
删除分支不再额外递增。对 vector,删除位置及其后的迭代器可能失效,因此不能继续使用删除前保存的这些位置。
关联容器与 map(第 31—32 页)
键、值与重复规则(第 31 页)
关联容器按键查找。map 保存键与对应值,set 只保存键。
| 容器 | 保存的内容 | 是否允许等价键重复 |
|---|---|---|
map<Key, T> | 键值对 | 不允许 |
multimap<Key, T> | 键值对 | 允许 |
set<Key> | 键 | 不允许 |
multiset<Key> | 键 | 允许 |
这些有序关联容器通常使用平衡搜索树实现,查找的时间复杂度为 O(log N),所需比较次数随元素数量的增长较慢。
键是否等价由比较规则决定。 默认按小于关系组织;若比较函数为 comp,当 !comp(a, b) && !comp(b, a) 时,认为两个键等价。判断不必直接调用 operator==。
map<Key, T> 的元素类型为 std::pair<const Key, T>。pair 把两个值组成一个对象:
first是键,带const,不能通过迭代器直接修改。second是对应值,可通过可修改迭代器更新。
键决定元素在容器中的组织位置,所以不能直接修改键。
定义 map、访问键值(第 32 页)
| |
Word["Hello"] 根据字符串键访问对应整数。键存在时返回该值的引用;键不存在时插入新元素。这里对应值是 int,新值初始化为 0,随后再被赋值为 1。
begin() 指向比较顺序中的第一个元素,不能把它当作最早插入的元素。
用 find() 或 count() 判断键是否存在(第 32 页)
课件提醒下面的判断有副作用:
| |
它既不能准确表达“键是否存在”,又会在键缺失时插入一个新元素。
需要找到元素后访问它时,使用成员 find():
| |
只需要判断是否存在时,可以使用 count():
| |
| 操作 | 返回结果 | 键不存在时是否插入 |
|---|---|---|
Word[key] | 对应值的引用 | 是 |
Word.find(key) | 元素迭代器,未找到则为 end() | 否 |
Word.count(key) | 等价键的数量 | 否 |
map 和 set 的键唯一,count() 只可能返回 0 或 1;multimap 和 multiset 的结果可能大于 1。对多重容器,count() 还要计入匹配元素数量,不能把它的全部成本都按单次树查找计算。
注意两个 find 的接口:std::find(first, last, value) 在范围中逐个比较元素;Word.find(key) 根据键执行关联容器查找。对 map 查键,使用成员 find。
课件代码修正与学习边界
本文保留教学推进顺序,代码做了以下必要修正:
| PDF 页码 | 原代码问题 | 本文处理 |
|---|---|---|
| 第 7 页 | 循环变量 iX 未声明 | 声明为容器的 size_type |
| 第 8 页 | 页脚对 typename 的解释与示例所在位置不对应 | 区分类型参数声明与依赖类型名称两种用途 |
| 第 11 页 | 循环体起始括号误写 | 修正为配对的 {} |
| 第 18 页 | 两段示例若直接拼接,会重复定义 auto it | 第二次查找改为给已有 it 赋值 |
| 第 21 页 | 返回类型写成未声明的 Iterator,函数起始括号缺失 | 返回类型统一为 Iter,补全括号 |
| 第 24—25 页 | 示例中的 T 未在具体代码中声明 | 按具体容器写类型,或使用 auto |
| 第 29 页 | 范围构造语句缺分号,部分字符串使用排版引号 | 补全分号,统一为代码使用的英文引号 |
文中的 my_find 演化版本是依次替换的阶段示例,学习时可分别使用;同名模板的多个阶段不必全部放进同一程序。ListIter 与 List 是解释机制的简化模型。迭代器失效、边界检查及智能指针完整性等补充用于说明实现条件;本章没有系统展开完整迭代器分类、分配器或 STL 源码实现。
复习重点
- 能写出最终的
my_find,说明*first、++first、first != last各自承担的操作。 - 理解
[first, last),牢记查找失败返回尾后位置,解引用前先判断。 - 能解释模板如何统一元素类型,迭代器如何统一遍历方式。
- 能区分前置和后置
++,以及iterator与const_iterator。 - 能按是否复制、是否修改元素,选择
auto、auto&或const auto&。 - 能结合存储方式说明三种顺序容器的操作代价,特别是
vector的均摊追加和list的已知位置条件。 - 能正确使用
insert与erase,利用删除操作的返回值继续遍历。 - 能区分
map的first与second,以及operator[]、成员find和count的作用与副作用。