STL 与泛型编程

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 中的元素。
  • 算法与元素类型分离。 函数模板根据实际类型生成相应的函数,但元素必须支持算法用到的操作。
1
2
3
std::vector<int> values{3, 1, 4, 2, 5};
std::sort(values.begin(), values.end());
// values:1 2 3 4 5

这里需要 <vector> 和 <algorithm>。values.begin() 与 values.end() 把待排序的范围交给算法。

1
2
std::sort(values.begin(), values.end(), std::greater<int>{});
// values:5 4 3 2 1

std::greater<int>{} 创建一个比较对象,比较规则相当于 a > b,需要 <functional>。{} 表示创建对象。

算法的通用性受迭代器能力限制。 std::sort 需要随机访问迭代器,即能直接跳到相隔若干元素的位置。vector 支持这类操作,list 不支持,所以链表排序使用成员函数:

1
2
std::list<int> l{3, 1, 2};
l.sort(std::greater<int>{});

从指针到迭代器:逐步实现 my_find(第 6—14 页)

这一部分依次放宽查找函数的限制:先查找 vector<int>,再支持不同元素类型,然后支持数组,最后支持链表。每一步都围绕同一件事展开:怎样表达要查找的元素范围。

在 vector<int> 中查找(第 7 页)

要求:找到目标时返回元素地址,找不到时返回 nullptr。

1
2
3
4
5
6
7
8
const int* my_find(const std::vector<int>& vec, int value) {
    for (std::vector<int>::size_type i = 0; i < vec.size(); ++i) {
        if (vec[i] == value) {
            return &vec[i];
        }
    }
    return nullptr;
}
写法含义
const std::vector<int>& vec用引用接收原容器,避免复制;函数不能通过它修改元素
vec[i]访问下标为 i 的元素
&vec[i]取得该元素的地址
const int*指向整数的指针,不能通过该指针修改整数
nullptr空指针,表示没有找到

查找按顺序进行,遇到第一个匹配元素就返回。若有 N 个元素,最坏需要检查全部元素,时间复杂度为 O(N);额外空间为 O(1)。

用函数模板支持不同元素类型(第 8 页)

把固定的 int 换成模板参数 T:

1
2
3
4
5
6
7
8
9
template <typename T>
const T* my_find(const std::vector<T>& vec, const T& value) {
    for (typename std::vector<T>::size_type i = 0; i < vec.size(); ++i) {
        if (vec[i] == value) {
            return &vec[i];
        }
    }
    return nullptr;
}

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> 都使用连续存储,可以统一提供首地址和元素数量:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
template <typename T>
const T* my_find(const T* array, int size, const T& value) {
    if (array == nullptr || size <= 0) {
        return nullptr;
    }
    for (int i = 0; i < size; ++i) {
        if (array[i] == value) {
            return &array[i];
        }
    }
    return nullptr;
}
1
2
3
4
5
int a[] = {1, 2, 3};
const int* p1 = my_find(a, 3, 2);

std::vector<int> v{1, 2, 3};
const int* p2 = my_find(v.data(), static_cast<int>(v.size()), 2);

data() 提供连续元素区的首地址。函数只按地址和数量遍历,不需要知道数据来自数组还是 vector。

上面的 int size 沿用课件写法;调用者必须提供正确数量,且转换到 int 时不能超出其表示范围。这个版本仍依赖连续存储,不能按相同方式遍历链表。

用两个指针表示左闭右开区间(第 11 页)

把元素数量换成尾后指针,形成范围 [first, last):

  • first 指向范围内第一个元素。
  • last 指向最后一个元素之后的位置,不属于范围。
  • first == last 表示空范围。
1
2
3
4
5
6
7
8
9
template <typename T>
const T* my_find(const T* first, const T* last, const T& value) {
    for (; first != last; ++first) {
        if (*first == value) {
            return first;
        }
    }
    return last;
}
1
2
3
4
5
int a[] = {1, 2, 3};
const int* p = my_find(a, a + 3, 2);
if (p != a + 3) {
    std::cout << *p;
}

*first 读取当前位置的元素,++first 移到下一个元素。a + 3 是合法的尾后位置,但不能解引用。

从这一版本开始,查找失败返回 last。 调用者先比较结果与尾后位置,确认找到后再解引用。尾后位置通常并非空指针。

用 begin() 和 end() 安全取得范围(第 12—13 页)

课件指出下面的取址方式有问题:

1
2
3
// 错误写法,不要使用:
// &words[0]
// &words[words.size()]

operator[] 要求下标小于 size()。空容器没有第 0 个元素;words[words.size()] 也超出了有效下标范围。仅仅取地址不能使越界访问合法。

