看完R1mao大佬的文章后的拙劣复现与分析，本文基本上都是复制R1mao大佬的，少部分是自己分析，可以支持一下R1mao大佬

https://bbs.kanxue.com/thread-275133.htm

准备找时间把所有常用的stl全部研究一遍，所以应该也是长期更新，有时间就搞

deque

基础知识

概论

deque（双端队列）是由一段一段的定量连续空间构成，可以向两端发展，因此不论在尾部或头部安插元素都十分迅速。 在中间部分安插元素则比较费时，因为必须移动其它元素。

定义

使用之前必须加相应容器的头文件：

1
#include <deque> // deque属于std命名域的，因此需要通过命名限定，例如using std::deque;

定义的实现代码如下：

1
2
3
4
5
deque<int> a; // 定义一个int类型的双端队列a
deque<int> a(10); // 定义一个int类型的双端队列a，并设置初始大小为10
deque<int> a(10, 1); // 定义一个int类型的双端队列a，并设置初始大小为10且初始值都为1
deque<int> b(a); // 定义并用双端队列a初始化双端队列b
deque<int> b(a.begin(), a.begin()+3); // 将双端队列a中从第0个到第2个(共3个)作为双端队列b的初始值

除此之外，还可以直接使用数组来初始化向量：

1
2
3
4
5
6
int n[] = { 1, 2, 3, 4, 5 };
// 将数组n的前5个元素作为双端队列a的初值
// 说明：当然不包括arr[4]元素，末尾指针都是指结束元素的下一个元素，
// 这个主要是为了和deque.end()指针统一。
deque<int> a(n, n + 5); 
deque<int> a(&n[1], &n[4]); // 将n[1]、n[2]、n[3]作为双端队列a的初值

基本操作函数

容量函数

  • 容器大小：deq.size();
  • 容器最大容量：deq.max_size();
  • 更改容器大小：deq.resize();
  • 容器判空：deq.empty();
  • 减少容器大小到满足元素所占存储空间的大小：deq.shrink_to_fit();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <deque>

using namespace std;

int main(int argc, char* argv[])
{
	deque<int> deq;
	for (int i = 0; i<6; i++)
	{
		deq.push_back(i);
	}

	cout << deq.size() << endl; // 输出：6
	cout << deq.max_size() << endl; // 输出：1073741823
	deq.resize(0); // 更改元素大小
	cout << deq.size() << endl; // 输出：0
	if (deq.empty())
		cout << "元素为空" << endl; // 输出：元素为空

	return 0;
}

添加函数

  • 头部添加元素：deq.push_front(const T& x);
  • 末尾添加元素：deq.push_back(const T& x);
  • 任意位置插入一个元素：deq.insert(iterator it, const T& x);
  • 任意位置插入 n 个相同元素：deq.insert(iterator it, int n, const T& x);
  • 插入另一个向量的 [forst,last] 间的数据：deq.insert(iterator it, iterator first, iterator last);
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
#include <iostream>
#include <deque>

using namespace std;

int main(int argc, char* argv[])
{
	deque<int> deq;

	// 头部增加元素
	deq.push_front(4);
	// 末尾添加元素
	deq.push_back(5);
	// 任意位置插入一个元素
	deque<int>::iterator it = deq.begin();
	deq.insert(it, 2);
	// 任意位置插入n个相同元素
	it = deq.begin(); // 必须要有这句
	deq.insert(it, 3, 9);
	// 插入另一个向量的[forst,last]间的数据
	deque<int> deq2(5,8);
	it = deq.begin(); // 必须要有这句
	deq.insert(it, deq2.end() - 1, deq2.end());

	// 遍历显示
	for (it = deq.begin(); it != deq.end(); it++)
		cout << *it << " "; // 输出：8 9 9 9 2 4 5
	cout << endl;

	return 0;
}

