Chapter 11 STL¶

1 Basic Ideas¶

Collection：可以保存任意数量其他对象的对象
STL（Standard Template Library）：是 ISO Standard C++ Library 的一部分，提供 C++ 中常用的数据结构和算法

Why should I use STL?

降低开发时间：常用数据结构已经写好、调试好
提高可读性：代码能直接表达用什么结构做什么事
更稳健：很多 STL 容器会自动扩容
可移植、易维护、容易使用

C++ Standard Library

pair
容器：vector、deque、list、set、map
基本算法：sort、search、copy
标准库标识符位于 std 命名空间中

STL 包含以下三个核心部分：

Containers：保存对象的数据结构
Algorithms：作用在一段元素范围上的算法
Iterators：连接容器和算法的位置对象

Top 3 data structures

map：任意 key 类型映射到任意 value 类型，按 key 自动有序
vector：类似 C 数组，但可以自动扩展
list：双向链表

Sequential containers

vector：动态数组
deque：双端队列
list：双向链表
forward_list：单向链表
array：定长数组
string：字符序列

2 vector¶

vector 是泛型容器，声明时既要说明容器类型，也要说明元素类型（vector<string> notes;）
vector 会自动管理容量，元素数量可以增长
vector 自己保存当前元素个数，可以通过 size() 获取
vector 会保持元素插入顺序

示例：vector 基本用法

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 定义一个存储 int 类型数据的空 vector 动态数组，变量名为 x
    vector<int> x;
    for (int a = 0; a < 100; a++) {
        // 将变量 a 的值添加到 vector 数组 x 的末尾
        x.push_back(a);
    }

    // 定义 vector<int> 类型的迭代器 p，迭代器作用类似指针，用于遍历 vector 元素
    vector<int>::iterator p;
    for (p = x.begin(); p < x.end(); p++) {
        // *p 解引用迭代器，获取 p 指向的元素值，输出该值并加一个空格
        cout << *p << " ";
    }
    return 0;
}

Basic vector operations

构造：vector<Elem> c;、vector<Elem> c1(c2);
大小：V.size()、V.empty()
比较：==、!=、<、>、<=、>=
交换：v1.swap(v2)
迭代器：V.begin()、V.end()
访问：V.at(index)、V[index]、V.front()、V.back()
增删查：V.push_back(e)、V.pop_back()、V.insert(pos, e)、V.erase(pos)、V.clear()、find(first, last, item)

Two ways to use vector

Preallocate

vector<int> v(100);
v[80] = 1;   // ok
v[200] = 1;  // error

Grow tail

vector<int> v2;
int i;
while (cin >> i) {
    v2.push_back(i);
}

如果能预估元素数量，应尽量提前保留空间，减少反复扩容
尽量避免不必要的对象拷贝
容器会自动管理内存，但不代表所有操作都是零成本

3 list¶

list 是双向链表，和 vector 一样也有构造、比较、首尾访问等概念
list 支持在首尾插入和删除：push_back()、push_front()、pop_back()、pop_front()
list 还可用 remove() 删除匹配元素

list 不是随机访问容器

遍历 vector 可以写 p < v.end()，但遍历 list 应写 p != s.end()
链表节点不保证连续存放，因此不能用 < 比较两个位置的先后

示例：维护有序链表

#include <iostream>
#include <list>
#include <string>
using namespace std;

int main() {
    // 定义一个存储 string 类型的双向链表容器 s，初始为空
    list<string> s;
    string t;
    // 定义 list<string> 类型的迭代器 p，迭代器用于遍历/操作 list 元素（类似指针）
    list<string>::iterator p;

    for (int a = 0; a < 5; a++) {
        cout << "enter a string: ";
        cin >> t;

        // 将迭代器 p 重置为链表的起始位置（指向第一个元素）
        p = s.begin();
        while (p != s.end() && *p < t) {
            p++;
        }

        // 在迭代器p指向的位置，插入字符串t，插入后链表始终保持字典序升序排列
        s.insert(p, t);
    }

    // 遍历整个链表，输出所有元素
    for (p = s.begin(); p != s.end(); p++) {
        // 解引用迭代器 *p，获取指向的字符串并输出，加空格分隔
        cout << *p << " ";
    }
    cout << endl;
}

示例：删除第二个元素并输出

#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
using namespace std;

list<int> L;
for (int i = 1; i <= 5; ++i) {
    // 向链表 L 末尾插入元素 i，最终链表：1,2,3,4,5
    L.push_back(i);
}

