STL | Serendipity

type

status

date

slug

summary

什么是STL

STL称为标准模板库（Standard Template Library），是惠普实验室开发的一系列软件的统称。现主要出现在C++中，STL从广义上分为：容器（Container）、算法（Algorithm）和迭代器（Iterator）。STL几乎所有的代码都采用了模板类或者模板函数，这相比传统的由函数和类组成的库来说提供了更好的代码重用机会。

STL六大组件

STL提供了六大组件，彼此之间可以组合套用，这六大组件分别是容器、算法、迭代器、仿函数、适配器、空间配置器。其中，在算法竞赛中用到最多的为容器、算法与迭代器。

容器（Container）：STL容器为各种数据结构，如vector、stack、queue、map、set等，用来存放数据，从实现角度来看，STL容器是一种class template。

算法（Algorithm）：STL的算法多数定义在<algorithm>头文件中，其中包括了各种常用的算法，如sort、find、copy、reverse等，从实现角度来看，STL算法是一种function template。

迭代器（Iterator）：STL迭代器扮演了容器与算法之间的胶合剂，共有五种类型，从实现角度来看，迭代器是一种将opetator*、opetator->、operator++等指针相关操作予以重载的class template。所有STL容器都附带有自己专属的迭代器，只有容器的设计者才知道如何遍历自己的元素。

仿函数（Functor）：行为类似函数，可作为算法的某种策略，从实现角度来看，仿函数是一种重载了operator()的class或者class template。

适配器（Adaptor）：一种用来修饰容器或仿函数或迭代器接口的东西。

空间配置器（Allocator）：负责空间的配置与管理。从实现角度来看，配置器是一个实现了动态空间配置、空间管理、空间释放的class template。

STL容器

1.vector

vector又称变长数组，定义在<vector>头文件中，vector容器是动态空间，随着元素的加入，它的内部机制会自动扩充空间以容纳新的元素。因此vector的运用对于内存的合理利用与运用的灵活性有很大的帮助。

1.1 vector的定义方式：

1.2 vector的常用内置函数：

2.stack

stack又称栈，是一种后进先出（Last In First Out，LIFO）的数据结构，定义在<stack>头文件中，stack容器允许新增元素、移除元素、取得栈顶元素，但是除了最顶端以外，没有任何方法可以存取stack的其它元素，换言之，stack不允许有遍历行为。

2.1 stack的定义方式：

2.2 stack的常用内置函数：

3 string

string又称字符串，定义在<string>头文件中。C风格的字符串（以空字符结尾的字符数组）太过复杂难于掌握，因此C++标准库定义了一种string类。string和vector<char>在数据结构、内存管理等方面都是相同的。但是，vector<char>只是单纯的一个“char元素的容器”，而string不仅是一个“char元素的容器”，它还扩展了一些针对字符串的操作，例如string可以使用c_str()函数转换为C风格的字符串，vector中并未对输入输出流操作符进行重载，因此无法直接对vector<char>进行cin或者cout这样的操作，但是string可以，且vector<char>并不能直接实现字符串的拼接，但是string可以，string中重载了+, +=运算符。

3.1 string的定义方式：

3.2 string的常用内置函数：

3.3 string的erase( )与remove( )函数的用法：

4 queue/priority_queue

queue又称队列，是一种先进先出（First In First Out，FIFO）的数据结构，定义在<queue>头文件中，queue容器允许从一端（称为队尾）新增元素（入队），从另一端（称为队头）移除元素（出队）。

priority_queue又称优先队列，同样定义在<queue>头文件中，与queue不同的地方在于我们可以自定义其中数据的优先级，优先级高的排在队列前面，优先出队。priority_queue具有queue的所有特性，包括基本操作，只是在这基础上添加了内部的一个排序，它的本质是用堆实现的，因此可分为小根堆与大根堆，小根堆中较小的元素排在前面，大根堆中较大的元素排在前面。（创建priority_queue时默认是大根堆！）

4.1 queue/priority_queue的定义方式：

4.2 queue/priority_queue的常用内置函数：

5 deque

deque又称双端队列，定义在<deque>头文件中，vector容器是单向开口的连续内存空间，deque则是一种双向开口的连续线性空间。所谓的双向开口，意思是可以在头尾两端分别做元素的插入和删除操作，当然，vector也可以在头尾两端插入元素，但是在其头部进行插入操作效率很低。deque和vector最大的差异一是在于deque允许使用常数项时间在头部进行元素的插入和删除操作，二是在于deque没有容量的概念，因为它是动态的以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。

5.1 deque的定义方式：

5.2 deque的常用内置函数：

6 map/multimap

map/multimap又称映射，定义在<map>头文件中，map和multimap的底层实现机制都是红黑树。map的功能是能够将任意类型的元素映射到另一个任意类型的元素上，并且所有的元素都会根据元素的键值自动排序。map所有的元素都是pair，同时拥有键值和实值（即(key, value)对），key被视为键值，value被视为实值，map不允许两个元素有相同的键值。multimap和map的操作类似，唯一区别是multimap的键值允许重复。

6.1 map/multimap的定义方式：

6.2 map/multimap的常用内置函数：

7 set/multiset

set/multiset又称集合，定义在<set>头文件中。set的特性是所有元素都会根据元素的键值自动被排序，set的元素不像map那样可以同时拥有键值和实值，set的元素既是键值又是实值，set不允许两个元素有相同的键值，因此总结来说就是set中的元素是有序且不重复的。~~multiset的特性和用法和set完全相同~~，唯一的区别在于multiset允许有重复元素，set和multiset的底层实现都是红黑树。

7.1 set/multiset的定义方式：

7.2 set/multiset的常用内置函数：

8 unordered_map/unordered_set

unordered_map/unordered_set分别定义在<unordered_map>与<unordered_set>头文件中，内部采用的是hash表结构，拥有快速检索的功能。与map/set相比最大的区别在于unordered_map/unordered_set中的元素是无序的，增删改查的时间复杂度为（map/set增删改查的时间复杂度为），但是不支持lower_bound ( )/upper_bound( )函数。

8.1 unordered_map/unordered_set的定义方式：

8.2 unordered_map/unordered_set的常用内置函数：

STL算法

C++标准库定义了一组泛型算法，之所以称为泛型指的是它们可以操作在多种容器上，不但可以作用于标准库类型，还可以用在内置数组类型甚至其它类型的序列上。泛型算法定义在<algorithm>头文件中，标准库还定义了一组泛化的算术算法（Generalized Numeric Algorithm），定义在<numeric>头文件中。使用方法如下：