删除函数

  • 头部删除元素：deq.pop_front();
  • 末尾删除元素：deq.pop_back();
  • 任意位置删除一个元素：deq.erase(iterator it);
  • 删除 [first,last] 之间的元素：deq.erase(iterator first, iterator last);
  • 清空所有元素：deq.clear();
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
#include <iostream>
#include <deque>

using namespace std;

int main(int argc, char* argv[])
{
	deque<int> deq;
	for (int i = 0; i < 8; i++)
		deq.push_back(i);

	// 头部删除元素
	deq.pop_front();
	// 末尾删除元素
	deq.pop_back();
	// 任意位置删除一个元素
	deque<int>::iterator it = deq.begin();
	deq.erase(it);
	// 删除[first,last]之间的元素
	deq.erase(deq.begin(), deq.begin()+1);

	// 遍历显示
	for (it = deq.begin(); it != deq.end(); it++)
		cout << *it << " ";
	cout << endl;

	// 清空所有元素
	deq.clear();

	// 遍历显示
	for (it = deq.begin(); it != deq.end(); it++)
		cout << *it << " "; // 输出：3 4 5 6
	cout << endl;

	return 0;
}

访问函数

  • 下标访问：deq[1]; // 并不会检查是否越界
  • at 方法访问：deq.at(1); // 以上两者的区别就是 at 会检查是否越界，是则抛出 out of range 异常
  • 访问第一个元素：deq.front();
  • 访问最后一个元素：deq.back();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <deque>

using namespace std;

int main(int argc, char* argv[])
{
	deque<int> deq;
	for (int i = 0; i < 6; i++)
		deq.push_back(i);

	// 下标访问
	cout << deq[0] << endl; // 输出：0
	// at方法访问
	cout << deq.at(0) << endl; // 输出：0
	// 访问第一个元素
	cout << deq.front() << endl; // 输出：0
	// 访问最后一个元素
	cout << deq.back() << endl; // 输出：5

	return 0;
}

其他函数

  • 多个元素赋值：deq.assign(int nSize, const T& x); // 类似于初始化时用数组进行赋值
  • 交换两个同类型容器的元素：swap(deque&);
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
#include <iostream>
#include <deque>

using namespace std;

int main(int argc, char* argv[])
{
	// 多个元素赋值
	deque<int> deq;
	deq.assign(3, 1);
	deque<int> deq2;
	deq2.assign(3, 2);

	// 交换两个容器的元素
	deq.swap(deq2);

	// 遍历显示
	cout << "deq: ";
	for (int i = 0; i < deq.size(); i++)
		cout << deq[i] << " "; // 输出：2 2 2
	cout << endl;

	// 遍历显示
	cout << "deq2: ";
	for (int i = 0; i < deq2.size(); i++)
		cout << deq2[i] << " "; // 输出：1 1 1
	cout << endl;

	return 0;
}

迭代器与算法

1. 迭代器

  • 开始迭代器指针：deq.begin();
  • 末尾迭代器指针：deq.end(); // 指向最后一个元素的下一个位置
  • 指向常量的开始迭代器指针：deq.cbegin(); // 意思就是不能通过这个指针来修改所指的内容，但还是可以通过其他方式修改的，而且指针也是可以移动的。
  • 指向常量的末尾迭代器指针：deq.cend();
  • 反向迭代器指针，指向最后一个元素：deq.rbegin();
  • 反向迭代器指针，指向第一个元素的前一个元素：deq.rend();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <deque>

using namespace std;

int main(int argc, char* argv[])
{
	deque<int> deq;
	deq.push_back(1);
	deq.push_back(2);
	deq.push_back(3);

	cout << *(deq.begin()) << endl; // 输出：1
	cout << *(--deq.end()) << endl; // 输出：3
	cout << *(deq.cbegin()) << endl; // 输出：1
	cout << *(--deq.cend()) << endl; // 输出：3
	cout << *(deq.rbegin()) << endl; // 输出：3
	cout << *(--deq.rend()) << endl; // 输出：1
	cout << endl;

	return 0;
}

