$$\color{#9933ff}{STL：}$$

$\ \ \ \ STL是一个功能强大的基于模板的容器库，通过直接使用这些现成的标准化组件可以大大提高算法$
$设计的效率和可靠性。$

$\color{blue}{— >另一种阅读体验}$

$$\color{red}{一、STL概述}$$

$STL主要由 container(容器)、algorithm(算法)和iterator(迭代器)三大部分构成，$

$容器用于存放数据对象（元素），算法用于操作容器中的数据对象。$

$算法和容器之间的关系就是迭代器。容器、算法和迭代器成为STL的三大件，它们之间的关系如下图所示：$

$$\color{blue}{1.什么是STL容器}$$

$\ \ \ \ 简单的说，一个STL容器就是一种数据结构，例如链表、栈和队列等，这些数据结构在STL中都已经$
$实现好了，在算法设计中可以直接使用它们。$

STL容器部分主要由头文件 <vector>、<string>、<deque>、<list>等组成。

$${常用的数据结构和相应的头文件:}$$

$$\color{blue}{2.什么是STL算法}$$

$\ \ \ \ STL算法是用来操作容器中数据的模板函数，STL提供了大约100个实现算法的模板函数。$
$例如，STL用sort()对一个vector中 的数据进行排序，用find()搜索一个list中的对象。$

$正是由于采用模板函数设计（即泛型设计），STL算法具有很好的通用性，例如排序算法sort()不仅可以$
$对内置数据类型的数据（如int数据）排序，也可以对自定义的结构体数据排序，不仅可以递增排序，$
$也可以按照程序员指定的方式排序（如递减），从而简化代码，提高算法设计效率。$

$$\color{blue}{3.什么是STL迭代器}$$

$\ \ \ \ 简单地说，STL迭代器用于访问容器中的数据对象。每个容器都有自己的迭代器，只有容器自己知道如何$
$访问自己的元素。迭代器像 C/C++ 中的指针，算法通过迭代器来定位和操作容器中的元素。$

$常用的迭代器如下：$

iterator:指向容器中存放元素的迭代器，用于正向遍历容器中的元素
const_iterator:指向容器中存放元素的常量迭代器，只能读取容器中的元素
reverse_iterator:指向容器中存放元素的反向迭代器，只能反向遍历容器中的元素
const_reverse_iterator:指向容器中存放元素的常量反向迭代器，只能读取容器中的元素

$迭代器的常用运算如下：$

++ ： 正向移动迭代器
-- : 反向移动迭代器
*： 返回迭代器所指的元素值

$$\color{red}{二、常用的STL容器}$$

$STL容器很多，每一个容器就是一个类模板，大致分为\color{red}{顺序容器、适配器容器和关联容器}3种类型。$

$$\color{blue}{1.顺序容器}$$

$\ \ \ \ 顺序容器按照线性次序的位置存储数据，即第1个元素，第2个元素，依次类推。$
$STL提供的顺序容器有vector、string、deque和list。$

$1）vector(向量容器)$

$它是一个向量类模板。向量容器相当于数组，它存储具有相同数据类型的一组元素，$
$如下图所示为vector容器v的一般存储方式，可以从末尾快速地插入与删除元素，$
$快速地随机访问元素，但是在序列中间插入、删除元素较慢，因为需要移动插入或删除位置后面地所有元素。$

$\ \ \ \ 如果初始分配的空间不够，当超过空间大小时会重新分配更大的的空间（通常按两倍大小扩展），$
$此时需要进行大量的元素复制，从而增加性能开销。$

定义vector容器的几种方式如下：

vector<int> v1;                     // 定义元素为int的向量v1
vector<int> v2(10);                 // 指定向量v2的初始大小为10个int元素
vector<double> v3(10, 1.23);        // 指定v3的10个初始元素的初值为1.23
vector<int> v4(a, a + 5);           // 用数组 a[0, 4] 共5个元素初始化v4

vector提供了一系列成员函数，vector的主要成员函数如下：

empty()：判断当前向量是否为空
size()：返回当前向量容器中的实际元素个数
[]：返回指定下标的元素
reserve(n)：为当前向量容器预分配n个元素的存储空间
capacity()：返回当前向量容器在重新进行内存分配以前所能容纳的元素个数
resize(n)：调整当前向量容器的大小，使其可以容纳n个元素
push_back()：在当前向量容器尾部添加一个元素
pop_back()：移除最后一个元素
insert(pos, elem)：在pos位置插入元素elem，即将元素elem插入到迭代器pos指定的元素之前
front()：获取当前容器的第一个元素
back()：获取当前容器的最后一个元素
erase()：删除当前向量容器中某个迭代器或者迭代器区间指定的元素
clear()：删除当前容器的所有元素
begin()：引用容器的第一个元素
end()：引用容器的最后一个元素后面的一个位置
rbegin()：引用容器的最后一个元素
rend()：引用容器的第一个元素前面的一个位置

$2）string(字符串容器)$

$string是一个保存字符序列的容器，下图所示为string容器s的一般存储方式，$
$它的所有元素为字符类型，类似vector<char>，因此除了有字符串的一些常用操作外，$
$还包含了所有序列容器的操作。常用操作包括增加，删除，查找，修改，输入，输出等。$

创建string容器的几种方式如下：

string()：建立一个空串
string(const string& str)：用字符串str建立当前字符串
string(const string& str, size_type idx)：用字符串str起始于idx的字符建立当前字符串
string(const string& str, size_type idx, size_type num)：用字符串str起始于idx的num个字符建立当前字符串
string(const char* cstr)：用C-字符串cstr建立当前字符串
string(const char* cstr, size_type len)：用C-字符串cstr开头的len个字符建立当前字符串
string(size_type num, char c)：用num个字符c建立当前字符串

示例：

char cstr[] = "China! Great Wall";      // C-字符串
string s1(cstr);                        // s1:China! Great Wall
string s2(s1);                          // s2:China! Great Wall
string s3(cstr, 7, 11);                 // s3:Great Wall
string s4(cstr, 6);                     // s4:China!
string s5(5, 'A');                      // s5:AAAAA

常用函数：

empty()：判断当前字符串是否为空
size()：返回当前字符串的实际字符个数
length()：返回当前字符串的实际字符个数
[idx]：返回当前字符串位于idx位置的元素，idx从0开始
at(idx)：返回当前字符串位于idx位置的元素
append(cstr)：在当前字符串末尾添加一个字符串str
insert(size_type idx, string str)：在当前字符串的idx处插入一个字符串str
find(string s, size_type pos)：从前字符串的pos位置开始查找s的第一个位置，找到返回位置，未找到返回-1
replace(size_type idx, size_type len, string str)：将当前字符串中起始于idx的len个字符用str替换
substr(size_type idx)：返回当前字符串起始于idx的子串
substr(size_type idx, size_type len)：返回当前字符串起始于idx的长度为len的子串
erase()：删除字符串的所有字符
clear()：删除字符串的所有字符
erase(size_type idx)：删除字符串从idx开始的所有字符

$3）deque(双端队列容器)$

$双端队列容器由若干个块构成，每个块中元素的地址是连续的，块之间的地址是不连续的。$
$可以从前面或后面快速的插入与删除元素，并可以快速的随机访问元素，但在中间位置插入和删除元素较慢。$

定义deque的几种方式：

deuqe<int> dq1;                                 // 定义元素为int的双端队列dq1
deque<int> dq2(10);                             // 指定dq2的初始大小为10个int元素
deque<double> dq3(10, 1.23);                    // 指定dq3的10个初始元素的初值为1.23
deque<int> dq4(dq2.degin(), dq2.end());         // 用dq2 的所有元素初始化dq4

常用函数：

empty()：判断双端队列是否为空
size()：返回双端队列的元素个数
front()：取队头元素
back()：取队尾元素
push_front(elem)：在队头插入元素elem
push_back(elem)：在队尾插入元素elem
pop_front(elem)：删除队头一个元素
pop_back(elem)：删除队尾一个元素
erase()：从双端队列中删除一个或几个元素
clear()：删除双端队列的所有元素
begin()：引用容器的第一个元素
end()：引用容器的最后一个元素后面的一个位置
rbegin()：引用容器的最后一个元素
rend()：引用容器的第一个元素前面的一个位置

$4）list（链表容器）$

$可从任何地方快速插入与删除。每个节点通过指针链接，不能随机访问元素，为了访问特定的元素，$
$必须从第一个元素位置（表头）开始，随指针从一个元素到下一个元素，直到找到。$

定义list的几种方式：

list<int> l1;                   // 定义元素为int的链表l1
list<int> l2(10);               // 指定链表l2的初始大小为10个int元素
list<double> l3(10, 1.23);      // 指定dq3的10个初始元素的初值为1.23
list<int> l4(a, a + 5);         // 用数组 a[0,·· 4] 共5个元素初始化l4

常用函数：

empty()：判断链表是否为空
size()：返回链表的元素个数
push_back()：在链表尾部插入元素
pop_back()：删除链表的最后一个元素
remove()：删除链表中所有指定值的元素
erase()：从链表中删除一个或几个元素
unique()：删除链表中相邻的重复元素
clear()：删除链表的所有元素
insert(pos, elem)：在pos位置插入元素elem
insert(pos, n, elem)：在pos位置插入n个元素elem
reverse()：反转链表
sort()：对链表中的元素排序
begin()：引用容器的第一个元素
end()：引用容器的最后一个元素后面的一个位置
rbegin()：引用容器的最后一个元素
rend()：引用容器的第一个元素前面的一个位置

$$\color{blue}{2.关联容器}$$

关联容器中的每个元素有一个key（关键字），通过key来存储和读取元素。这些关键字可能与元素在容器中的位置无关，所以关联容器不提供顺序容器中的front(), push_front(), back(), push_back()以及pop_back()操作。

$1）set(集合容器)/multiset(多重集合容器)$

$set和multiset都是集合类模板，其元素称为关键字。set的关键字是唯一的，multiset的关键字可以不唯一，$
$而且默认情况下会对元素按关键字自动升序排列，所以查找速度较快。$

函数：

empty()：判断容器是否为空
size()：返回容器中的实际元素个数
insert()：插入元素
erase()：从容器中删除一个或几个元素
clear()：删除所有元素
count(k)：返回容器中关键字k出现的次数
find(k)：如果存在k, 返回该元素的迭代器，否则返回end()值
upper_bound()：返回一个迭代器，指向关键字大于k的第一个元素
upper_bound()：返回一个迭代器，指向关键字不小于k的第一个元素
begin()：用于正向迭代，返回容器的第一个元素
end()：用于正向迭代，返回容器的最后一个元素后面的一个位置
rbegin()：用于反向迭代，返回容器的最后一个元素
rend()：用于反向迭代，返回容器的第一个元素前面的一个位置

$2）映射(map)/多重映射(multimap)$

set和multiset都是映射类模板，映射是实现关键字与值关系的存储结构，可以使用一个关键字key来访问相应的数据值value。set/multiset中的key和value都是key类型，而set/multiset中的key和value是一个pair类结构。

pair类结构的声明如下：

struct pair {
    T first;
    T second;
}

pair有两个分量（二元组），first为第一个分量（在map对应key），second为第二个分量（在map对应value）。

函数：

empty()：判断容器是否为空
size()：返回容器中的实际元素个数
map[key]：返回关键字key的元素的引用，如果不存在，则以key为关键字插入一个元素（不适合multimap）
insert(elem)：插入一个元素elem并返回该元素的位置
clear()：删除所有元素
count()：容器中指定关键字的元素个数（map中只有1或0）
find()：在容器中查找元素
begin()：用于正向迭代，返回容器的第一个元素
end()：用于正向迭代，返回容器的最后一个元素后面的一个位置
rbegin()：用于反向迭代，返回容器的最后一个元素
rend()：用于反向迭代，返回容器的第一个元素前面的一个位置

$$\color{blue}{3.适配器容器}$$

$适配器容器是指基于其他容器实现的容器。$

$1）stack(栈容器)$

后进先出。默认底层容器是deque.
stack容器只有一个出口，即栈顶，可以在栈顶插入（进栈）和删除（出栈）元素，而不允许顺序遍历。

函数：

empty()：判断栈是否为空
size()：返回栈的实际元素个数
push(elem)：元素elem进栈
top()：返回栈顶
pop()：元素出栈

$2）queue(队列容器)$

先进先出，不允许顺序遍历

函数：

empty()：判断队列是否为空
size()：返回队列的实际元素个数
front()：返回队头元素
back()：返回队尾元素
push(elem)：元素elem进队
pop()：元素出队

$3）priority$_$queue(优先队列容器)$

优先队列是一种受限访问操作的存储结构，元素可以以任意顺序进入优先队列。

函数：

empty()：判断优先队列是否为空
size()：返回优先队列的实际元素个数
push(elem)：元素elem进队
top()：获取队头元素
pop()：元素出队

参考：

$算法设计与分析（第2版）$