容器提供统一的范围接口:

1
2
3
4
5
6
std::vector<std::string> words;
auto it = std::find(words.begin(), words.end(), std::string("STL"));

if (it != words.end()) {
    std::cout << *it;
}

空容器的 begin() == end(),查找循环不会访问元素,结果直接等于 end()。

auto 让编译器根据右侧表达式推导变量类型,变量本身仍有确定类型。

取得范围的方式适用对象
c.begin()、c.end()提供这些成员函数的容器
std::begin(c)、std::end(c)标准容器,也支持内置数组
1
2
int a[] = {1, 2, 3};
auto p = std::find(std::begin(a), std::end(a), 2);

非成员形式的 std::begin 和 std::end 需要 <iterator>。对内置数组,它们得到首指针和尾后指针。标准接口没有要求空容器的迭代器必须是空指针。

链表为什么需要迭代器(第 14 页)

链表结点的位置不连续,不能靠地址加一找到下一个结点。

动作数组或普通 vector 的指针单链表内部的结点指针
读取元素*pp->value
前进一个位置++pp = p->next
判断是否到达边界比较指针比较结点位置

迭代器把不同结构的遍历方式封装起来。 算法统一使用 *it 读取元素,用 ++it 前进,用 it != last 判断范围。具体怎样前进,由迭代器内部实现。

迭代器的实现与使用(第 15—25 页)

运算符重载与指针式访问(第 15 页)

C++ 允许类定义 operator* 和 operator->,让对象支持 *对象 与 对象->成员 的写法。这叫运算符重载。

课件先用智能指针说明这种语法:

1
2
3
std::unique_ptr<std::string> ps(new std::string("jjhou"));
std::cout << *ps << '\n';         // jjhou
std::cout << ps->size() << '\n'; // 5

需要 <memory>。unique_ptr 拥有对象,销毁时负责释放对象;普通容器迭代器提供元素访问,销毁迭代器不会删除容器结点。

课件中自写的 Unique_ptr 只展示指针成员、析构函数及两个访问运算符。它没有完整处理复制与移动,不能直接当作完整智能指针使用。实际管理对象时使用标准库 std::unique_ptr。课件提到的旧类型 auto_ptr 已在 C++11 中弃用,并在 C++17 中移除。

实现单链表结点与迭代器(第 16—17 页)

下面合并课件分散在两页的实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
template <typename T>
struct Node {
    T value;
    Node* next = nullptr;
};

template <typename T>
class ListIter {
private:
    Node<T>* ptr_ = nullptr;

public:
    ListIter(Node<T>* p = nullptr) : ptr_(p) {}

    T& operator*() const {
        return ptr_->value;
    }

    ListIter& operator++() {
        ptr_ = ptr_->next;
        return *this;
    }

    ListIter operator++(int) {
        ListIter old = *this;
        ++(*this);
        return old;
    }

    bool operator==(const ListIter& other) const {
        return ptr_ == other.ptr_;
    }

    bool operator!=(const ListIter& other) const {
        return !(*this == other);
    }
};

ptr_ 保存当前结点地址,Node<T> 保存元素和后继指针。在 Node 类定义内部,Node* 指向当前模板实例对应的结点类型。

成员实现作用返回值的含义
operator*()读取 ptr_->valueT& 引用原元素,允许修改
operator++()沿 next 前进返回更新后的迭代器自身的引用
operator++(int)保存旧位置,再前进返回前进之前的迭代器副本
operator==比较结点地址判断两个迭代器是否指向同一位置
operator!=对相等判断取反判断位置是否不同

后置 ++ 的参数 int 用来区分重载形式,使用 it++ 时不需要显式传参。

this 是指向当前迭代器对象的指针,*this 是当前迭代器对象。因此,ListIter old = *this; 复制迭代器,++(*this) 调用前置递增。代码中的 *this 与 *it 所在层次不同:前者取得当前对象,后者调用迭代器的解引用运算符取得元素。

operator*() const 中的 const 表示该函数不修改迭代器自身的位置;由于返回类型是 T&,仍可通过它修改元素。这与只读迭代器返回只读元素访问不同。

此模型用内部的 nullptr 表示结束。到达结束后,既不能解引用,也不能继续递增。它是教学用的最小实现,未包含完整标准迭代器的全部定义。

组织链表范围并查找(第 18 页)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
Node<int> n3{3, nullptr};
Node<int> n2{2, &n3};
Node<int> n1{1, &n2};

ListIter<int> first(&n1);
ListIter<int> last; // 内部指针为 nullptr

auto it = my_find(first, last, 3);
if (it != last) {
    std::cout << "found: " << *it << '\n';
}
// found: 3