2. 算法

  • 遍历元素
1
2
3
4
5
6
7
deque<int>::iterator it;
for (it = deq.begin(); it != deq.end(); it++)
    cout << *it << endl;
// 或者
for (int i = 0; i < deq.size(); i++) {
    cout << deq.at(i) << endl;
}
  • 元素翻转
1
2
#include <algorithm>
reverse(deq.begin(), deq.end());
  • 元素排序
1
2
3
4
5
6
7
8
9
10
#include <algorithm>
sort(deq.begin(), deq.end()); // 采用的是从小到大的排序

// 如果想从大到小排序，可以采用先排序后反转的方式，也可以采用下面方法:
// 自定义从大到小的比较器，用来改变排序方式
bool Comp(const int& a, const int& b) {
    return a > b;
}

sort(deq.begin(), deq.end(), Comp);

分析

deque是queue，stack，deque等线性容器的底层实现，通过dump工具可以dump出具体的内存结构如下。不难发现在deque中，主要分为三个部分，第一个用于描述map的，其中包含map大小和map的指针，第二个则是指向deque中起始元素的Deque_iterator，第三个则是指向了deque中结束元素的Deque_iterator。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class.std::deque<string> {
    class.std::_Deque_base {
        struct.std::_Deque_base<std::__cxx11::basic_string<char>, std::allocator<std::__cxx11::basic_string<char> > >::_Deque_impl {
            struct.std::_Deque_base<std::__cxx11::basic_string<char>, std::allocator<std::__cxx11::basic_string<char> > >::_Deque_impl_data {
                class.std::__cxx11::basic_string** map;
                uint64_t map_size;
                struct.std::_Deque_iterator {
                    class.std::__cxx11::basic_string* cur;
                    class.std::__cxx11::basic_string* first;
                    class.std::__cxx11::basic_string* last;
                    class.std::__cxx11::basic_string** map;
                } start;
                struct.std::_Deque_iterator {
                    class.std::__cxx11::basic_string* cur;
                    class.std::__cxx11::basic_string* first;
                    class.std::__cxx11::basic_string* last;
                    class.std::__cxx11::basic_string** map;
                } finish;
            } field_0;
        } field_0;
    } field_0;
} field_0;

这里需要注意的是：deque对元素的保存采取了分块保存的机制。deque采用一块连续的内存保存了一系列的指针。其中map即指向这一块连续的内存，换句话说map是一个指针，指向一个指针数组。而这个指针数组中的指针指向的则是一篇连续的，用于实际保存数据的内存区域，我们称为data array(每个元素的大小取决于deque中的模板类型)，具体的内存示意图可以如下图所示。

img

而iterator的结构需要关注的是cur，他将直接指向数据数组中具体的元素，还有就是iterator下的map指针，这个元素则代表当前iterator指向的元素所在区块对应map中地址，last和first则指向data array的起始和结束。因此可以得知start和finish的map并不一定是相同的(即start迭代器指向元素不一定和finish迭代器指向元素处在同一个data array中)，所以iterator在进行迭代的时候是需要根据map跳跃到不同的data array中。

代码分析

纸上得来终觉浅，自己写了一段代码来对应分析

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
#include <iostream>
#include <deque>

using namespace std;

int main(int argc, char* argv[])
{
	deque<int> deq;
	for (int i = 0; i < 6; i++)
	{
		deq.push_back(i);
	}
	for (int i = 6; i < 6+6; i++)
	{
		deq.push_front(i);
	}
	for (int i = 12; i < 12+6; i++)
	{
		deq.push_back(i);
	}
	for (int i = 18; i < 18 + 6; i++)
	{
		deq.push_front(i);
	}
	cout << deq.size() << endl; // 输出：6


	return 0;
}

这里不要用vs的编译器编译，编译出来的库可能和上方的结构不一样，大概是msvc版本问题，用g++或者clang++都可以。下方的例子用的是linux的g++编译得到

