C++ STL容器底层结构及其复杂度分析_c++ stl 的map底层

vector
	1、底层：动态数组。可以自动调整大小。它使用一块连续的内存块来存储元素，可以通过指针运算来快速访问元素。
		当需要扩大容量时，会重新申请一块更大的内存，将原来的元素拷贝到新的内存块中，并释放原来的内存。
		因此，在插入和删除元素时，可能需要移动内存块中的很多元素，导致效率底下，当然，要看实际操作如何。
	2、时间复杂度
		2.1 访问元素O(1)：支持随机访问，也就是可以通过下标或者迭代器直接访问任意位置的元素；指针运算直接获取地址。
		2.2 插入、删除：在末尾插入删除时间复杂度为O(1)，不存在数据的移动；其他地方的情况下，时间复杂度平均为O(n)。
		2.3 扩容O(n)：当容量capcity == size时需要扩容，申请一块新的地址空间，然后将数据拷贝到新的空间中。
			vector容器对象，初始容量默认为0（C++11），如果进行数据添加一次，此时会扩容为1；若是再继续添加就会按照增加一倍的方式继续扩容（2、4、8...）。
		2.4 查找元素O(n)
	3、相关问题
		3.1 vector内部如何实现动态扩容？
			当容量不足以存储新元素时，会分配一个更大的内存块，将原有元素复制到新内存中，并释放原来的空间。新的内存块大小通常为当前容量的2倍数。
		3.2 vector如何避免内存浪费？
			vector采取预留空间的机制，即在未使用完当前容量时，可以预留一定的额外空间，避免不必要的内存重新分配。通过调用reserve(newCapcity)函数可以提前分配好内存块的大小。
		3.3 vector<int>和vector<bool> 的差异是什么？
			vector<int>是将整数类型存储在连续的内存中，每个元素都占用固定字节树。
			vector<bool>实现为位向量，每个元素都只占用一个二进制位，最小化内存占用。
		3.4 vector的迭代器失效情况有哪些？
			当vector进行插入或者删除操作时，可能会导致指向元素的迭代器失效。取决于这些位置是否发生了改变，可能未改变。
		3.5 如何遍历vector元素？
			for(int i = 0; i < vec.size(); i++){}
			for(auto itr = vec.begin(); itr != vec.end(); ++itr){}
			for(auto elem : vec){}
		3.6 vector和array的区别？
			vector是一种动态数组，可以动态增加和删除元素；
			array是一种静态数组，一旦声明之后就无法改变大小。
			此外，由于array是固定大小的，因此可以在栈上分配空间，比堆上分配的vector更快。
		3.7 如何从vector中移除重复元素？
			使用算法中的unique()函数，会将相邻的重复元素移动到容器尾部，并返回新的尾后迭代器，然后可以借助这个返回值，删除这个元素元素。
					vector<int> ints;
					ints.push_back(1);
					ints.push_back(2);
					ints.push_back(2);
					ints.push_back(2);
					ints.push_back(3);
					ints.push_back(5);
					

					auto last = unique(ints.begin(), ints.end());
					ints.erase(last, ints.end());
					for (auto i : ints)
					{
						cout << i << "\t";	//1 2 3 5
					}


​	

list
	1、底层：双向链表，即每个节点都包含指向前驱和后继节点的指针。与vector不同，list的元素在内存中不是连续存储的，因此可以高效的插入或者删除任意位置的元素。
	2、时间复杂度
		bool empty() const：								判断 list 是否为空，O(1)
		size_type size() const：							返回 list 的大小，O(1)
		void resize(size_type sz, T c = T())：				调整 list 大小为 sz，新增的元素使用值 c 初始化，O(n)
		void clear()：										清空 list，O(n)
		reference front()，const_reference front() const：	返回第一个元素的引用，O(1)
		reference back()，const_reference back() const：	返回最后一个元素的引用，O(1)
		void push_front(const T& x)：						在头部插入元素 x，O(1)
		void push_back(const T& x)：						在尾部插入元素 x，O(1)
		void pop_front()：									删除头部元素，O(1)
		void pop_back()：									删除尾部元素，O(1)
		iterator insert(iterator position, const T& x)：	在 position 前面插入元素 x，O(1)
		iterator erase(iterator position)：					删除 position 指向的元素，O(1)

		void remove(const T& val)：							删除所有值为 val 的元素，O(n)
		void reverse()：									反转 list，O(n)
		void unique()：										删除相邻重复的元素，O(n)
		void sort()：										使用默认排序规则（operator<）对 list 进行排序，O(n log n)
	
		bool operator==(const list& rhs) const：			判断两个 list 是否相等，O(n)
		bool operator!=(const list& rhs) const：			判断两个 list 是否不相等，O(n)
		总体来说，list 在插入、删除、反转、查找等操作方面表现优秀，而在随机访问和排序方面则不如 vector 表现。
	3、相关面试题
		3.1 与vector相比，list有什么优点？
			主要优点是支持高效地在任何位置添加或者删除节点元素，不会导致迭代器失效；
			缺点是不支持随机访问，只能通过迭代器来访问元素，另外，空间占用较大。

