一.模版

模版涉及的是泛型編程，即通過編譯器去確定類型的編程方式，模版分為：類模板和函數模版，下面我們一一復習：

函數模版：

格式：

template<typename T1, typename T2,......,typename Tn>
返回值類型 函數名(參數列表){}
//注意：typename是用來定義模板參數關鍵字，也可以使用class(切記：不能使用struct代替class)//模版既可以為typename，也可以為size_t

對于函數模版，原理就是通過編譯器在編譯時通過傳入的實參來推導形參對應的類型，然后產生專門對應的類型代碼，如下：

//模版：
template<class T>
void swap(T& a,T& b)
{T c=a;a=b;b=c;
}int main()
{//調用：int a=10,b=20;swap(a,b);//會去生成下面內容->最后面    return 0;
}//生成的代碼：
void swap(int a,int b)
{int c=a;a=b;b=c;
}

函數模版的實例化分為顯示實例化和隱式實例化，上面由編譯器推導的都是隱式實例化，顯示實例化是指調用時，由用戶指定類型，從而直接傳遞類型，如下：

//直接寫調用,還是swapint main()
{double d1=1.2;double d2=2.5;swap<double>(d1,d2);return 0;
}//注意點：
//如果類型不匹配，編譯器會嘗試進行隱式類型轉換，如果無法轉換成功編譯器將會報錯

類模板：

格式：

template<class T1, class T2, ..., class Tn>
class 類模板名
{// 類內成員定義
};

類模版大體與函數模版相似使用即可，不同的是類模板實例化必須在類模板名字后跟<>，然后將實例化的類型放在<>，類模板名字不是真正的類，而實例化的結果才是真正的類

然后就是大家還可以去復習下全特化與偏特化內容，然后還有模版最好不要分離編譯，使用.hpp，大家可以參考下面博客復習：

C++之模版詳解-CSDN博客

---

---

二.容器常見知識點

1.vector與list區別？

1.底層實現上：
vector底層是一段連續的順序表，而list是帶頭結點的雙向循環鏈表，底層不連續
2.訪問上：
vector由于其底層連續，可以支持下標隨機訪問，list不支持隨機訪問，必須要遍歷查找
3.操作上：
插入：vector任意位置插入由于可能需要挪動空間、開辟新空間，整體拷貝效率非常低下，list插入只需要改變指針指向和開辟一個節點空間即可，效率高
刪除：vector除尾刪外任意位置刪除都要挪動空間，效率低，而list不需要挪動空間，只需要改變指針指向，效率高
4.空間利用上：
vector是連續的順序表，不易造成空間碎片化，而list是通過指針將節點相連，各節點之間不連續，空間碎片化嚴重，空間利用率低
5.迭代器上：
vector是使用原生態的迭代器（即只是指針），list是將原生態迭代器進行了封裝，可以參考我的github：
https://github.com/zhutishou/C-STL-Copywriting/blob/main/list.cpp
6.使用場景上：
vector適用于高效存儲和隨機訪問上，不關系插入和刪除效率;list適用于大量插入和刪除上，不注重空間利用和隨機訪問

2.vector如何實現插入？

1.首先，先判斷插入位置是否正確
2.檢查空間是否需要擴容
3.將要插入以后的元素整體后移
4.插入當前位置
5.返回插入位置的迭代器
//具體代碼如下：
//插入：
//插入：
iterator insert(iterator pos,const T& val)
{if(pos < _begin|| pos > _end){std::cerr<<"該位置不存在"<<std::endl;}//判斷是否需要擴容：if(_end == _endofstorage){size_t len = _begin + pos;reserve(capacity()==0?4:2*capacity());pos = _begin + len;}//pos后續位置后移：iterator finish = _end -1;while(finish > pos){*(finish+1) = *finish;finish--;}*pos = val;_end++;return pos;
}
//vector實現代碼如下：
https://github.com/zhutishou/C-STL-Copywriting/blob/main/vector.cpp

3.vector和list都有缺陷，是否存在其他容器可以兼顧兩者優點呢？

能夠兼顧vector和list優點的容器就是deque(雙端隊列)
介紹：
deque是雙開口的“連續”空間的數據結構，注意：“連續”實際上是一段段小空間拼湊出來的，只是支持下標隨機訪問看做連續，支持頭插尾插，并且不需要挪動元素
相比于vector和list優點：
1.相比于vector頭插尾插O(1),不用挪動數據，并且擴容時，不需要整體拷貝
2.相比于list，空間利用率更高缺點：
不適合遍歷，由于其底層是一個個小空間實現的，迭代器需要不斷檢查邊界，效率低下，因此通常還是使用vector或list使用場景：
deque通常是stack和queue空間適配器默認的容器，原因是因為兩者都不需要遍歷，而且只在首尾操作

4.map和set底層是什么？

對于map/set和unordered_map/unordered_set這是我們必須掌握的
map/set底層是紅黑樹，unordered_map/unordered_set底層是哈希表
該問題實際上是問紅黑樹的相關信息：
一.規則：
1. 每個結點不是紅色就是黑色
2. 根節點是黑色的
3. 如果一個節點是紅色的，則它的兩個孩子結點是黑色的
4. 對于每個結點，從該結點到其所有后代葉結點的簡單路徑上，均包含相同數目的黑色結點
5. 每個葉子結點都是黑色的(此處的葉子結點指的是空結點)
紅黑樹通過規則2、3保證樹的其最長路徑中節點個數不會超過最短路徑節點個數的兩倍
效率：
紅黑樹是一個高效的平衡二叉樹，增刪查改效率都是O(LogN)
實現:
可以參考我的github注意：
multimap和multiset也是紅黑樹實現的，但是與set/map不同點在于這兩個允許出現重復的key值

5.map的operator[]是如何實現的？

V& operator[](const K& key)//V --- value 
{ return (*(_t.Insert(ValueType(key, V()))).first).second;
}operator[]如果存在key，就返回對應的value，如果不存在key，就插入key，返回默認值

6.一個什么類型才能做map和set的key值？

map和set底層都是紅黑樹，而紅黑樹是平衡搜索樹，所以一定支持比較大小，當然提供相應的仿函數來比較大小的類型也是可以的

7.unordered_map和unordered_set是如何實現的？

這個問題本質上是詢問我們其底層實現，顯然這兩者都是通過哈希實現的，那么就講述哈希特點
規則：
哈希是通過哈希函數進行相應的映射關系，使key與存儲位置建立一一的映射，在查找時就可以快速找到
對比：
哈希在查找時效率為O(1)，而紅黑樹效率為O(LogN),順序表效率為O(N)
常見問題：
哈希沖突：
該問題無法避免，是指不同關鍵字通過相同哈希哈數計算出相同的哈希地址，該種現象稱為哈希沖突或哈希碰撞，解決方法:建立合適的空間大小，減少通過哈希函數計算之后碰撞的發生，還有兩種常見處理方法：開散列和閉散列

8.一個類型做unordered_map和unordered_set的key有什么要求？

哈希是需要通過哈希函數進行映射的，所以key值必須可以實現向整數的轉換，這樣才能映射到存儲空間中

最后，感謝你的支持！！！