it = my_find(first, last, 7);
if (it == last) {
    std::cout << "not found\n";
}

查找函数使用下文第 21 页的通用版本。结点顺序为 n1 → n2 → n3 → nullptr,范围仍写为 [first, last)。这些结点必须在迭代器使用期间保持有效。

本章采用 *it 返回元素值的引用。这里的自定义迭代器用于说明查找所需操作;若要直接交给标准库算法,还需满足相应算法与标准库实现对迭代器的完整要求。

容器内部的迭代器类型(第 19 页)

容器把自己的迭代器类型命名为 iterator,再提供取得首尾位置的函数:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
template <typename T>
class List {
    Node<T>* head_ = nullptr;

public:
    using iterator = ListIter<T>;

    iterator begin() {
        return iterator(head_);
    }

    iterator end() {
        return iterator(nullptr);
    }
};

using iterator = ListIter<T>; 给已有类型起别名,也可写为课件中的 typedef ListIter<T> iterator;。这里仅展示类型别名与首尾接口,没有实现完整链表的插入、删除或资源管理。

1
2
std::vector<int>::iterator iv = v.begin();
std::list<int>::iterator il = l.begin();

:: 表示在指定作用域中查找名称。std::vector<int>::iterator 就是 vector<int> 内部定义的迭代器类型。不同容器可用相同的名称提供各自不同的实现。

普通、只读与反向迭代器(第 20 页)

类型能否通过它修改元素遍历方向常用范围接口
iterator本章的 vector、list 可以正向begin()、end()
const_iterator不可以正向,仍能递增cbegin()、cend()
reverse_iterator本章的可修改序列可以反向rbegin()、rend()
1
2
3
4
std::vector<std::string> words{"C++", "STL"};
for (auto it = words.begin(); it != words.end(); ++it) {
    std::cout << *it << ' ' << it->size() << '\n';
}

*it 取得字符串,it->size() 调用该字符串的成员函数。对支持箭头访问的迭代器,可把后者理解为 (*it).size()。

const_iterator 限制元素修改,不限制迭代器前进。 const iterator 则限制迭代器对象自身被修改,这两个类型含义不同。set 等容器还会限制对键的修改,不能把表中的元素可修改性推广到所有容器。

最终版本:基于迭代器的通用查找(第 21—22 页)

1
2
3
4
5
6
7
8
9
template <typename Iter, typename T>
Iter my_find(Iter first, Iter last, const T& value) {
    for (; first != last; ++first) {
        if (*first == value) {
            return first;
        }
    }
    return last;
}

Iter 表示遍历位置的类型,T 表示查找值的类型。这个实现只要求能复制遍历位置、比较位置、读取元素、递增位置,以及比较元素与目标值。

1
2
3
4
5
6
7
int a[] = {1, 1, 2, 3, 5, 8, 13, 21};
std::vector<int> v(std::begin(a), std::end(a));
std::list<int> l(std::begin(a), std::end(a));

auto p  = my_find(std::begin(a), std::end(a), 1024);
auto iv = my_find(v.begin(), v.end(), 1024);
auto il = my_find(l.begin(), l.end(), 1024);

这三个调用共用同一份函数模板。数组以原生指针遍历,另外两个容器使用各自的迭代器。由于 1024 不存在,返回值分别等于数组尾后指针、v.end() 和 l.end()。

参数 first 按值传入,函数内部前进的是迭代器副本,不会改变调用者原先保存的起始位置。算法返回第一个匹配位置;最坏时间为 O(N),额外空间为 O(1)。

迭代器的类型兼容与有效范围(第 23 页)

1
2
3
4
5
std::vector<int> v{1};
std::vector<int>::iterator it = v.begin();
std::vector<int>::const_iterator cit = v.cbegin();
cit = it; // 可以:增加只读限制
// it = cit; // 不可以:不能去掉只读限制

需要同时检查类型与所属范围:

  • vector<int>::iterator 与 vector<string>::iterator 的元素类型不同,不能直接赋值。
  • vector<int>::iterator 与 list<int>::iterator 来自不同容器类型,不能直接赋值。
  • vector<int>::iterator 不保证就是 int*,不能依赖它与 data() 的返回值直接互相赋值。
  • 即使迭代器类型相同,也不能据此把不同容器的首尾位置拼成有效范围。比较、求距离等操作须满足其范围要求。

vector 的遍历方法(第 24—25 页)

需要下标时,使用容器的大小类型:

1
2
3
for (std::vector<int>::size_type i = 0; i < v.size(); ++i) {
    std::cout << v[i];
}