​	
deque（双端队列double-ended queue）
	1、底层：一个或者多个连续地存储块，每个存储块内部是一个固定大小地数组。当deque容量不足时，会分配新的存储块（内存图见下面）。
    		这种设计使得deque可以在两端进行常数时间复杂度的插入和删除操作O(1)；在中间进行线性时间复杂度的插入和删除操作O(n)。
    2、时间复杂度
    	2.1 头插尾插、头删尾删：O(1)
    	2.2 访问头元素和尾元素O(1)
    	2.3 在指定位置插入元素O(n)
    	总的来说，deque的优点在于支持高效的在两端进行插入和删除操作。但是如果存储块过多会导致性能下降，可用其他容器替代。
    3、关于存储块
    	如果一个deque中的一个存储块中的数据被清空了，这个存储块还是会存在着，并占据一定空间。这是因为deque的实现通常由多个存储块组成，每个存储块都会被分配一定空间。即使一个存储块中的数据被删除了，这个存储块仍然会存在不会立即回收这些空闲存储块，只是变成了空闲状态。以备后续继续添加数据，避免频繁元素数据数量变动进行存储块的分配和释放操作。
    	一般情况下，当deque中的元素数量减少到某一定程度，实现会将多余的存储块释放掉，从而减少内存的占用，这个阈值可以是固定的也可以动态调整。
    4、相关问题
    	4.1 deque优势在哪？
    		它是一种双端队列容器，可以在队列的两端进行快速插入和删除。与vector相比，deque的插入和删除操作的时间复杂度更加稳定，不受插入和删除位置的影像。同时，deque支持随机访问和迭代器操作，可以快速定位元素，但是相比于vector的快速定位会更慢些。
    	4.2 deque和vector区别？
    		底层数据结构：vector使用连续内存块存储元素，而deque使用多个固定大小的存储块组成的双向链表存储元素。
    		插入和删除操作：vector时间复杂度为O(n)，除了尾部操作（O(1)）.deque两端操作为O(1)。
    		迭代器失效：对于vector在插入和删除时，迭代器可能会失效；而deque只有在删除中间元素时，迭代器才会失效。
    	4.3 使用场景
    		需要在两端进行频繁插入和删除操作。
    		需要对大量元素进行随机访问。
    		当元素数量较大时，使用deque可以避免vector的内存管理问题和迭代器失效问题。
​	
set
    1、介绍：一种关联容器，其中的元素按照一定的排序规则进行排序，并且每个元素只出现一次。因此可以使用set进行元素的查找和去重操作。
    2、底层：红黑树结构，红黑树是一种自平衡的二叉查找树，相对于平衡二叉树性能更优。可以理解为平衡二叉树是对二叉排序树的优化，红黑树是对平衡二叉树的优化，在自平衡上提高了性能。
    3、时间复杂度
    	3.1 插入元素(自排序)：O(logn)
    	3.2 删除元素：O(logn)
    	3.3 查找元素：O(logn)
    	3.4 遍历：O(n)
    4、排序
    	set中的元素可以按照元素类型的默认排序规则进行排序，也可以通过自定义比较函数来指定排序规则。对于基本数据类型，按照元素从小到大排序；自定义类型，可以重载运算符(<)或者传入自定义比较函数(在模板中指定存放数据的类型时，也可以再加一个指定比较函数所在的结构体类型)。
    
​  
multiset：同set红黑树结构，只是允许数据相同，不会去重。