image-20230201221327551

运行到初始化结束然后查看结构体

image-20230201221813141

结构和上方分析的图是一样的。此时由于刚刚初始化，可以看到front_map和back_map指向的是一个地方。front和back的start和end指向的内存也是同一段，而且我们可以看到这段内存的长度是0x200

push_back

image-20230201222533649

执行完毕后检查结构体(此处程序崩了重开了一次，不要在意内存和上面不一样的细节)

image-20230201222624850

可以看到上面front的四个元素完全没变，而back的cur发生了改变。双击进入

image-20230201222727072

指向了deque中元素的最后一位的后一位，同时我们可以看到刚刚push_back的元素在cur的低地址处

push_front

image-20230201223029386

照例看结构体

image-20230201223112011

这下是back的四个元素没变，front四个元素全部变了。此处改一下变量名方便观察

首先是front_map

image-20230201223638551

image-20230201223702421

可以看到定位在back_map前一个qword处，且再上面可以看到map的地址，和上方图示的相符

进入front_start

image-20230201223830544

可以看到在back_end的后面16字节处，front_end的地址在start的后0x200字节处，和back的那段一样。

这里发现start开始的内存值为0，可是我们刚刚明明push进了几个值，这是为什么呢，我们进入front_cur地址

image-20230201224100310

发现它是反过来push的，从end往start 存放我们push进来的值。

此处出现一个问题，如果我们再进行一遍刚刚的操作，值会存放到新开的内存还是刚刚的front,back的start和end之间维护的内存呢？

我们直接运行到程序结尾

image-20230201224234413

从结果得知，是会push到刚刚维护的内存中

至此结构清晰了

vector

分析

vector作为常见又方便的stl容器，其实现并不复杂，比上述的deque要简单得多。vector仅仅由三个指针构成：start,finish,end_of_storage。start用于指向数组的第一个元素，而finish指向结束的位置，即最后一个元素后面。而end_of_storage指向当前为vector分配的堆空间的结束地址。

1
2
3
4
5
6
7
8
9
10
11
class.std::vector<string> {
    struct.std::_Vector_base {
        struct.std::_Vector_base<std::__cxx11::basic_string<char>, std::allocator<std::__cxx11::basic_string<char> > >::_Vector_impl {
            struct.std::_Vector_base<std::__cxx11::basic_string<char>, std::allocator<std::__cxx11::basic_string<char> > >::_Vector_impl_data {
                class.std::__cxx11::basic_string* start;
                class.std::__cxx11::basic_string* finish;
                class.std::__cxx11::basic_string* end_of_storage;
            } field_0;
        } field_0;
    } field_0;
} field_0;

为什么需要有一个end_of_storage呢，vector是一个动态的容器，他会根据元素数目分配固定内存，但是当有新的元素加入时，如果分配的固定内存不足以存放新的元素的话，则会进行扩容。因此，这个指针则用于对vector需要扩容时使用(需要注意的是元素的大小取决于模板类型type的大小，因此存在(finish-start)%sizeof(type)==0)。具体的内存示意图可以如下图所示。

img

rb_tree

基础知识

特性如下

（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

注意：
(01) 特性(3)中的叶子节点，是只为空(NIL或null)的节点。
(02) 特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。

img

应用

红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。
例如，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。

分析

