|
STL（Standard Template Library,标准模版库）以模板类和模版函数的形式为程序员提供了各种数据结构和算法的实现，程序员通过利用STL，可以在代码空间、执行时间和编码效率上获得极大的好处。 STL大致可以分为三大类：算法（algorithm）、容器（container）、迭代器（iterator）。 1、vector相关 1.1vector 和 list 的异同？ vector和list是C++中的两种不同的容器类型，用于存储和操作元素的集合。它们有以下区别和应用： 内存结构 Vector: Vector使用连续的内存空间存储元素，类似于数组。它可以高效地进行随机存取，时间复杂度为O(1)。插入和删除操作会导致内存块的拷贝，时间复杂度为O(n)。 List: List使用双向链表来存储元素，内存空间不连续。它的随机存取效率较低，需要遍历链表，时间复杂度为O(n)。但是插入和删除操作非常高效。 容量动态增长： Vector: Vector具有动态增长的能力，当元素数量超过当前容量时，会自动重新分配更大的内存空间，并进行内存拷贝。程序员不需要手动处理容量问题。 List: List没有容量的限制，可以根据需要动态增长。 迭代器的有效性 Vector: 在对Vector进行插入和删除操作后，迭代器可能会失效，需要重新定位。 List: 在对List进行插入和删除操作后，迭代器仍然有效。 查找两者的倒数第二个元素： int mySize = vec.size();vec.at(mySize -2); list不提供随机访问，所以不能用下标直接访问到某个位置的元素，要访问list里的元素只能遍历，不过 你要是只需要访问list的最后N个元素的话，可以用反向迭代器来遍历。 1.2vector 的底层实现？ C++的vector底层通常使用动态分配的数组来实现，即连续的线性空间。下面分别介绍vector的底层实现、扩容机制和insert方法的几种情况： 底层实现：vector内部维护一个指针，指向连续的内存空间，用于存储元素。 初始时，vector会分配一块固定大小的内存空间，可以容纳一定数量的元素。当需要存储更多的元素时，vector会根据扩容机制重新分配更大的内存空间，并将原有元素移动到新的空间中。 扩容机制：vector的扩容是自动进行的，它会在需要添加元素时判断当前空间是否足够。 当空间不足以容纳新元素时，vector会进行扩容操作。扩容通常会分配一块更大的内存空间（例如原空间的两倍大小），将原有元素移动到新空间中，然后释放原空间。 扩容可能涉及到数据的复制或移动，因此会有一定的性能开销。 insert方法的几种情况： vector的insert方法用于在指定位置插入元素，它有多个重载形式，可以根据需要插入单个元素、一定数量的元素或者另一个容器中的元素。 如果插入位置是末尾（end）之前的位置，且当前空间足够容纳新元素，那么插入操作会在指定位置直接插入元素，不会触发扩容，时间复杂度为O(1)。 如果插入位置是末尾（end）之前的位置，但当前空间不足，需要进行扩容操作，那么插入操作会在指定位置插入元素，并触发扩容。扩容操作的时间复杂度为O(n)，其中n为需要插入的元素数量。 如果插入位置是末尾（end）位置，无论当前空间是否足够，插入操作都会在末尾添加元素，不会触发扩容，时间复杂度为O(1)。 如果插入位置是其他位置（非末尾），无论当前空间是否足够，插入操作都需要将插入位置后的元素逐个向后移动，然后在指定位置插入元素，时间复杂度为O(n)，其中n为元素的数量。 void vector::expandCapacity() {
size_t newCapacity = capacity * 2; // 扩容为原大小的两倍
T* newElements = new T[newCapacity]; // 配置新的更大空间
for (size_t i = 0; i < size; i++) {
newElements[i] = elements[i]; // 移动数据到新空间
}
delete[] elements; // 释放原空间
elements = newElements; // 更新指针指向新空间
capacity = newCapacity; // 更新容量
}
1.3vector 中的删除操作？ 向量容器vector的成员函数pop_back()可以删除最后一个元素。pop_back()会将最后一个元素从向量中移除，并且会调整向量的大小，使其减少一个元素。 函数erase()可以删除由一个iterator指向的元素，也可以删除一个指定范围的元素。erase()的用法有多种形式，可以传入一个迭代器指向要删除的元素，或者传入两个迭代器指定要删除的范围。 通用算法remove()并不能直接删除vector容器中的元素。remove()算法是用来移除容器中满足特定条件的元素，并将剩余的元素前移，返回一个指向新的逻辑末尾的迭代器。但是remove()并不会改变容器的大小，它只是移动元素并返回新的逻辑末尾位置，需要结合erase()函数来实际删除元素并改变容器大小。 pop_back()、erase()等成员函数会改变容器的大小，而remove()算法不会直接改变容器的大小，需要结合erase()函数才能删除元素并改变容器的大小。 2、容器指针和引用？ #include <vector>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
// 使用指针指向vector
std::vector<int>* ptr = &vec;
// 通过指针访问容器元素
(*ptr)[0] = 10;
// 通过指针调用容器的成员函数
ptr->push_back(6);
return 0;
}
#include <vector>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
// 使用引用引用vector
std::vector<int>& ref = vec;
// 直接访问容器元素
ref[0] = 10;
// 直接调用容器的成员函数
ref.push_back(6);
return 0;
}
3、STL 中vector删除其中的元素，迭代器如何变化？为什么是两倍扩容？释放空间？ vector的size()函数返回已使用的空间大小，capacity()函数返回总空间大小，而capacity() - size()表示剩余可用空间大小。 当size()和capacity()相等时，表示vector的空间已被用完，如果再添加新元素，则会引发vector空间的动态增长。 使用reserve(n)可以预先分配一块较大的指定大小的内存空间，这样在指定大小的内存空间未被使用完之前，不会引发重新分配内存空间，从而提高效率。只有当n大于capacity()时，调用reserve(n)才会改变vector的容量。 esize()函数只改变元素的数目，不改变vector的容量。 空的vector对象的size()和capacity()都为0。 当空间大小不足时，新分配的空间大小为原空间大小的2倍。 用reserve(size_type)只是扩大capacity值，这些内存空间可能还是“野”的，如果此时使用“[ ]”来访问，则可能会越界。而resize(size_type new_size)会真正使容器具有new_size个对象。
不同编译器下，vector的扩容大小可能有所不同，如在VS中为1.5倍，在GCC中为2倍。这是空间和时间的权衡，增加空间分配可以降低平摊时间复杂度，但也会浪费空间。 使用k=2增长因子的问题在于，每次扩展的新尺寸必然刚好大于之前分配的总和，也就是说，之前分配 的内存空间不可能被使用。这样对内存不友好。最好把增长因子设为(1,2) 采用成倍方式扩容可以保证常数的时间复杂度，而增加指定大小的容量只能达到O(n)的时间复杂度，因此推荐使用成倍的方式进行扩容。使用 reserve() 函数预先分配容量为 10，然后依次向 vector 中插入 20 个元素。 #include <iostream>
#include <vector>
int main() {
std::vector<int> vec;
// 增加指定大小的容量
vec.reserve(10); // 预分配容量为10
for (int i = 0; i < 20; i++) {
vec.push_back(i);
std::cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << std::endl;
}
return 0;
}
Size: 1, Capacity: 10
Size: 2, Capacity: 10
Size: 3, Capacity: 10
Size: 4, Capacity: 10
Size: 5, Capacity: 10
Size: 6, Capacity: 10
Size: 7, Capacity: 10
Size: 8, Capacity: 10
Size: 9, Capacity: 10
Size: 10, Capacity: 10
Size: 11, Capacity: 15
Size: 12, Capacity: 15
Size: 13, Capacity: 15
Size: 14, Capacity: 15
Size: 15, Capacity: 15
Size: 16, Capacity: 22
Size: 17, Capacity: 22
Size: 18, Capacity: 22
Size: 19, Capacity: 22
Size: 20, Capacity: 22
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec;
for (int i = 0; i < 20; i++) {
vec.push_back(i);
std::cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << std::endl;
}
return 0;
}
Size: 1, Capacity: 1
Size: 2, Capacity: 2
Size: 3, Capacity: 3
Size: 4, Capacity: 4
Size: 5, Capacity: 6
Size: 6, Capacity: 6
Size: 7, Capacity: 9
Size: 8, Capacity: 9
Size: 9, Capacity: 9
Size: 10, Capacity: 13
Size: 11, Capacity: 13
Size: 12, Capacity: 13
Size: 13, Capacity: 13
Size: 14, Capacity: 19
Size: 15, Capacity: 19
Size: 16, Capacity: 19
Size: 17, Capacity: 19
Size: 18, Capacity: 19
Size: 19, Capacity: 19
Size: 20, Capacity: 28
vector的内存空间只在析构时才会被系统回收，clear()函数可以清空所有元素，但无法保证内存的回收。如果需要动态缩小空间，可以考虑使用deque，或使用swap()函数来帮助释放内存。 vector(Vec).swap(Vec);
vector().swap(Vec);
vector(Vec).swap(Vec);: 这行代码的作用是清空Vec并释放其内存空间。它通过创建一个临时的vector对象，命名为vector(Vec)，该对象使用了Vec的拷贝构造函数，从而复制了Vec中的元素。接下来，通过调用swap函数，将临时的vector对象与原始的Vec进行交换。由于交换操作会将临时对象的内存空间释放掉，因此这样就清空了Vec并释放了其内存空间。 vector().swap(Vec);: 这行代码的作用也是清空Vec并释放其内存空间。它直接创建了一个临时的匿名vector对象，即vector()，并通过调用swap函数，将临时对象与Vec进行交换。由于临时对象没有任何元素，因此交换后的效果就是将Vec清空并释放其内存空间。 4、容器内部删除一个元素 在顺序容器（如vector、deque）中使用erase()函数删除元素时，被删除的迭代器不仅会失效，而且之后的所有迭代器也会失效（除了list容器）。 因此，不能使用erase(it++)的方式进行迭代器的删除操作。然而，erase()函数会返回被删除元素的下一个有效迭代器，因此可以通过将返回值赋给迭代器来更新迭代器的位置。 std::vector<int> vec = {1, 2, 3, 4, 5};
std::vector<int>::iterator it = vec.begin();
while (it != vec.end()) {
if (*it % 2 == 0) {
it = vec.erase(it); // 删除偶数元素，并将it更新为下一个有效迭代器
} else {
++it; // 移动到下一个元素
}
}
在关联容器（如map、set、multimap、multiset）中使用erase()函数删除元素时，被删除的迭代器失效，但是erase()函数没有返回值（返回void）。因此，可以使用erase(it++)的方式进行迭代器的删除操作。 std::set<int> mySet = {1, 2, 3, 4, 5};
std::set<int>::iterator it = mySet.begin();
while (it != mySet.end()) {
if (*it % 2 == 0) {
mySet.erase(it++); // 删除偶数元素，并将it更新为下一个迭代器
} else {
++it; // 移动到下一个元素
}
}
5、STL 中的迭代器 迭代器是一种抽象的设计理念，它提供了一种遍历容器内部元素的接口，使得我们可以在不了解容器内部原理的情况下对容器进行操作。 迭代器可以看作是容器与STL算法之间的粘合剂，通过迭代器，我们可以将算法应用于不同类型的容器。 迭代器的主要作用是提供遍历容器内部元素的能力。 迭代器内部通常保存有一个与容器相关联的指针（或其他迭代器所需的信息），并重载了一系列运算符，例如*运算符和->运算符，以及前缀和后缀形式的递增（++）和递减（--）运算符等。 这使得我们可以通过迭代器来访问容器中的元素并进行操作。迭代器的设计类似于C++中的智能指针，它们都封装了指针，并提供了方便的操作接口，例如自动释放内存。 在STL中，最常用的迭代器有五种相应的类型，分别是： 这些迭代器的类型特性和支持的操作可能会有所不同，它们适用于不同种类的容器，并提供了不同级别的功能和效率。通过使用这些迭代器，我们可以以统一的方式访问和操作各种容器，使得代码更加灵活和可复用。 6、map、set是怎么实现的，红黑树是怎么能够同时实现这两种容器？ 为什么使用红黑树？ 他们的底层都是以红黑树的结构实现，因此插入删除等操作都在O(logn)时间内完成，因此可以完成高效的插入删除； 在这里我们定义了一个模版参数，如果它是key那么它就是set，如果它是map，那么它就是map；
底层是红黑树，实现map的红黑树的节点数据类型是key+value，而实现set的节点数据类型是value 因为map和set要求是自动排序的，红黑树能够实现这一功能，而且时间复杂度比较低。
7、如何在共享内存上使用stl标准库？ 将STL容器（如map、vector、list等）放入共享内存中可以极大地增强进程间通信的能力。这样做的好处是我们不需要为共享内存设计额外的数据结构，因为STL容器本身已经提供了强大的通用数据结构和内存管理方案。 想象一下，当我们将一个元素插入到STL列表（list）中时，列表容器会自动为其分配内存并保存数据。考虑将STL容器放入共享内存中时，我们不希望容器自己在堆上分配内存，因为这样会导致问题。 一种笨拙的方法是在堆上构造STL容器，然后将容器复制到共享内存中，并确保容器内部分配的内存指向共享内存的相应区域。然而，这几乎是不可能完成的任务。 当进程A在共享内存中放置了多个容器时，进程B如何找到这些容器呢？有几种方法可以实现。 一种方法是进程A将容器放置在共享内存中的确定地址上（固定偏移量），然后进程B可以通过已知的地址来获取容器。另一种改进的方法是，进程A首先在共享内存的某个地址上放置一个map容器，然后进程A创建其他容器，并将它们的名称和地址一并保存到这个map容器中。 进程B知道如何获取保存地址映射的map容器，然后根据名称获取其他容器的地址。 这样，进程B可以通过已知的共享内存地址或者通过map容器来定位和访问进程A放置在共享内存中的容器，实现进程间通信和数据共享。 这种方法充分利用了STL容器的灵活性和可扩展性，并提供了一种方便的机制来管理和访问共享内存中的数据结构。 8、map 插入方式有几种？ 用insert函数插入pair数据， mapStudent.insert(pair<int, string>(1, "student_one")); 用insert函数插入value_type数据 mapStudent.insert(map<int, string>::value_type (1, "student_one")); 在insert函数中使用make_pair()函数 mapStudent.insert(make_pair(1, "student_one")); 用数组方式插入数据 mapStudent[1] = "student_one"; 9、vector越界访问下标，map越界访问下标？vector删除元素时会不会释放空间？ 通过下标访问vector中的元素时不会做边界检查，即便下标越界。也就是说，下标与first迭代器相加的结果超过了finish迭代器的位置，程序也不会报错，而是返回这个地址中存储的值。 如果想在访问vector中的元素时首先进行边界检查，可以使用vector中的at函数。通过使用at函数不但可以通过下标访问vector中的元素，而且在at函数内部会对下标进行边界检查。 map的下标运算符[]的作用是：将key作为下标去执行查找，并返回相应的值；如果不存在这个key，就将一个具有该key和value的键值对插入这个map。 erase()函数，只能删除内容，不能改变容量大小；erase成员函数，它删除了itVect迭代器指向的元素，并且返回要被删除的itVect之后的迭代器，迭代器相当于一个智能指针；clear()函数，只能清空内容，不能改变容量大小。如果要想在删除内容的同时释放内存，那么你可以选择deque容器。 10、map中[]与find的区别？ map的下标运算符[]的作用是：将关键码作为下标去执行查找，并返回对应的值；如果不存在这个关键码，就将一个具有该关键码和值类型的默认值的项插入这个map。 map的find函数用于通过关键码执行查找，如果找到了对应的关键码，则返回该位置的迭代器；如果不存在这个关键码，则返回尾迭代器（end()迭代器）。可以通过判断find函数的返回值与end()迭代器进行比较来确定是否找到了指定的关键码。 11、STL中list与queue之间的区别？ list不再能够像vector一样以普通指针作为迭代器，因为其节点不保证在存储空间中连续存在。由于list是双向链表，其节点可以在内存中的任意位置分布，因此使用普通指针作为迭代器无法准确表示节点的位置。 list的插入操作和删除操作不会造成原有的list迭代器失效。由于list的节点结构不会改变，插入或删除节点并不会影响其他节点的位置，因此在插入和删除操作之后，原有的list迭代器仍然有效。 list不仅是一个双向链表，而且还是一个环状双向链表，所以它只需要一个指针。list的最后一个节点的next指针指向头节点，形成一个环状的链表结构，这样可以方便地在头尾两端进行插入和删除操作。 list不像vector那样在空间不足时进行重新配置和数据移动的操作，因此在插入前的所有迭代器在插入操作之后仍然有效。由于list使用动态分配内存，并且节点的位置可以任意分布，因此在插入操作时并不需要重新分配内存或移动数据。 deque是一种双向开口的连续线性空间，可以在头尾两端进行元素的插入和删除操作。deque允许在起头端和末尾端常数时间内进行元素的插入和删除操作，这是deque和vector的一个重要差异。 deque和vector最大的差异在于，deque允许常数时间内对起头端进行元素的插入或移除操作，而vector只能在尾部进行常数时间内的插入或移除操作。此外，deque是动态地以分段连续空间组合而成的，可以随时增加新的空间段并链接起来，所以没有所谓的容量限制，不需要进行空间保留的操作。 12、常见容器性质总结 vector: 底层数据结构为数组，支持快速随机访问，动态数组。 list: 底层数据结构为双向链表，支持快速增删，不支持随机访问。 deque: 底层数据结构为中央控制器和多个缓冲区，支持首尾快速增删，也支持随机访问。是一个双端队列。 stack: 一般使用list或deque实现，封闭头部即可，用于实现栈的功能。 queue: 一般使用list或deque实现，封闭头部即可，用于实现队列的功能。 priority_queue: 底层数据结构一般为vector，使用堆heap作为处理规则来管理底层容器实现优先队列。 set: 底层数据结构为红黑树，有序，不重复。 multiset: 底层数据结构为红黑树，有序，可重复。 map: 底层数据结构为红黑树，有序，不重复，存储键值对。 multimap: 底层数据结构为红黑树，有序，可重复，存储键值对。 unordered_set: 底层数据结构为哈希表，无序，不重复。 unordered_multiset: 底层数据结构为哈希表，无序，可重复。 unordered_map: 底层数据结构为哈希表，无序，不重复，存储键值对。 unordered_multimap: 底层数据结构为哈希表，无序，可重复，存储键值对。
12.1什么是有序容器？ 在容器中，有序指的是容器中元素的排列顺序与插入顺序或者特定的排序规则相对应。 对于有序容器（如set、map等），它们会维护元素的有序性，这意味着元素在容器中按照一定的顺序排列。具体的排序方式可以是根据元素的比较运算符进行排序（默认是升序），或者通过自定义的比较函数来指定排序规则。 有序容器的特点是： 插入元素时会按照排序规则将元素放置在正确的位置，保持容器的有序性。 元素在容器中的位置是固定的，插入、删除元素不会改变其他元素的相对位置。 通过迭代器遍历有序容器时，可以按照元素的排序顺序逐个访问元素。 需要注意的是，有序容器的有序性是相对于元素的值而言的，而不是插入操作的顺序。因此，如果通过自定义的比较函数或者比较运算符来定义排序规则，那么容器中的元素将按照该规则进行排序，而不是按照插入顺序排列。
另外，还有无序容器（如unordered_set、unordered_map等），它们并不维护元素的有序性，元素在容器中的位置是无序的，主要通过哈希表实现高效的查找和插入操作。 13、STL 中每种容器对应的迭代器 vector：使用随机访问迭代器（Random Access Iterator）。随机访问迭代器允许通过指针算术运算来快速访问容器中的任意元素。 list：使用双向迭代器（Bidirectional Iterator）。双向迭代器支持向前和向后遍历容器中的元素，但不支持随机访问。 deque：使用随机访问迭代器（Random Access Iterator）。与vector相同，deque也支持通过指针算术运算来快速访问容器中的任意元素。 stack 和 queue：它们不提供公开的迭代器接口，因为它们是适配器而不是容器。它们使用底层容器的迭代器来实现功能。 set 和 multiset：使用双向迭代器（Bidirectional Iterator）。双向迭代器允许向前和向后遍历容器中的元素，并保持元素的有序性。 map 和 multimap：使用双向迭代器（Bidirectional Iterator）。类似于set，map和multimap也使用双向迭代器来遍历容器中的元素，同时保持元素的有序性。 unordered_set 和 unordered_multiset：使用正向迭代器（Forward Iterator）。正向迭代器允许向前遍历容器中的元素，但不支持反向遍历。 unordered_map 和 unordered_multimap：使用正向迭代器（Forward Iterator）。与unordered_set类似，unordered_map也使用正向迭代器来遍历容器中的元素。 14、 STL 中 slist 的实现？ list 是双向链表，而 slist（单链表）是单向链表。它们的主要区别在于迭代器的类型，list 使用的是双向迭代器（Bidirectional iterator），而 slist 使用的是单向迭代器（Forward iterator）。双向迭代器可以向前和向后遍历容器中的元素，而单向迭代器只能向前遍历。 
slist 的插入操作通常是将新元素插入到指定位置之前，而不是之后。由于 slist 是单向链表，无法回头，只能向后遍历，因此在其他位置插入或移除元素会很低效。 然而，在 slist 的开头插入或移除元素是高效的，因此 slist 提供了 insert_after() 和 erase_after() 函数来支持在开头进行灵活的操作。
slist 提供了 push_front() 操作，将元素插入到链表的开头。需要注意的是，插入到 slist 中的元素的存储顺序和输入顺序是相反的，即后插入的元素会位于前面。 template <class T, class Allco = alloc>
class slist {
...
private:
...
static list_node* create_node(const value_type& x) {} //配置空间、构造元素
static void destroy_node(list_node* node) {} //析构函数、释放空间
private:
list_node_base head; //头部
public:
iterator begin() {}
iterator end() {}
size_type size() {}
bool empty() {}
void swap(slist& L) {} //交换两个slist，只需要换head即可
reference front() {} //取头部元素
void push_front(const value& x) {} //头部插入元素
void pop_front() {} //从头部取走元素
...
}
#include <forward_list> #include <algorithm> #include <iostream> using namespace std; int main() { forward_list<int> fl; fl.push_front(1); fl.push_front(3); fl.push_front(2); fl.push_front(6); fl.push_front(5); forward_list<int>::iterator ite1 = fl.begin(); forward_list<int>::iterator ite2 = fl.end(); for (; ite1 != ite2; ++ite1) { cout << *ite1 << " "; // 5 6 2 3 1 } cout << endl; ite1 = find(fl.begin(), fl.end(), 2); //寻找2的位置 if (ite1 != ite2) fl.insert_after(ite1, 99); for (auto it : fl) { cout << it << " "; // 5 6 2 99 3 1 } cout << endl; ite1 = find(fl.begin(), fl.end(), 6); //寻找6的位置 if (ite1 != ite2) fl.erase_after(ite1); for (auto it : fl) { cout << it << " "; // 5 6 99 3 1 } cout << endl; return 0; }
15、STL 中list的实现？ list确实是一个双向链表，每个节点包含一个元素和指向前一个节点和后一个节点的指针。与vector相比，list的好处在于插入和删除操作只影响一个元素的空间，因此对于任何位置的元素插入和删除都是常数时间的复杂度。list的迭代器支持双向移动，可以使用"++"和"--"操作来遍历链表。 与vector不同，list的插入和接合操作不会导致原有迭代器失效。这是因为list的节点在存储空间中不一定连续，插入和删除操作只需要调整节点的指针，而不需要移动其他元素。这使得list成为一个非常灵活的容器。 另一个特点是list是一个环形链表，即最后一个节点的指针指向第一个节点，形成一个闭环。这样只需要一个指针便可以完整表示整个链表。list的节点指针始终指向尾部的一个空白节点，所以可以称为“前闭后开”的区间结构。 list的空间管理通常使用alloc作为空间配置器，并提供了list_node_allocator函数用于一次性配置多个节点的空间。由于list的双向特性，它支持在头部和尾部进行push和pop操作。此外，list还提供了其他操作，如erase、splice、sort、merge、reverse等。 总的来说，list是一种非常灵活的容器，适用于需要频繁插入和删除元素的场景，尤其是在元素数量较大时，因为它的插入和删除操作的时间复杂度都是常数时间。 1 template <class T>
2 struct list_node{
3 typedef void* void_pointer;
4 void_pointer prev;
5 void_pointer next;
6 T data; 7 }
16、STL 中set的实现？ set是STL中的关联式容器，它的特点是元素会根据其值自动进行排序，默认情况下是升序排序。set的元素的键值就是实值，实值就是键值，不允许有两个相同的键值存在于set中。 set的迭代器是一种const_iterator，也就是说，它不允许通过迭代器修改元素的值，只能进行读取操作。 标准的STL set使用红黑树（RB-tree）作为底层数据结构来实现。红黑树是一种自平衡的二叉查找树，具有以下特性： 每个节点要么是红色，要么是黑色。 根节点是黑色的。 如果一个节点是红色的，则它的子节点必须是黑色的。 任意节点到其每个叶子节点的路径上包含相同数量的黑色节点。 红黑树的特性保证了树的平衡性，使得set的插入、查找和删除操作的时间复杂度都能保持在对数时间内。 通过调用红黑树的操作行为，set可以实现插入、删除、查找等操作，并且这些操作的行为与红黑树的操作行为相对应。这种将操作委托给底层红黑树的方式使得set的实现更加高效和灵活。 17、STL 中 deque 的实现？ 
vector是单向开口（尾部）的连续线性空间，而deque是双向开口的连续线性空间。虽然vector也可以在头部进行元素操作，但是头部操作的效率较低，因为它需要涉及整体的元素移动。 deque相对于vector的最大差异在于： 对头端进行元素操作的效率都是常数时间，即在头部和尾部插入或删除元素的操作具有较高的效率。 deque没有容量的概念，它是动态地以分段连续空间组合而成的。当需要增加新的空间时，可以配置一段定量的连续空间并连接在头部或尾部，从而实现动态扩展。 需要注意的是，尽管deque也提供了随机访问的迭代器，但它的迭代器并非普通指针，其实现比vector的迭代器复杂。 因此，除非必要，一般情况下推荐使用vector而非deque。如果需要对deque进行排序，可以先将deque中的元素复制到vector中，利用vector的排序算法进行排序，然后再将结果复制回deque中。 由于deque的实现方式，它由一段一段的定量连续空间组成。当需要增加新的空间时，可以通过配置新的连续空间并将其拼接到头部或尾部来实现。因此，deque的主要任务是如何维护这种整体的连续性，以便实现高效的元素操作。 
deque内部通常包含一个指针指向一块称为map的小型连续空间，而map中的每个元素都是一个节点（node）。每个节点都是一个指针，指向另一段较大的连续空间，称为缓冲区（buffer）。实际上，缓冲区是deque中存储数据的区域。 默认情况下，deque的缓冲区大小通常为512字节（具体大小可能有所不同，取决于编译器和实现）。这意味着每个节点所指向的缓冲区可以存储一定数量的元素。 通过使用这种结构，deque能够实现动态扩展，当需要增加新的空间时，它可以分配新的缓冲区，并将新的节点插入到map中。这种设计使得deque能够在两端高效地插入和删除元素，同时保持数据的连续性。 class deque {
// ...
protected:
typedef pointer* map_pointer; // 指向map指针的指针
map_pointer map; // 指向map
size_type map_size; // map的大小
public:
// ...
iterator begin();
iterator end();
// ...
}
这里给大家推荐零声教育全网独家的【Linux C/C++开发】课程体系，通过原理技术+源码分析+案例分析+项目实战，全面解析Linux C/C++，8个上线项目，2W+行手写代码，全面解析：
1、精进基石专栏（一）数据结构与算法 随处可见的红黑树 红黑树的应用场景进程调度cfs，内存管理 红黑树的数学证明与推导 手撕红黑树的左旋与右旋 红黑树添加的实现与添加三种情况的证明 红黑树删除的实现与删除四种情况的证明 红黑树的线程安全的做法 分析红黑树工程实用的特点 磁盘存储链式的B树与B+树 磁盘结构分析与数据存储原理 多叉树的运用以及B树的定义证明 B树插入的两种分裂 B树删除的前后借位与节点合并 手撕B树的插入，删除，遍历，查找 B+树的定义与实现 B+树叶子节点的前后指针 B+树的应用场景与实用特点 B+树的线程安全做法 海量数据去重的abhloriter bitap hash的原理与hash函数的实现 hash的应用场景 分布式hash的实现原理 海量数据去重布隆过滤器 布隆过滤的数学推导与证明
（二）设计模式 创建型设计模式 单例模式 策略模式 观察者模式 工厂方法模式与抽象工厂模式 原型模式 结构型设计模式 适配器模式 代理模式 责任链模式 状态模式 桥接模式 组合模式
（三）c++新特性 （四）Linux工程管理 2、高性能网络设计专栏（一）网络编程异步网络库zvnet 网络io与io多路复用select/poll/epoll socket与文件描述符的关联 多路复用select/poll 代码实现LT/ET的区别 事件驱动reactor的原理与实现 reactor针对业务实现的优点 poll封装send_ cb/recv_ _cb/ accept_ _cb reactor多核实现 跨平台(select/epoll/kqueue)的封装reactor redis，memcached， nginx网 络组件 http服务器的实现 reactor sendbuffer与recvbuffer封装http协议 http协议格式 有限状 态机fsm解析http 其他协议websocket， tcp文件传输
（二）网络原理 服务器百万并发实现(实操) 同步处理与异步处理的数据差异 网络io线程池异步处理 ulimit的fd的百万级别支持 sysctI. conf的rmem与wmem的调优 conntrack的原理分析 Posix API与网络协议栈 connect，listen， accept与三次握 手 listen参数backlog syn泛洪的解决方案 close与四次挥手 11个状态迁移 大量close_ wait与time wait的原因与解决方案 tcp keepalive与 应用层心跳包 拥塞控制与滑动窗口 UDP的可靠传输协议QUIC udp的优缺点 udp高并发的设计方案 qq早期为什么选择udp作为通信协议 udp可靠传输原理 quic协议的设计原理 quic的开源方案quiche kcp的设计方案与算法原理 协程调度器实现与性能测试 调度器的定义分析 超时集合，就绪队列，io等待集合的实现 协程调度的执行流程 协程接口实现，异步流程实现 hook钩子的实现 协程实现mysql请求 协程多核方案分析 协程性能测试
（三）自研框架:基于dpdk的用户态协议栈的实现(已开源) 用户态协议栈设计实现 用户态协议栈的存在场景与实现原理 netmap开源框架 eth协议，ip协议， udp协议实现 arp协议实现 icmp协议实现 应用层posix api的具体实现 socket/bind/listen的实现 accept实现 recv/send的实现 滑动窗口/慢启动讲解 重传定时器，坚持定时器，time_ wait定时器，keepalive定时器 手把手设计实现epoll epoll数据结构封装与线程安全实现 协议栈fd就绪回调实现 epoll接口实现 LT/ET的实现 高性能异步io机制io_ _uring 与epo1l媲美的io_ uring io_ _uring系统调用io_ _uring_ setup， io_ _ur ing_ register， io_ _ur ing_ enter liburng的io_ uring的关系 io_ uring与epoll性能对比 io_ _uring的共享内存机制 io_ uring的使用场景 io_ ur ing的accept， connect， recv， send实现机制 io_ uring网络读写 io_ uring磁盘读写 proactor的实现
3、基础组件设计专栏（一）池式组件 （二）高性能组件 原子操作CAS与锁实现(项目) 互斥锁的使用场景与原理 自旋锁的性能分析 原子操作的汇编实现 无锁消息队列实现(项目) 有锁无锁队列性能 内存屏障Barrier 数组无锁队列设计实现 链表无锁队列设计实现 网络缓冲区设计 RingBuffer设计 定长消息包 ChainBuffer 设计 双缓冲区设计 定时器方案红黑树，时间轮，最小堆(项目) 定时器的使用场景 定时器的红黑树存储 时间轮的实现 最小堆的实现 分布式定时器的实现 手写死锁检测组件(项目) 死锁的现象以及原理 pthread_ _mutex_ lock/pthread_ _mutex_ _unlock dIsym的实现 有向图的构建 有向图dfs判断环的存在 三个原语操作 lock before, lock_ after, unlock_ after 死锁检测线程的实现 手写内存泄漏检测组件(项目) 内存泄漏现象 第三方内存泄漏与代码内存泄漏 malloc与free的dIsym实现 内存检测策略 应用场景测试 手把手实现分布式锁(项目) 多线程资源竞争互斥锁 自旋锁 加锁的异常情况 非公平锁的实现 公平锁的实现
（三）开源组件 4、中间件开发专栏（一）Redis Redis相关命令详解及其原理 string，set， zset， Iist，hash 分布式锁的实现 Lua脚本解决ACID原子性 Redis事务的ACID性质分析 Redis协议与异步方式 Redis协议解析 特殊协议操作订阅发布 手撕异步redis协议 存储原理与数据模型 string的三种编码方 式int, raw, embstr 双向链表的list实现 字典的实现，hash函数 解决键冲突与rehash 跳表的实现 与数据论证 整数集合实现 压缩列表原理证明 主从同步与对象模型 对象的类型与编码 广字符串对象 列表对象 哈希对象 集合对象 有序集合 类型检测与命令多态 内存回收 对象共享 对象空转时长 redis的3种集群方式主从复制，sentinel, cluster 4种持久化方案
（二）MySQL （三）Kafka （四）Nginx Nginx反 向代理与系统参数配置conf原理 Nginx静态文件的配置 Nginx动态接口代理配置 Nginx对Mqtt协议转发 Nginx对Rtmp推拉流 Openresty对Redis缓存数据代理 shmem的三种实现方式 原子操作 nginx channel 信号 信号量 Nginx过滤 器模块实现 Nginx Filter模块运行原理 过滤链表的顺序 模块开发数据结构 ngx_ str_ _t，ngx_ list_ t，ngx_ buf_ t，ngx_ chain_ t error日志的用法 ngx_ comond_ t的讲解 ngx_ http_ _module_ _t的执行流程 文件锁，互斥锁 slab共享内存 如何解决 "惊群”问题 如何实现负载均衡 Nginx Handler模块实现 Nginx Handler模块运行原理: ngx_ module_ t/ngx_ http_ module_ t的讲解 ngx_ http_ top_ body_ filter/ngx_ http_ _top_ header_ filter的 原理 ngx_ rbtree_ t的使用方法 ngx_ rbtree自定义添加方法 Nginx的核心数据结构ngx_ cycle_ t，ngx_ event. _moule_ t http请求的11个处理阶段 http包体处理 http响应发送 Nginx Upstream机制的设计与实现 模块性能测试
5、开源框架专栏（一）游戏服务器开发skynet (录播答疑) Skynet设计原理 多核并发编程-多线程，多进程，csp模型，actor模型 actor模型实现-lua服务和c服务 消息队列实现 actor消息调度 skynet网络层封装以及lua/c接口编程 skynet reactor 网络模型封装 socket/ socketchanne|封装 手撕高性能c服务 lua编程以及lua/c接口编程 skynet重要组件以及手撕游戏项目 基础接口 skynet. send, skynet. cal I, skynet. response 广播组件multicastd 数据共享组件 sharedatad datasheet 手撕万人同时在线游戏
（二）分布式API网关 （三）SPDK助力MySQL数据落盘， 让性能腾飞(基础设施) （四）高性能计算CUDA (录播答疑) gpu并行计算cuda的开发流程 cpu+gpu的异构计算 计算机体系结构中的gpu cuda的环境搭建nvcc 与srun的使用 cuda的向量加法与矩阵乘法 MPI与CUDA 音视频编解码中的并行计算 cuda的h264编解码 cuda的mpeg编解码 ffmpeg的cuda支持
（五）并行计算与异步网络引擎workflow （六）物联网通信协议mqtt的实现框架mosquitto mqtt的高效使用场景 mqtt的 发布订阅模式 解决低带宽网络环境的数据传输 3种Qos等级 0Auth与JWT的安全认证 mctt的broker mqtt的遗嘱机制 发布订阅的过滤器. mosqujitto的docker部暑 matt的日志实时监控
6、云原生专栏（一）Docker Docker风光下的内核功能(录播答疑) 进程namespace UTS namespace IPC namespace 网络namespace 文件系统namesapce cgroup的资源控制 Docker容器管理与镜像操作(录播答疑) Docker镜像下载与镜像运行 Docker存储管理 Docker数据卷 Docker与容器安全 Docker网络管理(项目) 5种Docker网络驱动 pipework跨主机通信 0vS划分vlan与隧道模式 GRE实现跨主机Docker间通信 Docker云与容器编排 (项目) Dockerfile的语法流程 编排神器Fig/Compose FIynn体系 架构 Docker改变了什么?
（二）Kubernetes k8s环境搭建(录播答疑) k8s集群安全设置 k8s集群网络设置 k8s核心服务配置 kubectI命令工具. yam|文件语法 Pod与Service的用法 (录播答疑) Pod的管理配置 Pod升级与回滚 DNS服务之于k8s http 7层策略与TLS安全设置 k8s集群管理的那些事儿(项目) Node的管理 namespace隔离机制 k8s集群日志管理 k8s集群监控 k8s二次开发与k8s API (项目) RESTful接口 API聚合机制 API组 Go访问k8s API
7、性能分析专栏（一）性能与测试工具 （二）观测技术bpf与ebpf 内核bpf的实现原理 跟踪，嗅探，采样，可观测的理解 动态hook: kpr obe/ upr obe 静态hook: tr acepoint和USDT 性能监控计时器PMC模 式 cpu的观测taskset的使 用 BPF工具bpftrace， BCC bpf对内核功 能的观测 内存观测kmalloc与vm_ area_ struct 文件系统观测vfs的状态: 磁盘io的观测bitesize, mdf lush bpf对网络流量的统计 bpf对redis-server观测 网络观测tcp_ connect， tcp_ accept, tcp_ close
（三）内核源码机制 8、分布式架构（一）分布式数据库 （二）分布式文件系统(录播答疑) 内核级支持的分布式存储Ceph ceph的集群部署 monitor与OSD ceph 5个核心组件 ceph集群监控 ceph性能调调优与benchmark 分布式ceph存储集群部署 同步机制 线性扩容 如何实现高可用 负载均衡
（三）分布式协同 注册服务中心Etcd etcd配置服务、服务发现、集群监控、leader选举、 分布式锁 etcd体系结构详解(gRPC， WAL，Snapshot、 BoItDB、 Raft) etcd存储原理深入剖析(B树、B+树) etcd读写机制以及事务的acid特性分析 raft共识算法详解(leader选举+日志复制) 协同事件用户态文件系统fuse (项目) fuse的使用场景 文件系统读写事件 fuse的实现原 理 /dev/fuse的 作用 快播核心技术揭秘P2P框架的实现(录播答疑) 网关NAT表分析 NAT类型，完全锥型NAT，对称NAT,端口限制锥形NAT，IP限制锥型NAT 代码逻辑实现NAT类型检测 网络穿透的原理 网络穿透的3种情况
9、上线项目实战（一）dkvstore实现(上线项目) （二）图床共享云存储(上线项目) 
ceph架构分析和配置 ceph架构分析 快速配置ceph 上传文件逻辑 分析 下载文件逻辑分析 文件传输和接口设计 http接口设计 图床数据库设计 图床文件上传，下载，分享功能实现 业务流程实现 容器化docker部署 crontab定时清理数据 docker server服 务 grpc连接池管理
（三）容器化docker部署 （四）零声教学AI助手一代(上线项目) 
AI助手架构设计与需求分析 chatgpt的构想 与需求分析 基于开源项目初步构建项目 gin框架实现代理服务 接口功能设计 grpc与protobuf的使用流程 token计数器与tokenizer的服务封装 敏感词识别服务 向量数据库与连接池设计 redis实现上下文管理 问题记录保存 web端协议解析 OneBot协议 服务部署上线 docker stack服务部署 wrk接口吞吐量测试 线上节点监控
（五）魔兽世界后端TrinityCore (上线项目) 网络模块实现 boost.asio跨平台网络库 boost. asio核心命名空间以及异步io接口 boost. asio在TrinityCore 中的封装 网络模块应用实践 地图模块实现 地图模块抽象: map、 area、grid、 cell 地图模块驱动方式 A0I 核心算法实现 AABB碰撞检测实现 A*寻路算法实现 战斗模块实现 技能设计以及实 现 Al设计 怪物管理 副本设计 TrinityCore 玩法实现 用户玩法实现-任务系统 数据配置以及数据库设计 触发机制实现 多人玩法实现-工会设计
10、适宜的工程师人群（共分为8大群体）1.从事业务开发多年，对底层原理理解不够深入的在职工程师 2.从事嵌入式方向开发，想转入互联网开发的在职工程师 3. 从事Qt/MFC等桌面开发的，薪资多年涨幅不大的在职工程师 4.从事非开发岗位(算法岗，运维岗，测试岗)，想转后台开发岗位的在职工程师 5.工作中技术没有挑战，工作中接触不到新技术的在职工程师 6.自己研究学习速度较慢，不能系统构建知识体系的开发人员 7.了解很多技术名词，但是深入细问又不理解的工程师 8.计算机相关专业想进入大厂的在校生(本科及以上学历，有c/c++基础)
11、配套书籍资料1. MySQL: 《高性能MySQL 第3版》 2. Nginx: 《深入理解Nginx: 模块开发与架构分析(第2版)》(陶辉） 3. Redis: Redis设计与实现 (黄健宏) 4. Linux内核: 《深入理解Linux内核架构》 (郭旭 译) 5. 数据结构与算法:《算法导论》(第3版) 6.性能分析:《性能之巅洞悉系统、企业与云计算》 7. MongoDB: 《MongoDB权威指南》 8. Ceph: 《Ceph分布式存储学习指南》 (Ceph中国社区) 9. Docker: 《Docker容器 与容器云(第2版)》 10. TCP/IP: 《Tcp/Ip详解卷一卷二卷三》 11. Linux系统编程: 《Unix环境高级编程》 12. 计算机: 《深入理解计算机系统》 13. DPDK: 《深入浅出DPDK》 14. k8s: 《Kubernates权威指南》 龚正等编著 15. bpf: 《BPF之巅洞悉Linux系统和应用性能》
学习成果检验 
  
腾讯offer比例15% 知名企业offer比例73% 最高offer腾讯T3.1(现T9)年薪65w 最高年薪涨幅30W 最快跳槽学习时间1个半月
如果是想在c/c++开发方向得到有效的快速提升（不是所谓的速成），这份学习体系是大家绕不过的具有参考意义的提升路线。从学习路线中可以对c/c++开发方向的技术栈有一个清晰的认识。 还不熟悉的朋友，这里可以先领取一份Linux c/c++开发新手学习资料包（入坑不亏）：
- 编程基本功扎实，掌握 C/C++/JAVA 等开发语言、常用算法和数据结构；
- 熟悉 TCP/UDP 网络协议及相关编程、进程间通讯编程；
- 了解 Python、Shell、Perl 等脚本语言；
- 了解 MYSQL 及 SQL 语言、编程，了解 NoSQL, key-value 存储原理；
- 全面、扎实的软件知识结构，掌握操作系统、软件工程、设计模式、数据结构、数据库系统、网络安全等专业知识；
- 了解分布式系统设计与开发、负载均衡技术，系统容灾设计，高可用系统等知识。
|