// 删除链表的第二个元素，删除后链表变为：1,3,4,5
L.erase(++L.begin()); // delete second item

// 输出链表所有元素，用逗号分隔
copy(L.begin(), L.end(), ostream_iterator<int>(cout, ","));

// Prints: 1,3,4,5,

4 map¶

map 保存一组 pair，每个 pair 包含一个 key 和一个 value
查找时提供 key，取回对应的 value

示例：查询输入的数字是否为预设的完全平方数

#include <iostream>
#include <map>
using namespace std;

int main() {
    // 定义一个 map 容器：键类型为 long，值类型为 int，容器名称为 root
    map<long, int> root;
    root[4] = 2;
    root[1000000] = 1000;

    long l;
    cin >> l;

    // 判断容器中是否存在 键 = l
    if (root.count(l)) {
        // 如果存在该键，输出 map 中键 l 对应的值（即平方根）
        cout << root[l];
    } else {
        cout << "Not perfect square";
    }
}

5 Iterators and Algorithms¶

迭代器表示容器中的一个位置，begin() 指向第一个元素，end() 指向最后一个元素之后的位置
迭代器可以递增，也可以解引用访问元素
STL 算法通常不直接依赖某个具体容器，而是依赖一对迭代器表示的范围，因此同一个算法可以作用在不同容器上
STL 算法接受迭代器作为参数，因此可以独立于容器工作
常见查找通常写作 std::find(first, last, item)，有序关联容器如 map / set 也提供自己的 find(key)

示例

list<int> L;
vector<int> V;

copy(L.begin(), L.end(), V.begin());

使用算法前要保证目标空间足够

vector<int> V;
copy(L.begin(), L.end(), V.begin()); // V 为空时不安全

更稳妥的方式是先分配空间，或使用插入迭代器：

vector<int> V(L.size());
copy(L.begin(), L.end(), V.begin());

vector<int> V2;
copy(L.begin(), L.end(), back_inserter(V2));

Typedefs

STL 类型名常常很长，尤其是嵌套容器和迭代器类型，如：

map<Name, list<PhoneNum>> phonebook;
map<Name, list<PhoneNum>>::iterator finger;

可以使用 typedef 进行简化，如：

typedef map<Name, list<PhoneNum>> PB;

PB phonebook;
PB::iterator finger;

在 C++11 之后，可以使用 auto 和 using，如：

using PB = map<Name, list<PhoneNum>>;

PB phonebook;
auto finger = phonebook.begin();

6 Using Your Own Classes in STL¶

把自定义类放入 STL 容器时，类本身可能需要提供一些基本能力，如：
- 可赋值：operator=
- 可默认构造：default constructor
- 可比较：有序容器如 set、map 通常需要 operator<
int、char、string 已经内建了合适的比较，但 char* 的默认比较是比较地址，不是比较字符串内容

示例：自定义 key 类型

#include <cstring>
#include <map>
using namespace std;

struct full_name {
    char* first;
    char* last;

    bool operator<(const full_name& a) const {
        return strcmp(first, a.first) < 0;
    }
};

map<full_name, int> phonebook;

char* 作为字符串成员要额外小心

char* 涉及资源管理时通常还需要考虑拷贝构造、赋值运算符和析构函数
更现代、也更安全的写法通常是使用 std::string

7 Pitfalls¶

越界访问 vector

vector<int> v;
v[100] = 1; // wrong

解决方式：

使用 push_back()
构造时预分配元素数量
使用 resize() 改变当前大小
访问前先检查 size()

map::operator[] 会自动插入

if (foo["bob"] == 1) {
    // "bob" 不存在时，这里会先创建一个新元素
}

如果只是检查 key 是否存在，应使用：

if (foo.count("bob")) {
    // found
}

if (foo.contains("bob")) {
    // C++20
}

判断容器是否为空

if (my_list.size() == 0) {
    // slow / less direct
}

更推荐：

if (my_list.empty()) {
    // fast and clear
}

失效迭代器

list<int> L;
list<int>::iterator li = L.begin();

L.erase(li);
++li; // wrong: li 已经失效

正确方式：

li = L.erase(li);

不同容器的迭代器失效规则不同

vector 扩容后，很多已有迭代器、指针和引用会失效
list 插入通常不影响其他节点，但被删除节点对应的迭代器立刻失效

Other data structures

set、multiset、multimap
queue、priority_queue
stack、deque
slist、bitset、valarray