rb_tree即红黑树，具体的定义可以去网上翻阅资料，这里并不讨论其具体的实现和算法，仅仅讨论其数据结构在内存中的表示。rb_tree分为两个部分，一个适用于比较的key_compare，另一个则是header。重点分析header，header中存在一个node，和node_count。node即这个红黑树的起始节点，而node_count则代表这颗红黑树拥有多少的节点。node中描述了当前节点的颜色，父亲节点，左儿子和右儿子节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class.std::map<string,string> {
    class.std::_Rb_tree.6 {
        struct.std::_Rb_tree<std::__cxx11::basic_string<char>, std::pair<const std::__cxx11::basic_string<char>, std::__cxx11::basic_string<char> >, std::_Select1st<std::pair<const std::__cxx11::basic_string<char>, std::__cxx11::basic_string<char> > >, std::less<std::__cxx11::basic_string<char> >, std::allocator<std::pair<const std::__cxx11::basic_string<char>, std::__cxx11::basic_string<char> > > >::_Rb_tree_impl {
            struct.std::_Rb_tree_key_compare {
                struct.std::less {
                    uint8_t value;
                } key_compare;
            } compare;
            struct.std::_Rb_tree_header {
                struct.std::_Rb_tree_node_base {
                    uint32_t color;
                    struct.std::_Rb_tree_node_base* parent;
                    struct.std::_Rb_tree_node_base* left;
                    struct.std::_Rb_tree_node_base* right;
                } node;
                uint64_t node_count;
            } field_1;
        } field_0;
    } field_0;
} field_0;

这里需要注意的是，当红黑树中不存在节点时，header中node的parent是0，而left和right则指向node自身。当插入了结点之后，这个parent则会指向树的根节点，而left和right则指向红黑树的最左边的节点和最右边的节点。
img
同时需要分清楚rb_tree变量本身和树本身。rb_tree变量中的node是不携带具体数据元素的，而树本身的节点在其node_base结构体结束后的内存区域则是数据元素。具体的内存示意图如下图所示。
img
map和set的实现皆是基于rb_tree，而唯一不同之处在于set直接在node中存储数据，而map在node中存储的是键值对，是一个pair，而pair<a,b>在内存中的表示则是直接a后存放b。

hashtable

分析

unordered_map和unordered_set的底层是由hashtable实现的。Prime_rehash_policy结构体适用于hashtable的rehash操作的不做分析，这里我们主要需要关注的是buckets，这个指针指向了一个_Hash_node_base*数组，如果指针为null则无效，这些指针数组中的指针指向的是一个链表，可以通过不断的访问next遍历链表中的所有node。bucket_count则表示buckets的大小，而element_count指的当前hashtable中所有的节点数目。默认的hashtable采用取模的方式找到对应的bucket，bucket_count一般为13。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class.std::unordered_map<int, string> {
        class.std::_Hashtable {
                struct.std::__detail::_Hash_node_base** buckets;
                uint64_t bucket_count;
                struct.std::__detail::_Hash_node_base {
                        struct.std::__detail::_Hash_node_base* next;
                } field_2;
                uint64_t element_count;
                struct.std::__detail::_Prime_rehash_policy {
                        float max_load_factor;
                        uint64_t next_resize;
                } field_4;
                struct.std::__detail::_Hash_node_base* field_5;
        } field_0;
} field_0;

因此需要遍历一个hashtable只需要遍历其bucket找到有效的list，并遍历各个list就能找到所有的数据了，类似rb_tree，元素的数据存储与链表结构_Hash_node_base的后面。具体的内存模型如下图所示。
img

string

分析

string的结构比较简单。主要由一个指针ptr和字符串长度string_length构成。除此之外还会存在一个联合体，当字符串的长度小于8时会直接存储与这个缓冲区中，此时ptr指针将指向这个local_buf，大于这个local_buf将会在堆上另外分配内存，此时这个union转而用于存储分配堆的大小。

1
2
3
4
5
6
7
8
9
10
class.std::__cxx11::basic_string {
    struct.std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_Alloc_hider {
        uint8_t* ptr;
    } dataplus;
    uint64_t string_length;
    union.anon {
        uint64_t allocated_capacity;
        uint8_t local_buf[8];
    };
} field_0;

这样设计的目的是方便字符串大小变化的适应，便于实现字符串拼接等工作，且小字符串不用在堆上分配，对速度有少量提升。具体的内存示意图如下图所示，左边的是长度小于8的string。
img