通常认为，STL是由容器、算法、迭代器、函数对象、适配器、内存分配器这 6 部分构成，其中后面 4 部分是为前 2 部分服务的，它们各自的含义如表所示。

STL的组成 含义
容器 一些封装数据结构的模板类，例如 vector 向量容器、list 列表容器等。
算法 STL 提供了非常多（大约 100 个）的数据结构算法，它们都被设计成一个个的模板函数，这些算法在 std 命名空间中定义，其中大部分算法都包含在头文件 中，少部分位于头文件 中。
迭代器 在C++STL 中，对容器中数据的读和写，是通过迭代器完成的，扮演着容器和算法之间的胶合剂。
函数对象 如果一个类将 () 运算符重载为成员函数，这个类就称为函数对象类，这个类的对象就是函数对象（又称仿函数）。
适配器 可以使一个类的接口（模板的参数）适配成用户指定的形式，从而让原本不能在一起工作的两个类工作在一起。值得一提的是，容器、迭代器和函数都有适配器。
内存分配器 为容器类模板提供自定义的内存申请和释放功能，由于往往只有高级用户才有改变内存分配策略的需求，因此内存分配器对于一般用户来说，并不常用。

容器的分类

image-20220313174635955

  • 顺序容器sequence Containers）：其共同的特点是不会对存储的元素进行排序，元素排列的顺序取决于存储它们的顺序。
  • 关联容器：元素是键/值对，特别适合做查找。你能控制插入的内容，但一般来讲你不能控制插入的位置
  • 无序容器(Unordered Containers) : c++11里推出:元素的位置不重要，重要的是这个元素是否在这个容器里边。
    无序容器他也属于一种关联容器

image-20220313212356620

array

image-20220313175116905

vector序列式容器

容器里有多少个元素用size()来查看，有多少空间用capacity()来查看，capacity()一定不会小于size()空间的数量。
用reverse可以预留空间，前提是你预先知道这个容器最多会容纳多少个元素;

vector扩容

vector容器的内存空间也是连续挨着的，vector容器有一个“空间”的概念，每一个空间可以装若干个元素，比如下面一个空间装了若干Test对象实例。

如果扩容的时候空间不够，vector会释放原先的内存，寻找新内存一块更大的空间，将原先的元素和新元素放到新的大空间。

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
#include <iostream>
#include <vector>
using namespace std;
class Test
{
public:
    Test() {
        cout << "执行了Test构造函数" << endl;
    }
    ~Test() {
        cout << "执行了~Test析构函数" << endl;
    }
    Test(const Test& t) {
        cout << "执行了Test(const Test& t)拷贝构造函数" << endl;
    }
};

int main()
{
    vector<Test>v;
    for (int i = 0; i < 5; i++) {
        cout << "--------begin-------" << endl;
        v.push_back(Test());
        cout << "---------end--------" << endl;
    }
    return 0;
}

可以观察到

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
--------begin-------
执行了Test构造函数
执行了Test(const Test& t)拷贝构造函数
执行了~Test析构函数
---------end--------
--------begin-------
执行了Test构造函数
执行了Test(const Test& t)拷贝构造函数
执行了Test(const Test& t)拷贝构造函数
执行了~Test析构函数
执行了~Test析构函数
---------end--------
--------begin-------
执行了Test构造函数
执行了Test(const Test& t)拷贝构造函数
执行了Test(const Test& t)拷贝构造函数
执行了Test(const Test& t)拷贝构造函数
执行了~Test析构函数
执行了~Test析构函数
执行了~Test析构函数
---------end--------
--------begin-------
执行了Test构造函数
执行了Test(const Test& t)拷贝构造函数
执行了Test(const Test& t)拷贝构造函数
执行了Test(const Test& t)拷贝构造函数
执行了Test(const Test& t)拷贝构造函数
执行了~Test析构函数
执行了~Test析构函数
执行了~Test析构函数
执行了~Test析构函数
---------end--------
--------begin-------
执行了Test构造函数
执行了Test(const Test& t)拷贝构造函数
执行了Test(const Test& t)拷贝构造函数
执行了Test(const Test& t)拷贝构造函数
执行了Test(const Test& t)拷贝构造函数
执行了Test(const Test& t)拷贝构造函数
执行了~Test析构函数
执行了~Test析构函数
执行了~Test析构函数
执行了~Test析构函数
执行了~Test析构函数
---------end--------
执行了~Test析构函数
执行了~Test析构函数
执行了~Test析构函数
执行了~Test析构函数
执行了~Test析构函数

E:\codeproject\sorce\Project2\x64\Debug\Project2.exe (进程 8172)已退出，代码为 0。
要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口. . .

deque双端队列

deque: 双端队列dobule-ended queue (双向开口)。相当于动态数组;头部和尾部插入与删除数据都很快;
如果往中间插入元素那么可能会涉及到移动其他元素，效率上会比较低;

