|
STL（Standard Template Library,標(biāo)準(zhǔn)模版庫）以模板類和模版函數(shù)的形式為程序員提供了各種數(shù)據(jù)結(jié)構(gòu)和算法的實現(xiàn),，程序員通過利用STL，可以在代碼空間,、執(zhí)行時間和編碼效率上獲得極大的好處,。 STL大致可以分為三大類：算法（algorithm）、容器（container）,、迭代器（iterator）,。 1,、vector相關(guān) 1.1vector 和 list 的異同？ vector和list是C++中的兩種不同的容器類型,，用于存儲和操作元素的集合,。它們有以下區(qū)別和應(yīng)用： 內(nèi)存結(jié)構(gòu) Vector: Vector使用連續(xù)的內(nèi)存空間存儲元素，類似于數(shù)組,。它可以高效地進(jìn)行隨機存取,，時間復(fù)雜度為O(1)。插入和刪除操作會導(dǎo)致內(nèi)存塊的拷貝,，時間復(fù)雜度為O(n),。 List: List使用雙向鏈表來存儲元素，內(nèi)存空間不連續(xù),。它的隨機存取效率較低,，需要遍歷鏈表，時間復(fù)雜度為O(n),。但是插入和刪除操作非常高效,。 容量動態(tài)增長： Vector: Vector具有動態(tài)增長的能力，當(dāng)元素數(shù)量超過當(dāng)前容量時,，會自動重新分配更大的內(nèi)存空間,，并進(jìn)行內(nèi)存拷貝。程序員不需要手動處理容量問題,。 List: List沒有容量的限制,，可以根據(jù)需要動態(tài)增長。 迭代器的有效性 Vector: 在對Vector進(jìn)行插入和刪除操作后,，迭代器可能會失效,，需要重新定位。 List: 在對List進(jìn)行插入和刪除操作后,，迭代器仍然有效,。 查找兩者的倒數(shù)第二個元素： int mySize = vec.size();vec.at(mySize -2); list不提供隨機訪問，所以不能用下標(biāo)直接訪問到某個位置的元素,，要訪問list里的元素只能遍歷,，不過 你要是只需要訪問list的最后N個元素的話，可以用反向迭代器來遍歷,。 1.2vector 的底層實現(xiàn),？ C++的vector底層通常使用動態(tài)分配的數(shù)組來實現(xiàn)，即連續(xù)的線性空間,。下面分別介紹vector的底層實現(xiàn),、擴容機制和insert方法的幾種情況： 底層實現(xiàn)：vector內(nèi)部維護(hù)一個指針，指向連續(xù)的內(nèi)存空間,，用于存儲元素,。 初始時,，vector會分配一塊固定大小的內(nèi)存空間，可以容納一定數(shù)量的元素,。當(dāng)需要存儲更多的元素時,，vector會根據(jù)擴容機制重新分配更大的內(nèi)存空間，并將原有元素移動到新的空間中,。 擴容機制：vector的擴容是自動進(jìn)行的,，它會在需要添加元素時判斷當(dāng)前空間是否足夠。 當(dāng)空間不足以容納新元素時,，vector會進(jìn)行擴容操作,。擴容通常會分配一塊更大的內(nèi)存空間（例如原空間的兩倍大小）,，將原有元素移動到新空間中,，然后釋放原空間。 擴容可能涉及到數(shù)據(jù)的復(fù)制或移動,，因此會有一定的性能開銷,。 insert方法的幾種情況： vector的insert方法用于在指定位置插入元素，它有多個重載形式,，可以根據(jù)需要插入單個元素,、一定數(shù)量的元素或者另一個容器中的元素。 如果插入位置是末尾（end）之前的位置,，且當(dāng)前空間足夠容納新元素,，那么插入操作會在指定位置直接插入元素，不會觸發(fā)擴容,，時間復(fù)雜度為O(1),。 如果插入位置是末尾（end）之前的位置，但當(dāng)前空間不足,，需要進(jìn)行擴容操作,，那么插入操作會在指定位置插入元素，并觸發(fā)擴容,。擴容操作的時間復(fù)雜度為O(n),，其中n為需要插入的元素數(shù)量。 如果插入位置是末尾（end）位置,，無論當(dāng)前空間是否足夠,，插入操作都會在末尾添加元素，不會觸發(fā)擴容,，時間復(fù)雜度為O(1),。 如果插入位置是其他位置（非末尾）,，無論當(dāng)前空間是否足夠,，插入操作都需要將插入位置后的元素逐個向后移動,，然后在指定位置插入元素，時間復(fù)雜度為O(n),，其中n為元素的數(shù)量,。 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]; // 移動數(shù)據(jù)到新空間
}
delete[] elements; // 釋放原空間
elements = newElements; // 更新指針指向新空間
capacity = newCapacity; // 更新容量
}
1.3vector 中的刪除操作？ 向量容器vector的成員函數(shù)pop_back()可以刪除最后一個元素,。pop_back()會將最后一個元素從向量中移除,，并且會調(diào)整向量的大小，使其減少一個元素,。 函數(shù)erase()可以刪除由一個iterator指向的元素,，也可以刪除一個指定范圍的元素。erase()的用法有多種形式,，可以傳入一個迭代器指向要刪除的元素,，或者傳入兩個迭代器指定要刪除的范圍。 通用算法remove()并不能直接刪除vector容器中的元素,。remove()算法是用來移除容器中滿足特定條件的元素,，并將剩余的元素前移，返回一個指向新的邏輯末尾的迭代器,。但是remove()并不會改變?nèi)萜鞯拇笮?，它只是移動元素并返回新的邏輯末尾位置，需要結(jié)合erase()函數(shù)來實際刪除元素并改變?nèi)萜鞔笮 ?/p> pop_back(),、erase()等成員函數(shù)會改變?nèi)萜鞯拇笮?，而remove()算法不會直接改變?nèi)萜鞯拇笮。枰Y(jié)合erase()函數(shù)才能刪除元素并改變?nèi)萜鞯拇笮 ?/p> 2,、容器指針和引用,？ #include <vector>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
// 使用指針指向vector
std::vector<int>* ptr = &vec;
// 通過指針訪問容器元素
(*ptr)[0] = 10;
// 通過指針調(diào)用容器的成員函數(shù)
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;
// 直接調(diào)用容器的成員函數(shù)
ref.push_back(6);
return 0;
}
3、STL 中vector刪除其中的元素,，迭代器如何變化,？為什么是兩倍擴容？釋放空間,？ vector的size()函數(shù)返回已使用的空間大小,，capacity()函數(shù)返回總空間大小，而capacity() - size()表示剩余可用空間大小,。 當(dāng)size()和capacity()相等時,，表示vector的空間已被用完，如果再添加新元素,，則會引發(fā)vector空間的動態(tài)增長,。 使用reserve(n)可以預(yù)先分配一塊較大的指定大小的內(nèi)存空間，這樣在指定大小的內(nèi)存空間未被使用完之前，不會引發(fā)重新分配內(nèi)存空間,，從而提高效率,。只有當(dāng)n大于capacity()時，調(diào)用reserve(n)才會改變vector的容量,。 esize()函數(shù)只改變元素的數(shù)目,，不改變vector的容量。 空的vector對象的size()和capacity()都為0,。 當(dāng)空間大小不足時,，新分配的空間大小為原空間大小的2倍。 用reserve(size_type)只是擴大capacity值,，這些內(nèi)存空間可能還是“野”的,，如果此時使用“[ ]”來訪問，則可能會越界,。而resize(size_type new_size)會真正使容器具有new_size個對象,。
不同編譯器下，vector的擴容大小可能有所不同,，如在VS中為1.5倍,，在GCC中為2倍。這是空間和時間的權(quán)衡,，增加空間分配可以降低平攤時間復(fù)雜度,，但也會浪費空間。 使用k=2增長因子的問題在于,，每次擴展的新尺寸必然剛好大于之前分配的總和,，也就是說，之前分配 的內(nèi)存空間不可能被使用,。這樣對內(nèi)存不友好,。最好把增長因子設(shè)為(1,2) 采用成倍方式擴容可以保證常數(shù)的時間復(fù)雜度，而增加指定大小的容量只能達(dá)到O(n)的時間復(fù)雜度,，因此推薦使用成倍的方式進(jìn)行擴容,。使用 reserve() 函數(shù)預(yù)先分配容量為 10,，然后依次向 vector 中插入 20 個元素。 #include <iostream>
#include <vector>
int main() {
std::vector<int> vec;
// 增加指定大小的容量
vec.reserve(10); // 預(yù)分配容量為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的內(nèi)存空間只在析構(gòu)時才會被系統(tǒng)回收，clear()函數(shù)可以清空所有元素，但無法保證內(nèi)存的回收。如果需要動態(tài)縮小空間,，可以考慮使用deque,，或使用swap()函數(shù)來幫助釋放內(nèi)存。 vector(Vec).swap(Vec);
vector().swap(Vec);
vector(Vec).swap(Vec);: 這行代碼的作用是清空Vec并釋放其內(nèi)存空間,。它通過創(chuàng)建一個臨時的vector對象,，命名為vector(Vec),，該對象使用了Vec的拷貝構(gòu)造函數(shù)，從而復(fù)制了Vec中的元素。接下來,，通過調(diào)用swap函數(shù),，將臨時的vector對象與原始的Vec進(jìn)行交換,。由于交換操作會將臨時對象的內(nèi)存空間釋放掉，因此這樣就清空了Vec并釋放了其內(nèi)存空間,。 vector().swap(Vec);: 這行代碼的作用也是清空Vec并釋放其內(nèi)存空間,。它直接創(chuàng)建了一個臨時的匿名vector對象，即vector(),，并通過調(diào)用swap函數(shù),，將臨時對象與Vec進(jìn)行交換。由于臨時對象沒有任何元素,，因此交換后的效果就是將Vec清空并釋放其內(nèi)存空間,。 4、容器內(nèi)部刪除一個元素 在順序容器（如vector,、deque）中使用erase()函數(shù)刪除元素時,，被刪除的迭代器不僅會失效，而且之后的所有迭代器也會失效（除了list容器）,。 因此,，不能使用erase(it++)的方式進(jìn)行迭代器的刪除操作。然而,，erase()函數(shù)會返回被刪除元素的下一個有效迭代器,，因此可以通過將返回值賦給迭代器來更新迭代器的位置,。 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); // 刪除偶數(shù)元素,，并將it更新為下一個有效迭代器
} else {
++it; // 移動到下一個元素
}
}
在關(guān)聯(lián)容器（如map、set,、multimap,、multiset）中使用erase()函數(shù)刪除元素時，被刪除的迭代器失效,，但是erase()函數(shù)沒有返回值（返回void）,。因此，可以使用erase(it++)的方式進(jìn)行迭代器的刪除操作,。 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++); // 刪除偶數(shù)元素,，并將it更新為下一個迭代器
} else {
++it; // 移動到下一個元素
}
}
5、STL 中的迭代器 迭代器是一種抽象的設(shè)計理念,，它提供了一種遍歷容器內(nèi)部元素的接口,，使得我們可以在不了解容器內(nèi)部原理的情況下對容器進(jìn)行操作。 迭代器可以看作是容器與STL算法之間的粘合劑,，通過迭代器,，我們可以將算法應(yīng)用于不同類型的容器。 迭代器的主要作用是提供遍歷容器內(nèi)部元素的能力,。 迭代器內(nèi)部通常保存有一個與容器相關(guān)聯(lián)的指針（或其他迭代器所需的信息）,，并重載了一系列運算符,，例如*運算符和->運算符，以及前綴和后綴形式的遞增（++）和遞減（--）運算符等,。 這使得我們可以通過迭代器來訪問容器中的元素并進(jìn)行操作,。迭代器的設(shè)計類似于C++中的智能指針，它們都封裝了指針,，并提供了方便的操作接口,，例如自動釋放內(nèi)存。 在STL中,，最常用的迭代器有五種相應(yīng)的類型,，分別是： value type：迭代器所指向元素的類型。 difference type：表示兩個迭代器之間的距離,，通常是一個帶符號整數(shù)類型,。 pointer：指向迭代器所指向元素的指針類型。 reference：迭代器所指向元素的引用類型,。 iterator category：迭代器的類型標(biāo)簽,，用于標(biāo)識迭代器的特性和支持的操作，例如輸入迭代器,、輸出迭代器,、前向迭代器、雙向迭代器和隨機訪問迭代器,。
這些迭代器的類型特性和支持的操作可能會有所不同,，它們適用于不同種類的容器，并提供了不同級別的功能和效率,。通過使用這些迭代器,，我們可以以統(tǒng)一的方式訪問和操作各種容器，使得代碼更加靈活和可復(fù)用,。 6,、map、set是怎么實現(xiàn)的,，紅黑樹是怎么能夠同時實現(xiàn)這兩種容器,？ 為什么使用紅黑樹？ 他們的底層都是以紅黑樹的結(jié)構(gòu)實現(xiàn),，因此插入刪除等操作都在O(logn)時間內(nèi)完成,，因此可以完成高效的插入刪除； 在這里我們定義了一個模版參數(shù),，如果它是key那么它就是set,，如果它是map，那么它就是map,；
底層是紅黑樹,，實現(xiàn)map的紅黑樹的節(jié)點數(shù)據(jù)類型是key+value,，而實現(xiàn)set的節(jié)點數(shù)據(jù)類型是value 因為map和set要求是自動排序的，紅黑樹能夠?qū)崿F(xiàn)這一功能,，而且時間復(fù)雜度比較低,。
7、如何在共享內(nèi)存上使用stl標(biāo)準(zhǔn)庫,？ 將STL容器（如map,、vector,、list等）放入共享內(nèi)存中可以極大地增強進(jìn)程間通信的能力,。這樣做的好處是我們不需要為共享內(nèi)存設(shè)計額外的數(shù)據(jù)結(jié)構(gòu),，因為STL容器本身已經(jīng)提供了強大的通用數(shù)據(jù)結(jié)構(gòu)和內(nèi)存管理方案。 想象一下,，當(dāng)我們將一個元素插入到STL列表（list）中時,，列表容器會自動為其分配內(nèi)存并保存數(shù)據(jù)?？紤]將STL容器放入共享內(nèi)存中時,，我們不希望容器自己在堆上分配內(nèi)存，因為這樣會導(dǎo)致問題,。 一種笨拙的方法是在堆上構(gòu)造STL容器,，然后將容器復(fù)制到共享內(nèi)存中，并確保容器內(nèi)部分配的內(nèi)存指向共享內(nèi)存的相應(yīng)區(qū)域,。然而,，這幾乎是不可能完成的任務(wù)。 當(dāng)進(jìn)程A在共享內(nèi)存中放置了多個容器時,，進(jìn)程B如何找到這些容器呢,？有幾種方法可以實現(xiàn)。 一種方法是進(jìn)程A將容器放置在共享內(nèi)存中的確定地址上（固定偏移量）,，然后進(jìn)程B可以通過已知的地址來獲取容器。另一種改進(jìn)的方法是,，進(jìn)程A首先在共享內(nèi)存的某個地址上放置一個map容器,，然后進(jìn)程A創(chuàng)建其他容器，并將它們的名稱和地址一并保存到這個map容器中,。 進(jìn)程B知道如何獲取保存地址映射的map容器,，然后根據(jù)名稱獲取其他容器的地址。 這樣,，進(jìn)程B可以通過已知的共享內(nèi)存地址或者通過map容器來定位和訪問進(jìn)程A放置在共享內(nèi)存中的容器,，實現(xiàn)進(jìn)程間通信和數(shù)據(jù)共享。 這種方法充分利用了STL容器的靈活性和可擴展性,，并提供了一種方便的機制來管理和訪問共享內(nèi)存中的數(shù)據(jù)結(jié)構(gòu),。 8,、map 插入方式有幾種？ 用insert函數(shù)插入pair數(shù)據(jù),， mapStudent.insert(pair<int, string>(1, "student_one")); 用insert函數(shù)插入value_type數(shù)據(jù) mapStudent.insert(map<int, string>::value_type (1, "student_one")); 在insert函數(shù)中使用make_pair()函數(shù) mapStudent.insert(make_pair(1, "student_one")); 用數(shù)組方式插入數(shù)據(jù) mapStudent[1] = "student_one"; 9,、vector越界訪問下標(biāo)，map越界訪問下標(biāo),？vector刪除元素時會不會釋放空間,？ 通過下標(biāo)訪問vector中的元素時不會做邊界檢查，即便下標(biāo)越界,。也就是說,，下標(biāo)與first迭代器相加的結(jié)果超過了finish迭代器的位置，程序也不會報錯,，而是返回這個地址中存儲的值,。 如果想在訪問vector中的元素時首先進(jìn)行邊界檢查，可以使用vector中的at函數(shù),。通過使用at函數(shù)不但可以通過下標(biāo)訪問vector中的元素,，而且在at函數(shù)內(nèi)部會對下標(biāo)進(jìn)行邊界檢查。 map的下標(biāo)運算符[]的作用是：將key作為下標(biāo)去執(zhí)行查找,，并返回相應(yīng)的值,；如果不存在這個key，就將一個具有該key和value的鍵值對插入這個map,。 erase()函數(shù),，只能刪除內(nèi)容，不能改變?nèi)萘看笮,?；erase成員函數(shù)，它刪除了itVect迭代器指向的元素,，并且返回要被刪除的itVect之后的迭代器,，迭代器相當(dāng)于一個智能指針；clear()函數(shù),，只能清空內(nèi)容,，不能改變?nèi)萘看笮 Ｈ绻朐趧h除內(nèi)容的同時釋放內(nèi)存,，那么你可以選擇deque容器,。 10、map中[]與?nd的區(qū)別,？ map的下標(biāo)運算符[]的作用是：將關(guān)鍵碼作為下標(biāo)去執(zhí)行查找,，并返回對應(yīng)的值；如果不存在這個關(guān)鍵碼，就將一個具有該關(guān)鍵碼和值類型的默認(rèn)值的項插入這個map,。 map的find函數(shù)用于通過關(guān)鍵碼執(zhí)行查找,，如果找到了對應(yīng)的關(guān)鍵碼，則返回該位置的迭代器,；如果不存在這個關(guān)鍵碼,，則返回尾迭代器（end()迭代器）?？梢酝ㄟ^判斷find函數(shù)的返回值與end()迭代器進(jìn)行比較來確定是否找到了指定的關(guān)鍵碼,。 11、STL中l(wèi)ist與queue之間的區(qū)別,？ list不再能夠像vector一樣以普通指針作為迭代器,，因為其節(jié)點不保證在存儲空間中連續(xù)存在。由于list是雙向鏈表,，其節(jié)點可以在內(nèi)存中的任意位置分布,，因此使用普通指針作為迭代器無法準(zhǔn)確表示節(jié)點的位置。 list的插入操作和刪除操作不會造成原有的list迭代器失效,。由于list的節(jié)點結(jié)構(gòu)不會改變,，插入或刪除節(jié)點并不會影響其他節(jié)點的位置，因此在插入和刪除操作之后,，原有的list迭代器仍然有效,。 list不僅是一個雙向鏈表，而且還是一個環(huán)狀雙向鏈表,，所以它只需要一個指針,。list的最后一個節(jié)點的next指針指向頭節(jié)點，形成一個環(huán)狀的鏈表結(jié)構(gòu),，這樣可以方便地在頭尾兩端進(jìn)行插入和刪除操作,。 list不像vector那樣在空間不足時進(jìn)行重新配置和數(shù)據(jù)移動的操作，因此在插入前的所有迭代器在插入操作之后仍然有效,。由于list使用動態(tài)分配內(nèi)存,，并且節(jié)點的位置可以任意分布，因此在插入操作時并不需要重新分配內(nèi)存或移動數(shù)據(jù),。 deque是一種雙向開口的連續(xù)線性空間,，可以在頭尾兩端進(jìn)行元素的插入和刪除操作。deque允許在起頭端和末尾端常數(shù)時間內(nèi)進(jìn)行元素的插入和刪除操作,，這是deque和vector的一個重要差異。 deque和vector最大的差異在于,，deque允許常數(shù)時間內(nèi)對起頭端進(jìn)行元素的插入或移除操作,，而vector只能在尾部進(jìn)行常數(shù)時間內(nèi)的插入或移除操作。此外，deque是動態(tài)地以分段連續(xù)空間組合而成的,，可以隨時增加新的空間段并鏈接起來,，所以沒有所謂的容量限制，不需要進(jìn)行空間保留的操作,。 12,、常見容器性質(zhì)總結(jié) vector: 底層數(shù)據(jù)結(jié)構(gòu)為數(shù)組，支持快速隨機訪問,，動態(tài)數(shù)組,。 list: 底層數(shù)據(jù)結(jié)構(gòu)為雙向鏈表，支持快速增刪,，不支持隨機訪問,。 deque: 底層數(shù)據(jù)結(jié)構(gòu)為中央控制器和多個緩沖區(qū)，支持首尾快速增刪,，也支持隨機訪問,。是一個雙端隊列。 stack: 一般使用list或deque實現(xiàn),，封閉頭部即可,，用于實現(xiàn)棧的功能。 queue: 一般使用list或deque實現(xiàn),，封閉頭部即可,，用于實現(xiàn)隊列的功能。 priority_queue: 底層數(shù)據(jù)結(jié)構(gòu)一般為vector,，使用堆heap作為處理規(guī)則來管理底層容器實現(xiàn)優(yōu)先隊列,。 set: 底層數(shù)據(jù)結(jié)構(gòu)為紅黑樹，有序,，不重復(fù),。 multiset: 底層數(shù)據(jù)結(jié)構(gòu)為紅黑樹，有序,，可重復(fù),。 map: 底層數(shù)據(jù)結(jié)構(gòu)為紅黑樹，有序,，不重復(fù),，存儲鍵值對。 multimap: 底層數(shù)據(jù)結(jié)構(gòu)為紅黑樹,，有序,，可重復(fù)，存儲鍵值對,。 unordered_set: 底層數(shù)據(jù)結(jié)構(gòu)為哈希表,，無序,，不重復(fù)。 unordered_multiset: 底層數(shù)據(jù)結(jié)構(gòu)為哈希表,，無序,，可重復(fù)。 unordered_map: 底層數(shù)據(jù)結(jié)構(gòu)為哈希表,，無序,，不重復(fù)，存儲鍵值對,。 unordered_multimap: 底層數(shù)據(jù)結(jié)構(gòu)為哈希表,，無序，可重復(fù),，存儲鍵值對,。
12.1什么是有序容器？ 在容器中,，有序指的是容器中元素的排列順序與插入順序或者特定的排序規(guī)則相對應(yīng),。 對于有序容器（如set、map等）,，它們會維護(hù)元素的有序性,，這意味著元素在容器中按照一定的順序排列。具體的排序方式可以是根據(jù)元素的比較運算符進(jìn)行排序（默認(rèn)是升序）,，或者通過自定義的比較函數(shù)來指定排序規(guī)則,。 有序容器的特點是： 插入元素時會按照排序規(guī)則將元素放置在正確的位置，保持容器的有序性,。 元素在容器中的位置是固定的,，插入、刪除元素不會改變其他元素的相對位置,。 通過迭代器遍歷有序容器時,，可以按照元素的排序順序逐個訪問元素。 需要注意的是,，有序容器的有序性是相對于元素的值而言的,，而不是插入操作的順序。因此,，如果通過自定義的比較函數(shù)或者比較運算符來定義排序規(guī)則,，那么容器中的元素將按照該規(guī)則進(jìn)行排序，而不是按照插入順序排列,。
另外,，還有無序容器（如unordered_set、unordered_map等）,，它們并不維護(hù)元素的有序性,，元素在容器中的位置是無序的,，主要通過哈希表實現(xiàn)高效的查找和插入操作,。 13,、STL 中每種容器對應(yīng)的迭代器 vector：使用隨機訪問迭代器（Random Access Iterator）。隨機訪問迭代器允許通過指針?biāo)阈g(shù)運算來快速訪問容器中的任意元素,。 list：使用雙向迭代器（Bidirectional Iterator）,。雙向迭代器支持向前和向后遍歷容器中的元素，但不支持隨機訪問,。 deque：使用隨機訪問迭代器（Random Access Iterator）,。與vector相同，deque也支持通過指針?biāo)阈g(shù)運算來快速訪問容器中的任意元素,。 stack 和 queue：它們不提供公開的迭代器接口,，因為它們是適配器而不是容器。它們使用底層容器的迭代器來實現(xiàn)功能,。 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 的實現(xiàn),？ list 是雙向鏈表,，而 slist（單鏈表）是單向鏈表。它們的主要區(qū)別在于迭代器的類型,，list 使用的是雙向迭代器（Bidirectional iterator）,，而 slist 使用的是單向迭代器（Forward iterator）。雙向迭代器可以向前和向后遍歷容器中的元素,，而單向迭代器只能向前遍歷,。 
slist 的插入操作通常是將新元素插入到指定位置之前，而不是之后,。由于 slist 是單向鏈表,，無法回頭,，只能向后遍歷，因此在其他位置插入或移除元素會很低效,。 然而,，在 slist 的開頭插入或移除元素是高效的，因此 slist 提供了 insert_after() 和 erase_after() 函數(shù)來支持在開頭進(jìn)行靈活的操作,。
slist 提供了 push_front() 操作,，將元素插入到鏈表的開頭。需要注意的是,，插入到 slist 中的元素的存儲順序和輸入順序是相反的,，即后插入的元素會位于前面。 template <class T, class Allco = alloc>
class slist {
...
private:
...
static list_node* create_node(const value_type& x) {} //配置空間,、構(gòu)造元素
static void destroy_node(list_node* node) {} //析構(gòu)函數(shù),、釋放空間
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 中l(wèi)ist的實現(xiàn),？ list確實是一個雙向鏈表，每個節(jié)點包含一個元素和指向前一個節(jié)點和后一個節(jié)點的指針,。與vector相比,，list的好處在于插入和刪除操作只影響一個元素的空間，因此對于任何位置的元素插入和刪除都是常數(shù)時間的復(fù)雜度,。list的迭代器支持雙向移動,，可以使用"++"和"--"操作來遍歷鏈表。 與vector不同,，list的插入和接合操作不會導(dǎo)致原有迭代器失效,。這是因為list的節(jié)點在存儲空間中不一定連續(xù)，插入和刪除操作只需要調(diào)整節(jié)點的指針,，而不需要移動其他元素,。這使得list成為一個非常靈活的容器。 另一個特點是list是一個環(huán)形鏈表,，即最后一個節(jié)點的指針指向第一個節(jié)點,，形成一個閉環(huán)。這樣只需要一個指針便可以完整表示整個鏈表,。list的節(jié)點指針始終指向尾部的一個空白節(jié)點,，所以可以稱為“前閉后開”的區(qū)間結(jié)構(gòu)。 list的空間管理通常使用alloc作為空間配置器,，并提供了list_node_allocator函數(shù)用于一次性配置多個節(jié)點的空間,。由于list的雙向特性，它支持在頭部和尾部進(jìn)行push和pop操作,。此外,，list還提供了其他操作,，如erase、splice,、sort,、merge、reverse等,。 總的來說,，list是一種非常靈活的容器，適用于需要頻繁插入和刪除元素的場景,，尤其是在元素數(shù)量較大時，因為它的插入和刪除操作的時間復(fù)雜度都是常數(shù)時間,。 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的實現(xiàn)？ set是STL中的關(guān)聯(lián)式容器,，它的特點是元素會根據(jù)其值自動進(jìn)行排序,，默認(rèn)情況下是升序排序。set的元素的鍵值就是實值,，實值就是鍵值,，不允許有兩個相同的鍵值存在于set中。 set的迭代器是一種const_iterator,，也就是說,，它不允許通過迭代器修改元素的值，只能進(jìn)行讀取操作,。 標(biāo)準(zhǔn)的STL set使用紅黑樹（RB-tree）作為底層數(shù)據(jù)結(jié)構(gòu)來實現(xiàn),。紅黑樹是一種自平衡的二叉查找樹，具有以下特性： 每個節(jié)點要么是紅色,，要么是黑色,。 根節(jié)點是黑色的。 如果一個節(jié)點是紅色的,，則它的子節(jié)點必須是黑色的,。 任意節(jié)點到其每個葉子節(jié)點的路徑上包含相同數(shù)量的黑色節(jié)點。 紅黑樹的特性保證了樹的平衡性,，使得set的插入,、查找和刪除操作的時間復(fù)雜度都能保持在對數(shù)時間內(nèi)。 通過調(diào)用紅黑樹的操作行為,，set可以實現(xiàn)插入,、刪除、查找等操作,，并且這些操作的行為與紅黑樹的操作行為相對應(yīng),。這種將操作委托給底層紅黑樹的方式使得set的實現(xiàn)更加高效和靈活,。 17、STL 中 deque 的實現(xiàn),？ 
vector是單向開口（尾部）的連續(xù)線性空間,，而deque是雙向開口的連續(xù)線性空間。雖然vector也可以在頭部進(jìn)行元素操作,，但是頭部操作的效率較低,，因為它需要涉及整體的元素移動。 deque相對于vector的最大差異在于： 對頭端進(jìn)行元素操作的效率都是常數(shù)時間,，即在頭部和尾部插入或刪除元素的操作具有較高的效率,。 deque沒有容量的概念，它是動態(tài)地以分段連續(xù)空間組合而成的,。當(dāng)需要增加新的空間時,，可以配置一段定量的連續(xù)空間并連接在頭部或尾部，從而實現(xiàn)動態(tài)擴展,。 需要注意的是,，盡管deque也提供了隨機訪問的迭代器，但它的迭代器并非普通指針,，其實現(xiàn)比vector的迭代器復(fù)雜,。 因此，除非必要,，一般情況下推薦使用vector而非deque,。如果需要對deque進(jìn)行排序，可以先將deque中的元素復(fù)制到vector中,，利用vector的排序算法進(jìn)行排序,，然后再將結(jié)果復(fù)制回deque中。 由于deque的實現(xiàn)方式,，它由一段一段的定量連續(xù)空間組成,。當(dāng)需要增加新的空間時，可以通過配置新的連續(xù)空間并將其拼接到頭部或尾部來實現(xiàn),。因此,，deque的主要任務(wù)是如何維護(hù)這種整體的連續(xù)性，以便實現(xiàn)高效的元素操作,。 
deque內(nèi)部通常包含一個指針指向一塊稱為map的小型連續(xù)空間,，而map中的每個元素都是一個節(jié)點（node）。每個節(jié)點都是一個指針,，指向另一段較大的連續(xù)空間,，稱為緩沖區(qū)（buffer）。實際上，緩沖區(qū)是deque中存儲數(shù)據(jù)的區(qū)域,。 默認(rèn)情況下,，deque的緩沖區(qū)大小通常為512字節(jié)（具體大小可能有所不同，取決于編譯器和實現(xiàn)）,。這意味著每個節(jié)點所指向的緩沖區(qū)可以存儲一定數(shù)量的元素,。 通過使用這種結(jié)構(gòu)，deque能夠?qū)崿F(xiàn)動態(tài)擴展,，當(dāng)需要增加新的空間時,，它可以分配新的緩沖區(qū)，并將新的節(jié)點插入到map中,。這種設(shè)計使得deque能夠在兩端高效地插入和刪除元素,，同時保持?jǐn)?shù)據(jù)的連續(xù)性。 class deque {
// ...
protected:
typedef pointer* map_pointer; // 指向map指針的指針
map_pointer map; // 指向map
size_type map_size; // map的大小
public:
// ...
iterator begin();
iterator end();
// ...
}
這里給大家推薦零聲教育全網(wǎng)獨家的【Linux C/C++開發(fā)】課程體系,，通過原理技術(shù)+源碼分析+案例分析+項目實戰(zhàn),，全面解析Linux C/C++，8個上線項目,，2W+行手寫代碼，全面解析：
1,、精進(jìn)基石專欄（一）數(shù)據(jù)結(jié)構(gòu)與算法 隨處可見的紅黑樹 紅黑樹的應(yīng)用場景進(jìn)程調(diào)度cfs,，內(nèi)存管理 紅黑樹的數(shù)學(xué)證明與推導(dǎo) 手撕紅黑樹的左旋與右旋 紅黑樹添加的實現(xiàn)與添加三種情況的證明 紅黑樹刪除的實現(xiàn)與刪除四種情況的證明 紅黑樹的線程安全的做法 分析紅黑樹工程實用的特點 磁盤存儲鏈?zhǔn)降腂樹與B+樹 磁盤結(jié)構(gòu)分析與數(shù)據(jù)存儲原理 多叉樹的運用以及B樹的定義證明 B樹插入的兩種分裂 B樹刪除的前后借位與節(jié)點合并 手撕B樹的插入，刪除,，遍歷,，查找 B+樹的定義與實現(xiàn) B+樹葉子節(jié)點的前后指針 B+樹的應(yīng)用場景與實用特點 B+樹的線程安全做法 海量數(shù)據(jù)去重的abhloriter bitap hash的原理與hash函數(shù)的實現(xiàn) hash的應(yīng)用場景 分布式hash的實現(xiàn)原理 海量數(shù)據(jù)去重布隆過濾器 布隆過濾的數(shù)學(xué)推導(dǎo)與證明
（二）設(shè)計模式 創(chuàng)建型設(shè)計模式 單例模式 策略模式 觀察者模式 工廠方法模式與抽象工廠模式 原型模式 結(jié)構(gòu)型設(shè)計模式 適配器模式 代理模式 責(zé)任鏈模式 狀態(tài)模式 橋接模式 組合模式
（三）c++新特性 stI容器，智能指針,，正則表達(dá)式 unordered_ _map stl容器 hash的用法與原理 shared_ ptr,，unique_ ptr basic_ regex，sub_ match 函數(shù)對象模板function, bind 新特性的線程,協(xié)程,，原子操作,，lamda表達(dá)式 atomic的用法與原理 thread_ local 與condition_ var iable 異常處理exception_ _ptr 錯誤處理error _ category coroutine的用法與原理
（四）Linux工程管理 Makefi le/ cmake/conf igure Makefile的規(guī)則與make的工作原理 單文件編譯與多文件編譯 Makefile的參數(shù)傳遞 多目錄文件夾遞歸編譯與嵌套執(zhí)行make Makefile的通配符，偽目標(biāo),，文件搜索 Makefile的操作函數(shù)與特殊語法 configure生成makefile的原則 cmake的寫法 分布式版本控制git git的工作流程 創(chuàng)建操作與基本操作 分支管理,，查看提交歷史 git服務(wù)器搭建 Linux系統(tǒng)運行時參數(shù)命令 進(jìn)程間通信設(shè)施狀態(tài)ipcs Linux系統(tǒng)運行時長upt ime CPU平均負(fù)載和磁盤活動iostat 監(jiān)控，收集和匯報系統(tǒng)活動sar 監(jiān)控多處理器使用情況mpstat 監(jiān)控進(jìn)程的內(nèi)存使用情況pmap 系統(tǒng)管理員調(diào)優(yōu)和基準(zhǔn)測量工具nmon 密切關(guān)注Linux系統(tǒng)glances 查看系統(tǒng)調(diào)用strace ftp服務(wù)器基本信息ftptop 電量消耗和電源管理powertop 監(jiān)控mysq| 的線程和性能mytop 系統(tǒng)運行參數(shù)分析htop/top/atop Linux網(wǎng)絡(luò)統(tǒng)計監(jiān)控工具netstat 顯示和修改網(wǎng)絡(luò)接口控制器ethtool 網(wǎng)絡(luò)數(shù)據(jù)包分析利刃tcpdump 遠(yuǎn)程登陸服務(wù)的標(biāo)準(zhǔn)協(xié)議teInet 獲取實時網(wǎng)絡(luò)統(tǒng)計信息iptraf 顯示主機上網(wǎng)絡(luò)接口帶寬使用情況iftop
2,、高性能網(wǎng)絡(luò)設(shè)計專欄（一）網(wǎng)絡(luò)編程異步網(wǎng)絡(luò)庫zvnet 網(wǎng)絡(luò)io與io多路復(fù)用select/poll/epoll socket與文件描述符的關(guān)聯(lián) 多路復(fù)用select/poll 代碼實現(xiàn)LT/ET的區(qū)別 事件驅(qū)動reactor的原理與實現(xiàn) reactor針對業(yè)務(wù)實現(xiàn)的優(yōu)點 poll封裝send_ cb/recv_ _cb/ accept_ _cb reactor多核實現(xiàn) 跨平臺(select/epoll/kqueue)的封裝reactor redis,，memcached， nginx網(wǎng) 絡(luò)組件 http服務(wù)器的實現(xiàn) reactor sendbuffer與recvbuffer封裝http協(xié)議 http協(xié)議格式 有限狀 態(tài)機fsm解析http 其他協(xié)議websocket,， tcp文件傳輸
（二）網(wǎng)絡(luò)原理 服務(wù)器百萬并發(fā)實現(xiàn)(實操) 同步處理與異步處理的數(shù)據(jù)差異 網(wǎng)絡(luò)io線程池異步處理 ulimit的fd的百萬級別支持 sysctI. conf的rmem與wmem的調(diào)優(yōu) conntrack的原理分析 Posix API與網(wǎng)絡(luò)協(xié)議棧 connect,，listen， accept與三次握 手 listen參數(shù)backlog syn泛洪的解決方案 close與四次揮手 11個狀態(tài)遷移 大量close_ wait與time wait的原因與解決方案 tcp keepalive與 應(yīng)用層心跳包 擁塞控制與滑動窗口 UDP的可靠傳輸協(xié)議QUIC udp的優(yōu)缺點 udp高并發(fā)的設(shè)計方案 qq早期為什么選擇udp作為通信協(xié)議 udp可靠傳輸原理 quic協(xié)議的設(shè)計原理 quic的開源方案quiche kcp的設(shè)計方案與算法原理 協(xié)程調(diào)度器實現(xiàn)與性能測試 調(diào)度器的定義分析 超時集合,，就緒隊列,，io等待集合的實現(xiàn) 協(xié)程調(diào)度的執(zhí)行流程 協(xié)程接口實現(xiàn),，異步流程實現(xiàn) hook鉤子的實現(xiàn) 協(xié)程實現(xiàn)mysql請求 協(xié)程多核方案分析 協(xié)程性能測試
（三）自研框架:基于dpdk的用戶態(tài)協(xié)議棧的實現(xiàn)(已開源) 用戶態(tài)協(xié)議棧設(shè)計實現(xiàn) 用戶態(tài)協(xié)議棧的存在場景與實現(xiàn)原理 netmap開源框架 eth協(xié)議，ip協(xié)議,， udp協(xié)議實現(xiàn) arp協(xié)議實現(xiàn) icmp協(xié)議實現(xiàn) 應(yīng)用層posix api的具體實現(xiàn) socket/bind/listen的實現(xiàn) accept實現(xiàn) recv/send的實現(xiàn) 滑動窗口/慢啟動講解 重傳定時器,，堅持定時器，time_ wait定時器,，keepalive定時器 手把手設(shè)計實現(xiàn)epoll epoll數(shù)據(jù)結(jié)構(gòu)封裝與線程安全實現(xiàn) 協(xié)議棧fd就緒回調(diào)實現(xiàn) epoll接口實現(xiàn) LT/ET的實現(xiàn) 高性能異步io機制io_ _uring 與epo1l媲美的io_ uring io_ _uring系統(tǒng)調(diào)用io_ _uring_ setup,， io_ _ur ing_ register， io_ _ur ing_ enter liburng的io_ uring的關(guān)系 io_ uring與epoll性能對比 io_ _uring的共享內(nèi)存機制 io_ uring的使用場景 io_ ur ing的accept,， connect,， recv， send實現(xiàn)機制 io_ uring網(wǎng)絡(luò)讀寫 io_ uring磁盤讀寫 proactor的實現(xiàn)
3,、基礎(chǔ)組件設(shè)計專欄（一）池式組件 手寫線程池與性能分析(項目) 線程池的異步處理使用場景 線程池的組成任務(wù)隊列執(zhí)行隊列 任務(wù)回調(diào)與條件等待 線程池的動態(tài)防縮 擴展: nginx線程池實現(xiàn)對比分析 內(nèi)存池的實現(xiàn)與場景分析(項目) 內(nèi)存池的應(yīng)用場景與性能分析 內(nèi)存小塊分配與管理 內(nèi)存大塊分配與管理 手寫內(nèi)存池,，結(jié)構(gòu)體封裝與API實現(xiàn) 避免內(nèi)存泄漏的兩種萬能方法 定位內(nèi)存泄漏的3種工具 擴展:nginx內(nèi)存池實現(xiàn) mysq|連接池的實現(xiàn)(項目) 連接池性能的影響的2個因素，top連接和mysq|認(rèn)證 連接請求歸還策略 連接超時未歸還策略 鏈接斷開重連策略 連接數(shù)量最優(yōu)策略
（二）高性能組件 原子操作CAS與鎖實現(xiàn)(項目) 互斥鎖的使用場景與原理 自旋鎖的性能分析 原子操作的匯編實現(xiàn) 無鎖消息隊列實現(xiàn)(項目) 有鎖無鎖隊列性能 內(nèi)存屏障Barrier 數(shù)組無鎖隊列設(shè)計實現(xiàn) 鏈表無鎖隊列設(shè)計實現(xiàn) 網(wǎng)絡(luò)緩沖區(qū)設(shè)計 RingBuffer設(shè)計 定長消息包 ChainBuffer 設(shè)計 雙緩沖區(qū)設(shè)計 定時器方案紅黑樹,，時間輪,，最小堆(項目) 定時器的使用場景 定時器的紅黑樹存儲 時間輪的實現(xiàn) 最小堆的實現(xiàn) 分布式定時器的實現(xiàn) 手寫死鎖檢測組件(項目) 死鎖的現(xiàn)象以及原理 pthread_ _mutex_ lock/pthread_ _mutex_ _unlock dIsym的實現(xiàn) 有向圖的構(gòu)建 有向圖dfs判斷環(huán)的存在 三個原語操作 lock before, lock_ after, unlock_ after 死鎖檢測線程的實現(xiàn) 手寫內(nèi)存泄漏檢測組件(項目) 內(nèi)存泄漏現(xiàn)象 第三方內(nèi)存泄漏與代碼內(nèi)存泄漏 malloc與free的dIsym實現(xiàn) 內(nèi)存檢測策略 應(yīng)用場景測試 手把手實現(xiàn)分布式鎖(項目) 多線程資源競爭互斥鎖 自旋鎖 加鎖的異常情況 非公平鎖的實現(xiàn) 公平鎖的實現(xiàn)
（三）開源組件 異步日志方案spdlog (項目) 日志庫性能瓶頸分析 異步日志庫設(shè)計與實現(xiàn) 批量寫入與雙緩存沖機制 奔潰后的日志找回 應(yīng)用層協(xié)議設(shè)計ProtoBuf(項目) IM， 云平臺,，nginx,， http， redis協(xié)議設(shè)計 如何保證消息完整性 手撕protobuf IM通信 協(xié)議 protobuf序列化與反序列化 protobuf編碼原理
4,、中間件開發(fā)專欄（一）Redis Redis相關(guān)命令詳解及其原理 string,，set， zset,， Iist,，hash 分布式鎖的實現(xiàn) Lua腳本解決ACID原子性 Redis事務(wù)的ACID性質(zhì)分析 Redis協(xié)議與異步方式 Redis協(xié)議解析 特殊協(xié)議操作訂閱發(fā)布 手撕異步redis協(xié)議 存儲原理與數(shù)據(jù)模型 string的三種編碼方 式int, raw, embstr 雙向鏈表的list實現(xiàn) 字典的實現(xiàn)，hash函數(shù) 解決鍵沖突與rehash 跳表的實現(xiàn) 與數(shù)據(jù)論證 整數(shù)集合實現(xiàn) 壓縮列表原理證明 主從同步與對象模型 對象的類型與編碼 廣字符串對象 列表對象 哈希對象 集合對象 有序集合 類型檢測與命令多態(tài) 內(nèi)存回收 對象共享 對象空轉(zhuǎn)時長 redis的3種集群方式主從復(fù)制,，sentinel, cluster 4種持久化方案
（二）MySQL SQL語句,，索引，視圖,，存儲過程,，觸發(fā)器 MySQL體系結(jié)構(gòu)，SQL執(zhí)行流程. SQL CURD與高 級查詢 視圖,，觸發(fā)器,，存儲過程 MySQL權(quán)限管理 MySQL索引原理以及SQL優(yōu)化 索引，約束以及之間的區(qū)別 B+樹,，聚集索引和輔助索引 最左匹配原則以及覆蓋索引 索引失效以及索引優(yōu)化原則 EXPLAIN執(zhí)行計劃以及優(yōu)化選擇過程分析 MySQL事務(wù)原理分析 事務(wù)的ACID特性 MySQL并發(fā)問題臟讀,，不可重復(fù)讀，幻讀 事務(wù)隔離級別 鎖的類型，鎖算法實現(xiàn)以及鎖操作對象 S鎖X鎖|S鎖IX鎖 記錄鎖,，間隙鎖,，next-key lock 插入意向鎖，自增鎖 MVCC原理剖析 MySQL緩存策略 讀寫分離,，連接池的場景以及其局限a 緩存策略問題分析 緩存策略強一致性解決方案 緩存策略最終一致性解決方案 2種mysql緩存同步方案從數(shù)據(jù)庫與觸發(fā)器+udf 緩存同步開源方案go-mysql-transfer 緩存同步開源方案canal原理分析 3種緩存故障,，緩存擊穿，緩存穿透,，緩存雪崩
（三）Kafka Kafka使 用場景與設(shè)計原理 發(fā)布訂閱模式 點對點消息傳遞 Kafka Brokers原 理 Topi cs和Partition Kafka存 儲機制 Partition存儲分布 Partition文件存儲機制 Segment文件存儲結(jié)構(gòu) offset查找message 高效文件存儲設(shè)計 微服務(wù)之間通信基石gRPC gRPC的 內(nèi)部組件關(guān)聯(lián) CI ientS ide與ServerSide,， Channel, Ser ivce， Stub的概念 異步gRPC的實現(xiàn) 回調(diào)方式的異步調(diào)用 Server 與CI ient對RPC的實現(xiàn) 基于http2的gRPC通信協(xié)議 基于http協(xié) 議構(gòu)造 ABNF語法 請求協(xié)議Request-Headers gRPC上下文傳遞
（四）Nginx Nginx反 向代理與系統(tǒng)參數(shù)配置conf原理 Nginx靜態(tài)文件的配置 Nginx動態(tài)接口代理配置 Nginx對Mqtt協(xié)議轉(zhuǎn)發(fā) Nginx對Rtmp推拉流 Openresty對Redis緩存數(shù)據(jù)代理 shmem的三種實現(xiàn)方式 原子操作 nginx channel 信號 信號量 Nginx過濾 器模塊實現(xiàn) Nginx Filter模塊運行原理 過濾鏈表的順序 模塊開發(fā)數(shù)據(jù)結(jié)構(gòu) ngx_ str_ _t,，ngx_ list_ t,，ngx_ buf_ t，ngx_ chain_ t error日志的用法 ngx_ comond_ t的講解 ngx_ http_ _module_ _t的執(zhí)行流程 文件鎖,，互斥鎖 slab共享內(nèi)存 如何解決 "驚群”問題 如何實現(xiàn)負(fù)載均衡 Nginx Handler模塊實現(xiàn) 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的核心數(shù)據(jù)結(jié)構(gòu)ngx_ cycle_ t,，ngx_ event. _moule_ t http請求的11個處理階段 http包體處理 http響應(yīng)發(fā)送 Nginx Upstream機制的設(shè)計與實現(xiàn) 模塊性能測試
5、開源框架專欄（一）游戲服務(wù)器開發(fā)skynet (錄播答疑) Skynet設(shè)計原理 多核并發(fā)編程-多線程,，多進(jìn)程,，csp模型，actor模型 actor模型實現(xiàn)-lua服務(wù)和c服務(wù) 消息隊列實現(xiàn) actor消息調(diào)度 skynet網(wǎng)絡(luò)層封裝以及l(fā)ua/c接口編程 skynet reactor 網(wǎng)絡(luò)模型封裝 socket/ socketchanne|封裝 手撕高性能c服務(wù) lua編程以及l(fā)ua/c接口編程 skynet重要組件以及手撕游戲項目 基礎(chǔ)接口 skynet. send, skynet. cal I, skynet. response 廣播組件multicastd 數(shù)據(jù)共享組件 sharedatad datasheet 手撕萬人同時在線游戲
（二）分布式API網(wǎng)關(guān) 高性能web網(wǎng)關(guān)Openresty Nginx與lua模塊 Openresty訪問Redis,，MySQL Restful API接口開發(fā) Openresty性能分析 Kong 動態(tài)負(fù)載均衡與服務(wù)發(fā)現(xiàn) nginx,，openresty, Kong之間的“茍且” 動態(tài) 負(fù)載均衡的原理 服務(wù)發(fā)現(xiàn)實現(xiàn)的原理 Serverless 監(jiān)控，故障檢測與恢復(fù) 二代理層緩存與響應(yīng)服務(wù) 系統(tǒng)日志
（三）SPDK助力MySQL數(shù)據(jù)落盤,， 讓性能騰飛(基礎(chǔ)設(shè)施) SPDK文件系統(tǒng)設(shè)計與實現(xiàn) NVMe與PCle的原理 NVMe Controller 與bdev之間的rpc blobstore與blob的關(guān)系 文件系統(tǒng)的posix api實現(xiàn) 4層結(jié)構(gòu)設(shè)計vfs spdk的 異步改造posix同步api open/wr ite/read/close的實現(xiàn) 文件系統(tǒng)的性能測試與承接mysql業(yè)務(wù) LD_ PRELOAD更好mysql系統(tǒng)調(diào)用實現(xiàn) iodepth講解 隨機讀，隨機寫,，順序讀,，順序?qū)?/p>
（四）高性能計算CUDA (錄播答疑) （五）并行計算與異步網(wǎng)絡(luò)引擎workflow （六）物聯(lián)網(wǎng)通信協(xié)議mqtt的實現(xiàn)框架mosquitto 6、云原生專欄（一）Docker Docker風(fēng)光下的內(nèi)核功能(錄播答疑) 進(jìn)程namespace UTS namespace IPC namespace 網(wǎng)絡(luò)namespace 文件系統(tǒng)namesapce cgroup的資源控制 Docker容器管理與鏡像操作(錄播答疑) Docker鏡像下載與鏡像運行 Docker存儲管理 Docker數(shù)據(jù)卷 Docker與容器安全 Docker網(wǎng)絡(luò)管理(項目) 5種Docker網(wǎng)絡(luò)驅(qū)動 pipework跨主機通信 0vS劃分vlan與隧道模式 GRE實現(xiàn)跨主機Docker間通信 Docker云與容器編排 (項目) Dockerfile的語法流程 編排神器Fig/Compose FIynn體系 架構(gòu) Docker改變了什么?
（二）Kubernetes 7,、性能分析專欄（一）性能與測試工具 測試框架gtest以及內(nèi)存泄漏檢測(錄播答疑) goog letest與goog lemock文件 函數(shù)檢測以及類測試 test fixture測試夾具 類型參數(shù)化 事件測試 內(nèi)存泄漏 設(shè)置期望,，期待參數(shù)，調(diào)用次數(shù),，滿足期望 性能工具與性能分析(錄播答疑) MySQL性能測試工具mysqlslap Redis性能測試工具redis-benchmark http性能測試工具wrk Tcp性能測試工具TCPBenchmarks 磁盤,，內(nèi)存，網(wǎng)絡(luò)性能分析 火焰圖的生成原理與構(gòu)建方式 火焰圖工具講解 火焰圖使用場景與原理 nginx動態(tài)火焰圖 MySQL火焰圖 Redis火焰圖
（二）觀測技術(shù)bpf與ebpf 內(nèi)核bpf的實現(xiàn)原理 跟蹤,，嗅探,，采樣，可觀測的理解 動態(tài)hook: kpr obe/ upr obe 靜態(tài)hook: tr acepoint和USDT 性能監(jiān)控計時器PMC模 式 cpu的觀測taskset的使 用 BPF工具bpftrace,， BCC bpf對內(nèi)核功 能的觀測 內(nèi)存觀測kmalloc與vm_ area_ struct 文件系統(tǒng)觀測vfs的狀態(tài): 磁盤io的觀測bitesize, mdf lush bpf對網(wǎng)絡(luò)流量的統(tǒng)計 bpf對redis-server觀測 網(wǎng)絡(luò)觀測tcp_ connect,， tcp_ accept, tcp_ close
（三）內(nèi)核源碼機制 進(jìn)程調(diào)度機制哪些事兒 qemu調(diào)試內(nèi)存 進(jìn)程調(diào)度cfs與 其他的四個調(diào)度類 task_ struct結(jié)構(gòu)體 RCU機制與內(nèi)存優(yōu)化屏障 內(nèi)核內(nèi)存管理運行機制 虛擬內(nèi)存地址布局 SMP/NUMA模型 頁表與頁表緩存原理 伙伴系統(tǒng)實現(xiàn) 塊分配(SIab/SIub/Slob) 原理實現(xiàn) brk/kmalloc/vmalloc系統(tǒng)調(diào)用流程 文件系統(tǒng)組件 虛擬文件系統(tǒng)vfs Proc文件系統(tǒng) super_ _block與 inode結(jié)構(gòu)體 文件描述符與掛載流程
8、分布式架構(gòu)（一）分布式數(shù)據(jù)庫 不一樣的kv存儲RocksDB的使用場景 前綴搜索 低優(yōu)先級寫入 生存時間的支持 Transact i ons 快照存儲 日志結(jié)構(gòu)的數(shù)據(jù)庫引擎 TiDB存儲引擎的原理 TiKV的Key-Value存儲引擎 基于RBAC的權(quán)限管理 數(shù)據(jù)加密 TiDB集群方案與Replication原理 集群三個組件 TiDB Server, PD Server, TiKV Server Raft協(xié)議講解 OLTP與0LAP
（二）分布式文件系統(tǒng)(錄播答疑) （三）分布式協(xié)同 注冊服務(wù)中心Etcd etcd配置服務(wù)、服務(wù)發(fā)現(xiàn),、集群監(jiān)控,、leader選舉、 分布式鎖 etcd體系結(jié)構(gòu)詳解(gRPC,， WAL,，Snapshot、 BoItDB,、 Raft) etcd存儲原理深入剖析(B樹,、B+樹) etcd讀寫機制以及事務(wù)的acid特性分析 raft共識算法詳解(leader選舉+日志復(fù)制) 協(xié)同事件用戶態(tài)文件系統(tǒng)fuse (項目) fuse的使用場景 文件系統(tǒng)讀寫事件 fuse的實現(xiàn)原 理 /dev/fuse的 作用 快播核心技術(shù)揭秘P2P框架的實現(xiàn)(錄播答疑) 網(wǎng)關(guān)NAT表分析 NAT類型，完全錐型NAT,，對稱NAT,端口限制錐形NAT,，IP限制錐型NAT 代碼邏輯實現(xiàn)NAT類型檢測 網(wǎng)絡(luò)穿透的原理 網(wǎng)絡(luò)穿透的3種情況
9、上線項目實戰(zhàn)（一）dkvstore實現(xiàn)(上線項目) （二）圖床共享云存儲(上線項目) 
ceph架構(gòu)分析和配置 ceph架構(gòu)分析 快速配置ceph 上傳文件邏輯 分析 下載文件邏輯分析 文件傳輸和接口設(shè)計 http接口設(shè)計 圖床數(shù)據(jù)庫設(shè)計 圖床文件上傳,，下載,，分享功能實現(xiàn) 業(yè)務(wù)流程實現(xiàn) 容器化docker部署 crontab定時清理數(shù)據(jù) docker server服 務(wù) grpc連接池管理
（三）容器化docker部署 crontab定時清理數(shù)據(jù) docker server服 務(wù) grpc連接池管理 產(chǎn)品上云公網(wǎng)發(fā)布/測試用例 使用云服務(wù)器的各種坑分析 fiddler監(jiān)控http請求，postman模 擬請求 wrk測試接口吞吐量 jmeter壓力測試 微服務(wù)即時通訊(上線項目) IM即時通訊項目框架分析和部暑 即時通訊應(yīng)用場景分析 即時通訊自研和使用第三方SDK優(yōu)缺點 即時通訊數(shù)據(jù)庫設(shè)計 接入層,、 邏輯層,、路由層、數(shù)據(jù)層架構(gòu) 即時通訊項目部署 即時通訊web賬號注冊源碼分析 IM消息服務(wù)器/文件傳輸服務(wù)器 protobuf通信協(xié)議設(shè)計 reactor模型C++實現(xiàn) login_ server 負(fù)載均衡手寫代碼實現(xiàn) 用戶登錄請求驗證密碼+混淆碼MD5匹對 如何全量,、增量拉取好友列表,、用戶信息 知乎、b站小紅點點未讀消息如何實現(xiàn) IM消息服務(wù)器和路由服務(wù)器設(shè)計 請求登錄邏輯 最近聯(lián)系會話邏輯. 查詢用戶在線主題 未讀消息機制 單聊消息推拉機制 群聊消息推拉機制 路由轉(zhuǎn)發(fā)機制 數(shù)據(jù)庫代理服務(wù)器設(shè)計 main函數(shù)主流程 reactor+線程池+連接池處理邏輯分析 redis緩存實現(xiàn)消息計數(shù)(單聊和群聊) redis實現(xiàn)未讀消息機制 如何實現(xiàn)群消息的推送 單聊消息推送,、拉取優(yōu)缺點 文件服務(wù)器和ooker部署 在線文件傳輸機制分析 離線文件傳輸機制分析 etcd微服務(wù)注冊與發(fā)現(xiàn) docker制作與部暑
（四）零聲教學(xué)AI助手一代(上線項目) 
（五）魔獸世界后端TrinityCore (上線項目) 網(wǎng)絡(luò)模塊實現(xiàn) boost.asio跨平臺網(wǎng)絡(luò)庫 boost. asio核心命名空間以及異步io接口 boost. asio在TrinityCore 中的封裝 網(wǎng)絡(luò)模塊應(yīng)用實踐 地圖模塊實現(xiàn) 地圖模塊抽象: map,、 area、grid,、 cell 地圖模塊驅(qū)動方式 A0I 核心算法實現(xiàn) AABB碰撞檢測實現(xiàn) A*尋路算法實現(xiàn) 戰(zhàn)斗模塊實現(xiàn) 技能設(shè)計以及實 現(xiàn) Al設(shè)計 怪物管理 副本設(shè)計 TrinityCore 玩法實現(xiàn) 用戶玩法實現(xiàn)-任務(wù)系統(tǒng) 數(shù)據(jù)配置以及數(shù)據(jù)庫設(shè)計 觸發(fā)機制實現(xiàn) 多人玩法實現(xiàn)-工會設(shè)計
10,、適宜的工程師人群（共分為8大群體）1.從事業(yè)務(wù)開發(fā)多年，對底層原理理解不夠深入的在職工程師 2.從事嵌入式方向開發(fā),，想轉(zhuǎn)入互聯(lián)網(wǎng)開發(fā)的在職工程師 3. 從事Qt/MFC等桌面開發(fā)的,，薪資多年漲幅不大的在職工程師 4.從事非開發(fā)崗位(算法崗，運維崗,，測試崗),，想轉(zhuǎn)后臺開發(fā)崗位的在職工程師 5.工作中技術(shù)沒有挑戰(zhàn)，工作中接觸不到新技術(shù)的在職工程師 6.自己研究學(xué)習(xí)速度較慢,，不能系統(tǒng)構(gòu)建知識體系的開發(fā)人員 7.了解很多技術(shù)名詞,，但是深入細(xì)問又不理解的工程師 8.計算機相關(guān)專業(yè)想進(jìn)入大廠的在校生(本科及以上學(xué)歷，有c/c++基礎(chǔ))
11,、配套書籍資料1. MySQL: 《高性能MySQL 第3版》 2. Nginx: 《深入理解Nginx: 模塊開發(fā)與架構(gòu)分析(第2版)》(陶輝） 3. Redis: Redis設(shè)計與實現(xiàn) (黃健宏) 4. Linux內(nèi)核: 《深入理解Linux內(nèi)核架構(gòu)》 (郭旭 譯) 5. 數(shù)據(jù)結(jié)構(gòu)與算法:《算法導(dǎo)論》(第3版) 6.性能分析:《性能之巔洞悉系統(tǒng),、企業(yè)與云計算》 7. MongoDB: 《MongoDB權(quán)威指南》 8. Ceph: 《Ceph分布式存儲學(xué)習(xí)指南》 (Ceph中國社區(qū)) 9. Docker: 《Docker容器 與容器云(第2版)》 10. TCP/IP: 《Tcp/Ip詳解卷一卷二卷三》 11. Linux系統(tǒng)編程: 《Unix環(huán)境高級編程》 12. 計算機: 《深入理解計算機系統(tǒng)》 13. DPDK: 《深入淺出DPDK》 14. k8s: 《Kubernates權(quán)威指南》 龔正等編著 15. bpf: 《BPF之巔洞悉Linux系統(tǒng)和應(yīng)用性能》
學(xué)習(xí)成果檢驗 
  
如果是想在c/c++開發(fā)方向得到有效的快速提升（不是所謂的速成）,，這份學(xué)習(xí)體系是大家繞不過的具有參考意義的提升路線。從學(xué)習(xí)路線中可以對c/c++開發(fā)方向的技術(shù)棧有一個清晰的認(rèn)識,。 還不熟悉的朋友,，這里可以先領(lǐng)取一份Linux c/c++開發(fā)新手學(xué)習(xí)資料包（入坑不虧）：
- 編程基本功扎實，掌握 C/C++/JAVA 等開發(fā)語言,、常用算法和數(shù)據(jù)結(jié)構(gòu),；
- 熟悉 TCP/UDP 網(wǎng)絡(luò)協(xié)議及相關(guān)編程、進(jìn)程間通訊編程,；
- 了解 Python,、Shell、Perl 等腳本語言,；
- 了解 MYSQL 及 SQL 語言,、編程，了解 NoSQL, key-value 存儲原理,；
- 全面,、扎實的軟件知識結(jié)構(gòu)，掌握操作系統(tǒng),、軟件工程,、設(shè)計模式、數(shù)據(jù)結(jié)構(gòu),、數(shù)據(jù)庫系統(tǒng),、網(wǎng)絡(luò)安全等專業(yè)知識；
- 了解分布式系統(tǒng)設(shè)計與開發(fā),、負(fù)載均衡技術(shù),，系統(tǒng)容災(zāi)設(shè)計，高可用系統(tǒng)等知識,。
|
