目錄
1.STL知識梳理
2.c++知識梳理? ?
3.數(shù)據(jù)結(jié)構(gòu)知識梳理
STL知識掌握：
底層實現(xiàn)角度：六大組件。
上層用的角度：容器、算法、迭代器。
底層實現(xiàn)角度：
注：
1.可以認為迭代器是容器和算法的粘合劑，如果沒有迭代器，那么算法要訪問容器有兩大問題：
（1）訪問需要暴露容器底層結(jié)構(gòu)及實現(xiàn)細節(jié)，封裝性就不在了。
（2）使用門檻較高，比如要訪問map，需要對二叉樹遍歷掌握，這個成本是很高的。
通過迭代器解決了上面的問題，迭代器優(yōu)勢如下：
（1）封裝隱藏了底層實現(xiàn)細節(jié)。
（2）提供統(tǒng)一的方式去訪問容器，極大降低了使用成本。
2.容器如果頻繁的申請小塊內(nèi)存，就需要空間配置器來提高內(nèi)存申請和釋放的效率。
3.容器適配器：stack、queue、priority_queue等。適配器可以認為是一種特殊的容器，體現(xiàn)了復(fù)用的思想。
其他適配器：反向迭代器也是一種適配器，封裝容器正向迭代器就可以實現(xiàn)這個容器的反向迭代器。
4.仿函數(shù)主要作用在容器和算法上，其本質(zhì)上是實現(xiàn)了operator()的類，這個類對象可以像函數(shù)一樣去使用。使用場景舉例：
場景一：map/set的key比較大小規(guī)則。
場景二：unoredered_map/unoredered_set的key轉(zhuǎn)換成整型的規(guī)則，影響沖突率。
場景三：sort排序比較規(guī)則。
上層用的角度：
注：
1.容器
重點熟練掌握的容器：vector、list、map、set、unoredered_map、unoredered_set。
map和set：
（1）需要熟練掌握這些容器的常見接口使用（增刪查改：insert、erase、find、operator[]、iterator）
（2）常見經(jīng)典問題，例如：
底層實現(xiàn)原理，即紅黑樹。掌握紅黑樹的規(guī)則、增刪查改的效率。
（3）multi版本特點。
unoredered_map和unoredered_set：
（1）需要熟練掌握這些容器的常見接口使用（增刪查改：insert、erase、find、operator[]、iterator）
（2）常見經(jīng)典問題，例如：
（3）multi版本特點。
vector和list：
（1）需要熟練掌握這些容器的常見接口使用。
vector：push_back/pop_back、resize/reserve（注意二者區(qū)別）、insert/erase、[]+size()、iterator
list：push_back/pop_back、push_front/pop_front、insert/erase、iterator
（2）常見經(jīng)典問題，例如：
其他容器：
（1）需要熟練使用，了解原理的容器。
string：+=、find、insert/erase、[]、迭代器、c_str、sub_str、reserve/resize、to_string/stoi
stack/queue：push/pop、top、front/back、empty/size
priority_queue：push/pop、top、size/empty
bitset：set、reset、test
（2）不需要熟練使用，稍微了解原理。
array(C++11)：核心價值相比c靜態(tài)數(shù)組，[]絕對檢查越界。委員會期望替代靜態(tài)數(shù)組，實際效果不明顯
forward_list(C++11)：只是頭插頭刪，又想節(jié)省一點點空間，比起list有一點點優(yōu)勢
deque：頭尾插入刪除多，可能還需要一些下標的隨機訪問。要注意的是不要大量下表隨機訪問，否則不如用vector好
2.迭代器
（1）什么迭代器(熟練掌握)
答：行為像指針一樣的類型?？赡苁侵羔樋赡苁潜活惙庋b的指針，不關(guān)注容器底層細節(jié)的情況下輕松訪問容器。
（2）迭代器價值是什么？(熟練掌握)
（3）什么是迭代器失效？(熟練掌握)
答：①迭代器指向的空間野指針。 ②迭代器指向的位置已經(jīng)不是原來的位置，意義變了。
vector：①insert擴容，導(dǎo)致野指針。 ②insert不擴容，但是挪動數(shù)據(jù)，指向位置已經(jīng)不是原來的位置。 ③erase數(shù)據(jù)以后，挪動數(shù)據(jù)，指向位置已經(jīng)不是原來位置。
list：erase以后，節(jié)點刪除，導(dǎo)致野指針。
map/set/unordered_map/unordered_set：erase以后，節(jié)點刪除，導(dǎo)致野指針。
（4）反向迭代器的原理（了解）
答：適配器，封裝正向迭代器實現(xiàn)。
（5）迭代器分類(了解)
答：迭代器被分成了五個類型，如下圖所示，前兩個類型只寫input_iterator_tag和只讀output_iterator_tag是抽象類型，STL中沒有對應(yīng)的實際類型。有實際對應(yīng)類型的是后三個類型迭代器，單向forward_iterator_tag、雙向bidirectional_iterator_tag、隨機random_access_iterator_tag。
單向（支持++）：forward_list、unordered_map/unordered_set
雙向（支持++/--）：map/set、list
隨機（支持++/--/+/-）：string、vector、deque
注：如下圖所示，算法庫中函數(shù)的迭代器參數(shù)名暗示了要傳迭代器的類型，所以使用函數(shù)前需確定了容器的迭代器的類型。
需要傳單向迭代器的函數(shù)可以傳單向迭代器、雙向迭代器、隨機迭代器，需要傳雙向迭代器的函數(shù)可以傳雙向迭代器、隨機迭代器，需要傳隨機向迭代器的函數(shù)只能傳隨機迭代器。
3.算法
解釋：
（1）next_permutation/prev_permutation的使用方式如下圖所示，其中next_permutation進行全排列前要求數(shù)據(jù)是升序的，prev_permutation進行全排列前要求數(shù)據(jù)是降序的。
（2）lower_bound/upper_bound使用前需要進行排序。lower_bound函數(shù)返回數(shù)據(jù)中第一個大于等于給定數(shù)值的位置，upper_bound函數(shù)返回數(shù)據(jù)中第一個大于給定數(shù)值的位置。
4.仿函數(shù)/函數(shù)對象
問題：什么是仿函數(shù)？仿函數(shù)作用是什么(結(jié)合實際用場景講解)
答：仿函數(shù)主要作用在容器和算法上，其本質(zhì)上是實現(xiàn)了operator()的類，這個類對象可以像函數(shù)一樣去使用。
5.STL原理
問題：說說你理解STL是什么？整體說一下六大組件是什么？互相之間關(guān)聯(lián)關(guān)系？
答：前面底層實現(xiàn)角度的內(nèi)容。
C++知識掌握：基礎(chǔ)入門語法、類和對象、模板、繼承和多態(tài)、異常、IO流、C++類型轉(zhuǎn)換、C++11、STL、拓展學(xué)習(xí)。
注：
1.基礎(chǔ)入門語法
（1）函數(shù)重載：①函數(shù)重載的規(guī)則要求。 ②為什么C語言不支持重載？C++支持
（2）引用(重點)：①什么是引用？ ②指針和引用區(qū)別是什么？ ③引用的使用場景是什么？
（3）inline：①inline價值和意義是什么？?②宏的缺點？③C++用inline、const、enum去替代宏。
（4）缺省參數(shù)
（5）namespace
2.類和對象
（1）面向?qū)ο蠛兔嫦蜻^程的理解。結(jié)合實際樣例解答。
（2）面向?qū)ο笕筇匦允鞘裁?？封裝、繼承、多態(tài)、你對他們理解是什么？結(jié)合實際樣例解答。
（3）8個默認成員函數(shù)：①構(gòu)造和析構(gòu)?②拷貝構(gòu)造和拷貝賦值?③移動構(gòu)造和移動賦值 ④operator&不關(guān)注 ⑤什么情況下會默認生成？默認生成的都干了什么？ ⑥構(gòu)造函數(shù)初始化列表（初始化列表價值，哪些成員必須在初始化列表初始化）
（4）對象實例化：①對象大小計算--內(nèi)存對齊?②空類的大小？為什么是1？
（5）this指針：①什么是this指針?②this存在哪？
（6）運算符重載：①哪些運算符不能重載?②運算符重載意義是什么？
（7）static成員
（8）友元
3.模板
（1）模板分類：函數(shù)模板、類模板
（2）模板的原理：模板的實例化
（3）讓你寫一個函數(shù)模板或者類模板檢驗語法掌握
（4）非類型模板參數(shù)
（5）模板的特化：unordered_map默認支持string做key就是特化一個場景
（6）為什么模板不支持分離編譯？怎么解決？解決原理是什么？
4.繼承和多態(tài)
（1）什么是繼承？什么是多態(tài)？
（2）繼承后成員權(quán)限
（3）派生中的默認成員函數(shù)
（4）子類到父類對象之間賦值兼容轉(zhuǎn)換
（5）多繼承--菱形繼承：①菱形繼承的問題是什么？如何解決？?②虛繼承是如何解決的？（切記不要跟虛函數(shù)多態(tài)混了，兩個地方都用了virtual但是他們之間沒有關(guān)聯(lián)關(guān)系）
（6）繼承和組合：is-a和has-a
（7）多態(tài)的條件是什么？原理是什么？
（8）還有一些問題。如：static是否可以是虛函數(shù)？inline是否可以是虛函數(shù)等等。
5.異常
（1）異常優(yōu)缺點
（2）異常的使用規(guī)則
6.IO流
（1）筆試面試基本不考。從用的角度掌握一下文件流和字符串流，一些項目中可能會用。
7.C++類型轉(zhuǎn)換
（1）四種強制類型轉(zhuǎn)是什么？他們作用是什么
8.C++11
（1）右值引用：①右值引用和左值引用的區(qū)別？?②移動構(gòu)造和移動賦值?③右值引用的使用場景？(push_back(T&& val)、傳值返回的函數(shù)如to_string)如何減少拷貝？提高效率 ④完美轉(zhuǎn)發(fā)解決什么問題？
（2）lamdba：①語法規(guī)則 ②使用場景和優(yōu)勢?③底層實現(xiàn)原理
（3）智能指針：①發(fā)展歷史?②auto_ptr/unique_ptr/shared_ptr/weak_ptr原理及簡單模擬實現(xiàn)?③什么是循環(huán)引用？如何解決？解決原理 ④定制刪除器
（4）其他：①線程庫?②列表初始化?③STL中容器變化（新容器、移動構(gòu)造和移動賦值、插入接口的變化例如push_back(T&& val)和empalce等） ④可變參數(shù)模板 ⑤auto ⑥范圍for
9.STL
10.拓展學(xué)習(xí)
（1）《effctive C++》值得去讀一遍
（2）《C++ primer》第五版，推薦手邊留一本作為語法字典
（3）《STL源碼剖析》有時間可以結(jié)合源代碼進行學(xué)習(xí)
（4）設(shè)計模式：①單例模式 ②工廠模式 ③適配器模式 ④迭代器模式 ⑤觀察者模式
數(shù)據(jù)結(jié)構(gòu)知識掌握：線性表、樹型結(jié)構(gòu)、哈希、排序、圖、擴展學(xué)習(xí)
注：
1.線性表
（1）順序表
（2）鏈表
（3）棧和隊列
（4）串
2.樹型結(jié)構(gòu)
（1）基礎(chǔ)二叉樹：①二叉樹概念及性質(zhì) ②常見OJ題，下去手撕一遍 ③堆（topK、堆排序）?
（2）搜索樹：①二叉搜索樹（缺陷） ②AVL樹（規(guī)則、如何旋轉(zhuǎn)平衡、效率） ③紅黑樹（規(guī)則、如何旋轉(zhuǎn)平衡、效率、對比AVL樹的優(yōu)勢是什么？） ④B樹系列
3.哈希
（1）什么是哈希/散列
（2）什么是哈希沖突？
（3）哈希表①閉散列開放定址法（線性探測、二次探測） ②哈希桶（單個桶沖突很多怎么辦？改成掛紅黑樹） ③負載因子 ④跟紅黑樹會有一些對比
（4）位圖
（5）布隆過濾器：①在是準確的？還是不在是準確的？不在是準確的 ②是否支持刪除
（6）海量數(shù)據(jù)處理：①位圖問題 ②topk問題 ③哈希切分問題
4.排序
（1）常見排序思想及實現(xiàn)：①插入排序 ②希爾排序 ③選擇排序 ④堆排序 ⑤冒泡排序 ⑥快速排序（什么時候最壞且如何優(yōu)化、非遞歸） ⑦歸并排序 ⑧計數(shù)排序
（2）復(fù)雜度
（3）穩(wěn)定性
5.圖
6.擴展學(xué)習(xí)
（1）跳表
（2）LRUCahe
（3）并查集
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
重慶分公司
重慶分公司