size_type 用于表示容器大小。直接用 int 与 size() 比较可能产生有符号和无符号类型不一致的问题,也可能无法表示较大容器的大小。v[i] 不做越界检查。

需要迭代器位置时:

1
2
3
for (auto it = v.begin(); it != v.end(); ++it) {
    std::cout << *it;
}

只需逐个处理元素时,使用 C++11 的范围 for:

1
2
3
4
5
6
7
8
9
for (auto x : v) {          // 复制当前元素
    // 修改 x 不会修改 v 中对应的 int 元素
}
for (auto& x : v) {         // 引用原元素
    x *= 2;
}
for (const auto& x : v) {   // 只读引用,避免复制
    std::cout << x;
}

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 页)

1
2
3
4
5
6
7
8
std::list<std::string> a;             // 空容器
std::list<std::string> b(1024);       // 1024 个空字符串
std::list<std::string> c(1024, "Hi"); // 1024 个 "Hi"

int values[] = {1, 2, 3, 4, 5, 6};
std::list<int> d(values, values + 6); // 复制范围 [values, values + 6)

std::list<std::string> e(c);          // 复制 c 的全部元素

范围构造函数只需要一对合适的迭代器,来源可以是数组或其他兼容范围。复制构造创建独立的新容器;修改本例 e 中的字符串不会修改 c 中对应的字符串。

操作含义vectordeque、list
push_back(x)尾部插入支持支持
pop_back()删除尾部元素,不返回该元素支持支持
front()、back()访问首尾元素支持支持
push_front(x)头部插入无此成员函数支持
pop_front()删除头部元素无此成员函数支持

按位置插入与删除(第 30 页)

以下接口针对本节的顺序容器。insert 在 pos 之前插入;erase(first, last) 删除左闭右开范围。

1
2
3
4
5
6
c.insert(pos, value);         // 插入一个元素
c.insert(pos, count, value);  // 插入 count 个相同元素
c.insert(pos, first, last);   // 插入另一个范围的元素

c.erase(pos);                // 删除 pos 指向的元素
c.erase(first, last);        // 删除 [first, last)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
std::vector<int> v{1, 2, 3, 4};
auto inserted = v.insert(v.begin() + 2, 99);
// v:1 2 99 3 4;inserted 指向 99

std::list<std::string> l{"A", "B", "C"};
auto pos = l.begin();
++pos;
l.insert(pos, 3, "X");
// l:A X X X B C

std::vector<int> w{1, 2, 3, 4};
auto after = w.erase(w.begin() + 1, w.begin() + 3);
// 删除 2 和 3,w:1 4;after 指向 4

vector 的迭代器支持 + 2,list 的迭代器需要逐步递增。erase(pos) 要求 pos 指向有效元素,不能用 end();在尾部插入时则可以把 end() 作为插入位置。

本节这些 insert 重载在现代 C++ 中返回插入位置;插入多个元素时返回第一个插入元素的位置,空插入返回 pos。erase 返回删除范围之后的位置,删除到末尾时返回新的 end()。

补充一个与返回值直接相关的实现方法:遍历中删除元素时,用 erase 的返回值继续遍历。

1
2
3
4
5
6
7
for (auto it = w.begin(); it != w.end(); ) {
    if (*it == 4) {
        it = w.erase(it);
    } else {
        ++it;
    }
}

删除分支不再额外递增。对 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 页)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
#include <map>
#include <string>
#include <iostream>

std::map<std::string, int> Word;
Word["Hello"] = 1;

if (!Word.empty()) {
    auto it = Word.begin();
    std::cout << it->first << "---" << it->second << '\n';
}
// 本例输出:Hello---1

Word["Hello"] 根据字符串键访问对应整数。键存在时返回该值的引用;键不存在时插入新元素。这里对应值是 int,新值初始化为 0,随后再被赋值为 1。

begin() 指向比较顺序中的第一个元素,不能把它当作最早插入的元素。

用 find() 或 count() 判断键是否存在(第 32 页)

课件提醒下面的判断有副作用:

1
2
3
if (1 != Word["Hello"]) {
    // 判断的是对应值是否不等于 1
}

它既不能准确表达“键是否存在”,又会在键缺失时插入一个新元素。

需要找到元素后访问它时,使用成员 find():

1
2
3
4
auto it = Word.find("Hello");
if (it != Word.end()) {
    std::cout << it->second;
}

只需要判断是否存在时,可以使用 count():

1
2
3
if (Word.count("Hello") != 0) {
    std::cout << "Found it!\n";
}
操作返回结果键不存在时是否插入
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 的作用与副作用。
使用 Hugo 构建
主题 Stack 由 Jimmy 设计