華束师免天學数学科学学院 School of Mathematical Sciences,East China Normal University 第十六讲 标准模板库 STL:Standard Template Library http://math.ecnu.edu.cn/~jypan
http://math.ecnu.edu.cn/~jypan 第十六讲 标准模板库 STL：Standard Template Library
标准模板库STL C++STL是一套功能强大的C++模板库，提供了大量的通 用模板类和模板函数，这些模板类和模板函数可以实现多种 流行和常用的算法和数据结构，如向量、链表、队列、栈， 等等，大大提升软件开发的效率。 http://math.ecnu.edu.cn/~jypan
http://math.ecnu.edu.cn/~jypan 标准模板库 STL C++ STL 是一套功能强大的 C++ 模板库，提供了大量的通 用模板类和模板函数，这些模板类和模板函数可以实现多种 流行和常用的算法和数据结构，如向量、链表、队列、栈， 等等，大大提升软件开发的效率
STL三大核心组件 容器Containers 用来存储数据的一种数据结构（模板类)，如向量，链表 ■算法Algorithms 对数据的各种操作（模板函数），如插入，排序，搜索等 ■迭代器iterators 访问容器中的数据的方法，作用类似于指针 http://math.ecnu.edu.cn/~jypan 3
http://math.ecnu.edu.cn/~jypan 3 STL 三大核心组件 容器 Containers 用来存储数据的一种数据结构（模板类），如向量，链表 算法 Algorithms 对数据的各种操作（模板函数），如插入，排序，搜索等 迭代器 iterators 访问容器中的数据的方法，作用类似于指针
容器Containers 顺序容器/序列容器 关联容器 容器适配器 http://math.ecnu.edu.cn/~jypan 4
http://math.ecnu.edu.cn/~jypan 容器 Containers 顺序容器/序列容器 关联容器 容器适配器 1 4
容器：顺序容器 口顺序容器/序列容器(Sequential Containers) 按顺序（物理/逻辑）存储数据，如数组，链表等→数据结构 array 数组，长度不能改变 vector 只能在最后面插入或删除数据 deque 与vector类似，但允许在最前面插入或删除数据 list 双向链表，可在任意位置插入或删除数据 forward list 与1ist类似，但是单向的，只能沿一个方向访问 string 字符串，与vector类似，但存储的是字符 http://math.ecnu.edu.cn/~jypan 5
http://math.ecnu.edu.cn/~jypan 容器：顺序容器 顺序容器/序列容器（Sequential Containers） 按顺序（物理/逻辑）存储数据，如数组，链表等 数据结构 array 数组，长度不能改变 vector 只能在最后面插入或删除数据 deque 与 vector 类似，但允许在最前面插入或删除数据 list 双向链表，可在任意位置插入或删除数据 forward_list 与 list 类似，但是单向的，只能沿一个方向访问 string 字符串，与 vector 类似，但存储的是字符 5
array:长度固定，可随意访问其中的任何元素 obi obj obj obj obj obj vector:与数组类似，且长度可变，但只能在最后面添加或删除数据 ob时 obj obj obj obj new deque:与vector类似，但可在两头添加或删除数据 new obj obj obj new http://math.ecnu.edu.cn/~jypan 6
http://math.ecnu.edu.cn/~jypan obj obj obj obj obj obj array：长度固定，可随意访问其中的任何元素 vector：与数组类似，且长度可变，但只能在最后面添加或删除数据 deque：与 vector 类似，但可在两头添加或删除数据 obj obj obj obj obj obj new new obj obj obj obj obj obj new 6
1st:双向链表，可在任意位置添加或删除数据，但只能从第一个 元素或最后一个元素开始访问 new new 购☒k☒k forward1ist:单向链表，与list类似，但只能单向访问 new new ob ☒☒ b http://math.ecnu.edu.cn/~jypan 7
http://math.ecnu.edu.cn/~jypan forward_list：单向链表，与 list 类似，但只能单向访问 obj list：双向链表，可在任意位置添加或删除数据，但只能从第一个 元素或最后一个元素开始访问 obj obj obj obj obj new new obj obj obj obj obj obj new new 7
容器：关联容器 ▣关联容器(Associative Containers) 按排序方式存储数据，就像词典一样→方便搜索 set 存储互不相同的数据，插入数据时进行排列 unordered set 与set类似，但按Hash值排序 map 存储“键值”对，按唯一的键排序 unordered_map 与map类似，但按“键”的Hash值排序 multiset 与set类似，但允许有相同的数据 unordered multiset 与unordered_set类似，但允许有相同的数据 multimap 与map类似，但不要求“键”唯一 unordered_multimap 与unordered_map类似，但不要求“键”唯一 http://math.ecnu.edu.cn/~jypan 8
http://math.ecnu.edu.cn/~jypan 容器：关联容器 关联容器（Associative Containers） 按排序方式存储数据，就像词典一样 方便搜索 set 存储互不相同的数据，插入数据时进行排列 unordered_set 与 set 类似，但按 Hash 值排序 map 存储“键-值”对，按唯一的键排序 unordered_map 与 map 类似，但按“键”的 Hash 值排序 multiset 与 set 类似，但允许有相同的数据 unordered_multiset 与 unordered_set 类似，但允许有相同的数据 multimap 与 map 类似，但不要求“键”唯一 unordered_multimap 与 unordered_map 类似，但不要求“键”唯一 8
容器适配器 ▣ 容器适配器(Associative adapters) 顺序适配器和关联适配器的变种，增加一些特殊功能 stack 栈，按后进先出(LIFO)方式存储数据 queue 队列，按先进先出(FIF0)方式存储数据 priority_queue 队列，但能保证最大元素总在最前面 http://math.ecnu.edu.cn/~jypan 9
http://math.ecnu.edu.cn/~jypan 容器适配器 容器适配器（Associative adapters） 顺序适配器和关联适配器的变种，增加一些特殊功能 stack 栈，按后进先出（LIFO）方式存储数据 queue 队列，按先进先出（FIFO）方式存储数据 priority_queue 队列，但能保证最大元素总在最前面 9
2 算法Algorithms 对容器进行的各种操作，如排序，查找，反转等等，也可 以理解为容器所具有的功能（成员函数)。 #include find 查找指定的值 find if 根据条件查找 reverse 反转 remove if 根据条件删除相应的数据 transform 根据用户给定的方法对数据进行交换 http://math.ecnu.edu.cn/~jypan 10
http://math.ecnu.edu.cn/~jypan 算法 Algorithms 对容器进行的各种操作，如排序，查找，反转等等，也可 以理解为容器所具有的功能（成员函数）。 find 查找指定的值 find_if 根据条件查找 reverse 反转 remove_if 根据条件删除相应的数据 transform 根据用户给定的方法对数据进行交换 #include 2 10