分段连续

image-20220313204719450

stack栈

unordered_set

image-20220313212142765

  • 以往hash_set, hash_map, hash_multiset, hash_multimap老版本容器，不推荐使用了;用unordered开头的容器取代了;
  • 增加篮子( 桶子)数量的目的就是为了防止某个篮子后边挂的元素太多，从而影响查找速度;
  • 自动指定元素位置，不需要使用者手工干预
  • 篮子的数量不少于元素数量

hashtable中的bucket所维护的list既不是list也不是slist，而是其自己定义的由hashtable_node数据结构组成的linked-list，而bucket聚合体本身使用vector进行存储。hashtable的迭代器只提供前进操作，不提供后退操作

在hashtable设计bucket的数量上，其内置了28个质数[53, 97, 193,…,429496729]，在创建hashtable时，会根据存入的元素个数选择大于等于元素个数的质数作为hashtable的容量（vector的长度），其中每个bucket所维护的linked-list长度也等于hashtable的容量。如果插入hashtable的元素个数超过了bucket的容量，就要进行重建table操作，即找出下一个质数，创建新的buckets vector，重新计算元素在新hashtable的位置。

unordered_set/unordered_multiset底层机制以hashtable完成
unordered_set采用insert_unique进行插入，unordered_multiset采用insert_equal完成

unordered_map/unordered_multimap底层机制以hash table完成
unordered_map采用insert_unique进行插入，unordered_multimap采用insert_equal完成

分配器

缺省分配器基本没什么太大的作用，比如vector<int>::allocator_type，底层调用的是malloc()，free()，并没有用到内存池

allocator分配器， 是个类模板，我们写代码时极少会直接用到这个allocator这种容器的分配器;
但从语法上来讲，allocator分配器是能够被直接编码使用的

1
2
3
4
5
6
7
8
9
10
11
void func()
{
    allocator<int>alloc;//定义alloc对象，为类型int分配内存
    int* p = alloc.allocate(3);//allocate分配器中的重要函数
                                //这段内存能保存3个类型为int的对象（12字节）
    int* q = p;
    *q = 1; q++;
    *q = 2; q++;
    *q = 3;
    alloc.deallocate(p, 3);//deallocate()也是分配器的重要函数，用于释放内存
}

其他分配器

linux GNU C++(gcc,g++)

image-20220315210032501

在SGI STL中的某个版本中，实现了_pool_alloc，指的是运用内存池来进行内存分配，对于容器的第二个参数默认为alloc。这主要是为了解决小型区块从而造成的内存碎片问题，以此来提升性能。

采用了双层分配器策略，第一级分配器直接使用malloc和free，第二级分配器根据分配区块的大小采取不同的策略：分配区块若大于128字节，则调用第一级分配器，否则用内存池的方式分配管理内存。

第一级分配器__malloc_alloc_template需要注意的是，其在allocate中直接调用malloc，当调用不成功时候，会转入一个循环，不断地尝试调用内存（内存不足处理例程），期望在某次调用后可以得到足够的内存而终止，否则丢出异常。这里注意一下，只有第一级分配器有内存申请异常处理，也可以用set_new_handle来设置异常处理。

因为malloc出来的内存都会带一些“额外的记录”，当申请的内存较小时，额外的负担所占的比例就很大，就会很浪费内存空间。所以当申请的区块小于128字节，则会每次申请一块大内存，并维护对应着自由链表free-lists。首先其是一个16节点的数组，数组中的每一个元素是一个指针，指向一个链表free-list，链表中的每一个节点当有相同大小的内存需求时，直接从free-list中取出，如果释放小内存时，也会放到相应的free-list中。对于一整块内存，只有最上面才有记录（用于记录内存大小），因此减小了开销。

SGI第二级分配器总共管理16个free-list（8 bytes ~ 128 bytes），因此会将任何小区块的需求上调至8的整数倍。

迭代器

1、 迭代器是一种抽象的设计理念，通过迭代器可以在不了解容器内部原理的情况下遍历容器，除此之外，STL中迭代器一个最重要的作用就是作为容器与STL算法的粘合剂。

2、 迭代器的作用就是提供一个遍历容器内部所有元素的接口，因此迭代器内部必须保存一个与容器相关联的指针，然后重载各种运算操作来遍历，其中最重要的是*运算符与->运算符，以及++、–等可能需要重载的运算符重载。这和C++中的智能指针很像，智能指针也是将一个指针封装，然后通过引用计数或是其他方法完成自动释放内存的功能。

算法

仿函数

适配器

把一个既有的东西进行适当的改造，比如增加一点东西或者减少一点东西，就构成了一个适配器

容器适配器

stack可以看成deque只用了一边。底层就是deque

queue可以看成只使用了deque的部分功能（封死了某一入口和某一出口）。

算法适配器

最典型的就是绑定器（binder）

老版本bind1st，bind2nd，C++11中修改为bind