​
unordered_set
    1、介绍：是哈希表实现，提供了快速的元素查找、插入、删除等操作。
    2、底层：unordered_set底层使用了哈希表，一种根据关键字直接访问内存存储位置的数据结构，因此具被非常快的查找和插入速度。内部维护了一个动态数组和一个哈希表，哈希表中存储着指向动态数组中元素的指针。每个元素的位置是由哈希函数计算出来的，不同的元素可能会被映射到同一个位置上，因此哈希表中的每个元素都是一个链表，用于解决冲突。
    3、插入流程介绍：
    	有元素插入，根据该元素计算出该元素的哈希值，这个哈希值直接定位到内存地址，也就是上面动态数组中的位置（桶）；
    	如果该位置不存在任何元素，那么就插入；
    	但是，哈希函数表示绝对完美的，可能会出现多个元素映射到同一个地址，此时，会在桶中维护一个链表，将哈希值相同的元素存储在同一个链表中。这种情况下，若是冲突过多，查找效率会变低。
    4、时间复杂度
    	4.1 插入：O(1); 最坏O(n)，也就是所有元素全部映射到一个地址。
    	4.2 删除：O(1)；最坏O(n)
    	4.3 查找：O(1)；最坏O(n)
    	4.3 遍历：O(n)
    5、特点：
    	5.1 元素无序
    	5.2 不允许有重复元素，会去重
    	5.3 可以自定义哈希函数，用来计算元素的哈希值。在自定义类型中就需要自定义哈希函数，用于比较两个元素时候相同。
	6、相关问题
    	6.1 实现原理是什么？
    		通过哈希表实现，具体来说是一个数组，每个数组元素都是一个链表。当要插入或者查找元素时，首先根据元素的哈希值得到它在数组中的位置，然后在对应链表中进行操作。
    	6.2 使用场景？
    		适用于需要快速查找和插入元素的场景，因为哈希表的查找和插入复杂度都是常数级别。
    	6.3 为什么unordered_set的迭代器只支持前向迭代器？
    		因为底层是哈希表，每个桶中可能有多个元素，采用链表或者红黑树来解决哈希冲突。每个桶内的元素是无序的，不会按照用户的插入顺序存放，因此只能向前遍历每个桶中的元素。此外，内部的存储结构可能随时变化，因此迭代器的递增过程也比较复杂，只能实现向前遍历。

​
map
    1、介绍：是一个关联容器，用于存储键值对，其中的键和值都可以是任何类型。每个键在map中都是唯一的，内部采用红黑树实现。
    2、底层：底层使用红黑树实现，每个节点包含一个键值对pair，按照键值关系构建一颗二叉查找树。
    3、时间复杂度：
    	插入、删除、查找 ： O(logn); 遍历O(n)
    	虽然能够自平衡，但是在极端情况下会退化为链表，比如插入的数据有序。
    4、特性：
    	类似于set，根据键自动排序；可自定义比较函数。如果插入键相同的元素，那么之前的值会被替换成新插入的。
    5、相关问题
    	5.1 Map 和 unordered_map 的区别是什么?
    		Map 和 unordered_map 都是 C++ 中的关联式容器，它们的区别在于底层的实现方式不同。Map 使用红黑树来实现，而 unordered_map 使用哈希表来实现。因此，在大多数情况下，unordered_map 的查找和插入操作比 Map 更快，但是在某些情况下，Map 的性能可能会更好。

​
multimap：基本同map，但是可以插入键相同的元素。

​    
unordered_map（底层类似于unordered_set)
    	1、介绍： unordered_map（无序映射）是一种关联容器，用于存储由键值对组成的元素。它使用哈希表作为底层实现，可以实现常数时间内的查找、插入和删除操作，因此在需要快速访问元素的场景中很有用。
    	2、底层：unordered_map 的底层实现是哈希表，哈希表是一种通过哈希函数将键映射到值的数据结构。哈希表通常包含一个数组，每个元素都是一个桶，桶中存放着哈希值相同的键值对。
    	3、时间复杂度
    		查找一个元素（operator[]、at、find）：平均时间复杂度为 O(1)，最坏情况下为 O(n)；
            插入一个元素（insert）：平均时间复杂度为 O(1)，最坏情况下为 O(n)；
            删除一个元素（erase）：平均时间复杂度为 O(1)，最坏情况下为 O(n)；
            遍历所有元素（begin/end/for）：时间复杂度为 O(n)。
    	4、相关问题
   			4.1 unordered_map 是如何实现的？
                unordered_map 通常是使用哈希表实现的，它的键和值都存储在桶中。哈希表将键映射到桶中，这是通过哈希函数计算出来的。当多个键被映射到同一个桶时，它们存储在链表中。当链表变得太长时，它们被转换为更高效的数据结构，如红黑树。
       		4.2 unordered_map 的底层数据结构是什么？
       		   unordered_map 的底层数据结构是哈希表，具体实现可能会有所不同，但通常包括一个桶数组和一个哈希函数。
        	4.3 unordered_map 的时间复杂度是什么？
       		   在平均情况下，unordered_map 的插入、删除和查找操作的时间复杂度都是 O(1)，但在最坏情况下，这些操作的时间复杂度会退化到 O(n)。这是因为如果哈希函数产生的哈希冲突太多，就会导致链表变得非常长，降低了效率。

​
stack
    1、介绍：一种先进后出的容器，即栈。
    2、底层使用deque进行二次封装。因此它也可以动态扩容。

​
queue
    1、介绍：是一种先进先出的数据结构。队列容器在任务队列、消息队列等应用中非常常见。
    2、底层：通常使用deque作为其底层数据结构来实现。但是queue是不支持随机访问的。

​
array
    1、底层：底层是C++的普通数组，是固定大小的。初始化时需要指定大小
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187

deque内存图