總結(jié)了語法、數(shù)據(jù)結(jié)構(gòu)、常見排序算法、操作系統(tǒng)、網(wǎng)絡(luò)五大塊常見校招面試題。歡迎補充與修正。

★★語法知識★★

一、C++與C的區(qū)別

面向?qū)ο笈c面向過程的區(qū)別

面向過程

面向過程編程是就分析出解決問題題的步驟，然后把這些步驟一步一步的實現(xiàn)，使用的時候一個一個的一次調(diào)用就可以了。

面向?qū)ο?/h3>

面向?qū)ο缶幊叹褪前褑栴}分解成各個對象，建立對象的目的不是為了完成一個步驟，而是為了描述某個市委在整個解決問題的步驟中的行為。

舉個例子（玩五子棋）

使用面向過程的思想來考慮就是：開始游戲，白棋先走、繪制畫面、輪到黑子、繪制畫面、判斷輸贏、重復(fù)之前的過程，輸出最終結(jié)果。

使用面向?qū)ο蟮乃枷雭砜紤]就是：玩家系統(tǒng)、棋盤系統(tǒng)、判定系統(tǒng)、輸出系統(tǒng)。

面向?qū)ο缶褪歉叨鹊膶嵨锍橄蠡?#xff0c;也就是功能的劃分，面向過程就是自頂向下編程，也就是步驟的劃分

具體語言的區(qū)別

1、關(guān)鍵字不同

C99有32個關(guān)鍵字

C++98有63個關(guān)鍵字

一些關(guān)鍵字細微的區(qū)別

1、struct：在C語言猴子那個struct定義的變量中不能由函數(shù)，在C++中可以有函數(shù)

2、malloc：malloc的返回值是void*，在C語言中可以賦值給任意類型的指針，在C++中必須要進行強制類型轉(zhuǎn)換，否則會報錯。

3、class和struct：class是對struct的擴展，struct的默認訪問權(quán)限是public，而class的默認訪問全顯示private

2、后綴名不同

C源文件的后綴是.c，C++源文件的后綴是.cpp，在VS中，如果在創(chuàng)建源文件的時候什么都不給，默認的就是.cpp

3、返回值不同

在C語言中，如果一個函數(shù)沒有指定返回值得類型，默認的返回值為int類型，并且會返回一個隨機數(shù)，一般為0xCCCCCCCC，C++中如果一個函數(shù)沒有返回值，則必須要指定為void，否則編譯不會通過。

4、參數(shù)列表不同

在C語言中，函數(shù)沒有指定參數(shù)列表的時候，默認可以接受多個參數(shù)，但是不支持無名參數(shù)，在C++中，因為嚴格的參數(shù)類型檢測，沒有參數(shù)列表的函數(shù)，默認為void，不接受任何參數(shù)，但是他支持無名參數(shù)。

5、缺省參數(shù)

缺省參數(shù)的聲明或定制函數(shù)時的參數(shù)指定一個默認值。在調(diào)用該函數(shù)時，如果沒有指定實參則可以采用該默認值，則使用指定的參數(shù)。但是這在C語言中是不支持的。

6、函數(shù)重載

函數(shù)重載是函數(shù)的一種特殊情況，指的是在同一作用域中，聲明幾個功能類似的同名函數(shù)，這些同名函數(shù)的形參列表必須不同，或者是在類中使用const修飾的函數(shù)和沒有使用const修飾的函數(shù)，常用來處理實現(xiàn)功能類似但是數(shù)據(jù)類型不同的問題。在C語言中沒有函數(shù)重載，是因為C語言對函數(shù)名的修飾只是在函數(shù)名前添加一個下劃線，但是C++對函數(shù)名的修飾會添加上該函數(shù)的返回值和參數(shù)列表。

7、標準輸入輸出

在C語言中使用的是scanf()和printf()來實現(xiàn)的，但是C++中是使用類來實現(xiàn)的。cin、cout對象，他們本身并不是C++語言的組成部分，在C++中不提供內(nèi)在的輸入輸出運算符，這時與其他語言不相同的地方，他的輸入和輸出是通過C++中的類來實現(xiàn)的，cin和cout都是這些類的實例，是在C++語言的外部實現(xiàn)的。

8、動態(tài)內(nèi)存管理

C語言使用的是malloc/free函數(shù)，C++在此基礎(chǔ)上還添加了new/delete兩個關(guān)鍵字。

9、const修飾的變量

C語言中const修飾的變量不可以用在定義數(shù)組時的大小，并且在定義的時候可以不設(shè)定初始值，但是在C++中修飾的變量在定義的時候必須要設(shè)定初始值，并且可以用在定義數(shù)組的大小，，如果不進行取地址或解引用的話，是存放在符號表中的，不開辟內(nèi)存。

二、C++面向?qū)ο?/h1>

面向?qū)ο蟮奶攸c

維護性、復(fù)用性、擴展性。

封裝體現(xiàn)了維護性，按照信息屏蔽的原則，把對象的屬性和操作結(jié)合在一起，構(gòu)成一個獨立的對象。通過限制對屬性和操作的訪問權(quán)限，可以將屬性隱藏在對象內(nèi)部，對外提供一定的接口，在對象之外只能通過接口對對象進行操作，這樣增加了對象的獨立性，外部的對象不能直接操作對象的屬性，只能使用對象提供的服務(wù)，從而保證了數(shù)據(jù)的可靠性。

繼承體現(xiàn)了復(fù)用性，當定義了一個類后，又需要定義一個新類但是這個類與原來的類相比只是增加或修改了部分屬性和操作，這時可以引用原來的類派生出新的類，新類中只需要描述自己特有的屬性和操作，這樣就大大的簡化了對問題的描述，提高了程序的復(fù)用性。

多態(tài)體現(xiàn)了擴展性，多態(tài)就是一個接口多種實現(xiàn)，當需要添加新的模塊功能的時候，不需要改變原來的功能，只需要添加新的即可，這樣就實現(xiàn)了擴展性。

面向?qū)ο蟮膬?yōu)點

易于維護：可讀性比較高，如果有改變的需求，由于繼承的存在，維護也只是局部模塊，所以說維護起來是非常方便和較低成本的。

質(zhì)量高：可重用現(xiàn)有的，在以前的項目的領(lǐng)域中一杯測試過的類使系統(tǒng)滿足業(yè)務(wù)需求并具有較高的質(zhì)量。

效率高：在軟件開發(fā)時，根據(jù)設(shè)計的需要對現(xiàn)實事件的事務(wù)進行抽象，產(chǎn)生類。這樣結(jié)局問題的方法接近于日常生活和自然的思考方式，必定會提高軟件開發(fā)的效率和質(zhì)量。

1、c語言是面向過程的結(jié)構(gòu)化 語言，易于調(diào)試和維護。

2、表現(xiàn)能力和處理能力極強，可以直接訪問內(nèi)存的物理地址。

3、C語言實現(xiàn)了對硬件的編程操作，也適合于引用軟件的開發(fā)。

概述

封裝可以使得代碼模塊化，繼承可以擴展已經(jīng)存在的代碼，他們的目的是為了代碼重用。而多態(tài)的目的是為了接口重用。

封裝

封裝是設(shè)計類的一個基本原理，是將抽象得到的數(shù)據(jù)和行為相結(jié)合，形成一個有機的整體，也就是將數(shù)據(jù)與對數(shù)據(jù)進行的操作進行有機的結(jié)合，從而形成類，其中的數(shù)據(jù)和函數(shù)都是類的成員。

繼承

如果B是繼承了A，那么就把這個B稱為是A的子類，把A稱為B的父類。繼承可以使子類具有父類的各種屬性和方法和方法，就不用再次編寫相同的代碼。子類繼承父類的同時，可以重新定義某些屬性，并重定義其中的一些方法，也就是隱藏父類中原有的屬性和方法，使其獲得于父類不同的功能。

單繼承

單繼承就是一個派生類繼承一個基類。單繼承的繼承規(guī)則為：所有繼承下來的基類成員變量存放在派生類添加的成員變量之前，也就是基類的成員變量的內(nèi)存地址低于派生類的內(nèi)存地址，可以看做是將基類的內(nèi)存空間進行了一次拷貝，并且在拷貝的內(nèi)存空間后面加上派生類自己的成員。

多繼承

菱形繼承

菱形繼承存在的問題就是數(shù)據(jù)二義性，相應(yīng)的解決方案就是虛擬繼承。多繼承的繼承規(guī)則是：以單繼承的方式按照父類聲明的順序繼承每個父類，可以看做是按照聲明的順序?qū)⒚總€父類的內(nèi)存空間拷貝到一起，并且在后面添加上派生類自己的成員。

虛擬繼承

虛擬繼承是解決C++中多重繼承問題的一種手段，從不同途徑繼承來的同一基類，會在子類中存在多份拷貝。這樣會存在兩個問題，一個是對于存儲空間的浪費，還有就是數(shù)據(jù)的二義性。虛擬繼承就是針對這兩個問題出現(xiàn)的，虛擬繼承的底層實現(xiàn)原理與編譯器相關(guān)，一般通過虛基類和虛基表實現(xiàn)，每個虛繼承的子類都有一個虛基類指針和虛基表，當虛擬繼承的子類被當做父類繼承時，虛基類指針也會被繼承。實際上vbptr指的是虛基類表指針，這個指針指向虛基類表，在虛基類表中記錄了虛基類與本類的偏移地址，通過偏移地址，可以找到虛基類的成員，虛擬繼承和虛函數(shù)有著相同之處，都是利用了虛指針和虛表，虛基類表中存儲的是虛基類相對于直接繼承類的便宜，而虛函數(shù)表中存儲的時候虛函數(shù)的地址。

繼承中的訪問權(quán)限

父類的私有成員在子類中無論以什么方式繼承都是不可見的，這個的不可見指的是private成員仍然被繼承到了子類中，但是在語法上限制子類對象不管實在類內(nèi)還是在類外都是無法訪問它的。

子類以公有方式繼承父類時，父類的成員在子類中保持原有的屬性。

子類以保護方式繼承父類時，父類中的公有成員在子類中成了保護成員。

子類以私有方式繼承父類時，父類中所有成員在子類中都是私有的。

使用class時默認的繼承方式時私有的，使用struct時則默認的繼承方式是共有的。

還有一點就是友元是類級別的，不存在繼承的問題，也就是子類不能繼承父類的友元關(guān)系。

多態(tài)

多態(tài)可以簡單的概括為“一個接口，多種方法”，字面意思是多種形態(tài)。多態(tài)分為靜態(tài)多態(tài)和動態(tài)多態(tài)。

靜態(tài)多態(tài)

靜態(tài)多態(tài)也稱作靜態(tài)綁定或者是早綁定。地址的綁定是編譯器在編譯的時候完成的，編譯器根據(jù)函數(shù)實參的類型，可以推斷出要調(diào)用那個函數(shù)，這里可能會進行隱式的類型轉(zhuǎn)換，如果有對應(yīng)的函數(shù)就調(diào)用了，否則編譯報錯。靜態(tài)多態(tài)又分為函數(shù)重載和泛型編程。

函數(shù)重載

函數(shù)重載是在相同的作用域中，只有函數(shù)的名稱相同，參數(shù)個數(shù)或參數(shù)類型不同。編譯器根據(jù)函數(shù)不同的參數(shù)表，對同名函數(shù)的名稱修飾，然后這些同名函數(shù)就成了不同的函數(shù)。這個在C語言中是不支持的，因為c語言中對函數(shù)的名稱修飾較為簡單，在VS2013編譯器中，c語言對函數(shù)名稱修飾的處理只關(guān)注到了函數(shù)名，對函數(shù)名的修飾只是簡單的在函數(shù)名前添加_，而c++語言除了函數(shù)名，還關(guān)注了函數(shù)的參數(shù)，對函數(shù)名的修飾時候要加上參數(shù)，通過對函數(shù)名稱的修飾不同，編譯器調(diào)用函數(shù)時所找的符號就不同。

泛型編程

泛型編程指的是編寫?yīng)毩⒂谔囟愋偷拇a，泛型編程在C++中的主要是實現(xiàn)為函數(shù)模板和類模板。泛型編程的特性有如下幾點：

1、函數(shù)模板并不是真正的函數(shù)，他只是C++編譯器生成具體的函數(shù)的一個模子。

2、函數(shù)模板本身并不生成函數(shù)，實際生成的函數(shù)是替換函數(shù)模板的那個函數(shù)，這種替換在編譯期就綁定了。

3、函數(shù)模板不是只編譯一份滿足多重需要，而是為每一種替換他的函數(shù)編譯一份。

4、函數(shù)模板不允許自動類型轉(zhuǎn)換。

5、函數(shù)模板不可以設(shè)置默認模板參數(shù)。

動態(tài)多態(tài)

C++中的動態(tài)多態(tài)是基于虛函數(shù)的。對于相關(guān)的對象類型，確定他們之間的一個共同的功能集，然后在父類中把這些共同的功能聲明為多個公共的虛函數(shù)接口。各個子類重寫這些虛函數(shù)，完成具體的功能。操作函數(shù)通過指向基類的引用或指針來操作這些對象，對虛函數(shù)的調(diào)用會自動綁定到實際提供的子類對象上去。

虛函數(shù)

虛函數(shù)之所以叫做虛函數(shù)，是因為他的推遲聯(lián)編和動態(tài)聯(lián)編，一個類的虛函數(shù)的調(diào)用并不是在編譯的時候確定的，而是在運行的時候確定的，虛函數(shù)通過基類的指針或者引用指向派生類對象實現(xiàn)多態(tài)。

純虛函數(shù)

純虛函數(shù)指的是在基類中聲明的虛函數(shù)，但是沒有在基類中定義，要求在任何派生類中都要定義自己實現(xiàn)方法。如果一個類中有純虛函數(shù)，則這個類被稱為抽象類，由于這個類的構(gòu)建并不完成，所以不能生成一個對象。繼承了抽象類的派生類必須要將純虛函數(shù)實現(xiàn)，否則同樣是抽象類，不能生成對象。

虛函數(shù)表

在C++中虛函數(shù)通話四通過虛函數(shù)表來實現(xiàn)的，這個表中存放的是虛函數(shù)的地址，他是屬于類的，不屬于某個具體的對象，在一個類中只有一個虛表，所有對象共享同一份虛表。為了指定對象的虛表，在對象構(gòu)造的時候就在對象的內(nèi)部包含了虛表指針_vfptr，一般是放在頭部。

關(guān)于虛函數(shù)表有兩種情況是要分清楚的，多繼承和多重繼承中的虛表是不一樣的。

多繼承指的是有一個子類繼承了兩個基類，比如說有A，B，C三個類，在A和B類中都有虛函數(shù)，C類依次繼承了A類和B類，這時候C類中的虛表就有了A類和B類兩個虛表，并且C類中的虛表指針是以A類虛表地址為基礎(chǔ)的，如果想要獲取到B類虛表的地址可以讓指針向后偏移A類的大小或者給出一個B類的指針指向C類對象發(fā)生一個天然的轉(zhuǎn)換，需要注意的是在C類中的重寫的虛函數(shù)會覆蓋A類和B類中的同名虛函數(shù)，如果C類中的虛函數(shù)在A類和B類中沒有，就添加到A類的虛函數(shù)表中，但是A類指針不可以調(diào)用，如果是只在A類或者B類中有的虛函數(shù)，在C類中沒有，那么只能是擁有虛函數(shù)的父類和C類可以調(diào)用。

多重繼承就是B類繼承了A類，C類繼承了B類，在B類中的重寫的虛函數(shù)會在虛函數(shù)表中覆蓋A類的同名虛函數(shù)，并將B類新添加的虛函數(shù)放在B類虛函數(shù)表的末尾，C類也是如此，C類的虛表是從B類中繼承的，在C類中的重寫的虛函數(shù)會在虛函數(shù)表中覆蓋B類的同名虛函數(shù)，并將C類新添加的虛函數(shù)放在C類虛函數(shù)表的末尾。

靜態(tài)多態(tài)多態(tài)的比較

靜態(tài)多態(tài)

優(yōu)點

1、靜態(tài)多態(tài)通過模板編程為C++帶來了泛型設(shè)計的概念,比如STL。

2、靜態(tài)多態(tài)是在編譯期完成的，所以效率很高，編譯器可以對其進行優(yōu)化。

缺點

由于模板是實現(xiàn)靜態(tài)多態(tài),所以模板的不足也是靜態(tài)多態(tài)的劣勢,比如調(diào)試困難、編譯耗時、代碼膨脹。

動態(tài)多態(tài)

優(yōu)點

1、實現(xiàn)與接口分離，可復(fù)用。

缺點

1、運行時綁定，導(dǎo)致一定程度上的運行時開銷。

2、編譯器無法對虛函數(shù)進行優(yōu)化。

3、笨重的類繼承體系，對接口的修改影響整個類層次。

不同點

本質(zhì)不同：

早晚綁定，靜態(tài)多態(tài)是在編譯期決定的，由模板實現(xiàn)完成，而動態(tài)多態(tài)是在運行期間決定的，由繼承、虛函數(shù)實現(xiàn)。

接口方式不同：

動態(tài)多態(tài)的接口是顯式的，以函數(shù)名為中心，通過虛函數(shù)在運行期間實現(xiàn)，靜態(tài)多態(tài)的接口是隱式的，以有效表達為中心，通過模板在編譯期間完成。

應(yīng)用形式上：

靜多態(tài)是發(fā)散式的，讓相同的實現(xiàn)代碼應(yīng)用于不同的場合。

動多態(tài)是收斂式的，讓不同的實現(xiàn)代碼應(yīng)用于相同的場合。

思維方式上：

靜多態(tài)是泛型式編程風(fēng)格，它看重的是算法的普適性。

動多態(tài)是對象式編程風(fēng)格，它看重的是接口和實現(xiàn)的分離度。

相同點

夠可以實現(xiàn)多態(tài)性，靜態(tài)多態(tài)/編譯期多態(tài)，動態(tài)多態(tài)/運行期多態(tài)。

都可以是使接口和實現(xiàn)分離，一個是模板定義接口，類型參數(shù)定義實現(xiàn)，一個是基類定義接口，繼承類負責實現(xiàn)。

虛函數(shù)面試題

inliine函數(shù)可以實虛函數(shù)碼？

不可以，因為inline函數(shù)沒有地址，無法將他存放到虛函數(shù)表中。

靜態(tài)成員可以是虛函數(shù)嗎？

不能，因為靜態(tài)成員函數(shù)中沒有this指針，使用：：成員函數(shù)的嗲用用方式無法訪問虛函數(shù)表，所以靜態(tài)成員函數(shù)無法放進虛函數(shù)表。

構(gòu)造函數(shù)可以是虛函數(shù)嗎？

不可以，因為對象中的虛函數(shù)指針是在對象構(gòu)造的時候初始化的。

析構(gòu)函數(shù)可以是虛函數(shù)嗎？什么場景下析構(gòu)函數(shù)是虛函數(shù)？

可以，最好將析構(gòu)函數(shù)設(shè)置為虛函數(shù)，因為這樣可以避免內(nèi)存泄漏的問題，如果一個父類的指針指向了子類的的對象，如果子類對象中的虛函數(shù)沒有寫成多態(tài)的，他只會調(diào)用父類的析構(gòu)函數(shù)，不會調(diào)用自己的析構(gòu)函數(shù)，但是他創(chuàng)建對象的時候調(diào)用了構(gòu)造函數(shù)，所以說就用子類的構(gòu)造函數(shù)就應(yīng)該該取調(diào)用他的析構(gòu)函數(shù)，這樣才能保證所有的必須釋放的資源都是放了，才可以保證不會有內(nèi)存泄漏。如果是多態(tài)的，就會先去調(diào)用子類的析構(gòu)函數(shù)，然后再取調(diào)用父類的析構(gòu)函數(shù)，這樣子類和父類的資源就都可以釋放。

對象訪問普通函數(shù)快還是虛函數(shù)快？

如果是普通對象，是一樣快的，如果是指針對象或者是引用對象，調(diào)用普通函數(shù)更快一些，因為構(gòu)成了多態(tài)，運行時調(diào)用虛函數(shù)要先到虛函數(shù)表中去查找。這樣然后才拿到韓式的地址，這樣就不如直接可以拿到函數(shù)地址的普通函數(shù)快。

虛函數(shù)表時再什么階段生成的？他存放在哪里？

虛函數(shù)時再編譯階段生成的，他一般存放再代碼段，也就是常量區(qū)。

是否可以將類中的所有成員函數(shù)都聲明稱為虛函數(shù)，為什么？

虛函數(shù)是在程序運行的時候通過尋址操作才能確定真正要調(diào)用的的函數(shù)，而普通的成員函數(shù)在編譯的時候就已經(jīng)確定了要調(diào)用的函數(shù)。這個兩者的區(qū)別，從效率上來說，虛函數(shù)的效率要低于普通成員函數(shù)，因為虛函數(shù)要先通過對象中的虛標指針拿到虛函數(shù)表的地址，然后再從虛函數(shù)表中找到對應(yīng)的函數(shù)地址，最后根據(jù)函數(shù)地址去調(diào)用，而普通成員函數(shù)直接就可以拿到地址進行調(diào)用，所以沒必要將所有的成員函數(shù)聲明成虛函數(shù)。

虛函數(shù)表指針被編譯器初始化的過程怎么理解的？

當類中聲明了虛函數(shù)是，編譯器會在類中生成一個虛函數(shù)表VS中存放在代碼段，虛函數(shù)表實際上就是一個存放虛函數(shù)指針的指針數(shù)組，是由編譯器自動生成并維護的。虛表是屬于類的，不屬于某個具體的對象，一個類中只需要有一個虛表即可。同一個類中的所有對象使用同一個虛表，為了讓每個包含虛表的類的對象都擁有一個虛表指針，編譯器在每個對象的頭添加了一個指針，用來指向虛表，并且這個指針的值會自動被設(shè)置成指向類的虛表，每一個virtaul函數(shù)的函數(shù)指針存放在虛表中，如果是單繼承，先將父類的虛表添加到子類的虛表中，然后子類再添加自己新增的虛函數(shù)指針，但是在VS編譯器中我們通常看不到新添加的虛函數(shù)指針，是編譯器故意將他們隱藏起來，如果是多繼承，在子類中新添加的虛函數(shù)指針會存放在第一個繼承父類的虛函數(shù)表中。

多態(tài)的分類？

靜態(tài)綁定的多態(tài)的是通過函數(shù)的重載來實現(xiàn)的。動態(tài)綁定的多態(tài)是通過虛函數(shù)實現(xiàn)的。

為什么要引入抽象類和純虛函數(shù)？

為了方便使用多態(tài)特性，在很多情況下由基類生成對象是很不合理的，純虛函數(shù)在基類中是沒有定義的，要求在子類必須加以實現(xiàn)，這種包含了純虛函數(shù)的基類被稱為抽象類，不能被實例化，如果子類沒有實現(xiàn)純虛函數(shù)，那么它他也是一個抽象類。

虛函數(shù)和純虛函數(shù)有什么區(qū)別？

從基類的角度出發(fā)，如果一個類中聲明了虛函數(shù)，這個函數(shù)是要在類中實現(xiàn)的，它的作用是為了能讓這個函數(shù)在他的子類中能被重寫，實現(xiàn)動態(tài)多態(tài)。純虛函數(shù)，只是一個接口，一個函數(shù)聲明，并沒有在聲明他的類中實現(xiàn)。對于子類來說它可以不重寫基類中的虛函數(shù)，但是他必須要將基類中的純虛函數(shù)實現(xiàn)。虛函數(shù)既繼承接口的同時也繼承了基類的實現(xiàn)，純虛函數(shù)關(guān)注的是接口的統(tǒng)一性，實現(xiàn)完全由子類來完成。

什么是多態(tài)？他有什么作用？

多態(tài)就是一個接口多種實現(xiàn)，多態(tài)是面向?qū)ο蟮娜筇匦灾弧６鄳B(tài)分為靜態(tài)多態(tài)和動態(tài)多態(tài)。靜態(tài)多態(tài)包含函數(shù)重載和泛型編程，進程多態(tài)是程序調(diào)用函數(shù)，編譯器決定使用哪個可執(zhí)行的代碼塊。靜態(tài)多態(tài)是由繼承機制以及虛函實現(xiàn)的，通過指向派生類的基類指針或者引用，訪問派生類中同名重寫成員函數(shù)。墮胎的作用就是把不同子類對象都當作父類來看，可以屏蔽不同子類之間的差異，從而寫出通用的代碼，做出通用的編程，以適應(yīng)需求的不斷變化。

三、虛函數(shù)和純虛函數(shù)

概述

虛函數(shù)，它虛就虛在所謂的“推遲聯(lián)編”和“動態(tài)聯(lián)編”上，一個類虛函數(shù)的調(diào)用并不是在編譯時刻確定的，而是在運行的時候被確定。由于編寫代碼的時候并不能確定被調(diào)用的是基類函數(shù)還是那個派生類的函數(shù)，所以被稱為虛函數(shù)。

虛函數(shù)只能借助指針或引用來達到多態(tài)的效果。常用的方式是基類指針或引用指向子類的對象。當有多個子類的繼承時，可以統(tǒng)一用父類指針來表示各子類對象，但事實上所指的對象具體是哪一個，或者調(diào)用的函數(shù)是哪個子類中的函數(shù)，要在運行的時候才知道，這就實現(xiàn)了多態(tài)。

class parent {public:vritual void fun(){cout <<"parent::fun" << endl;} };class child :　public parent {public:void fun(){cout << "child :: fun" << endl;} };int main() {parent *a = new child;a->fun(); //這里的指針雖然是parent類型，但是指向的是child的fun函數(shù)。構(gòu)成了多態(tài)。return 0; }

語法

virtual void fun()=0; //純虛函數(shù) virtual void fun(); //虛函數(shù)

純虛函數(shù)

純虛函數(shù)是指在基類中聲明的虛函數(shù)，并沒有在基類中定義，要求在任何派生類中都要定義自己的實現(xiàn)方法。在類中有純虛函數(shù)的類被稱為抽象類，由于他的構(gòu)建并不完整，所以不能用抽象類來生成對象。繼承了抽象類的派生類必須要將純虛函數(shù)實現(xiàn)，否則同樣是抽象類，不能生成對象。

虛函數(shù)表

在C++中虛汗是是通過虛函數(shù)表來實現(xiàn)的（以下稱為虛表），在這張表中存放的是虛函數(shù)的地址，它是屬于類的，不屬于某個具體的對象，一個類中只有一個虛表，在同一個類中的所有對象都是用類中唯一這個虛表。為了指定對象的虛表，在對象構(gòu)造的時候就在對象內(nèi)部包含了虛表指針。為此編譯器在類中添加了一個*_vptr來指向虛表，并且這個指針的值會自動被設(shè)置為指向該類的虛表。在C++編譯器中，虛表指針在存放在每個對象的頭四個字節(jié)，并且虛函數(shù)表的末尾是以空指針結(jié)束。

關(guān)于虛函數(shù)表有兩種情況是要分清楚的，多繼承和多重繼承這兩種繼承中的虛表是不一樣的。

多繼承指的是有一個子類繼承了兩個基類，比如說有A，B，C三個類，在A和B類中都有虛函數(shù)，C類依次繼承了A類和B類，這時候C類中的虛表就有了A類和B類兩個虛表，并且C類中的虛表指針是以A類虛表地址為基礎(chǔ)的，如果想要獲取到B類虛表的地址可以讓指針向后偏移A類的大小或者給出一個B類的指針指向C類對象發(fā)生一個天然的轉(zhuǎn)換，需要注意的是在C類中的重寫的虛函數(shù)會覆蓋A類和B類中的同名虛函數(shù)，如果C類中的虛函數(shù)在A類和B類中沒有，就添加到A類的虛函數(shù)表中，但是A類指針不可以調(diào)用，如果是只在A類或者B類中有的虛函數(shù)，在C類中沒有，那么只能是擁有虛函數(shù)的父類和C類可以調(diào)用。

多重繼承就是B類繼承了A類，C類繼承了B類，在B類中的重寫的虛函數(shù)會在虛函數(shù)表中覆蓋A類的同名虛函數(shù)，并將B類新添加的虛函數(shù)放在B類虛函數(shù)表的末尾，C類也是如此，C類的虛表是從B類中繼承的，在C類中的重寫的虛函數(shù)會在虛函數(shù)表中覆蓋B類的同名虛函數(shù)，并將C類新添加的虛函數(shù)放在C類虛函數(shù)表的末尾。

虛函數(shù)面試題

inliine函數(shù)可以實虛函數(shù)碼？

不可以，因為inline函數(shù)沒有地址，無法將他存放到虛函數(shù)表中。

靜態(tài)成員可以是虛函數(shù)嗎？

不能，因為靜態(tài)成員函數(shù)中沒有this指針，使用：：成員函數(shù)的嗲用用方式無法訪問虛函數(shù)表，所以靜態(tài)成員函數(shù)無法放進虛函數(shù)表。

構(gòu)造函數(shù)可以是虛函數(shù)嗎？

不可以，因為對象中的虛函數(shù)指針是在對象構(gòu)造的時候初始化的。

析構(gòu)函數(shù)可以是虛函數(shù)嗎？什么場景下析構(gòu)函數(shù)是虛函數(shù)？

可以，最好將析構(gòu)函數(shù)設(shè)置為虛函數(shù)，因為這樣可以避免內(nèi)存泄漏的問題，如果一個父類的指針指向了子類的的對象，如果子類對象中的虛函數(shù)沒有寫成多態(tài)的，他只會調(diào)用父類的析構(gòu)函數(shù)，不會調(diào)用自己的析構(gòu)函數(shù)，但是他創(chuàng)建對象的時候調(diào)用了構(gòu)造函數(shù)，所以說就用子類的構(gòu)造函數(shù)就應(yīng)該該取調(diào)用他的析構(gòu)函數(shù)，這樣才能保證所有的必須釋放的資源都是放了，才可以保證不會有內(nèi)存泄漏。如果是多態(tài)的，就會先去調(diào)用子類的析構(gòu)函數(shù)，然后再取調(diào)用父類的析構(gòu)函數(shù)，這樣子類和父類的資源就都可以釋放。

對象訪問普通函數(shù)快還是虛函數(shù)快？

如果是普通對象，是一樣快的，如果是指針對象或者是引用對象，調(diào)用普通函數(shù)更快一些，因為構(gòu)成了多態(tài)，運行時調(diào)用虛函數(shù)要先到虛函數(shù)表中去查找。這樣然后才拿到韓式的地址，這樣就不如直接可以拿到函數(shù)地址的普通函數(shù)快。

虛函數(shù)表時再什么階段生成的？他存放在哪里？

虛函數(shù)時再編譯階段生成的，他一般存放再代碼段，也就是常量區(qū)。

是否可以將類中的所有成員函數(shù)都聲明稱為虛函數(shù)，為什么？

虛函數(shù)是在程序運行的時候通過尋址操作才能確定真正要調(diào)用的的函數(shù)，而普通的成員函數(shù)在編譯的時候就已經(jīng)確定了要調(diào)用的函數(shù)。這個兩者的區(qū)別，從效率上來說，虛函數(shù)的效率要低于普通成員函數(shù)，因為虛函數(shù)要先通過對象中的虛標指針拿到虛函數(shù)表的地址，然后再從虛函數(shù)表中找到對應(yīng)的函數(shù)地址，最后根據(jù)函數(shù)地址去調(diào)用，而普通成員函數(shù)直接就可以拿到地址進行調(diào)用，所以沒必要將所有的成員函數(shù)聲明成虛函數(shù)。

虛函數(shù)表指針被編譯器初始化的過程怎么理解的？

當類中聲明了虛函數(shù)是，編譯器會在類中生成一個虛函數(shù)表VS中存放在代碼段，虛函數(shù)表實際上就是一個存放虛函數(shù)指針的指針數(shù)組，是由編譯器自動生成并維護的。虛表是屬于類的，不屬于某個具體的對象，一個類中只需要有一個虛表即可。同一個類中的所有對象使用同一個虛表，為了讓每個包含虛表的類的對象都擁有一個虛表指針，編譯器在每個對象的頭添加了一個指針，用來指向虛表，并且這個指針的值會自動被設(shè)置成指向類的虛表，每一個virtaul函數(shù)的函數(shù)指針存放在虛表中，如果是單繼承，先將父類的虛表添加到子類的虛表中，然后子類再添加自己新增的虛函數(shù)指針，但是在VS編譯器中我們通常看不到新添加的虛函數(shù)指針，是編譯器故意將他們隱藏起來，如果是多繼承，在子類中新添加的虛函數(shù)指針會存放在第一個繼承父類的虛函數(shù)表中。

多態(tài)的分類？

靜態(tài)綁定的多態(tài)的是通過函數(shù)的重載來實現(xiàn)的。動態(tài)綁定的多態(tài)是通過虛函數(shù)實現(xiàn)的。

為什么要引入抽象類和純虛函數(shù)？

為了方便使用多態(tài)特性，在很多情況下由基類生成對象是很不合理的，純虛函數(shù)在基類中是沒有定義的，要求在子類必須加以實現(xiàn)，這種包含了純虛函數(shù)的基類被稱為抽象類，不能被實例化，如果子類沒有實現(xiàn)純虛函數(shù)，那么它他也是一個抽象類。

虛函數(shù)和純虛函數(shù)有什么區(qū)別？

從基類的角度出發(fā)，如果一個類中聲明了虛函數(shù)，這個函數(shù)是要在類中實現(xiàn)的，它的作用是為了能讓這個函數(shù)在他的子類中能被重寫，實現(xiàn)動態(tài)多態(tài)。純虛函數(shù)，只是一個接口，一個函數(shù)聲明，并沒有在聲明他的類中實現(xiàn)。對于子類來說它可以不重寫基類中的虛函數(shù)，但是他必須要將基類中的純虛函數(shù)實現(xiàn)。虛函數(shù)既繼承接口的同時也繼承了基類的實現(xiàn)，純虛函數(shù)關(guān)注的是接口的統(tǒng)一性，實現(xiàn)完全由子類來完成。

什么是多態(tài)？他有什么作用？

多態(tài)就是一個接口多種實現(xiàn)，多態(tài)是面向?qū)ο蟮娜筇匦灾弧６鄳B(tài)分為靜態(tài)多態(tài)和動態(tài)多態(tài)。靜態(tài)多態(tài)包含函數(shù)重載和泛型編程，進程多態(tài)是程序調(diào)用函數(shù)，編譯器決定使用哪個可執(zhí)行的代碼塊。靜態(tài)多態(tài)是由繼承機制以及虛函實現(xiàn)的，通過指向派生類的基類指針或者引用，訪問派生類中同名重寫成員函數(shù)。墮胎的作用就是把不同子類對象都當作父類來看，可以屏蔽不同子類之間的差異，從而寫出通用的代碼，做出通用的編程，以適應(yīng)需求的不斷變化。

四、引用和指針的區(qū)別

指針

對于一個類型T，T* 就是一個指向T的指針類型，也就是一個T*類型的變量能夠保存一個T對象的地址，而類型T可以添加一些限定詞，如const、volatile等等。

volatile提醒編譯器它后面所定義的變量隨時有可能改變。精確地說就是，遇到這個關(guān)鍵字聲明的變量，編譯器對訪問該變量的代碼就不再優(yōu)化，從而可以提供對特殊地址的穩(wěn)定訪問；如果不使用volatile，則編譯器對所聲明的語句進行優(yōu)化。

<1>中斷服務(wù)程序中修改的供其他程序檢測的變量需要加volatile；

<2>多任務(wù)環(huán)境下各任務(wù)間共享的標志應(yīng)該加volatile；

<3>多存儲器映射的硬件寄存器通常也要加volatile，因為每次對它的讀寫都可能有不同意義。

需要注意的是：頻繁地使用volatile很可能會增加代碼尺寸和降低代碼性能，因此要合理地使用volatile。

引用

引用就是一個對象的別名，主要用于函數(shù)參數(shù)和返回值類型，類型+&+變量名 = 被引用的對象。

不同點

1、引用是某塊內(nèi)存的別名，而指針指向的是一塊內(nèi)存，他的內(nèi)容是所指內(nèi)存的地址。

2、引用在創(chuàng)建時必須被初始化，但是指針可以為空，在C語言中NULL，在C++中是nullptr。所以指針在使用的時候必須要判空，引用就沒有必要。

3、引用不可以改變指向，一旦初始化了，就不能改變。指針可以改變自己的指向，可以指向其他對象。

4、對于引用來說，const int &a 和 int& const a沒有區(qū)別，因為都表示指向的對象是常量。對于指針來說，const int *p 說明p是指向常量的指針， int * const p 說明p本身就是一個常量。

5、引用的大小是指向?qū)ο蟮拇笮?#xff0c;而指針在32位機上是四字節(jié)，在64位機上是8字節(jié)，是指針本身的大小。

6、對引用++操作就是對引用指向的對象進行++操作，但是對指針++操作，表示的是地址的變化，向后移動一個指針的大小。

7、指針傳遞和引用傳遞

? 指針傳遞傳遞的是地址，在函數(shù)中定義了一個局部的指針變量，存放的是實參的地址，消耗了內(nèi)存，可以對地址進行加減操作，指向另一個變量，由于傳遞的是地址，所以不需要返回值，因為實際修改的就是實參的值。

? 引用傳遞同樣是地址，但是不會在函數(shù)中消耗內(nèi)存，直接對地址進行使用，對函數(shù)中的引用變量的加減操作直接影響外部的實參，并且不能指向另一個變量。在實際使用中傳遞引用的時候如果不希望實參被改變，通常要用const將其修飾。

五、深拷貝和淺拷貝

? 淺拷貝指的是將原始對象中的數(shù)據(jù)型字段拷貝到新對象中，將引用型對象的引用賦值到新對象中去，不把引用的對象復(fù)制進去，所以原始對象和新對象引用同一對象，新對象中的引用型字段發(fā)生變化會導(dǎo)致原始對象中對應(yīng)的字段發(fā)生變化。

? 深拷貝是在引用方面不同，深拷貝就是重新創(chuàng)建一個新的和原始字段內(nèi)容相同的字段，所以兩者的引用是不同的。其中一個對象發(fā)生變化并不會影響另一個對象。

編譯系統(tǒng)會在我們自己沒有定義拷貝構(gòu)造的時候調(diào)用默認的拷貝構(gòu)造函數(shù)，進行淺拷貝，也就是兩個對象使用同一份資源。當兩個對象調(diào)用析構(gòu)函數(shù)的時候，就會析構(gòu)兩次，導(dǎo)致內(nèi)存泄漏。所以對含有指針成員的對象或類中存在資源的對象進行拷貝的時候，必須要自己定義拷貝構(gòu)造函數(shù)，實現(xiàn)深拷貝，避免內(nèi)存泄漏。

六、常見關(guān)鍵字的作用

static

static有靜態(tài)局部變量、靜態(tài)全局變量和靜態(tài)方法三種使用方法，他們的共同點就是在本文件中聲明的靜態(tài)變量和靜態(tài)方法是不能被其他文件所使用的，和對應(yīng)的extern關(guān)鍵字，extern關(guān)鍵字聲明的全局變量和函數(shù)在整個工程中都是可以被使用的。

全局變量

有static聲明的全局變量，只能在函數(shù)體外部被定義，并且只能在本文件中有效，這點就是區(qū)別于普通的全局變量，普通的全局變量在其他的文件中也是可見的。在函數(shù)體重可以定義同名的局部變量，這時會隱藏這個靜態(tài)的，如果要使用靜態(tài)的全局變量，需要在變量名前添加::作用域運算符。

局部變量

static局部變量同樣只能在本文件中使用，靜態(tài)局部變量的生命周期不隨著函數(shù)的結(jié)束而結(jié)束，只能在第一調(diào)用函數(shù)的時候回他進行初始化，之后調(diào)用就會跳過初始化，他會在函數(shù)結(jié)束之后在內(nèi)存中保存當前的結(jié)果，而不會像普通的局部變量在清棧的時候銷毀，在內(nèi)存中他區(qū)別與局部變量的是局部變量每次調(diào)用函數(shù)時分配的內(nèi)存空間可能是不一樣的，但是靜態(tài)局部變量具有全局唯一性的特點，每次調(diào)用使用的時候用的都是同一塊內(nèi)存空間，但是這也造成了一個不可重入的問題。（現(xiàn)在有兩個進程A、B都要去調(diào)用這個函數(shù)fun()，如果是A先調(diào)用函數(shù)fun，在運行函數(shù)的時候突然失去了運行權(quán)，但是已經(jīng)將局部變量修改成了自己要試用的值，由于使用的是同一塊內(nèi)存空間，進程B調(diào)用函數(shù)的時候也將局部變量修改成了自己要使用的值，當進程A需要繼續(xù)執(zhí)行的時候，由于這塊內(nèi)存空間中的值已經(jīng)被修改了，所有進程A就得不到自己想要的結(jié)果）。

方法

static數(shù)據(jù)成員和成員函數(shù)

在C++中繼承了C語言中的static這個關(guān)鍵字，并且在類中給了第三種定義方法，表示只屬于一類而不是屬于類的某個對象的變量和函數(shù)。這個和普通的成員最大的區(qū)別就是在類中是唯一的，并且在內(nèi)存中只有一份，普通成員函數(shù)調(diào)用的時候需要傳入this指針，但是靜態(tài)成員函數(shù)調(diào)用的時候是沒有this指針的，只能在調(diào)用的時候使用類名加作用域來調(diào)用。在設(shè)計多線程操作的時候，有POSIX庫下的線程函數(shù)要求是全局的，所以普通的成員函數(shù)是無法直接作為線程函數(shù)的，但是靜態(tài)的成員函數(shù)是可以做線程函數(shù)的。

static函數(shù)和普通函數(shù)

普通函數(shù)的定義和聲明默認是extern的，在同一個工程中的其他文件中是可見的，如果在另一個文件中定義了相同的函數(shù)就會穿線重定義錯誤，當然這個重定義和繼承中的 重定義是不一樣的，這里的重定義指定的命名沖突。靜態(tài)函數(shù)在內(nèi)存中只有一份，但是普通的函數(shù)在每個被調(diào)用中都會維護一份拷貝。

extern

extern置于變量或函數(shù)前，用于標示變量或函數(shù)的定制在別的文件中，提示編譯器遇到這個變量或函數(shù)要在其他的模塊中查找。

extern “C”

如果是extern“C” void fun(int a, int b)；這樣是高數(shù)編譯器在編譯fun這個函數(shù)的時候要按照C的規(guī)則去編譯，而不是按照C++的，這一點主要是與C++支持重載，C語言不支持重載和函數(shù)被C++編譯器編譯后在苦衷的名字與C語言的不同有關(guān)。

當extern不與“C”在一起修飾變量或者函數(shù)時，比如extern int a；他的作用就是聲明函數(shù)或者全局變量的作用范圍和關(guān)鍵字，其生命的函數(shù)和變量可以在本工程中的所有文件中使用。需要注意的是他只是一個聲明，并不是定義。

const

使用const修飾類的成員變量的時候，必須要在初始化列表進行初始化，并且引用類型的成員變量和沒有默認默認構(gòu)造函數(shù)的對象成員也必須要在初始化列表進行初始化，如果有繼承的關(guān)系，如果父類沒有默認的構(gòu)造函數(shù)，也必須要在初始化列表進行初始化，初始化列表對數(shù)據(jù)成員的初始化順序時按照數(shù)據(jù)成員的聲明順序嚴格執(zhí)行的。

const修飾成員函數(shù)的時候，一般是放在成員函數(shù)的最后面，修飾的類的成員函數(shù)中隱藏的this指針，代表不可以通過this指針修改類的數(shù)據(jù)成員，這個使用方法也可以與普通的相同的成員函數(shù)構(gòu)成重載。

關(guān)于const還有一個問題就是傳參和賦值的問題，一般來說使用const修飾的變量是安全的，沒有使用const修飾的變量是不安全的，在傳參的時候可以讓非const修飾的變量傳給const修飾的，但是const修飾的變量不可以傳給非const修飾的形參，這就相當于將安全的變量交給了不安全的變量。

volatile

volatile一般用來修飾變量，他的存在是因為我們的程序在進行編譯的時候編譯器會進行一系列的優(yōu)化，比如說某個變量被修飾為const，編譯器就會認為這個值是只讀的，就會在寄存器中保存這個變量的值，每次需要的時候直接從寄存器中讀取，但是有的時候會在不經(jīng)意間修改了這個變量的值，那么編譯器是并不知道的，還是從寄存器中進行讀取，這樣就會造成結(jié)果不匹配。但是如果使用volatile聲明后，就是相當與告訴編譯器這個變量隨時會給變，需要每次都要從內(nèi)存中讀取，不需要優(yōu)化，從而避免了這個問題，volatile的應(yīng)用場景最多的是多線程對

define、const、inline區(qū)別

define作用域程序的預(yù)處理節(jié)點，而預(yù)處理主要的工作是宏替換、去注釋以及條件編譯，而define起作用的地方就在宏替換階段，只是單純的將宏替換為代碼。但是define只是單純的代碼替換，不會進行類型的檢查，很容易出錯。在C++中建議使用const、枚舉定義常量，這樣就會有類型檢查。于是C++中有提供了一個inline關(guān)鍵字，可以實現(xiàn)和define相同的功能，并且支持類型檢查和調(diào)試，一般生命在函數(shù)的定義前面，但是inline只是對編譯器的一種建議，一般建議代碼為3-5航左右，并且沒有復(fù)雜的邏輯結(jié)構(gòu)，例如循環(huán)、遞歸之類的。

七、malloc/free和new/delete的區(qū)別

1、malloc是從堆上開辟空間，而new是從自由存儲區(qū)開辟空間。自由存儲區(qū)是C++抽象出來的概念，不僅可以是堆，還可以是靜態(tài)存儲區(qū)。

2、malloc是函數(shù)，而new是關(guān)鍵字。

3、malloc對開辟的空間大小需要嚴格的指定，而new只需要對象名。

4、malloc開辟的空間既可以給單個對象使用也可以給數(shù)組使用，釋放的方式都是free()；而new開辟對象數(shù)組需要使用new[size]，釋放是使用delete[]。

5、malloc成功的返回值是void*，需要用戶進行強轉(zhuǎn)，申請空間失敗會返回NULL，所以在使用的時候需要進行判空處理，new成功返回的是對象指針，不需要強轉(zhuǎn)，失敗拋出異常，但是為了最大程度的兼容C，C++的new也支持失敗返回NULL，但是一般不使用。

6、new不僅負責開辟空間，還會去調(diào)用對象的構(gòu)造函數(shù)和析構(gòu)函數(shù)。

7、new申請空間的效率要低于malloc，因為new的底層是通過malloc實現(xiàn)的。

八、類中的成員函數(shù)占空間嗎？怎么調(diào)用？

類中的普通成員函數(shù)和靜態(tài)成員函數(shù)是不占用類的內(nèi)存的，只有在類中函數(shù)有虛函數(shù)的時候才會在類中添加一個虛函數(shù)指針，增加一個指針的大小。類中的成員函數(shù)實際上與普通的全局函數(shù)一眼，只不過是在編譯的時候在成員函數(shù)中國添加了一個指向當前對象的this指針，成員函數(shù)的地址是全局已知的，所以對象的內(nèi)存空間中是沒有必要去保存成員函數(shù)的地址的。在編譯的時候就已經(jīng)綁定了，類的屬性值得是類中的數(shù)據(jù)成員，他們是實例化一個對象的時候就為數(shù)據(jù)成員分配了內(nèi)存，但是成員函數(shù)是所有對象多公有的。

但是空類的大小是1個字節(jié)，這是為了保證兩個不同對象的地址不同。類的實例化是在內(nèi)存中分配一塊地址，每個勢力在內(nèi)存中歐擁有獨一無二的地址。同樣的，空類也會實例化，所以編譯器會給類隱含的添加一個字節(jié)，這樣空類實例化后就有了獨一無二的地址了。在一個空類中，在第一次實例化對象的時候就創(chuàng)建了默認的成員函數(shù)，并且這個成員函數(shù)是public和inline的。

九、NULL和nullptr的區(qū)別

傳統(tǒng)意義上來說，c++把NULL、0視為同一種東西，有些編譯器將NULL定義為 （（void*）0），有些將其定義為0 c++不允許直接將void隱式的轉(zhuǎn)化為其他類型，但是如果NULL被定義為 （（void*）0），當編譯char *p = NULL,NULL只好被定義為0。 還有：void func（int）；void func（char*）； 如果NULL被定義為0，func（NULL）會去調(diào)用void func（int），這是不合理的 所以引入nullptr，專門用來區(qū)分0、NULL。nullptr的類型為nullptr_t，能夠隱式的轉(zhuǎn)換為任何指針。所以用空指針就盡可能的使用nullptr。

十、智能指針

什么是智能指針？

智能指針最主要的作用就是管理一個指針，因為有可能申請的空間在函數(shù)結(jié)束的時候沒有及時的釋放，從而造成的了內(nèi)存泄漏。使用智能指針是要是針對這個問題，因為只能指針是一個類，在他生命周期結(jié)束的時候回去調(diào)用析構(gòu)函數(shù)進行資源的釋放，不需要進行手動的釋放資源。智能指針一共有auto_ptr、unique_ptr、shard_ptr、week_ptr四種。

auto_ptr：

是C++98提出來的智能指針，它采用的是所有權(quán)模式。就是將智能指針A賦值給智能指針B，就是將A的所有權(quán)交給了B，如果再想訪問A就會出錯，auto_ptr的缺點就是存在潛在的內(nèi)存崩潰問題。

unique_ptr

他解決了auto_ptr的問題，從名字可以知道他是獨有的智能指針，也就是說他不能進行賦值和拷貝操作，在unique_ptr中將拷貝構(gòu)造函數(shù)和賦值運算符重載私有，并且將其刪除。

shared_ptr

shared_ptr實現(xiàn)了共享的概念，多個智能指針可以指向同一份資源。他的原理是多個智能指針共同維護一份引用計數(shù)，當有第二個進行賦值和拷貝構(gòu)造的時候回將引用計數(shù)+1，每當一個智能指針使用完需要調(diào)用析構(gòu)函數(shù)的時候就會檢查是不是最后一個使用資源的，如果不是不進行釋放，否則要進行資源釋放。但是在使用的時候會出現(xiàn)這么一個情況，就是相互引用產(chǎn)生的死鎖問題，那么這兩個智能指針的引用計數(shù)將永遠不會下降為0，也就是資源不會得到釋放。這時就需要week_ptr了。

week_ptr

week_ptr是一種不控制對象生命周期的智能指針，他指向一個sheard_ptr管理的對象，進行該對象的內(nèi)存管理的是那個強引用的shared_ptr。week_ptr只是提供了對管理對象的一各訪問的手段，他只能從一個shared_ptr或另一個weak_ptr對象構(gòu)造，他的構(gòu)造函數(shù)和析構(gòu)函數(shù)是不會引起引用計數(shù)的改變。weak_ptr是用來解決shared_ptr相互引用時的死鎖問題,如果說兩個shared_ptr相互引用,那么這兩個指針的引用計數(shù)永遠不可能下降為0,資源永遠不會釋放。它是對對象的一種弱引用，不會增加對象的引用計數(shù)，和shared_ptr之間可以相互轉(zhuǎn)化，shared_ptr可以直接賦值給它，它可以通過調(diào)用lock函數(shù)來獲得shared_ptr。week_ptr只能是協(xié)助shared_ptr，他不能直接指向?qū)ο蟆?/p>

十一、默認構(gòu)造函數(shù)

默認構(gòu)造函數(shù)我認為是在調(diào)用時不需要顯式地傳入實參的構(gòu)造函數(shù)。如果定義一個對象時沒有使用初始化式，編譯器就會使用默認的構(gòu)造函數(shù)。編譯器生成默認構(gòu)造函數(shù)的情況用一句話可以進行概括，就是唯有默認構(gòu)造函數(shù)被編譯器需要的時候，編譯器才會生成默認的構(gòu)造函數(shù)。關(guān)于這個被編譯器需要分為幾種情況：當該類的類對象數(shù)據(jù)成員有默認構(gòu)造函數(shù)時，當類的基類有默認的構(gòu)造函數(shù)時、當該類的基類為虛基類時、當該類有虛函數(shù)時這四種情況。

默認構(gòu)造函數(shù)中有這么幾點需要注意：

1、不能讓無參的默認構(gòu)造函數(shù)和帶缺省的默認構(gòu)造函數(shù)同時存在，這樣就會讓編譯器產(chǎn)生二義性，從而生成編譯錯誤。

2、在使用無參默認構(gòu)造函數(shù)的時候不能再對象名后面加括號，否則會產(chǎn)生警告，讓編譯器誤認為是要聲明一個函數(shù)，但是又沒有找到該函數(shù)的定義，所以就產(chǎn)生了警告。

十二、前置++和后置++區(qū)別

1、從使用的角度來說：c++是先使用，后自增，++c是先自增，后使用

2、從系統(tǒng)的角度來說：c++表示取c的地址，把他放入寄存器中，然后增加內(nèi)存中的c，使用寄存器中的值，對于++c表示取c的地址，自增后把他放入寄存器中使用，很顯然++c的效率要比c++高，因為c++會生成一個臨時變量。

3、如果不需要返回自增后之前的值，那么c++和++c的效果是一樣的，但是要優(yōu)先使用++c，效率高。

十三、lambda表達式

[函數(shù)對象參數(shù)](操作符重載函數(shù)參數(shù))mutable或exception聲明 ->返回值類型{函數(shù)體}

函數(shù)對象參數(shù)

空：沒有使用任何的函數(shù)對象參數(shù)。 = ：函數(shù)體內(nèi)可以使用lambda所在作用域范圍內(nèi)所有可見的局部變量，并且是值傳遞。 & ：函數(shù)體內(nèi)可以使用lambda所在作用域范圍內(nèi)所有可見的局部變量，并且是引用傳遞。 a ：將a按值傳遞，但是a的默認是const的，可以添加mutable修飾后變?yōu)槠胀ǖ摹?&a：將a按引用傳遞。 a，&b：將a按值傳遞，b按引用傳遞。 =，&a，&b：除了a和b，其他參數(shù)均按值傳遞。 &，a，b：除了a和b，其他參數(shù)均按引用傳遞。 this：函數(shù)體重可以使用lambda所在類中的所有成員變量

操作符重載函數(shù)參數(shù)

表示重載的()操作符的參數(shù)，沒有參數(shù)的時候這個可以省略。

mutable或exception聲明

按值傳遞函數(shù)對象參數(shù)時，加上mutable修飾可以修改值傳遞進來的拷貝。exception聲明用于指定函數(shù)拋出的異常，如拋出整形的異常可以使用throw進行捕獲。

->返回值類型

標識函數(shù)返回值的類型，當返回值為void或者函數(shù)同種只有一處return的地方，這部分可以省略。

{函數(shù)體}

表示函數(shù)的實現(xiàn)，這部分不可以省略，但是函數(shù)體可以為空。

十四、什么是右值？

左值和右值是編譯器和程序中經(jīng)常出現(xiàn)的詞匯，在C++中被廣泛認同的說法就是可以取地址的、有名字的就是左值，沒有地址的，不能取取名字的就是右值。

在C++11中，右值由純右值和將亡值組成。

純右值，用于辨識臨時變量和一個不跟對象有關(guān)聯(lián)的值，比如說非引用返回的函數(shù)返回值，運算表達式、不跟對象關(guān)聯(lián)的字面量值（true、false、常量等）、類型轉(zhuǎn)換函數(shù)的返回值，lambda表達式。

將亡值，是C++11新增的跟右值引用相關(guān)的表達式，這樣表達式通常是將要被移動的對象，比如說返回右值引用T&&的函數(shù)的返回值，move庫函數(shù)的返回值，轉(zhuǎn)換為T&&的類型轉(zhuǎn)換函數(shù)的返回值。

除了純右值和將亡值剩余的所有值都是左值。

十五、右值引用

右值引用:

C++中，左值通常指可以取地址，有名字的值就是左值，而不能取地址，沒有名字的就是右值。而在指C++11中，右值是由兩個概念構(gòu)成，將亡值和純右值。純右值是用于識別臨時變量和一些不跟對象關(guān)聯(lián)的值，比如1+3產(chǎn)生的臨時變量值，2、true等，而將亡值通常是指具有轉(zhuǎn)移語義的對象，比如返回右值引用T&&的函數(shù)返回值等。

C++11中，右值引用就是對一個右值進行引用的類型。由于右值通常不具有名字，所以我們一般只能通過右值表達式獲得其引用，比如：T && a=ReturnRvale();

假設(shè)ReturnRvalue()函數(shù)返回一個右值，那么上述語句聲明了一個名為a的右值引用，其值等于ReturnRvalue函數(shù)返回的臨時變量的值。基于右值引用可以實現(xiàn)轉(zhuǎn)移語義和完美轉(zhuǎn)發(fā)新特性。

十六、 說一說c++中四種cast轉(zhuǎn)換

C++中四種類型轉(zhuǎn)換是：static_cast, dynamic_cast, const_cast, reinterpret_cast

1、const_cast

用于將const變量轉(zhuǎn)為非const

2、static_cast

用于各種隱式轉(zhuǎn)換，比如非const轉(zhuǎn)const，void*轉(zhuǎn)指針等, static_cast能用于多態(tài)向上轉(zhuǎn)化，如果向下轉(zhuǎn)能成功但是不安全，結(jié)果未知；

3、dynamic_cast

用于動態(tài)類型轉(zhuǎn)換。只能用于含有虛函數(shù)的類，用于類層次間的向上和向下轉(zhuǎn)化。只能轉(zhuǎn)指針或引用。向下轉(zhuǎn)化時，如果是非法的對于指針返回NULL，對于引用拋異常。要深入了解內(nèi)部轉(zhuǎn)換的原理。

向上轉(zhuǎn)換：指的是子類向基類的轉(zhuǎn)換

向下轉(zhuǎn)換：指的是基類向子類的轉(zhuǎn)換

它通過判斷在執(zhí)行到該語句的時候變量的運行時類型和要轉(zhuǎn)換的類型是否相同來判斷是否能夠進行向下轉(zhuǎn)換。

4、reinterpret_cast

幾乎什么都可以轉(zhuǎn)，比如將int轉(zhuǎn)指針，可能會出問題，盡量少用；

5、為什么不使用C的強制轉(zhuǎn)換？

C的強制轉(zhuǎn)換表面上看起來功能強大什么都能轉(zhuǎn)，但是轉(zhuǎn)化不夠明確，不能進行錯誤檢查，容易出錯。

十七、數(shù)組和指針的區(qū)別

1、指針中保存的是數(shù)據(jù)的地址，而數(shù)組中保存的是數(shù)據(jù)。

2、指針是間接訪問數(shù)據(jù)，要訪問一個數(shù)據(jù)要先獲得指針的內(nèi)容，然后通過這個地址提取出數(shù)據(jù)，而數(shù)組是直接訪問數(shù)據(jù)。

3、指針通常用于動態(tài)的數(shù)據(jù)結(jié)構(gòu)，鏈表、鏈式二叉樹等，數(shù)組通常用語固定數(shù)目并且數(shù)據(jù)類型相同的數(shù)據(jù)結(jié)構(gòu)，順序表等。

4、指針通過malloc或new申請內(nèi)存，并且使用完要進行釋放，數(shù)組則是隱式的分配和刪除。

十八、函數(shù)指針與指針函數(shù)

十九、請你來說一下一個C++源文件從文本到可執(zhí)行文件經(jīng)歷的過程？

對于C++源文件，從文本到可執(zhí)行文件一般需要四個過程：

預(yù)處理階段：對源代碼文件中文件包含關(guān)系（頭文件）、預(yù)編譯語句（宏定義）進行分析和替換，生成預(yù)編譯文件。

編譯階段：將經(jīng)過預(yù)處理后的預(yù)編譯文件轉(zhuǎn)換成特定匯編代碼，生成匯編文件后綴為.s

匯編階段：將編譯階段生成的匯編文件轉(zhuǎn)化成機器碼，生成可重定位目標文件.o

鏈接階段：將多個目標文件及所需要的庫連接成最終的可執(zhí)行目標文件.exe

二十、內(nèi)存泄漏

內(nèi)存泄漏(memory leak)是指由于疏忽或錯誤造成了程序未能釋放掉不再使用的內(nèi)存的情況。內(nèi)存泄漏并非指內(nèi)存在物理上的消失，而是應(yīng)用程序分配某段內(nèi)存后，由于設(shè)計錯誤，失去了對該段內(nèi)存的控制，因而造成了內(nèi)存的浪費。

內(nèi)存泄漏的分類：

1、堆內(nèi)存泄漏 （Heap leak）。對內(nèi)存指的是程序運行中根據(jù)需要分配通過malloc,realloc new等從堆中分配的一塊內(nèi)存，再是完成后必須通過調(diào)用對應(yīng)的 free或者delete 刪掉。如果程序的設(shè)計的錯誤導(dǎo)致這部分內(nèi)存沒有被釋放，那么此后這塊內(nèi)存將不會被使用，就會產(chǎn)生Heap Leak.

2、系統(tǒng)資源泄露（Resource Leak）。主要指程序使用系統(tǒng)分配的資源比如 Bitmap,handle ,SOCKET等沒有使用相應(yīng)的函數(shù)釋放掉，導(dǎo)致系統(tǒng)資源的浪費，嚴重可導(dǎo)致系統(tǒng)效能降低，系統(tǒng)運行不穩(wěn)定。

3、沒有將基類的析構(gòu)函數(shù)定義為虛函數(shù)。當基類指針指向子類對象時，如果基類的析構(gòu)函數(shù)不是virtual，那么子類的析構(gòu)函數(shù)將不會被調(diào)用，子類的資源沒有正確是釋放，因此造成內(nèi)存泄露。

二十一、C++對象模型

★★數(shù)據(jù)結(jié)構(gòu)★★

一、STL總結(jié)

什么是STL

STL是一套高效的C++程序庫，采用泛型編程的思想對常見的數(shù)據(jù)結(jié)構(gòu)和算法進程封裝，里面處處體現(xiàn)著泛型編程的設(shè)計思想以及設(shè)計模式，現(xiàn)在已經(jīng)被集成到了C++標準庫中。STL里面包含了容器、適配器、空間配置器、迭代器、仿函數(shù)和算法。

六大組件

容器：就是各種數(shù)據(jù)結(jié)構(gòu)，根據(jù)底層的實現(xiàn)由分為序列式容器和關(guān)聯(lián)式容器。

適配器：是一種用來修飾容器或者仿函數(shù)或迭代器接口的東西。比如queue和stack。

空間配置器：負責空間配置與管理。從實現(xiàn)角度看，配置器是一個實現(xiàn)了動態(tài)空間配置、空間管理、空間釋放額class template。

迭代器：扮演容器與算法之間的膠合劑，是所謂的“泛型指針”。

算法：各種常見算法，如sort，search，copy，erase等。

仿函數(shù)：行為類函數(shù)，可作為算法的某種策略，從實現(xiàn)角度看，仿函數(shù)是一種重載了operator()的class或class template。一般函數(shù)指針可視為狹義的仿函數(shù)。

他們之間的關(guān)系：空間配置器給容器分配存儲空間，算法通過迭代器獲取容器中的內(nèi)容，仿函數(shù)可以協(xié)助算法完成各種操作，配接器用來套接適配仿函數(shù)

容器

其中容器分為序列容器和關(guān)聯(lián)式容器兩大類，序列容器包括靜態(tài)數(shù)組array、動態(tài)數(shù)組vector、動態(tài)二維數(shù)組deque、帶頭結(jié)點的循環(huán)單鏈表forward_list、帶頭結(jié)點的雙向循環(huán)鏈表list、字符串string。關(guān)聯(lián)式容器根據(jù)地層的實現(xiàn)紅黑樹實現(xiàn)和哈希表實現(xiàn)兩大類，關(guān)聯(lián)式容器中的兩大類主要區(qū)別于底層的實現(xiàn)，紅黑樹和哈希表，

紅黑樹是一種二叉搜索樹，在每個節(jié)點上都增加了一個存儲位表示結(jié)點的顏色，可以紅色或者是黑色，通過對任何一條從根到葉子結(jié)點的路徑上各個節(jié)點的顏色限制，確保沒有一條路徑會比其他路徑長出2倍，所以是接近平衡的，是比較穩(wěn)定的二叉搜索樹，由于二叉搜索樹的任意根節(jié)點總是大于它左子樹的所有節(jié)點，小于他的右子樹的所有節(jié)點，所以在查找的時候可以采用類似于二分查找的思想，快速找到某個節(jié)點，紅黑樹是一個平衡二叉樹，他的查找時間復(fù)雜度也是logN。

哈希表是根據(jù)關(guān)鍵碼值直接進行訪問的數(shù)據(jù)結(jié)構(gòu)。通過關(guān)鍵碼值可以直接映射到哈希表中的一個位置來訪問對應(yīng)的值，以加快查找的速度，查找的時間復(fù)雜度是O(1)。哈希表主要解決的是哈希函數(shù)和哈希沖突，哈希函數(shù)也叫散列函數(shù)，要根據(jù)不同的輸入值得到一個固定長度的消息摘要。理想的哈希函數(shù)要對不同的輸入產(chǎn)生不同的不同的輸出結(jié)果，同時還要滿足同一性和雪崩效應(yīng)。哈希沖突就是不同的關(guān)鍵碼值通過哈希函數(shù)計算出相同的哈希地址。

解決哈希沖突的常見方法有閉散列和開散列兩種，閉散列采用的是線性探測法，當發(fā)生哈希沖突時，如果哈希表沒有被裝滿，就說明還可以將關(guān)鍵碼值存放到下一個空位置，然后從沖突位置一次向后探測，直到空位置為止，閉散列可以緩解哈希沖突，但是不能徹底解決。開散列使用的是拉鏈法，先將關(guān)鍵碼通過哈希函數(shù)計算得到相應(yīng)的哈希地址，然后將相同的哈希地址的關(guān)鍵碼放在同一個子集合中，這個子集合通常稱之為桶，每個桶中的元素通過單鏈表的方式連接起來，然后將各個鏈表的頭結(jié)點存放在哈希表中。

但是對于哈希表來說通的個數(shù)是固定，如果某個桶中的元素超過了8個，就要將這個桶中的單鏈表轉(zhuǎn)換為紅黑樹，如果桶中的元素小于6個的時候要將紅黑樹結(jié)構(gòu)再次轉(zhuǎn)換為單鏈表。這個轉(zhuǎn)換是由于桶中的元素是由鏈表保存的，鏈表的查找時間復(fù)雜度是O(N)，而紅黑樹的查找時間復(fù)雜度是logN，但是當鏈表中的長度很小的時候，查找也是很快的，當鏈表不斷變長了他的查找性能就會降低，需要轉(zhuǎn)換成紅黑樹。一開始不將桶的結(jié)構(gòu)初始化為樹是因為一個紅黑樹的節(jié)點占用的空間是單鏈表節(jié)點的二倍，為了時間和空間的權(quán)衡只有當鏈表長度到8才進行單鏈表向紅黑樹的轉(zhuǎn)換。但一個哈希表的離散性很好的情況下，將單鏈表轉(zhuǎn)換為紅黑樹的概率很小，因為數(shù)據(jù)均勻分布在每個哈希桶中，幾乎不會有哈希桶中的鏈表長度達到8，理想情況下哈希表中的所有哈希桶中節(jié)點分布頻率會遵循泊松分布，長度為8的概率是6*10^-8，幾乎是不可能的。

hash和紅黑都是性能非常高的兩個數(shù)據(jù)結(jié)構(gòu)，但是他們還是有區(qū)別的，hash的查找速度比紅黑樹快，并且查找速度基本上是和數(shù)據(jù)量無關(guān)的，屬于常數(shù)級別，但是紅黑樹的查找速度是logN的，但是hash還有hash函數(shù)，并且它的構(gòu)造速度也是比較慢的，并且還需要實現(xiàn)分配足夠的內(nèi)存存儲散列表，并且hash是無序的。紅黑樹所需要的內(nèi)存較小，只需要為節(jié)點分配內(nèi)存，并且紅黑樹中的節(jié)點是有序，它的查找時間復(fù)雜度是LogN，但是不能說就比常數(shù)大。基于這兩個數(shù)據(jù)結(jié)構(gòu)各自的特點和性能，STL將關(guān)聯(lián)式容器分成了基于紅黑樹的map、set、multimap、multiset和基于hash的unordered_map、unordered_map、unordered_set、unordered_multimap、unordered_multiset。

vector

vector是線性容器，他的元素嚴格按照線性序列排序和動態(tài)數(shù)組很相識，他和數(shù)組一樣，所有的元素存儲在一塊連續(xù)的存儲空間中，這也意味著我們不僅可以使用迭代器訪問元素，還可以使用指針偏移的方式訪問，和常規(guī)數(shù)組不一樣的是，vector能夠自動存儲元素，可以自動增長和縮小存儲空間。和數(shù)組相比，雖然vector在在自動處理容量的大小時會消耗更多的內(nèi)存，但是容器可以提供和數(shù)組一樣的性能，而且可以很好的調(diào)整存儲空間的大小。相比其他的序列容器，能更有效地訪問容器中的元素和在末尾添加和刪除元素，在其他位置添加和刪除元素就不如其他序列容器了，并且在迭代器當面也不如list支持的好。

vector的迭代器，無論在迭代器位置進行增加元素還是刪除元素都會導(dǎo)致所有的迭代器失效，因為vector中刪除和添加元素后可能會改變?nèi)萜鞯拇笮?#xff0c;所以要更新所有的迭代器，關(guān)于vector的空間這里需要注意的是size和capacity這兩個成員函數(shù)的區(qū)別，size指的是當前容器中擁有元素的個數(shù)，而capacity指的是當前容器可以存放的元素個數(shù)。vector在分配空間這塊他會分配一些額外的空間來適應(yīng)可能的增長。不同的庫采用的不同的策略權(quán)衡空間的使用和重新分配，在vs中PJ版本的STL是以1.5倍的方式進行擴容的，在gcc中的SGI版本的STL是按2倍的方式進行擴容的。

list

list是可以在常數(shù)范圍內(nèi)在任意位置進行插入和刪除的序列式容器，并且該容器可以向前向后雙向迭代。list的地層是一個雙向鏈表結(jié)構(gòu)，雙向鏈表中每個元素存儲在互不相關(guān)的獨立節(jié)點中，在節(jié)點中通過指針指向其前一個元素和后一個元素。他與forward_list非常相似，最主要的區(qū)別就是forward_list是單鏈表，只能向后迭代，而list是雙向鏈表，可以向前迭代也可以向后迭代。與其他容器相比較，list和forward_list最大的缺陷就是不支持在任意位置的隨機訪問，比如：要訪問list的第6個元素，必須從頭部或者尾部迭代到該位置，這段位置上的迭代需要線性的時間開銷，list還需要開辟一些額外的空間，以保存每個節(jié)點相關(guān)聯(lián)的信息。

list中也存在迭代器失效的問題，因為list的底層結(jié)構(gòu)是雙向循環(huán)鏈表，所以在list中插入時不會導(dǎo)致list的迭代器失效，只有在刪除的時候才會導(dǎo)致迭代器失效，但是失效的僅是被刪除節(jié)點的迭代器，其他的迭代器并不會受到影響。

vector和list的區(qū)別

底層結(jié)構(gòu)

vector是動態(tài)的順序表，在內(nèi)存中是一段連續(xù)的空間，list使用的是帶頭結(jié)點的雙向循環(huán)鏈表。

隨機訪問

vector支持隨機訪問，訪問某個元素的時間復(fù)雜度是O(1),list不支持隨機訪問，訪問某個元素的時間復(fù)雜度是O(n)

插入和刪除

vector在任意位置的插入和刪除的效率較低，需要搬移元素，時間復(fù)雜度為O(N)，插入的時候還有可能會增容，增容操作中有開辟新空間、拷貝元素、釋放舊空間，導(dǎo)致效率更低。list在任意位置插入和刪除效率比較高，不需要搬移元素，只需要更改上下兩個節(jié)點的指針指向，時間復(fù)雜度是O(1)。

空間利用率

vector的底層為一段連續(xù)的空間，不容易造成內(nèi)存碎片，空間利用率高，緩存利用率高。list底層節(jié)點動態(tài)開辟，容易造成內(nèi)存碎片，空間利用率低，緩存利用率低。

迭代器

vector使用的是原生態(tài)的指針，list是將原生態(tài)的指針進行了封裝。vector在插入元素是要給所有的迭代器重新賦值，因為插入元素有可能會導(dǎo)致擴容，致使原來的迭代器會失效，并且刪除元素的時候也會對迭代器進行重新賦值，同樣也會使原來的迭代器失效。對弈list來說，他的底層是雙向循環(huán)鏈表，插入元素時并不會導(dǎo)致迭代器失效，刪除元素是只會導(dǎo)致當前的迭代器失效，其他的迭代器并不受影響。

使用場景

vector適用于需要高效存儲，需要隨機訪問，并且不關(guān)心插入和刪除的效率。list適用于大量的插入和刪除操作，不需要隨機訪問，也不關(guān)心存儲的場景。

set

set是按照一定次序進行存儲的容器。set中元素只有一個value，并且每個value必須是唯一的，set中的元素不能再容器中進行修改，元素總是const的，但是可以容容器中對他們進行刪除或者插入。并且元素總是按照其內(nèi)部的比較對象所指是的特定的嚴格弱排序標準進行排序的，set訪問元素的速度要比unordered_set慢，但是它允許直接迭代，并且是有序的，set的底層實現(xiàn)是紅黑樹。他與map/multimap不同的是set中只存放的value，但是他的底層存放的是由構(gòu)成的鍵值對，由于set中不允許有重復(fù)的元素，所以可以使用set去重，

map

map是關(guān)聯(lián)式容器，他按照特定的次序來存儲由建值key和值value組合而成的元素。在map中，建值key通常用于排序和唯一標識元素，而值value中存儲的是與建值key相關(guān)聯(lián)的內(nèi)容。建值key和值value的類型可能不同，并且在map中，key與value通過成員類型value_type綁定在一起。在map中，元素總是按照建值key進行比較排序，并且他訪問某個元素時通常要比unordered_map慢，但是map中的元素直接進行迭代是有序的。他的底層實現(xiàn)是紅黑樹結(jié)構(gòu)。map與multimap唯一的不同就是map中的key值是唯一的，但是multimap中的key是可以重復(fù)的。set于multiset的區(qū)別就是multiset中的元素是可以重復(fù)的。

list、set、map的區(qū)別

從結(jié)構(gòu)上來說

list和set是存儲的單列數(shù)據(jù)的集合，map中存儲的是鍵值對這樣的雙列數(shù)據(jù)的集合。list的底層結(jié)構(gòu)是雙向循環(huán)列表，set和map的底層結(jié)構(gòu)是紅黑樹。

從數(shù)據(jù)上來說

list中存儲的數(shù)據(jù)是有順序的，并且是允許有重復(fù)的，查找的時間復(fù)雜度是O(N)，每個節(jié)點只有一個值value；map中的存儲的數(shù)據(jù)是無序的，他的鍵值是不允許重復(fù)的，但是他的值是允許重復(fù)的，并且他的鍵值是有序的，查找時間復(fù)雜度是logN，每個節(jié)點是由鍵值key，值value構(gòu)成的鍵值對，set中存儲的數(shù)據(jù)是有序的，不允許重復(fù)，查找時間復(fù)雜度是logN，每個節(jié)點是值value，但是他的底層節(jié)點是value,value的鍵值對。

STL面試題

一、STL常用的容器有哪些以及各自的特點是什么?

1.vector:底層數(shù)據(jù)結(jié)構(gòu)為數(shù)組 ，支持快速隨機訪問。

2.list:底層數(shù)據(jù)結(jié)構(gòu)為雙向鏈表，支持快速增刪。

3.stack:底層一般用順序表和鏈表實現(xiàn)，封閉頭部即可，不用vector的原因應(yīng)該是容量大小有限制，擴容耗時

4.queue:底層一般用順序表和鏈表實現(xiàn)，封閉頭部即可，不用vector的原因應(yīng)該是容量大小有限制，擴容耗時（stack和queue其實是適配器,而不叫容器，因為是對容器的再封裝）

5.set:底層數(shù)據(jù)結(jié)構(gòu)為紅黑樹，有序，不重復(fù)。

6.multiset:底層數(shù)據(jù)結(jié)構(gòu)為紅黑樹，有序，可重復(fù)。

7.map:底層數(shù)據(jù)結(jié)構(gòu)為紅黑樹，有序，不重復(fù)。

8.multimap:底層數(shù)據(jù)結(jié)構(gòu)為紅黑樹，有序，可重復(fù)。

9.hash_set:底層數(shù)據(jù)結(jié)構(gòu)為hash表，無序，不重復(fù)。

10.hash_multiset:底層數(shù)據(jù)結(jié)構(gòu)為hash表，無序，可重復(fù) 。

11.hash_map :底層數(shù)據(jù)結(jié)構(gòu)為hash表，無序，不重復(fù)。

12.hash_multimap:底層數(shù)據(jù)結(jié)構(gòu)為hash表，無序，可重復(fù)。

二、什么情況下用vector，什么情況下用list。

vector可以隨機存儲元素（即可以通過公式直接計算出元素地址，而不需要挨個查找），但在非尾部插入刪除數(shù)據(jù)時，效率很低，適合對象簡單，對象數(shù)量變化不大，隨機訪問頻繁。

list不支持隨機存儲，適用于對象大，對象數(shù)量變化頻繁，插入和刪除頻繁。

三、什么時候需要用hash_map，什么時候需要用map?

總體來說，hash_map 查找速度會比map快，而且查找速度基本和數(shù)據(jù)數(shù)據(jù)量大小，屬于常數(shù)級別;而map的查找速度是log(n)級別。并不一定常數(shù)就比log(n)小，hash還有hash函數(shù)的耗時，明白了吧，如果你考慮效率，特別是在元素達到一定數(shù)量級時，考慮考慮hash_map。但若你對內(nèi)存使用特別嚴格，希望程序盡可能少消耗內(nèi)存，那么一定要小心，hash_map可能會讓你陷入尷尬，特別是當你的hash_map對象特別多時，你就更無法控制了，而且hash_map的構(gòu)造速度較慢。

四、請你來說一說STL迭代器刪除元素

這個主要考察的是迭代器失效的問題。1.對于序列容器vector,deque來說，使用erase(itertor)后，后邊的每個元素的迭代器都會失效，但是后邊每個元素都會往前移動一個位置，但是erase會返回下一個有效的迭代器；2.對于關(guān)聯(lián)容器map set來說，使用了erase(iterator)后，當前元素的迭代器失效，但是其結(jié)構(gòu)是紅黑樹，刪除當前元素的，不會影響到下一個元素的迭代器，所以在調(diào)用erase之前，記錄下一個元素的迭代器即可。3.對于list來說，它使用了不連續(xù)分配的內(nèi)存，并且它的erase方法也會返回下一個有效的iterator，因此上面兩種正確的方法都可以使用。

五、請你來說一下STL中迭代器的作用，有指針為何還要迭代器

1、迭代器

Iterator（迭代器）模式又稱Cursor（游標）模式，用于提供一種方法順序訪問一個聚合對象中各個元素, 而又不需暴露該對象的內(nèi)部表示。或者這樣說可能更容易理解：Iterator模式是運用于聚合對象的一種模式，通過運用該模式，使得我們可以在不知道對象內(nèi)部表示的情況下，按照一定順序（由iterator提供的方法）訪問聚合對象中的各個元素。

由于Iterator模式的以上特性：與聚合對象耦合，在一定程度上限制了它的廣泛運用，一般僅用于底層聚合支持類，如STL的list、vector、stack等容器類及ostream_iterator等擴展iterator。

2、迭代器和指針的區(qū)別

迭代器不是指針，是類模板，表現(xiàn)的像指針。他只是模擬了指針的一些功能，通過重載了指針的一些操作符，->、*、++、–等。迭代器封裝了指針，是一個“可遍歷STL（ Standard Template Library）容器內(nèi)全部或部分元素”的對象， 本質(zhì)是封裝了原生指針，是指針概念的一種提升（lift），提供了比指針更高級的行為，相當于一種智能指針，他可以根據(jù)不同類型的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)不同的++，–等操作。

迭代器返回的是對象引用而不是對象的值，所以cout只能輸出迭代器使用*取值后的值而不能直接輸出其自身。

3、迭代器產(chǎn)生原因

Iterator類的訪問方式就是把不同集合類的訪問邏輯抽象出來，使得不用暴露集合內(nèi)部的結(jié)構(gòu)而達到循環(huán)遍歷集合的效果。

說說你所知道的容器都有哪些？

map與set的區(qū)別？使用map有哪些優(yōu)勢？

map的底層實現(xiàn)，說下紅黑樹？

map的迭代器會失效嗎？什么情況下回失效？

AVLTree和RBTree的對比，為什么map和set使用了紅黑樹？紅黑樹的優(yōu)勢是什么？

AVLTree和RBTree所達到的平衡有什么區(qū)別？

RBTree節(jié)點的顏色是紅或者黑色？其他顏色行不行？

RBTree是如何插入？如何旋轉(zhuǎn)的？

二、哈希

哈希表是根據(jù)關(guān)鍵碼值而直接進行訪問的數(shù)據(jù)結(jié)構(gòu)。通過關(guān)鍵碼值映射到表中的一個位置來訪問記錄，以加快查找的速度。哈希表主要是解決兩個問題，哈希函數(shù)和哈希沖突。

哈希函數(shù)

哈希函數(shù)也叫散列函數(shù)，他對不同的輸出值得到一個固定長度的消息摘要。理想的哈希函數(shù)對不同的輸入要產(chǎn)生不同的結(jié)構(gòu)，同時散列結(jié)果也應(yīng)當具有同一性和雪崩效應(yīng)（微小的輸入值發(fā)生的變化使得輸出值發(fā)生巨大的變化）。

哈希沖突

哈希沖突就是不同的關(guān)鍵字通過相同的哈希函數(shù)計算出了相同的哈希地址。解決哈希沖突最常見的方法是閉散列和開散列，閉散列使用的是線性探測法，當發(fā)生哈希沖突時，如果哈希表沒有被裝滿，說明可以將key值保存到下一個空位置中，從沖突發(fā)生的位置開始，依次向后探測，直到找到下一個空位置為止。開散列使用的是拉鏈法，先對關(guān)鍵碼使用哈希函數(shù)計算哈希地址，具有相同的哈希地址的關(guān)鍵碼歸于同一個子集，稱子集合為一個桶，每個桶中的元素通過一個單鏈表連接起來，然后將各個鏈表的頭結(jié)點存放在哈希表中。由于哈希表中桶的個數(shù)是固定的，如果某個桶中的元素非常多，這樣會影響真?zhèn)€哈希表的性能。一般來說如果桶中的元素過多，會將單鏈表的存儲方式換成紅黑樹，或者是對哈希表進行增容。

十、二叉樹的先序遍歷、中序遍歷和后序遍歷

//二叉樹的遞歸遍歷

void PreOrde(BTree* root)
{
if(root)
{
cout << root->data << " ";
PreOrde(root->left);
PreOrde(root->right);
}
}

void InOrde(BTree* root)
{
if(root)
{
PreOrde(root->left);
cout << root->data << " ";
PreOrde(root->right);
}
}

void PostOrde(BTree* root)
{
if(root)
{
PreOrde(root->left);
PreOrde(root->right);
cout << root->data << " ";
}
}

void PreOrde1(BTree* root)
{
stack<BTree*> s;
BTree* cur = root;

while(!s.empty() || cur) {while(cur){cout << cur->data << " ";s.push(cur);cur = cur->left;}if(!s.empty()){BTree* tmp = s.top();s.pop();cur = tmp->right;} }

}

void InOrde1(BTree* root)
{
stack<BTree*> s;
BTree* cur = root;

while(!s.empty() || cur) {while(cur){s.push(cur);cur = cur->left;}if(!s.empty()){BTree* tmp = s.top();cout << tmp->data << " ";s.pop();cur = tmp->right;} }

}

void PasrOrde1(BTree* root)
{
stack<BTree*> s;
stack flag;
BTree* cur = root;

while(!s.empty() || cur) {while(cur){s.push(cur);flag.push(false);cur = cur->left;}if(!s.empty()){if(flag.top()){cout << s.top()->data << " ";s.pop();flag.pop();}else{cur = s.top()->right;flag.top() = true;}} }

}

三、鏈表環(huán)

判斷是否有環(huán)

定義一個快指針和一個慢指針，快指針一次走兩步，慢指針一次走兩步，會出現(xiàn)兩種情況，情況一指針走到了空的位置，那就說明這個鏈表不帶環(huán)。情況二兩個指針相遇，說明這個鏈表帶環(huán)。

獲得入環(huán)節(jié)點

如果不考慮空間復(fù)雜度，可以使用一個map來記錄走過的節(jié)點，這個指針一直向后遍歷如果遇到空，說明這個鏈表不帶環(huán)，也就沒有入環(huán)節(jié)點，如果沒有遇到空，如果遇到第一個在map中存在的節(jié)點，就說明回到了出發(fā)點，這個節(jié)點就是環(huán)的入口節(jié)點。

如果不建立額外的空間，先使用快慢指針判斷這個鏈表是否有環(huán)，如果有環(huán)將相遇節(jié)點記錄，然后一個指針從鏈表的起始位置開始一次走一步，另一個指針從記錄的節(jié)點開始一次走一步，當兩個節(jié)點再次相遇，這個相遇節(jié)點就是環(huán)的入口節(jié)點。

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-7uf3JqSR-1637763958108)(C:\Users\LENOVO\AppData\Roaming\Typora\typora-user-images\1565675547490.png)]

四、棧和隊列

兩個棧模擬實現(xiàn)隊列

隊列的特性就是只能在隊尾進行插入操作，在隊頭進行刪除操作，兩個棧實現(xiàn)一個隊列，一個棧s1負責入隊列，另一個棧s2負責出隊列，當刪除隊列的時候，如果s2中有元素，直接取棧頂元素，如果s2是空棧，將s1中的所有元素搬移到s2中，然后再取棧頂元素。

兩個隊列模擬實現(xiàn)棧

棧的特性就是只能在一端進行插入和刪除操作，用兩個隊列一個用來進行入棧操作，另一個進行刪除的時候才會用到，將有元素的棧的size-1個元素全部搬移到另一個空隊列中，然后將最后一個元素刪除，就完成了刪除操作。

五、hashmap和map的區(qū)別？

map是STL中的一個關(guān)聯(lián)式容器，它提供一對一的K-V的數(shù)據(jù)處理能力，由于這個特性，在我們需要完成Key-Value數(shù)據(jù)處理的時候可以很方便的調(diào)用。map的底層結(jié)構(gòu)是紅黑樹，這棵樹對數(shù)據(jù)有自動排序的功能，所以map中的數(shù)據(jù)都是有序的，并且查找的時間復(fù)雜度基本是LogN。他的特點是增加和刪除節(jié)點對迭代器的影響很小，只對操作的節(jié)點有影響，但是對于迭代器來說，可以修改節(jié)點對應(yīng)的V值，不能修改K值。

HashMap是基于哈希表的Map，它具有著map的特性。當我們將K值傳遞給put()方法時，它調(diào)用對象的hashCode()方法來計算hashcode，然后找到對應(yīng)的位置來存放value。hashmap使用開散列的方法來解決哈希沖突。他是線程不安全的，hashmap中的初始容量和裝填因子會影響他的性能。

1、他們的底層實現(xiàn)不同，map使用的是紅黑樹來實現(xiàn)，Hashmap使用的哈希表來實現(xiàn)。

2、他們的查找時間復(fù)雜度不同，map的時間復(fù)雜度是log(n)，hashmap的時間復(fù)雜度O(1)。

3、map不允許有NULL值，但是hashmap允許有NULL。

★★排序算法★★

一、冒泡排序

??冒泡排序時通過無序區(qū)中相鄰記錄的關(guān)鍵字間的比較和位置的交換，使關(guān)鍵字最小的元素如氣泡似的逐步上浮直水面。有序區(qū)逐漸擴大，無序區(qū)逐漸縮小。
??冒泡排序算法的原理如下：

比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。

對每一對相鄰元素做同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點，最后的元素應(yīng)該會是最大的數(shù)。

針對所有的元素重復(fù)以上的步驟，除了最后一個。

持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較

動畫演示

冒泡排序是一種非常容易理解的排序
時間復(fù)雜度：O(N^2)
空間復(fù)雜度：O(1)
穩(wěn)定性：穩(wěn)定

普通冒泡

void bubble0(vector<int>& arr){ int size = arr.size(); for(int i = 0; i < size; ++i) { for(int j = 0; j < size-i-1; ++j) { if(arr[j] > arr[j+1]) { swap(arr[j+1], arr[j]); } } }}

優(yōu)化一
??第一種優(yōu)化就是在交換的地方加一個標記，如果某一趟排序沒有交換元素，說明這組數(shù)據(jù)已經(jīng)有序，不用再繼續(xù)下去。這樣對部分連續(xù)有序而整體無序的數(shù)據(jù)大大提升了效率。

void bubble1(vector<int>& arr){ int size = arr.size(); for(int i = 0; i < size; ++i) { bool flag = true; for(int j = 0; j < size-i-1; ++j) { if(arr[j] > arr[j+1]) { flag = false; swap(arr[j+1], arr[j]); } } if(flag) return; }}

優(yōu)化二
??對于優(yōu)化一來說，僅僅對部分連續(xù)有序而整體無序的數(shù)據(jù)效率高一些，如果這組數(shù)據(jù)時前面無序，但是后面的部分有序，效率就不是那么高了。因此可以在優(yōu)化一的基礎(chǔ)上記下最后一次交換的位置，這個位置后沒有交換，必然是有序的，然后下一次排序從第一個比較到上次記錄的位置結(jié)束即可。

void bubble2(vector<int>& arr){ int size = arr.size() -1; int pos = size; for(int i = 0; i < size; ++i) { bool flag = true; int k = 0; for(int j = 0; j < pos; ++j) { if(arr[j+1] < arr[j]) { flag = false; swap(arr[j+1], arr[j]); k = j; } } if(flag) return; pos = k; }}

優(yōu)化三
??冒泡算法經(jīng)過優(yōu)化二后效率有很大的提升，但是效率還可以繼續(xù)優(yōu)化，就是在一趟排序中確定兩個最值，也就是一個正向查找最大值，另一個反向查找最小值

void bubble3(vector<int>& arr){ int size = arr.size() -1; int pos = size; int pos1 = 0; for(int i = 0; i < size; ++i) { bool flag = true; int k = 0; //正向冒最大值 for(int j = 0; j < pos; ++j) { if(arr[j+1] < arr[j]) { flag = false; swap(arr[j+1], arr[j]); k = j; } } if(flag) return; pos = k; //反向冒最小值 int n = pos1; for(int j = k; j > pos1; --j) { if(arr[j-1] > arr[j]) { swap(arr[j-1], arr[j]); n = j-1; flag = false; } } if(flag) return; pos1 = n; }}

二、選擇排序

??選擇排序是一種簡單直觀的排序算法。
??選擇排序原理

初始時設(shè)第一個元素為最大值，并記錄其下標為maxpos

從剩余未排序元素中繼續(xù)尋找最大元素，如果當前元素比下標為maxpos的元素大，將maxpos更新到當前位置

一次遍歷后，將下標為maxpos的元素與最后一個元素交換位置

以此類推，直到整個數(shù)組有序。

??注意：選擇排序與冒泡排序是區(qū)別的，冒泡排序通過依次交換相鄰兩個順序不合法的元素位置，從而將當前最大元素放到合適的位置，而選擇排序每遍歷一次都記住了當前最大元素的位置，最后僅需一次交換操作即可將其放到合適的位置。

直接選擇排序思考非常好理解，但是效率不是很好。實際中很少使用
時間復(fù)雜度：O(N^2)
空間復(fù)雜度：O(1)
穩(wěn)定性：不穩(wěn)定

void slectSort(vector<int>& arr){ int size = arr.size(); for (int i = 0; i < size - 1; ++i) { int maxPos = 0; for (int j = 1; j < size - i; ++j) { if (arr[j] > arr[maxPos]) maxPos = j; } if (maxPos != size-i-1) swap(arr[maxPos], arr[size - i-1]); }}

優(yōu)化
??選擇排序的優(yōu)化就是在原來的一次只標記一個最值，優(yōu)化為一個標記兩個最值，這樣效率可以提升原來的一半。

void SlectSort(vector<int>& arr){ int size = arr.size(); int begin = 0; int end = size - 1; while (begin < end) { int minPos = begin; int maxPos = begin; int index = begin + 1; while (index <= end) { if (arr[minPos] > arr[index]) minPos = index; if (arr[maxPos] < arr[index]) maxPos = index; ++index; } if (maxPos != end) swap(arr[maxPos], arr[end]); //這段小代碼在在下面介紹其作用 if (minPos == end) minPos = maxPos; if (minPos != begin) swap(arr[begin], arr[minPos]); ++begin; --end; }}

??上面代碼標記的一小段代碼是為了防止minpos在最大值要插入的位置。比如序列（2，15，4，1）這時候的maxpos為1，minpos為3，調(diào)整過最大值后，序列就成了（2，1，4，15），這時候的minpos還是3，如果直接進行最小值交換，就恢復(fù)到之前的位置了，所以要加上這段判斷代碼。這樣如果最小值在最大值要交換的位置，最大值交換后要將最小值的位置更新到maxpos的位置。

三、插入排序

??直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的記錄按其關(guān)鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 。實際中我們玩撲克牌時，就用了插入排序的思想
??當插入第i(i>=1)個元素時，前面的arr[0],arr[1],…,arr[i-1]已經(jīng)排好 序，此時用arr[i]與arr[i-1],arr[i-2]進行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移。
元素集合越接近有序，直接插入排序算法的時間效率越高，其時間效率在O(n)與O(n^2)之間。直接插入排序的空間復(fù)雜度為O(1)，它是一種穩(wěn)定的排序算法。

元素集合越接近有序，直接插入排序算法的時間效率越高
時間復(fù)雜度：O(N^2)
空間復(fù)雜度：O(1)，它是一種穩(wěn)定的排序算法
穩(wěn)定性：穩(wěn)定

void InsertSort(vector<int>& arr){ int size = arr.size(); for (int i = 1; i < size; ++i) { //待插入元素 int key = arr[i]; //找插入位置 int end = i - 1; while (end >= 0 && arr[end] > key) { //向后搬移數(shù)據(jù) arr[end + 1] = arr[end]; end--; } //開始插入 arr[end + 1] = key; }}

優(yōu)化
??普通的插入排序就是不斷的依次將元素插入前面已排好序的序列中。由于前半部分為已排好序的數(shù)列，這樣我們不用按順序依次尋找插入點，可以采用折半查找的方法來加快尋找插入點的速度。
??折半插入排序算法是一種穩(wěn)定的排序算法，比普通插入算法明顯減少了關(guān)鍵字之間比較的次數(shù)，因此速度比直接插入排序算法快，但記錄移動的次數(shù)沒有變，所以折半插入排序算法的時間復(fù)雜度仍然為O(n^2)，與直接插入排序算法相同。

void InsertSort1(vector<int>& arr){ int size = arr.size(); for (int i = 1; i < size; ++i) { //待插入元素 int key = arr[i]; //找插入位置 int right = i - 1; int left = 0; if(arr[right] > key) { while (left <= right ) { int mid = left+((right-left)>>1); if(arr[mid] < key) left = mid+1; else right = mid-1; } } //開始搬移數(shù)據(jù) int end = i -1; while(end >= left) { arr[end+1] = arr[end]; --end; } //開始插入數(shù)據(jù) arr[end + 1] = key; }}

四、希爾排序

??希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數(shù)，把待排序文件中所有記錄分成個組，所有距離為的記錄分在同一組內(nèi)，并對每一組內(nèi)的記錄進行排序。然后，重復(fù)上述分組和排序的工作。當?shù)竭_=1時，所有記錄在統(tǒng)一組內(nèi)排好序。

希爾排序是對直接插入排序的優(yōu)化。
當gap > 1時都是預(yù)排序，目的是讓數(shù)組更接近于有序。當gap == 1時，數(shù)組已經(jīng)接近有序的了，這樣就會很快。這樣整體而言，可以達到優(yōu)化的效果。我們實現(xiàn)后可以進行性能測試的對比。
希爾排序的時間復(fù)雜度不好計算，需要進行推導(dǎo)，推導(dǎo)出來平均時間復(fù)雜度： O(N^1.3 - N^2）
穩(wěn)定性：不穩(wěn)定

void ShellSort(vector<int>& arr){ int size = arr.size(); int gap = size; while (gap > 0) { gap = gap / 3 + 1; for (int i = gap; i < size; ++i) { //待插入元素 int key = arr[i]; //找插入位置 int end = i - gap; while (end >= 0 && arr[end] > key) { arr[end + gap] = arr[end]; end -= gap; } //開始插入 arr[end + gap] = key; } if(gap == 1) break; }}

五、快速排序

??快速排序快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復(fù)該過程，直到所有元素都排列在相應(yīng)位置上為止。

快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序
時間復(fù)雜度：平均O(N*logN) 最壞：O(n^2)【每次的關(guān)鍵值都是最大值或者最小值】

空間復(fù)雜度：O(logN)
穩(wěn)定性：不穩(wěn)定

普通快排：
普通快排就是將當前序列的最后一個值作為標志，然后開始分割序列。

int Partion(vector<int>& arr, int left, int right){ int key = arr[right-1]; int begin = 0; int end = right-1; while (begin < end) { while (begin < end && arr[begin] <= key) begin++; while (begin < end && arr[end] >= key) end--; if (begin != end) swap(arr[begin], arr[end]); } if (begin != right - 1) swap(arr[begin], arr[right - 1]); return begin;}

優(yōu)化一：挖坑法
??挖坑法的原理就是在左邊找到不符合條件的元素時，將這個元素放在end處，這時候begin位置就成了一個“坑”，在右邊找到不符合條件的元素時，將這個元素放到begin位置，將之前的“坑”填好，以此類推，最后將標志key保存的值放在begin位置，將最后一個“坑”填滿。

int Partion1(vector<int>& arr, int left, int right){ int end = right - 1; int begin = left; int key = arr[right - 1]; while (begin < end) { while (begin < end && arr[begin] <= key) begin++; if (begin < end) { arr[end] = arr[begin]; end--; } while (begin < end && arr[end] >= key) end--; if (begin < end) { arr[begin] = arr[end]; begin++; } } arr[begin] = key; return begin;}//齊頭并進法int Partion2(vector<int>& arr, int left, int right){ int key = arr[right - 1]; int cur = left; int pre = cur - 1; while (cur < right) { if (arr[cur] < key && ++pre != cur) { swap(arr[pre], arr[cur]); } cur++; } if (++pre != right-1) swap(arr[pre], arr[right - 1]); return pre;}//三數(shù)取中法int MidNum(vector<int>& arr,int left, int right){ int mid = left + ((right - left) >> 1); if (arr[left] > arr[right]) { if (arr[mid] > arr[left]) mid = left; if (arr[mid] < arr[right]) mid = right; } else { if (arr[mid] < arr[left]) mid = left; if (arr[mid] > arr[right]) mid = right; } return mid;}int Partion3(vector<int>& arr, int left, int right){ int end = right - 1; int begin = left; int mid = MidNum(arr, left, end); swap(arr[mid], arr[right - 1]); int key = arr[right - 1]; while (begin < end) { while (begin < end && arr[begin] <= key) begin++; if (begin < end) { arr[end] = arr[begin]; end--; } while (begin < end && arr[end] >= key) end--; if (begin < end) { arr[begin] = arr[end]; begin++; } } arr[begin] = key; return begin;}void QuickSort(vector<int>& arr, int left, int right){ if (right - left > 1) { int key = Partion3(arr, left, right); QuickSort(arr, left, key); QuickSort(arr, key + 1, right); }}//非遞歸快排void QuickSortNor(vector<int>& arr){ int right = arr.size(); int left = 0; stack<int> s; s.push(right); s.push(left); while (!s.empty()) { left = s.top(); s.pop(); right = s.top(); s.pop(); if (right - left > 1) { int key = Partion3(arr, left, right); //保存右值 s.push(right); s.push(key + 1); //保存左值 s.push(key); s.push(left); } }}

六、堆排序

??堆排序就是利用堆（堆的詳細介紹）這種數(shù)據(jù)結(jié)構(gòu)進行排序的算法，堆排序?qū)儆谶x擇排序

時間復(fù)雜度：O(nlogn)
空間復(fù)雜度：O(1)
穩(wěn)定性：不穩(wěn)定
堆排序的步驟為：
1、基于所給元素創(chuàng)建一個大堆
2、使用堆刪除的思想從最后一個結(jié)點向前調(diào)整

typedef struct Heap{ HPData* _array; int _size; int _capacity;}Heap;void HeapAdjust(HPData* array, int size, int root){ int child = root * 2 + 1; while (child < size) { if (child + 1 < size && array[child] < array[child + 1]) child += 1; if (array[child] > array[root]) { swap(array[child], array[root]); root = child; child = root * 2 + 1; } else return; }}void HeapSort(HPData* array, int size){ //建大堆 //找倒數(shù)第一個非葉子節(jié)點 int root = (size - 2) >> 1; for (; root >= 0; --root) HeapAdjust(array, size, root); //開始排序，使用刪除節(jié)點的思想 int end = size - 1; while (end) { swap(array[0], array[end]); HeapAdjust(array, end, 0); end--; }}

七、歸并排序

??歸并排序是簡歷在歸并操作上的一中有效的排序算法，該算法是采用分治法的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列。顯示每個子序列有序，再使子序列段間有序。若兩個有序列表合并成一個有序列表，陳偉二路歸并。

歸并的缺點在于需要O(N)的空間復(fù)雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題。
時間復(fù)雜度：O(N*logN)
空間復(fù)雜度：O(N)
穩(wěn)定性：穩(wěn)定

void _MergeData(vector<int>& arr, int left, int mid, int right, vector<int>& temp){ int begin1 = left; int end1 = mid; int begin2 = mid; int end2 = right; int index = left; while (begin1 < end1 && begin2 < end2) { if (arr[begin1] < arr[begin2]) temp[index++] = arr[begin1++]; else temp[index++] = arr[begin2++]; } while (begin1 < end1) temp[index++] = arr[begin1++]; while (begin2 < end2) temp[index++] = arr[begin2++];}void _MergeSort(vector<int>& arr, int left, int right, vector<int>& temp){ if ((right - left) > 1) { int mid = left + ((right - left) >> 1); _MergeSort(arr, left, mid, temp); _MergeSort(arr, mid, right, temp); _MergeData(arr, left, mid, right, temp); copy(temp.begin() + left, temp.begin() + right, arr.begin() + left); }}

★★系統(tǒng)知識★★

一、進程

進程間通信

為什么要為用戶提供程間通信方式？

因為進程的獨立性，每個進程操作的都是自己虛擬地址空間中的虛擬地址，無法訪問別人的地址，所以無法直接通信。

管道（半雙工）

本質(zhì)：內(nèi)核中的一塊緩沖區(qū)

原理：人多個進程訪問到相同的緩沖區(qū)來實現(xiàn)通信，管道通信使用的系統(tǒng)調(diào)用的IO接口，遵循一切皆文件的思想。

匿名管道

一個進程創(chuàng)建匿名管道，操作系統(tǒng)再內(nèi)核中重建一塊緩沖區(qū)，并返回兩個人文件描述符作為管道的操作句柄（一個用于讀，一個用于寫，方向的選擇權(quán)交給用戶），但是這個緩沖區(qū)在內(nèi)核中沒有標識。

操作接口

創(chuàng)建管道

int pipe(int pipefd[2]);pipefd:至少有兩個int型元素的數(shù)組創(chuàng)建一個管道，通過pipefd獲取系統(tǒng)返回的管道操作句柄，其中pipefd[0]: 用于從管道中讀取數(shù)據(jù)pipefd[1]: 用于向管道中寫入數(shù)據(jù)返回值成功返回 0 失敗返回-1

ipc：進程間通信方式

? 管道必須創(chuàng)建于子進程之前，子進程這樣才能復(fù)制到管道的操作句柄

管道的讀寫特性

? 1、若管道中沒有數(shù)據(jù)，則read會阻塞等待，直到數(shù)據(jù)被寫入

? 2、若管道中數(shù)據(jù)滿了，則write會阻塞等待，直到數(shù)據(jù)被讀取

? 3、若管道中的所有讀端被關(guān)閉，則wirte會觸發(fā)異常，進程退出

? 4、若管道的所有寫端被關(guān)閉，則read會返回0

? 5、管道的read返回0，不僅僅指的是沒有讀到數(shù)據(jù)，還有可能是寫端被關(guān)閉

grep make：從標準輸入循環(huán)讀取數(shù)據(jù)，對讀到的數(shù)據(jù)進行過濾匹配

匿名管道的實現(xiàn)就是創(chuàng)建兩個進程，一個運行l(wèi)s，另一個運行g(shù)rep

讓ls這個進程標準輸出，重定向到管道寫入端

命名管道

? 在命名管道中，同一主機上的任意進程之間通信，命名管道在內(nèi)核中這塊緩沖區(qū)是由標識的，一維著所有的進程都可以通過這個標識找到這塊緩沖區(qū)來實現(xiàn)通信。命名管道的標識符實際上是一個文件，可見于文件系統(tǒng)，意味著所有進程都可以通過打開文件來訪問到內(nèi)核中的緩沖區(qū)。

命名管道的打開特性：

? 若文件當前沒有被已讀的方式打開，則以O(shè)_WRONLY打開時會阻塞

? 若文件當前沒有被已讀的方式打開，則以O(shè)_RDONLY打開時會阻塞

命名管道的讀寫特性：類同于匿名管道

命名管道和匿名管道

匿名管道只能用于具有親緣關(guān)系的進程間通信

命名管道可以作用于同一主機上任意進程間通信

管道特性

1、管道是半雙工通信

2、管道的讀寫特性+（命名管道的打開特性）

3、管道的生命周期隨進程（所有管道的操作句柄被關(guān)閉）

4、管道自帶同步與互斥（管道的讀寫大小不超過PIPE_BUF時是安全的）

5、管道提供字節(jié)流服務(wù)，但是存在粘包問題

管道通信

管道通信的本質(zhì)是通過內(nèi)核中的緩沖區(qū)來實現(xiàn)通信，

進程1將數(shù)據(jù)從用戶態(tài)緩沖區(qū)拷貝到內(nèi)核態(tài)緩沖區(qū)，然后進程2將數(shù)據(jù)沖內(nèi)核態(tài)緩沖區(qū)拷貝到用戶態(tài)緩沖區(qū)，涉及兩次用戶態(tài)與內(nèi)核態(tài)之間的數(shù)據(jù)拷貝。

共享內(nèi)存

最快的進程間通信方式

共享內(nèi)存原理

1、在物理內(nèi)存中開辟一塊內(nèi)存空間

2、將這塊空間通過頁表映射到進程的虛擬地址空間中

3、進程可以直接通過進程虛擬地址空間訪問這塊物理內(nèi)存，進行操作，若多個進程映射同一塊物理內(nèi)存，就可以實現(xiàn)相互通信，這樣就可以通過虛擬地址改變內(nèi)存中的數(shù)據(jù)，其他進程也會隨之改變。

4、相較于其他進程間通信方式，少了兩步內(nèi)核態(tài)和用戶態(tài)之間的數(shù)據(jù)拷貝

5、釋放映射關(guān)系

6、刪除共享內(nèi)存

1、創(chuàng)建共享內(nèi)存int shmget(key_t key, size_t size, int shmflg); key: 共性內(nèi)存在操作系統(tǒng)中的標識符 size: 共享內(nèi)存大小 shmflag: IPC_CREAT 共享內(nèi)若存在則打開，否則創(chuàng)建 IPC_EXCL 與IPC_CREAT同時使用，若共享內(nèi)存村在則報錯返回 mode 貢獻內(nèi)存的操作權(quán)限 返回值: 正整數(shù)-->共享內(nèi)存的操作句柄 2、將共享內(nèi)存映射到虛擬地址空間void *shmat(int shmid, const void *shmaddr, int shmflg); shmid 創(chuàng)建共享內(nèi)存返回的操作句柄 shmaddr 共享內(nèi)存在虛擬地址空間中的首地址--通常置空（NULL）,有操作系統(tǒng)來指定 shmflg SHM_RDONLY--映射之后，共享內(nèi)存只讀，通常置0，可讀可寫 返回值 映射首地址 失敗(void*) -1

3、通過虛擬地址進行操作

mencpy

4、解除映射關(guān)系

int shmdt(const void *shmaddr); shmaddr shmat建立映射關(guān)系是返回的映射首地址

5、刪除共享內(nèi)存

int shmctl(int shmid, int cmd, struct shmid_ds *buf); shmid 共享內(nèi)存操作句柄 cmd 共享內(nèi)存操作（）即將進行的操作 IPC_RMID buf 用于獲取/設(shè)置共享內(nèi)存信息

共享內(nèi)存的刪除流程：共向內(nèi)存在刪除的時候，首先會判斷當前映射鏈接數(shù)是否為0，若為0直接刪除，否則表示現(xiàn)在還有其他進程在使用，則共享內(nèi)存不能立即被刪除，但是會拒絕后續(xù)進程的映射鏈接，等待映射鏈接數(shù)為0時刪除這塊共享內(nèi)存。

消息隊列

操作系統(tǒng)在內(nèi)核中為用戶闖將一個隊列，其他進程通過訪問相同的隊列進行通信，消息隊列傳輸?shù)氖怯蓄愋偷臄?shù)據(jù)塊，共享內(nèi)存、消息隊列的生命周期隨內(nèi)核

用于多個進程間有類型的數(shù)據(jù)塊傳輸

ipcs 查看 -m 共享內(nèi)存 -s 信號量 -q 消息隊列ipcrm -m shmid 刪除對應(yīng)的共享內(nèi)存 -m 共享內(nèi)存 -s 信號量 -q 消息隊列

信號量

實現(xiàn)進程間的同步與互斥，

本質(zhì):在內(nèi)核中是一個計數(shù)器+喚醒+等待.

同步：保證多個進程之間對臨界資源訪問的時序合理性-—-等待與喚醒

互斥：保存多個進程之間同一時間對臨界資源的唯一訪問型性

原理:

進程對資源進行訪問操作之前，先進行臨界資源計數(shù)判斷，

若計數(shù)<=0,則阻塞，等待創(chuàng)建資源 --計數(shù)-1 等待在等待隊列中

若計數(shù)> 0,則直接返回,按照程序流程就可以直接擦做資源了,計數(shù)-1

有進程創(chuàng)建了資源,計數(shù)+1, 并喚醒等待隊列上的那些進程

二、線程

線程是在Linux中使用PCB模擬實現(xiàn)的輕量級進程，進程從表面來說是一個運行起來的程序，但是從操作系統(tǒng)角度來說，進程就是操作系統(tǒng)堆為一個正在執(zhí)行的程序而創(chuàng)建的描述符，操作系統(tǒng)通過對這個描述來對程序進行控制，這個描述信息就是PCB，所以說線程就是一個輕量級的進程，是一個進程等的子任務(wù)，線程共享進程中部分資源，包括數(shù)據(jù)段、代碼段和擴展段，每個線程擁有自己的線程描述符、數(shù)據(jù)棧、用于存放上下文數(shù)據(jù)的寄存器、錯誤碼、信號屏蔽字。線程是進程中的一個執(zhí)行流，是操作系統(tǒng)調(diào)度和執(zhí)行的最小單位。

線程間通信(同步)的方式

臨界區(qū)：通過多線程的串行化來訪問公共資源或一段代碼，速度快，適合控制數(shù)據(jù)訪問；

互斥量：采用互斥對象機制，只有擁有互斥對象的線程才有訪問公共資源的權(quán)限。因為互斥對象只有一個，所以可以保證公共資源不會被多個線程同時訪問

信號量：為控制具有有限數(shù)量的用戶資源而設(shè)計的，它允許多個線程在同一時刻去訪問同一個資源，但一般需要限制同一時刻訪問此資源的最大線程數(shù)目。

事件(信號）：通過通知操作的方式來保持多線程同步，還可以方便的實現(xiàn)多線程優(yōu)先級的比較操作

三、進程與線程

什么是線程？

線程是在Linux中使用PCB模擬實現(xiàn)的輕量級進程，進程從表面來說是一個運行起來的程序，但是從操作系統(tǒng)角度來說，進程就是操作系統(tǒng)堆為一個正在執(zhí)行的程序而創(chuàng)建的描述符，操作系統(tǒng)通過對這個描述來對程序進行控制，這個描述信息就是PCB，所以說線程就是一個輕量級的進程，是一個進程等的子任務(wù)，線程共享進程中部分資源，包括數(shù)據(jù)段、代碼段和擴展段，每個線程擁有自己的線程描述符、數(shù)據(jù)棧、用于存放上下文數(shù)據(jù)的寄存器、錯誤碼、信號屏蔽字。線程是進程中的一個執(zhí)行流，是操作系統(tǒng)調(diào)度和執(zhí)行的最小單位。

線程和進程的區(qū)別？

1、一個線程只能屬于一個進程，而一個進程可以有一個或多個線程，線程是依賴于進程存在的。

2、進程在執(zhí)行過程中擁有一個獨立的內(nèi)存單元，而多個線程共享同一個進程的內(nèi)存。也就是說資源分配給進程，在這個進程中的所有線程共享其中的所有資源，同一個進程中所有線程共享代碼段、數(shù)據(jù)段、擴展段。但是每個線程擁有自己的棧段，棧段又叫運行時段，用來存放所有局部變量和臨時變量。棧寄存器（上下文數(shù)據(jù)）信號屏蔽字errno(錯誤碼)線程標識符

3、進程是資源分配的最小單元，線程是CPU調(diào)度的最小單元

4、系統(tǒng)的開銷：由于創(chuàng)建或撤銷進程時，系統(tǒng)都要為他分配或回收，如內(nèi)存空間、I/O設(shè)備等。因為操作系統(tǒng)所付出的開銷將顯著的大于在創(chuàng)建線程或撤銷線程時的開銷。類似地，在進行進程切換時，涉及到整個當前進程CPU環(huán)境的保存以及新被調(diào)度運行的進程的CPU環(huán)境的設(shè)置。而線程切換只需要保存和設(shè)置少量的寄存器的內(nèi)容，并不涉及存儲器管理方面的操作。所以進程切換的開銷要遠遠大于線程切換的開銷。

5、通信：由于同一個進程中的多個線程具有相同的地址空間，所以他們之間的同步和通信的實現(xiàn)也變得比較簡單。進程間通信IPC有管道、共享內(nèi)存、消息隊列、信號量進行通信。線程間可以直接讀寫進程數(shù)據(jù)段來進行通信。在有的系統(tǒng)中，線程的切換、同步和通信都無需操作系統(tǒng)內(nèi)核干預(yù)。

6、進程編程調(diào)試簡單可靠性高，但是創(chuàng)建和銷毀的開銷較大，相對于線程來說正好相反，開銷小、切換速度快，但是編程調(diào)試相對復(fù)雜。

7、進程之間不會相互影響，但是同一個進程中只有一個線程掛掉了將導(dǎo)致整個進程掛掉。

8、多線程適合于I/O密集的工作場景、多進程適合于CPU密集型的工作場景。

怎么實現(xiàn)線程池？

1、設(shè)置一個生產(chǎn)者消費者隊列，作為臨界資源。

2、初始化n個線程，并讓其運行起來，以加解鎖的方式去隊列取任務(wù)運行。

3、當任務(wù)隊列為空的時候所有的線程阻塞。

4、當生產(chǎn)者隊列來了一個任務(wù)后，先對隊列加鎖，把任務(wù)掛在隊列上，然后使用條件變量去通知阻塞中的一個線程。

四、線程安全

什么是線程安全

多線程對臨界資源進程操作二不會產(chǎn)生二義性。

保證線程安全的機制

使用同步與互斥保證線程安全。

線程同步

同步就是協(xié)同步調(diào)，按預(yù)定的先后次序進行運行。線程同步是指多線程通過特定的設(shè)置（如互斥量，事件對象，臨界區(qū)）來控制線程之間的執(zhí)行順序（即所謂的同步）也可以說是在線程之間通過同步建立起執(zhí)行順序的關(guān)系，如果沒有同步，那線程之間是各自運行各自的！

線程互斥是指對于共享的進程系統(tǒng)資源，在各單個線程訪問時的排它性。當有若干個線程都要使用某一共享資源時，任何時刻最多只允許一個線程去使用，其它要使用該資源的線程必須等待，直到占用資源者釋放該資源。線程互斥可以看成是一種特殊的線程同步。

線程同步有四種方式：臨界區(qū)、互斥對象、信號量、事件對象。

臨界區(qū)、互斥對象：主要用于互斥控制，都具有擁有權(quán)的控制方法，只有擁有互斥對象的線程才能執(zhí)行任務(wù)，所以擁有互斥對象的線程，執(zhí)行完任務(wù)后一定要釋放該對象。

信號量、事件對象：事件對象是以通知的方式進行控制，主要用于同步控制。

臨界區(qū)

通過對多線程的串行化來訪問公共資源或一段代碼，速度快，適合控制數(shù)據(jù)訪問。在任意時刻只允許一個線程對共享資源進行訪問，如果有多個線程試圖訪問公共資源，那么在有一個線程進入后，其他試圖訪問公共資源的線程將被掛起，并一直等到進入臨界區(qū)的線程離開，臨界區(qū)在被釋放后，其他線程才可以搶占。它并不是核心對象，不是屬于操作系統(tǒng)維護的，而是屬于進程維護的。

互斥對象

互斥對象和臨界區(qū)很像，采用互斥對象機制，只有擁有互斥對象的線程才有訪問公共資源的權(quán)限。因為互斥對象只有一個，所以能保證公共資源不會同時被多個線程同時訪問。當前擁有互斥對象的線程處理完任務(wù)后必須將線程交出，以便其他線程訪問該資源。

信號量

信號量也是內(nèi)核對象。它允許多個線程在同一時刻訪問同一資源，但是需要限制在同一時刻訪問此資源的最大線程數(shù)目。

條件變量

條件變量是一種同步機制，允許線程掛起，直到共享數(shù)據(jù)上的某些條件得到滿足。條件變量要和互斥鎖相結(jié)合，避免出現(xiàn)條件競爭，就是一個線程預(yù)備等待一個條件變量，當它在真正等待之前，另一個線程恰好觸發(fā)了該條件。

互斥鎖

互斥從表面上理解就是相互排斥。所以互斥鎖從字面上理解就是一個進程擁有了這個鎖，他將排斥其他所有的進程訪問被鎖住的東西，其他的進程如果需要鎖只能阻塞等待，等擁有鎖的進程解鎖后才能繼續(xù)運行。在使用互斥鎖的時候要注意一點就是解鈴還須系鈴人，如果擁有鎖的進程不解鎖，那么其他進程將永遠不能得到互斥鎖。

讀寫鎖

互斥鎖是排它鎖，條件變量出現(xiàn)后和互斥鎖配合能夠有效地節(jié)省系統(tǒng)資源并提高線程之間的協(xié)同工作效率。互斥鎖的目的是為了獨占，條件變量的目的是為了等待和通知。對于文件來說，最常見的操作就是讀和寫，讀文件不會修改文件的內(nèi)容，所以多個進程同時讀也是可以的，但是當寫進程需要寫數(shù)據(jù)的時候為了保證數(shù)據(jù)的一致性，所有讀的進程都不能讀數(shù)據(jù)，否則讀到的數(shù)據(jù)可能是一半是舊的，一半是新的，這樣就亂了。所以為了防止讀數(shù)據(jù)的時候?qū)懭胄碌臄?shù)據(jù)，在讀數(shù)據(jù)的時候就必須對文件加鎖，但是如果有兩個進程要同時讀，另一個進程就只能等待，從性能上講，是浪費時間。所以這是要用到讀寫鎖，讀寫鎖的出現(xiàn)有效地解決了多進程并行讀的問題，這樣每個進程在讀的時候需要申請讀鎖，進程之間相互不干擾。如果有進程要寫數(shù)據(jù)，需要申請寫鎖，如果有讀鎖或者寫鎖存在，那么只能等待所有的鎖都解鎖了才可以進行寫操作。有一點值得注意的是，讀鎖是所有進程共享的，但是寫鎖是互斥的。

記錄鎖

為了增加同步的性能，可以在讀寫鎖的基礎(chǔ)上進一步細分被鎖對象的粒度。比如說寫操作是針對文件的前1k字節(jié)，但是讀操作是針對文件的后1k字節(jié)，這樣就可以對文件的前1k上寫鎖，后1k上讀鎖，這樣讀和寫就可以并發(fā)進行了，文件鎖是記錄鎖的一個特例，記錄鎖針對的是文件中的某一部分內(nèi)容，如果記錄鎖將整個文件上鎖，這時候的記錄鎖就是一個文件鎖。

線程互斥

五、死鎖的條件以及解決的辦法

什么死鎖

死鎖的條件

必須要滿足以下的四個條件才可以發(fā)生死鎖。

1、互斥條件

指的是某個資源同時只能讓一個進程占有，比如說打印機。必須要在占有該資源的進程主動釋放資源后其他進程才可以占有。這時有資源本身屬性決定的。

2、不可搶占資源

進程獲得的資源在沒有使用完的情況下，這份資源不能被資源申請者強行占有，只能等該資源釋放候才可以申請。

3、占有且申請條件

一個進程至少占有了一個資源，他又要申請新的資源，但是申請的資源被另一個進程所占有，這時進程阻塞，在他阻塞的時候仍然占有已有的資源。

4、循環(huán)等待條件

可以說是一個進程等待隊列，p1等待p2所占有的資源，同時p1不對自己的資源進行釋放，p2在等待p1所占有的資源，同樣的p2也不對自己所占有的資源進行釋放，這樣就形成了一個進程的循環(huán)等待。

死鎖的預(yù)防

死鎖的預(yù)防就是保證系統(tǒng)不進入死鎖的狀態(tài)的一種策略。

1、破壞互斥條件

但是有些資源確實不能被共享，這是由資源的屬性決定的。

2、破壞不可搶占條件

將資源的申請設(shè)置為可搶占式，也就是要求申請失敗的進程要釋放自己占有的資源給其他進程使用，但是會降低系統(tǒng)性能。

3、破壞占有且申請條件

直接一次性將自己所需要的資源申請完。當時這樣有兩個問題，一個是有時候不可預(yù)知需要什么資源，另一個是資源的利用率低，進程可能會長期占有自己可能用不到的資源。

4、破壞循環(huán)等待條件

將資源進行分類、編號，讓進程按照排好的序號進行申請。存在的問題是對資源的編號可能是困難的，維護相應(yīng)的序列也可能是困難的。

死鎖的避免

死鎖的避免是指不限制進程有關(guān)申請資源的命令，而是對進程所發(fā)出的每一個申請資源命令甲乙動態(tài)的檢查，并且根據(jù)檢查結(jié)果來判斷是否進行資源分配。

銀行家算法：我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當于銀行家管理的資金，進程向操作系統(tǒng)請求分配資源相當于用戶向銀行家貸款。
為保證資金的安全，

銀行家規(guī)定：

當一個顧客對資金的最大需求量不超過銀行家現(xiàn)有的資金時就可接納該顧客；
顧客可以分期貸款，但貸款的總數(shù)不能超過最大需求量；
當銀行家現(xiàn)有的資金不能滿足顧客尚需的貸款數(shù)額時，對顧客的貸款可推遲支付，但總能使顧客在有限的時間里得到貸款；
當顧客得到所需的全部資金后，一定能在有限的時間里歸還所有的資金.

操作系統(tǒng)按照銀行家制定的規(guī)則為進程分配資源，當進程首次申請資源時，要測試該進程對資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當前的申請量分配資源，否則就推遲分配。當進程在執(zhí)行中繼續(xù)申請資源時，先測試該進程本次申請的資源數(shù)是否超過了該資源所剩余的總量。若超過則拒絕分配資源，若能滿足則按當前的申請量分配資源，否則也要推遲分配。

六、IO多路轉(zhuǎn)接

select

對大量的IO事件是否就緒進行監(jiān)控，并且可以告訴進程哪一個IO就緒了，然后就可以對就緒的IO進行具體的操作。事件是否就緒指的是文件描述符可讀/可寫/異常。他的流程是這樣的：用戶將需要監(jiān)控的文件描述符添加到一個描述符集合中，然后select將描述符集合拷貝到內(nèi)核中，對集合中的描述符進行輪詢判斷，如果有描述符事件就緒了，select調(diào)用返回，并且返回描述符的個數(shù)。否則隔一會再進行輪詢判斷。在調(diào)用返回之前會將集合中沒有就緒的時間描述符移除，在集合中只剩下就緒的文件描述符。返回之后進程判斷有哪個文件描述符在集合中，然后對其進行操作。

select的缺點

select所能監(jiān)控的文件描述符最多只有1024個，他每次都需要將文件描述符集合拷貝到內(nèi)核中進行監(jiān)控，在用戶態(tài)和內(nèi)核態(tài)之間進行數(shù)據(jù)的拷貝，在內(nèi)核中要對所有的文件描述符進行輪詢遍歷判斷，性能會隨著描述符的增加而降低，每次返回的時候都需要將文件描述符集合中非就緒的描述符進行移除，再次監(jiān)控的時候需要添加新的描述符，編碼復(fù)雜，select雖然返回給用戶文件描述符集合，但并不會告訴用戶哪些文件描述符是就緒的，需要用戶自己去遍歷判斷，性能同樣會隨著描述符的增多而降低。

select的優(yōu)點

select遵循posix標準，可以跨平臺使用，并且他監(jiān)控超時的等待時間可以精細到微秒。

poll

poll的功能也是對大量的文件描述符事件進行監(jiān)控，用戶為每一個關(guān)心的文件描述符定義一個事件結(jié)構(gòu)，內(nèi)容為文件描述符+所關(guān)心的事件，poll將描述符事件結(jié)構(gòu)數(shù)組拷貝到內(nèi)核中進行監(jiān)控，同樣是輪詢遍歷數(shù)組中的描述符判斷事件是否就緒，如果就緒了就將事件放到事件結(jié)構(gòu)revents中，調(diào)用返回，否則會隔一段時候后繼續(xù)遍歷判斷，當調(diào)用返回后，用戶遍歷事件結(jié)構(gòu)數(shù)組，判斷結(jié)構(gòu)中的revents事件中是否包含了所關(guān)心的事件。

poll缺點

每次監(jiān)控需要將所有的事件結(jié)構(gòu)信息拷貝到內(nèi)核中，在內(nèi)核中進行輪詢判斷描述符事件是否就緒，會隨著描述符的增多而降低性能，poll的返回同樣不會直接告訴用戶哪些描述符就緒了，需要用戶輪詢?nèi)ケ闅v事件結(jié)構(gòu)數(shù)組，判斷哪個是用戶所關(guān)心的，并且對其進行操作，poll相對于select來說沒有大的改變，性能并沒有提升多少，并且poll沒有遵循POSIX標準，所以不能跨平臺。

poll優(yōu)點

poll采用事件結(jié)構(gòu)的方式對描述符進行監(jiān)控，簡化了多個描述符集合的監(jiān)控編碼流程，poll監(jiān)控的文件描述符的數(shù)量沒有上限。

epoll

epoll可以說是Linux中最優(yōu)秀的多路轉(zhuǎn)接，他的性能是最高的，他在內(nèi)核中創(chuàng)建eventpoll結(jié)構(gòu)體，這個結(jié)構(gòu)體是由紅黑樹（存放事件節(jié)點）和雙向鏈表（存放就緒的文件描述符）實現(xiàn)。在linux2.6.8之前需要對epoll監(jiān)控的文件描述符數(shù)量上限進行設(shè)置，但是在Linux2.6.8之后就忽略了這一參數(shù)，只要大于0就可以。epoll是一個異步操作，epoll開始監(jiān)控后，告訴操作系統(tǒng)開始進程監(jiān)控eventpoll結(jié)構(gòu)體中紅黑樹中的所有事件節(jié)點，操作系統(tǒng)為每一個文件描述符就定義了 一個事件回溯，當文件描述符指定的事件就緒后，就將這個描述符指定的事件接收信息節(jié)點添加到eventpoll中的雙向鏈表中。相當于直接告訴了用戶哪些文件描述符就緒了。

epoll觸發(fā)方式

水平觸發(fā)

對于可讀事件來說，文件描述符接收緩沖區(qū)數(shù)據(jù)大小只要大于低水位標記就會觸發(fā)，對于可寫事件來說只要是文件描述符的發(fā)送緩沖區(qū)空間大小只要大于低水位標記就會觸發(fā)。水平觸發(fā)是epoll的默認觸發(fā)方式，EPOLLLT宏；

邊緣觸發(fā)

對于可讀事件來說，描述符緩沖區(qū)中每當有新數(shù)據(jù)到來時才會觸發(fā)一次，對于可寫事件來說描述符發(fā)送緩沖區(qū)從沒有剩余空間到有剩余空間時才會觸發(fā)一次。邊緣觸發(fā)需要手動設(shè)置，EPOLLET。邊緣觸發(fā)每條數(shù)據(jù)值觸發(fā)一次，這就意味著這次觸發(fā)的過程中需要用戶將所有的數(shù)據(jù)存取完畢，因為這條數(shù)據(jù)不會觸發(fā)第二次，只有等到下一條數(shù)據(jù)到來才會觸發(fā)下一次。由于邊緣觸發(fā)需要一次性將所有的數(shù)據(jù)都處理完，但是用戶有可能也不知道數(shù)據(jù)有多長，所以要使用循環(huán)才可以將所有的數(shù)據(jù)處理完，但是循環(huán)會出現(xiàn)一個就是讀到?jīng)]有數(shù)據(jù)的時候就會阻塞。相應(yīng)的解決方案是將IO操作設(shè)置為非阻塞的。

將描述符設(shè)置為非阻塞：int flag = fcntl(fd, F_GETFD,0) ----獲取描述符屬性fcntl(fd, F_GETFD, flag | O_NONBLOCK)---設(shè)置描述符屬性為增加一個非阻塞屬性

epoll優(yōu)點

監(jiān)控的文件描述符沒有上限，采用事件結(jié)構(gòu)對描述符進行監(jiān)控，簡化了多個描述符集合的監(jiān)控流程，每條epoll的事件信息只向內(nèi)核中拷貝一次，是一個異步阻塞操作，操作系統(tǒng)僅對描述符事件進行監(jiān)控，并且使用的是事件回調(diào)方式，描述符就緒后直接拷貝到對應(yīng)的位置，不需要輪詢遍歷判斷，所以描述符的增加不會影響性能，在回調(diào)的過程中是將就緒的描述符添加到雙向鏈表中，epoll_wait只需要判斷雙向鏈表就知道當前是否有描述符事件就緒，當epoll_wait返回時，是直接將就緒信息拷貝到之前給予的事件結(jié)構(gòu)數(shù)組中，這就相當于直接將就緒的描述符告訴給了用戶。

epoll缺點

epoll沒有遵循POSIX標準，所以不能跨平臺，他監(jiān)控超時只能精確到毫秒。

同步異步和阻塞非阻塞的區(qū)別

阻塞是為了完成一個功能發(fā)起調(diào)用，如果當前不滿足條件，要等待滿足條件了才調(diào)用返回。非阻塞恰恰相反，如果不滿足條件直接報錯返回，阻塞和非阻塞強調(diào)的是發(fā)起一個調(diào)用后是否立即返回。同步指的是如果不滿足條件需要進程進行等待，知道條件滿足了才會調(diào)用返回，對于異步來說，他為了完成某個功能只發(fā)起一個調(diào)用，進程自身并不去完成，功能由操作系統(tǒng)完成后調(diào)用進程，所以說同步和異步強調(diào)的是發(fā)起調(diào)用后，功能是否有進程自己完成。同步功能是由進程自身完成的，通常是阻塞的，異步功能是由系統(tǒng)完成的，有阻塞也有非阻塞。在多路轉(zhuǎn)接中select和poll是同步的，需要進程自己來實現(xiàn)輪詢的遍歷監(jiān)控，epoll是異步阻塞的，因為功能的完成是操作系統(tǒng)完成的，而進程是調(diào)用epoll_wait阻塞等待操作系統(tǒng)完成監(jiān)控。

場景

多路轉(zhuǎn)接模型實現(xiàn)高并發(fā)模型相較于多線程/多進程消耗資源較少，但并不是說所有的場景都使用多路轉(zhuǎn)接模型，它只是用于有大量的文件描述符需要監(jiān)控，但是同一時間只有少量活躍，并且每個描述符的處理過程時間不能太長。

七、用戶態(tài)和內(nèi)核態(tài)

在inter x86結(jié)構(gòu)的cpu中一共有四個級別，0-3級，0級特權(quán)最高，3級特權(quán)最低，這樣做是為了讓最關(guān)鍵的工作交給特權(quán)級最高的進程去執(zhí)行，可以做到集中管理，減少有限資源的訪問和使用沖突。

當一個進程在執(zhí)行用戶自己的代碼時處于用戶態(tài)，此時特權(quán)級最低，為3級，是普通用戶進程運行的特權(quán)級，大部分用戶直接面對的程序都是運行在用戶態(tài)，并且Ring3狀態(tài)不能訪問Ring0狀態(tài)的地址空間，包括代碼和數(shù)據(jù)，當一個進程因為系統(tǒng)調(diào)用陷入內(nèi)核代碼中執(zhí)行時處于內(nèi)核運行態(tài)，此時特權(quán)級最高，為0級。執(zhí)行的內(nèi)核代碼會使用當前進程的內(nèi)核棧，每個進程都有自己的內(nèi)核棧。內(nèi)核態(tài)的進程執(zhí)行完又會切換到Ring3，回到用戶態(tài)。這樣用戶態(tài)的程序就不能隨意操作內(nèi)核地址空間，具有一定的安全保護作用。用戶態(tài)切換到內(nèi)核態(tài)通常有三種方式：系統(tǒng)調(diào)用、異常、外圍設(shè)備的斷。

系統(tǒng)電泳是用戶態(tài)進程主動要求切換內(nèi)核態(tài)的一種方式。用戶態(tài)進程通過系統(tǒng)調(diào)用申請使用操作系統(tǒng)的服務(wù)程序完成工作。比如說fork()就是執(zhí)行了一個創(chuàng)建新進程的系統(tǒng)調(diào)用。

異常是當cpu在執(zhí)行運行在用戶態(tài)的程序時，發(fā)生了一些沒有預(yù)知的異常，這時會觸發(fā)由當前運行進程切換到處理詞異常的內(nèi)核相關(guān)進程中，也就是切換到了內(nèi)核態(tài)。

外圍設(shè)備的中斷指的是當外圍設(shè)備完成用戶請求的操作后，會向CPU發(fā)出相應(yīng)的中斷信號，這時CPU會暫停執(zhí)行下一條即將要執(zhí)行的指令而轉(zhuǎn)到與中斷信號對應(yīng)的處理程序去執(zhí)行，如果當前執(zhí)行的執(zhí)行時用戶態(tài)下的程序，那么轉(zhuǎn)換的過程自然就是由用戶態(tài)轉(zhuǎn)換到內(nèi)核態(tài)。

這三種方式是系統(tǒng)在運行時有用戶態(tài)切換到內(nèi)核態(tài)的主要方式，其中系統(tǒng)調(diào)用可以認為是用戶進程主動發(fā)起的，異常和外圍設(shè)備中斷是被動的。

八、什么是POSIX標準？

posix表示可移植操作系統(tǒng)接口，它定義了操作系統(tǒng)應(yīng)該為應(yīng)用程序提供的接口，這一標準帶來的好處就是在一個POSIX兼容的操作系統(tǒng)中編寫的符合其標準的應(yīng)用程序可以直接在其他的POSIX支持的操作系統(tǒng)中無需修改而能夠直接編譯運行。

九、協(xié)程★★☆☆☆

協(xié)程可以認為是比線程更小的執(zhí)行單元，它自帶CPU上下文，只要在合適的時機，就可以把一個協(xié)程切換到另一個協(xié)程，只要在這個過程中保存或恢復(fù)CPU上下文那么程序還是可以運行的。
線程與協(xié)程的區(qū)別就是系統(tǒng)為了程序運行的高效性每個線程都有自己緩存Cacge等數(shù)據(jù)，操作系統(tǒng)還會幫助做這些數(shù)據(jù)的恢復(fù)操作，可以說線程的切換時非常耗性能，但是協(xié)程的切換只是單程的操作CPU的上下文，所以一秒鐘切換上百萬次系統(tǒng)都扛得住。但是協(xié)程有一個問題就是系統(tǒng)并不感知，所以操作系統(tǒng)不會對其做切換。在設(shè)計的時候可以是一個線程作為容器，然后再里面放置多個協(xié)程，構(gòu)成一個協(xié)程池，在協(xié)程池中有一個被動的調(diào)度器，當有協(xié)程執(zhí)行不了的時候，就要去通知協(xié)程調(diào)度器通過算法找到當前最需要CPU的協(xié)程，然后去執(zhí)行。

十、Linux程序典型內(nèi)存布局

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-YdIAz6xP-1637763958109)(C:\Users\LENOVO\AppData\Roaming\Typora\typora-user-images\1566374936321.png)]

十一、內(nèi)存管理

虛擬內(nèi)存

什么是虛擬內(nèi)存

內(nèi)存是一個程序運行的物質(zhì)基礎(chǔ)，由于內(nèi)存空間總是有限的，所以讓有限的空間運行較大的程序這個問題就出現(xiàn)了，Linux中就使用了虛擬內(nèi)存技術(shù)解決了這個問題。虛擬內(nèi)存是計算機系統(tǒng)管理的一種技術(shù)，可以讓應(yīng)用程序認為自己有擁有連續(xù)的可用內(nèi)存，讓系統(tǒng)看上去具有比實際物理內(nèi)存大得多的內(nèi)存空間，而實際上是被分隔成多個物理內(nèi)存的碎片，還有部分暫時存儲在外部磁盤存儲器上，在需要時進行數(shù)據(jù)交換。由于程序是逐段被運行的，虛擬內(nèi)存技術(shù)是先將一段程序?qū)雰?nèi)存中，執(zhí)行完后導(dǎo)入下一段程序，給我們的感覺是內(nèi)存變大了，實際上物理內(nèi)存并沒有發(fā)生變化。

每個進程都有自己獨立的4G內(nèi)存空間，各個進程的內(nèi)存空間具有類似的結(jié)構(gòu)，這個空間知識虛擬內(nèi)存空間，每次訪問內(nèi)存空間的某個地址，都需要吧地址翻譯成實際的物理內(nèi)存地址。每一個進程都會建立自己的內(nèi)存空間，用來存放這個進程的數(shù)據(jù)、代碼等，這些內(nèi)存空間都與對應(yīng)的磁盤空間映射。所有進程都共享同一物理內(nèi)存，每個進程只把自己目前需要的虛擬內(nèi)存并保存到物理內(nèi)存中。進程通過頁表來記錄哪些數(shù)據(jù)在物理內(nèi)存上，哪些不在，如果在是在物理內(nèi)存的哪里。頁表一般分為兩個部分，一部分記錄此頁是否在物理內(nèi)存中，另一部分用來記錄在物理內(nèi)存中的地址，當一個進程需要訪問某個虛擬地址的時候，要先去看頁表，如果發(fā)絲昂對象的數(shù)據(jù)不在物理內(nèi)存中，就會缺頁異常，然后通過解決缺頁異常處理后，訪問對應(yīng)的物理內(nèi)存。

虛擬內(nèi)存的優(yōu)點

1、每個進程的內(nèi)存空間都是一致并且是固定的，所以鏈接器在鏈接可執(zhí)行文件的時候，可以設(shè)定內(nèi)存地址，就可以不用去管這些數(shù)據(jù)最終實際的內(nèi)存地址，這是獨立內(nèi)存空間的好處。當不同的進程使用的同樣的代碼的時候，比如說庫文件中的代碼，物理內(nèi)存中可以只存儲一份這樣的代碼，不同的進程只需要將自己的虛擬內(nèi)存映射到對應(yīng)的位置就可以，這樣節(jié)省了內(nèi)存。在程序需要分配連續(xù)的內(nèi)存空間的時候，只需要在虛擬內(nèi)存空間中分配連續(xù)的空間，而不需要實際的物理內(nèi)存空間連續(xù)，這樣可以利用物理內(nèi)存中的內(nèi)存碎片，提高了內(nèi)存的利用率。

2、虛擬內(nèi)存保證了讀寫內(nèi)存的安全性。物理內(nèi)存本身是不限制訪問的，任何地址都可以讀寫，而操作系統(tǒng)要求不同的頁面要具有不同的訪問權(quán)限，這是利用CPU模式和MMU的內(nèi)存保護機制實現(xiàn)的。

3、如果一個操作系統(tǒng)同時運行著很多進程，并且為各個進程分配的內(nèi)存之和大于實際可用的物理內(nèi)存，虛擬內(nèi)存管理就可以使這種情況各個進程仍然可以正常運行。因為各個進程分配的只不過是虛擬內(nèi)存的頁面，這些頁面的數(shù)據(jù)可以映射到物理頁面，也可以臨時保存到磁盤上而不占用物理頁面，在磁盤上臨時保存的虛擬內(nèi)存頁面可能是一個磁盤分區(qū)，也可能是一個磁盤文件，被稱為交換設(shè)備。當物理內(nèi)存不夠用的時候，可以將一些不常用的物理頁面中的數(shù)據(jù)臨時保存到交換設(shè)備中，然后這個物理頁面就可以被認為是空閑的，可以重新分配給進程使用，這個過程稱為換出。如果進程要用到被換出的頁面，就從交換設(shè)備再加載回物理內(nèi)存，這個過程稱為換入。換出和換入在操作系統(tǒng)中統(tǒng)稱為換頁，所以系統(tǒng)中可分配的內(nèi)存總量為：物理內(nèi)存的大小+交換設(shè)備的大小。

4、虛擬內(nèi)存作為內(nèi)存管理工具，大大的簡化了內(nèi)存管理，并且為每個進程提供了一個獨立的虛擬地址空間，多個虛擬頁面可以映射到同一個共享的物理頁面上。按照需要進行頁面的調(diào)度和獨立的虛擬地址空間的結(jié)合，讓虛擬內(nèi)存簡化了連接和加載，代碼和數(shù)據(jù)共享，以及應(yīng)用程序的內(nèi)存分配。

簡化鏈接：說的是獨立的地址空間允許每個進程的內(nèi)存映射使用相同的基本格式，不用考慮代碼和數(shù)據(jù)在物理內(nèi)存的地址。當不用的進程使用相同的代碼的時候，比如說庫文件中的代碼，在物理內(nèi)存中只存放了一份這樣的代碼，不同的進程只需要將自己的虛擬內(nèi)存映射到對應(yīng)的位置就可以。

簡化加載：指的是虛擬內(nèi)存讓向內(nèi)存中中加載可執(zhí)行文件和共享對象文件變得容易。將一組連續(xù)的虛擬頁面映射到任意一個文件中的任意位置的表示法稱為內(nèi)存映射。

簡化共享：指的是獨立地址空間為操作系統(tǒng)提供了一個管理用戶進程和操作系統(tǒng)自身之間共享的機制。一般情況下每個進程都有自己獨立的內(nèi)存空間，里面存放著該進程的代碼、數(shù)據(jù)、堆棧，這些內(nèi)容都是不與其他進程所共享的。在操作系統(tǒng)中為了多個進程之間通訊的考慮，預(yù)留出了一塊內(nèi)存區(qū)，多個進程如果要實現(xiàn)共享，由操作系統(tǒng)創(chuàng)建頁表，將相應(yīng)的虛擬頁映射到不連續(xù)的物理頁面，然后將這個頁表映射到進程的這塊內(nèi)存中，這樣多個進程就可以對同一塊物理內(nèi)存進行讀寫，實現(xiàn)數(shù)據(jù)的共享。

簡化內(nèi)存分配：指的是虛擬內(nèi)存向用戶進程提供一個簡單的分配額外空間的機制。當一個用戶程序要求額外空間的時候，操作系統(tǒng)分配K個適當?shù)倪B續(xù)的虛擬內(nèi)存頁面，并且將他們映射到物理內(nèi)存中的K個任意頁面，操作系統(tǒng)沒有必要分配K個連續(xù)的物理內(nèi)存頁面。

鑒于《深入理解計算機系統(tǒng)》龔奕利·譯

缺頁異常解決辦法

什么是缺頁異常

在分頁系統(tǒng)中，可以通過查詢頁表的狀態(tài)為來確定要訪問的頁面時候存在內(nèi)存中，每當所有訪問的頁面不在內(nèi)存時，或者訪問的頁面在內(nèi)存中但是時不可寫的，會產(chǎn)生一次缺頁中斷。缺頁本身就是一種中斷，它與一般的中斷一樣，需要經(jīng)過4個處理步驟

1、保護CPU現(xiàn)場。

2、分析中斷的原因

3、轉(zhuǎn)入缺頁中斷處理程序中進行處理

4、恢復(fù)CPU現(xiàn)場，繼續(xù)執(zhí)行

但是缺頁中斷時可能由于要訪問的頁面不在內(nèi)存中，這時就會由硬件產(chǎn)生一種特殊的中斷，缺頁中斷與一般的中斷區(qū)別在于：在指令執(zhí)行期間產(chǎn)生和處理缺頁中斷信號、一條指令在執(zhí)行期間可能會產(chǎn)生多次缺頁中斷、缺頁中斷返回時執(zhí)行的是產(chǎn)生中斷的那一條指令，而不是像一般中斷去執(zhí)行下一條指令。

頁面置換算法

進程運行過程中，如果發(fā)生缺頁中斷，但是內(nèi)存中沒有空間的物理塊，為了能夠把所缺的頁面裝入內(nèi)存，系統(tǒng)必須要從內(nèi)存中選擇一頁調(diào)出到磁盤的對換區(qū)。但此時應(yīng)該吧那個頁面換出，則需要根據(jù)一定的頁面置換算法來確定。通常有最佳置換、先進先出置換、最近最久未使用置換、時鐘置換算法。

最佳置換算法（OPT）

從主存中移除永遠不需要的頁面，如果沒有這樣的頁面存在，則選擇最長時間不需要的訪問的頁面。由于所選擇的被淘汰的頁面是以后永不使用的，或者是在長時間內(nèi)不再被訪問的頁面，這樣就可以保證獲得最低的缺頁率。

先進先出算法（FIFO）

是最簡單的頁面置換算法。這種算法的思想是當需要淘汰一個頁面的時候，總是選擇駐留主存事件最長的頁面進行淘汰，也就是先進入主存的頁面會被先淘汰。這是因為最早調(diào)入主存的頁面的不再被使用的可能性最大。

FIFO算法還會產(chǎn)生當所分配的物理塊樹增大而頁故障數(shù)不減少反而增加的異常現(xiàn)象，這是由Belady于1969年發(fā)現(xiàn)，所以稱為Belady異常，只有FIFO算法會出現(xiàn)Belady異常，而LRU和OPT算法永遠不會出現(xiàn)Belady異常。

需要注意的是內(nèi)存的頁面中最先進入隊列的頁面會被來的頁面直接覆蓋，而不是先出隊，然后再從大隊尾入隊。

最近最久未使用算法（LRU）

這種算法的思想是：利用局部性原理，根據(jù)一個作業(yè)在執(zhí)行中過去的頁面訪問歷史來推測未來的行為。他認為過去一段時間里不曾被訪問的頁面，在最近的將來也不會再被訪問。所以這種算法的實質(zhì)就是當需要淘汰一個頁面的時候，總是選擇在最近一段時間內(nèi)最久沒有使用的頁面淘汰。

時鐘置換算法（CLOCK）

由于LRU算法的性能接近于OPT，但是實現(xiàn)起來比較困難，并且開銷大，FIFO算法實現(xiàn)簡單，但是性能差。所以師徒用比較小的開銷接近LRU的性能，這類算法都是CLOCK算法的變體。

簡單的CLOCK算法是給每一幀關(guān)聯(lián)一個附加位，稱為使用位。當某一頁首次裝入主存時，該幀的使用位設(shè)置為1，當給爺雖有在被訪問到時，它的使用位也置為1。對于也替換算法來說，用于替換的候選幀集合看做一個循環(huán)緩沖區(qū)，并且有一個指針與之關(guān)聯(lián)。當某一頁被替換時，給指針被設(shè)置成指向緩沖區(qū)中的下一幀。當需要替換一頁時，操作系統(tǒng)掃描緩沖區(qū)，以查找使用位被置為0的一幀。每當遇到一個使用位為1的幀時，操作系統(tǒng)就會將該位重新置為0，如果在這個過程開始時，緩沖區(qū)中所有的使用位均為0，則選擇遇到的第一個幀替換；如果所有的幀使用位均為1，則指針在緩沖區(qū)中完整的循環(huán)一周，把所有的使用位都置為0，并且停留在最初始的位置上，替換該幀中的頁。由于這個算法循環(huán)地檢測各頁面的情況，所以被稱為CLOCK算法，又稱為最近未使用算法。

MMU

內(nèi)存管理單元簡稱MMU，他杜澤虛擬地址到物理地址的映射，并提供硬件機制的訪問權(quán)限檢查。MMU使得每個用戶進程擁有自己獨立的地址空間，并通過內(nèi)存訪問權(quán)限的檢查保護每個進程所用的內(nèi)存不被其他的進程破壞。

物理內(nèi)存

在內(nèi)核態(tài)申請內(nèi)存比在用戶態(tài)申請內(nèi)存更為直接，他沒有采用用戶態(tài)的延遲分配內(nèi)存技術(shù)。內(nèi)核認為一旦有內(nèi)核函數(shù)申請內(nèi)存就必須立即滿足該申請的請求，并且這個請求一定是合理的。相反，對于用戶態(tài)申請內(nèi)存的請求，內(nèi)核總是盡量延后分配內(nèi)存，用戶進程總是先獲得一個虛擬內(nèi)存區(qū)的使用權(quán)，最終通過缺頁異常獲得一塊真正的物理內(nèi)存。

十二、動態(tài)庫和靜態(tài)庫

什么是庫？

平時在寫代碼的時候會經(jīng)常添加一些頭文件，添加這些頭文件其實是讓編譯器從一個目錄下去尋找這個文件，這個目錄就是我們常說的庫。在Linux中庫一般存放在user/lib目錄。庫就是將一些常用的函數(shù)的目標文件打包在一起，提供相應(yīng)的函數(shù)接口，以便于使用。

什么是靜態(tài)庫？

靜態(tài)庫就是在編譯連接的時候，將庫中的代碼連接直接復(fù)制到可執(zhí)行文件中，這樣程序在運行的時候就不用去連接動態(tài)庫了。靜態(tài)庫的這個連接過程就是靜態(tài)鏈接。

什么是動態(tài)庫？

動態(tài)庫就是程序在運行的時候才去連接動態(tài)庫的代碼，可以多個程序共享動態(tài)庫中的代碼，這個動態(tài)庫的連接過程就是動態(tài)鏈接，也就是在執(zhí)行文件開始之前將外部函數(shù)的機器碼有系統(tǒng)從磁盤上對應(yīng)的動態(tài)庫中向內(nèi)存復(fù)制一份。

靜態(tài)庫和動態(tài)庫的區(qū)別？

1、動態(tài)庫是在運行時有系統(tǒng)調(diào)用庫函數(shù)實現(xiàn)鏈接，代碼較小巧。而靜態(tài)庫是在鏈接是復(fù)制到代碼中，代碼量比較龐大，冗余度高。
2、由于靜態(tài)庫是通過復(fù)制的方式，所以他在編譯連接之后就不再需要靜態(tài)庫，代碼的可以執(zhí)行強，但是動態(tài)庫由于是利用本地的庫函數(shù)，如果將代碼移植到其他電腦會出現(xiàn)運行bug等，可移植性差。
3、動態(tài)庫必須放在指定的目錄下完成連接，但是靜態(tài)庫只需要給出鏈接文件的路徑就可以。
4、他們的相同點就是在庫文件中不能出現(xiàn)main函數(shù)，庫都是用來提供函數(shù)接口的，不暴露源代碼，所有的庫的目的都是為了增加代碼的復(fù)用，可共享性，減小冗余。
5、在windows中靜態(tài)庫是后綴是.lib，動態(tài)庫是.dll，在Linux中靜態(tài)庫是.a,動態(tài)庫是so。
6、使用ar創(chuàng)建靜態(tài)庫

生成動態(tài)和靜態(tài)庫

? gcc -fPIC -c child.c -o child.o 生成目標文件

? gcc --share child.o -o lid+庫名稱+.so 動態(tài)庫

? gcc -ar rcd lib+庫名稱+.a 靜態(tài)庫

? windows下的動態(tài)庫 .dll 靜態(tài)庫 .lib

先生成二進制的.o文件gcc -fPIC -c child.c -o child.o生成靜態(tài)庫ar -rc libchild.a child.o生成動態(tài)庫gcc --shared -fpic libchild.so child.o鏈庫-l + 庫名，但是庫必須保存在lib、usr/lib、usr/local/lib目錄下，否則要用-L + 文件路徑 + -l + 庫名

十三、軟連接和硬鏈接

十四、線程的切換

★★網(wǎng)絡(luò)知識★★

一、TCP和UDP的區(qū)別及應(yīng)用場景

區(qū)別

1、面向連接和無連接角度

tcp建立一個鏈接需要三次握手，斷開的時候需要進行四次揮手。TCP在斷開是主動方要進入一個TIME_WAIT狀態(tài)，要等待2MSL才會對連接（端口）釋放，這個時間要根據(jù)系統(tǒng)來定，Windows一般為120秒。

但是UDP不需要建立連接，直接發(fā)起。

2、可靠和不可靠角度

TCP利用三次握手、四次揮手、ACK確認應(yīng)答、重傳機制等來保證可靠性，UDP沒有。

TCP中保證可靠性的機制有：

校驗和：用來校驗數(shù)據(jù)是否損壞

定時器：用來確認分組是否丟失，丟失需要重傳

序列號：用來檢測丟失的分組和重傳的分組。

確認應(yīng)答ACK：用來讓接收方通知發(fā)送方已經(jīng)正確接受，以及期望的下一個分組。

否定確認：用來讓接收方通知發(fā)送方?jīng)]有被正確接受的分組。

窗口和流水線：用于增加信道的吞吐量。

3、有序性

TCP利用seq序列號來對包進行排序，UDP沒有

4、面向字節(jié)流和面向報文

面向報文

面向報文的傳輸方式是應(yīng)用層交給UDP多少報文，UDP就按原樣發(fā)送，也就是一個發(fā)送一個報文。所以應(yīng)用層就要選擇合適的大小的報文交給UDP，如果報文太長，在IP層就會進行分片。

面向字節(jié)流

面向字節(jié)流的傳輸方式是雖然應(yīng)用層交給TCP的是一次一個數(shù)據(jù)塊，但是TCP會將這個數(shù)據(jù)塊看成一連串無結(jié)構(gòu)的字節(jié)流。在TCP的發(fā)送端有一個發(fā)送緩沖區(qū)，當數(shù)據(jù)塊太大，TCP就將它劃分的小一些在發(fā)送，如果數(shù)據(jù)塊太小了，TCP就會等待累計夠足夠多的字節(jié)后再發(fā)送。

5、TCP有流量控制機制，UDP沒有

6、TCP頭部為20字節(jié)，UDP頭部為8字節(jié)

應(yīng)用場景

TCP的應(yīng)用場景

對效率要求較低，但是對準確要求很高的場景。因為在使用TCP傳輸?shù)臅r候需要對數(shù)據(jù)進行確認、重發(fā)、排序等操作，相對UDP來說效率降低了許多。這些場景都有：文件傳輸、遠程登錄。

UDP應(yīng)用場景

對效率要求較高，對準確要求較低的場景，因為在使用UDP傳輸?shù)臅r候沒有對數(shù)據(jù)進行任何的檢驗操作，相對于TCP效率提升了很多。這些應(yīng)用場景有：QQ聊天、在線視頻、廣播通信等。

二、TCP連接的建立和斷開

TCP建立連接

tcp采用三次握手建立連接，

1、客戶端向服務(wù)端發(fā)起SYN連接請求，這條連接請求中還包含了客戶端的窗口大小

2、服務(wù)端收到連接、請求后，為客戶端申請資源同時向客戶端回復(fù)一個SYN+ACK，還有自己的窗口大小。

3、如果這條消息丟失，客戶端沒有收到這條消息，那么客戶端不會做任何響應(yīng)，也就不會向服務(wù)端發(fā)送ACK確認，由于服務(wù)端遲遲沒有發(fā)送確認的ACK，服務(wù)器就會將之前申請的資源釋放。如果客戶端收到了這條消息，開始申請資源，同時回復(fù)服務(wù)端一個ACK確認，開始進行收發(fā)數(shù)據(jù)。

4、如果最后這條ACK消息丟失，導(dǎo)致服務(wù)端沒有收到，服務(wù)端就認為連接失敗，將之前的資源釋放，但是客戶端認為連接已經(jīng)建立好了，就會向服務(wù)端發(fā)送數(shù)據(jù)。服務(wù)端由于沒有收到最后一條ACK消息，就會以RST包對客戶端進行響應(yīng)，重新建立連接。

TCP斷開連接

TCP采用四次揮手斷開連接，

1、主動關(guān)閉方向被動方發(fā)送FIN請求，進入FIN_WAIT_1狀態(tài)，等待被動方的ACK確認。

2、被動接收到FIN請求后，回復(fù)一個ACK確認，這時被動方進入CLOSE_WAIT狀態(tài)，進入這個狀態(tài)是為了將自己的所有要發(fā)送的數(shù)據(jù)都發(fā)送完，將自己申請的空間都釋放完。這時候主動方接受到ACK請求沒有直接斷開連接，而是進入FIN_WAIT_2狀態(tài)，在這個狀態(tài)下，主動方只能接受數(shù)據(jù)，不能進行發(fā)送。

3、等被動方將自己的事情都處理完，向主動方發(fā)送FIN請求，進入LAST_ACK狀態(tài)，等待主動方的ACK確認。

4、主動方接收到被動方的FIN請求后，進入TIME_WAIT狀態(tài)，向被動方發(fā)送ACK，等待2MSL后，進入CLOSED的狀態(tài)。這里的MSL是一個報文在網(wǎng)絡(luò)中的最大生命周期，進入TIME_WAIT狀態(tài)，并且等待2MSL是為了防止由于網(wǎng)絡(luò)原因，最后一個ACK沒有到達被動方，如果被動方一直沒有收到ACK確認，會再次向主動方發(fā)送FIN請求，這時主動方重新進入TIMR_WAIT狀態(tài)。將等待時間設(shè)置為2MSL還有一個原因就是要將網(wǎng)絡(luò)中所有殘留的數(shù)據(jù)消失，防止由于網(wǎng)絡(luò)原因某些數(shù)據(jù)阻塞在網(wǎng)絡(luò)中，如果沒有等待2MSL而是立即重新建立連接，很有可能之前的滯留在網(wǎng)絡(luò)中的數(shù)據(jù)到達了，這時就會造成數(shù)混亂。如果在2MSL之內(nèi)主動方?jīng)]有接收到被動方FIN請求，則認為對方已經(jīng)接收到ACK，主動方進入CLOSED狀態(tài)，也就是斷開連接。對于被動方來說，一旦接收到了來自主動方的ACK確認，就會進入CLOSED狀態(tài)，關(guān)閉連接。

三、socket編程過程

基于TCP的socket：

服務(wù)端程序：

創(chuàng)建一個socket，調(diào)用socket（）函數(shù)，返回綁定IP地址、等信息到socket上，調(diào)用函數(shù)bind（）設(shè)置允許的最大連接數(shù),調(diào)用函數(shù)listen()，通常設(shè)置為5接受來自客戶端的連接，調(diào)用accept(),使用send和recv開始收發(fā)數(shù)據(jù) 返回值： 成功返回實際接收字節(jié)數(shù)，錯誤返回的-1，對端已經(jīng)關(guān)閉了連接返回0關(guān)閉網(wǎng)絡(luò)連接

客戶端程序

創(chuàng)建一個socket，調(diào)用socket()函數(shù)設(shè)置要連接的對方的IP地址和端口等屬性連接服務(wù)器，調(diào)用函數(shù)connect()使用send和recv開始收發(fā)數(shù)據(jù)關(guān)閉網(wǎng)絡(luò)連接

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-nzGXRIl7-1637763958110)(C:\Users\LENOVO\AppData\Roaming\Typora\typora-user-images\1566711302816.png)]

/************************************************************************* -> 文件名: tcp_socket.hpp -> 作者: bean -> 郵箱: 17331372728@163.com -> 創(chuàng)建時間: Fri 24 May 2019 06:05:41 AM PDT -> 備注: 封裝一個TcpSocket類，向外提供輕便的socket接口 1.創(chuàng)建套接字 2.為套接字綁定地址 3.客戶端向服務(wù)端發(fā)起連接請求 4.服務(wù)端開始監(jiān)聽 4.服務(wù)端獲取一個已經(jīng)連接成功的客戶端的新建socket 5.客戶端與服務(wù)端開始收發(fā)數(shù)據(jù) 6.關(guān)閉套接字 *************************************************************************/#include<iostream>#include<string>#include<stdlib.h>#include<stdio.h>#include<unistd.h>#include <sys/types.h>#include<sys/socket.h>#include<netinet/in.h>#include<arpa/inet.h>#include<string.h>using namespace std;#define CHECK_RET(q) if((q) == false){return -1;}class TcpSocket{ public: TcpSocket():_sockfd(-1) {} ~TcpSocket(){} bool Socket() { _sockfd = socket(AF_INET,SOCK_STREAM,IPPROTO_TCP); if(_sockfd < 0) { cout << "socket error" << endl; return false; } return true; } bool Bind(string &ip, uint16_t port) { struct sockaddr_in addr; addr.sin_family = AF_INET; addr.sin_port = htons(port); addr.sin_addr.s_addr = inet_addr(ip.c_str()); socklen_t len = sizeof(struct sockaddr_in); int ret = bind(_sockfd, (struct sockaddr*)&addr, len); if(ret < 0) { cout << "bind error" << endl; return false; } return true; } //開始監(jiān)聽，并且設(shè)置服務(wù)端的同一時間最大并發(fā)連接數(shù) bool Listen(int baklog = 5) { //int listen(int sockfd, int backlog); //sockfd: 套接字描述符 //backlog: 同一時間最大連接數(shù)，設(shè)置內(nèi)核中已完成連接的最大節(jié)點數(shù) int ret = listen(_sockfd, baklog); if(ret < 0) { cout << "Listen error" << endl; return false; } return true; } //獲取連接成功客戶端socket，并且返回客戶端的地址信息 bool Accept(TcpSocket &sock, struct sockaddr_in *addr = NULL) { //int accept(int sockfd, struct sockaddr *addr, socklen_t *addrlen); //sockfd: 套接字描述符 //addr: 用于存儲客戶端地址信息 //addrlen: 用于設(shè)置想要的地址長度和保存實際的地址長度 //返回值： 為客戶端連接新建的socket描述符 //接下來與客戶端的通信都是通過這個新的描述符實現(xiàn)的 struct sockaddr_in _addr; socklen_t len = sizeof(struct sockaddr_in); int newfd = accept(_sockfd, (struct sockaddr*)&_addr, &len); if(newfd < 0) { cout << "Accept error" << endl; return false; } sock.SetFd(newfd); if(addr != NULL) { memcpy(addr, &_addr, len); } return true; } //客戶端向服務(wù)端發(fā)起連接請求 bool Connect(string &ip, uint16_t port) { //int connect(int sockfd, const struct sockaddr *addr,socklen_t addrlen); //sockfd: 套接字描述符 //addr: 服務(wù)端監(jiān)聽地址信息 //addrlen: 地址信息長度 struct sockaddr_in addr; addr.sin_family = AF_INET; addr.sin_port = htons(port); addr.sin_addr.s_addr = inet_addr(ip.c_str()); socklen_t len = sizeof(struct sockaddr_in); int ret = connect(_sockfd,(struct sockaddr*)&addr, len); //cout << ip << " "<< port << " " << ret<< " " <<"1" << endl; if(ret < 0) { cout << "connect error" << endl; return false; } cout << "來了，老弟！！！" << endl; return true; } //通信接口：tcp服務(wù)端也可以直接發(fā)送數(shù)據(jù)（因為連接已經(jīng)發(fā)送成功） bool Recv(string &buff) { //ssize_t recv(int sockfd, void *buf, size_t len, int flags); //sockfd: 套接字描述符 //buf: 接收的數(shù)據(jù)存儲 //len: 想要接收的數(shù)據(jù)長度 //flags: 0 默認是阻塞接收 // MSG_PEEK 接收數(shù)據(jù)但是數(shù)據(jù)不從接收緩沖區(qū)中移除 探測性接收 //返回值： 成功返回實際接收字節(jié)數(shù)，錯誤返回的-1，對端已經(jīng)關(guān)閉了連接返回0 char tmp[1024] = {0}; int ret = recv(_sockfd, tmp, 1024, 0); if(ret == 0) { cout << "peer shutdown" << endl; return false; } else if(ret < 0) { cout << "recv error" << endl; return false; } buff.assign(tmp,ret); return true; } ssize_t Send(string &buff) { //ssize_t send(int sockfd, const void *buf, size_t len, int flags); //返回值： 成功就是實際發(fā)送的字節(jié)數(shù) 失敗 -1 //如果連接已經(jīng)斷開，發(fā)送就會觸發(fā)異常，導(dǎo)致進程退出 int ret = send(_sockfd, buff.c_str(), buff.size(), 0); if(ret < 0) { cout << "send error" << endl; return false; } return true; } bool Close() { close(_sockfd); _sockfd = -1; return true; } void SetFd(int sockfd) { _sockfd = sockfd; } private: int _sockfd;};/************************************************************************* *文件名: tcp_ser.cpp *作者: bean *郵箱: 17331372728@163.com * 創(chuàng)建時間: Fri 24 May 2019 07:27:34 AM PDT * 備注:通過封裝的TcpSocket類實現(xiàn)服務(wù)端程序 * 1、創(chuàng)建套接字 * 2、綁定地址信息 * 3、開始監(jiān)聽 * 4、獲取連接成功的客戶端新建socket * 5、通過新建的socket與客戶端進行通信 * 6、關(guān)閉套接字 *************************************************************************/#include"tcpsocket.hpp"int main(int argc, char* argv[]){ if(argc != 3) { cout << "./tcp_ser ip port" << endl; return -1; } string ip = argv[1]; uint16_t port = atoi(argv[2]); TcpSocket sock; CHECK_RET(sock.Socket()); CHECK_RET(sock.Bind(ip, port)); CHECK_RET(sock.Listen()); while(1) { //程序會卡在accept是應(yīng)為用戶無法獲知客戶端的新連接什么時候到來 //如果能知道什么時候盜壘就不會阻塞，只需要在來的時候調(diào)用一次就行 TcpSocket client; if(sock.Accept(client) == false) { continue; } while(1) { string buff; client.Recv(buff); cout << "Tcp->Client say:" << buff << endl; buff.clear(); cout << "Tcp->Server say:"; fflush(stdout); getline(cin,buff); client.Send(buff); } } sock.Close(); return 0;}/**************************************************************************文件名: tcp_ser.cpp*作者: bean*郵箱: 17331372728@163.com* 創(chuàng)建時間: Fri 24 May 2019 07:27:34 AM PDT* 備注:通過封裝的TcpSocket類實現(xiàn)服務(wù)端程序* 1、創(chuàng)建套接字* 2、綁定地址信息* 3、開始監(jiān)聽* 4、獲取連接成功的客戶端新建socket* 5、通過新建的socket與客戶端進行通信* 6、關(guān)閉套接字*************************************************************************/#include"tcpsocket.hpp"#include<signal.h>#include<sys/wait.h>void sigcb(int no){ while(waitpid(-1, NULL, WNOHANG) > 0);}int main(int argc, char* argv[]) if(argc != 3) { cout << "./tcp_ser ip port" << endl; return -1; } //如果多個進程同時退出了，要等他處理完了再退出 signal(SIGCHLD, sigcb); string ip = argv[1]; uint16_t port = atoi(argv[2]); TcpSocket sock; CHECK_RET(sock.Socket()); CHECK_RET(sock.Bind(ip, port)); CHECK_RET(sock.Listen()); while(1) { //程序會卡在accept是應(yīng)為用戶無法獲知客戶端的新連接什么時候到來 //如果能知道什么時候盜壘就不會阻塞，只需要在來的時候調(diào)用一次就行 TcpSocket client; if(sock.Accept(client) == false) { continue; } //創(chuàng)建一個子進程負責聊天 int pid = fork(); if(pid == 0) { while(1) { string buff; client.Recv(buff); cout << "Client say:" << buff << endl; cout << "Server asy:"; fflush(stdout); cin >> buff; client.Send(buff); } } client.Close(); } sock.Close(); return 0;}

基于UDP的socket

服務(wù)端流程

創(chuàng)建套接字文件描述符，調(diào)用socket();設(shè)置服務(wù)器地址和監(jiān)聽關(guān)口，初始化要綁定的網(wǎng)絡(luò)地址結(jié)構(gòu)。綁定監(jiān)聽端口，調(diào)用bind()函數(shù)，接收客戶端數(shù)據(jù)，調(diào)用recvfrom()函數(shù)向客戶端發(fā)送數(shù)據(jù)，調(diào)用sendto()函數(shù)向客戶端發(fā)送數(shù)據(jù)關(guān)閉套接字，調(diào)用close()函數(shù)釋放資源。

客戶端流程

創(chuàng)建套接字文件描述符，調(diào)用socket()設(shè)置服務(wù)器地址和端口，struct sockaddr()向服務(wù)端發(fā)送數(shù)據(jù)，調(diào)用sendto()，接受服務(wù)端的數(shù)據(jù)，調(diào)用recvfrom()關(guān)閉套接字，調(diào)用close()函數(shù)釋放資源。 /*************************************************************************-> 文件名: udp_socket.hpp-> 作者: bean-> 郵箱: 17331372728@163.com-> 創(chuàng)建時間: Thu 23 May 2019 04:20:18 AM PDT-> 備注:分裝一個udp的套接字接口類 實現(xiàn)： 套接字創(chuàng)建、綁定地址、接收數(shù)據(jù)、發(fā)送數(shù)據(jù)、關(guān)閉套接字*************************************************************************/#include<iostream>#include<string>#include<sys/socket.h>#include<errno.h>#include<netinet/in.h>#include<arpa/inet.h>#include<stdio.h>#include<stdlib.h>#include<sys/types.h>#include<string.h>#include<unistd.h>#define CHECK_RET(q) if((q) == false){return -1;}using namespace std;class UdpSocket{ public: UdpSocket() { } ~UdpSocket() { } bool Socket() //創(chuàng)建套接字 { //int socket(int domain, int type, int protocol); //domain: 地址域，確定通信范圍 // AF_INET 表示使用IPV4網(wǎng)絡(luò)協(xié)議 //type： 套接字類型 // SOCK_STREAM 流式套接字----默認使用TCP // SOCK_DGRSM 數(shù)據(jù)包套接字--默認使用UDP //protocol: // 0 使用默認協(xié)議 // IPPROTO_TCP 6 TCP協(xié)議 // IPPROTO_UDP 17 UDP協(xié)議 //返回值：套接字操作句柄---文件描述符 失敗：-1 _sock = socket(AF_INET, SOCK_DGRAM, IPPROTO_UDP); if(_sock < 0) { perror("socket error"); return false; } return true; } bool Bind(string &ip, uint16_t port) //為套接字綁定地址信息 { struct sockaddr_in addr; addr.sin_family = AF_INET; //因為網(wǎng)絡(luò)通信使用大端字節(jié)序，因此端口和IP地址信息都要轉(zhuǎn)換成網(wǎng)絡(luò)字節(jié)序 //uint16_t htons(uint16_t hostshort); // 將一個16為數(shù)據(jù)從主機字節(jié)序轉(zhuǎn)換為網(wǎng)絡(luò)字節(jié)序 //uint32_t htonl(uint32_t hostlong); //將一個32為數(shù)據(jù)從主機字節(jié)序轉(zhuǎn)換為網(wǎng)絡(luò)字節(jié)序 //不能使用htonl，因為端口只有2的字節(jié)，由于htonl是兩個字節(jié)來轉(zhuǎn)換的，所以經(jīng)htonl后，還是原來的 addr.sin_port = htons(port); //in_addr_t inet_addr(const char *cp); //將字符串點分十進制IP地址，轉(zhuǎn)換為網(wǎng)絡(luò)字節(jié)序的整數(shù)IP地址 addr.sin_addr.s_addr = inet_addr(ip.c_str()); //int bind(int sockfd, const struct sockaddr *addr,socklen_t addrlen); //sockfd: 創(chuàng)建套接字返回套接字描述符 //addr: 要綁定的地址信息 //addrlen: 地址信息長度 //返回值： 成功：0 失敗：-1 socklen_t len = sizeof(struct sockaddr_in); int ret = bind(_sock, (struct sockaddr*)&addr, len); if(ret < 0) { perror("Bind error"); return -1; } return true; } bool Recv(string &buf, sockaddr_in *_addr = NULL) //接收數(shù)據(jù) { //recvfrom(int sockfd, void *buf, size_t len, int flags, struct sockaddr *src_addr, socklen_t *addrlen); //sockfd: 套接字描述符 //buf: 用于保存接收的數(shù)據(jù) //len: 要接受的數(shù)據(jù)長度 //flags: 默認0，表示阻塞接收，沒有數(shù)據(jù)就阻塞 //src_addr: 發(fā)送端的地址信息 //addelen: 用于獲取地址信息長度（輸入輸出型參數(shù)） //返回值： 實際接收數(shù)據(jù)長度，錯誤返回-1 char tmp[1024] = {0}; struct sockaddr_in addr; socklen_t len = sizeof(struct sockaddr_in); int ret = recvfrom(_sock, tmp, 1024, 0,(struct sockaddr*)&addr, &len); if(ret < 0) { perror("recvfrom error"); return false; } buf.assign(tmp, ret); //從tmp中拷貝獲取的實際長度到buf中 if(_addr != NULL)//如果用戶想要獲取發(fā)送端的地址，這是_addr就不為空，這時就將獲取到的地址拷貝到_addr中 memcpy(_addr,&addr,len); return true; } bool Send(string &buf, struct sockaddr_in &addr) //發(fā)送數(shù)據(jù) { //sendto(int sockfd, void *buf, size_t len, int flags,struct sockaddr *dest_addr, socklen_t addrlen); //dest_addr: 目的端地址信息 //addrlen: 發(fā)送地址信息長度 socklen_t len = sizeof(struct sockaddr_in); int ret = sendto(_sock, buf.c_str(), buf.size(), 0,(struct sockaddr*)&addr, len); if(ret < 0) { perror("sendto error"); return false; } return true; } bool Close() //關(guān)閉套接字 { close(_sock); _sock = -1; return true; } private: int _sock;};/*************************************************************************-> 文件名: udp_ser.cpp-> 作者: bean-> 郵箱: 17331372728@163.com-> 創(chuàng)建時間: Thu 23 May 2019 04:08:16 AM PDT-> 備注:使用UdpSock類完勝UDP服務(wù)端程序*************************************************************************/#include"udp_socket.hpp"int main(int argc, char *argv[]){ if(argc != 3) { cout << "./dup_srv ip port" << endl; return -1; } string ip = argv[1]; uint16_t port = atoi(argv[2]); UdpSocket sock; //創(chuàng)建套接字 CHECK_RET(sock.Socket()); CHECK_RET(sock.Bind(ip, port)); while(1) { string buff; struct sockaddr_in c_addr; sock.Recv(buff, &c_addr); cout << "client asy:" << buff.c_str() << endl; cout << "server say:"; fflush(stdout); getline(cin, buff); sock.Send(buff, c_addr); } sock.Close(); return 0;}/*************************************************************************-> 文件名: udp_cli.cpp-> 作者: bean-> 郵箱: 17331372728@163.com-> 創(chuàng)建時間: Fri 24 May 2019 05:06:34 AM PDT-> 備注: 通過udpsocket實現(xiàn)客戶端程序*************************************************************************/#include "udp_socket.hpp"int main(int argc, char* argv[]){ if(argc != 3) { cout << "./dup_cli ip port" << endl; return -1; } string ip = argv[1]; uint16_t port = atoi(argv[2]); UdpSocket sock; CHECK_RET(sock.Socket()); struct sockaddr_in s_addr; s_addr.sin_family = AF_INET; s_addr.sin_port = htons(port); s_addr.sin_addr.s_addr = inet_addr(ip.c_str()); while(1) { string buff; cout << "client say:"; getline(cin, buff); sock.Send(buff, s_addr); buff.clear(); sock.Recv(buff); cout << "server say:" << buff << endl; } sock.Close(); return 0;}

四、應(yīng)用層的協(xié)議

基于TCP的有FTP、Telnet、SMTP、HTTP、POP3與DNS
基于UDP的有TFTP、SNMP與DNS
其中DNS既可以基于TCP，也可以基于UDP。

FTP(File Transfer Protocol)：文本傳輸協(xié)議 端口號： 20 和21一個端口用于控制，一個端口用于傳輸數(shù)據(jù)

Telnet：端口號為23，功能：遠程管理，而在Linux中為SSH 端口號為22

SMTP: 發(fā)送郵件 TCP：25

POP3：接收郵件TCP:110

HTTP:超文本傳輸協(xié)議 TCP:80
HTTPS：相對于HTTP安全 對數(shù)據(jù)包進行加密 TCP：43

DNS：域名解析服務(wù) 網(wǎng)絡(luò)下標如果出現(xiàn)談好很可能是DNS配置不對 TCP UDP:53

TFTP：簡單文件傳輸協(xié)議 早先FTP服務(wù)器代碼太大了相對于服務(wù)器的容量來說，所以主要傳輸一些小文件的時候就是用TFTP，對于網(wǎng)絡(luò)設(shè)備的維護一直使用 端口號為69

五、HTTP協(xié)議

HTTP協(xié)議（超文本傳輸協(xié)議），是互聯(lián)網(wǎng)上引用最廣泛的一種網(wǎng)絡(luò)協(xié)議，所有的www文件都要必須遵守這個標準。HTTP和TCp是不沖突的，HTTP定義在應(yīng)用層、TCP是在傳輸層，解決的是傳輸層的邏輯。HTTP使用TCP不使用UDP是因為打開一個網(wǎng)頁需要傳送很多的數(shù)據(jù)，而TCP提供傳輸控制，按順序數(shù)字數(shù)據(jù)和錯誤糾正，并且保證數(shù)據(jù)的可靠傳輸。

URL、URI、URN的區(qū)別

URI：用來唯一標識一個資源。由URL和URN組成。

URL：統(tǒng)一資源定位：通過描述資源的位置來標識資源

URN：通過名字來標識資源，與其位置沒有關(guān)系，及時資源的位置發(fā)生了變化URN也不會變化

請求報文格式（請求行、請求頭部、請求正文）

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-TPGBDTCi-1637763958112)(D:/%E6%9C%89%E9%81%93%E7%AC%94%E8%AE%B0/%E6%9C%89%E9%81%93%E6%96%87%E4%BB%B6/qqFD408D4C0254F01133B894C843A4BA78/3bcc5219fdc64197a7027c676ad4a85f/clipboard.png)]

請求行

請求方法：GET、HEAD、PUT、POST、TRACE、OPTIONS、DELETE

URL：通過描述資源的位置來標識資源。

協(xié)議版本：常見有1.0和1.1

常見的請求頭

請求頭部

請求頭部為請求報文添加了一些附加信息，由“名/值”組成，每行一對，名和值之間使用冒號分割

常見的請求頭

請求頭說明

Host	接受請求的服務(wù)器地址，可以是IP:端口號，也可以是域名
User-Agent	發(fā)送請求的應(yīng)用程序名稱
Connection	指定與連接相關(guān)的屬性，如Connection:Keep-Alive
Accept-Charset	通知服務(wù)端可以發(fā)送的編碼格式
Accept-Encoding	通知服務(wù)端可以發(fā)送的數(shù)據(jù)壓縮格式
Accept-Language	通知服務(wù)端可以發(fā)送的語言

請求頭部的最后會有一個空行，表示請求頭部結(jié)束，接下來為請求報文，這一行必不可少

請求正文

響應(yīng)報文格式

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-ppe4AVAq-1637763958113)(D:/%E6%9C%89%E9%81%93%E7%AC%94%E8%AE%B0/%E6%9C%89%E9%81%93%E6%96%87%E4%BB%B6/qqFD408D4C0254F01133B894C843A4BA78/e011fb9e44af4a808701792c293fb77c/clipboard.png)]

狀態(tài)行

協(xié)議版本

狀態(tài)碼：100 ~ 199信息狀態(tài)碼（1.1），200~299表示成功，300 ~ 399資源重定向， 400 ~ 499 表示客戶端請求出錯， 500 ~ 599表示服務(wù)端出錯。

常見狀態(tài)碼

狀態(tài)碼狀態(tài)說明

200	響應(yīng)成功
301	永久重定向，搜索引擎將刪除原地址，保留重定向地址
302	暫時重定向，重定向地址由響應(yīng)投中的Locaition屬性指定，由于搜索引擎的判定問題，較為復(fù)雜的URL容易被其他的網(wǎng)站使用更為精簡的URL及302重定向劫持
304	緩沖文件并未過期，還可以繼續(xù)使用，無需再次從服務(wù)端獲取
400	客戶端請求語法錯誤，不能被服務(wù)器識別
403	服務(wù)器收到了請求，但是拒絕提供服務(wù)
404	請求的資源不存在
500	服務(wù)器的內(nèi)部錯誤

響應(yīng)頭部

與請求頭部類似，為響應(yīng)報文添加了一些附加信息

響應(yīng)頭說明

Server	服務(wù)器應(yīng)用程序軟件的名稱和版本
Content-Type	響應(yīng)正文的類型（是圖片還是二進制字符串）
Content-Length	響應(yīng)正文長度
Content-Charset	響應(yīng)正文使用的編碼
Content-Encoding	響應(yīng)正文使用的數(shù)據(jù)壓縮格式
Content-Language	響應(yīng)正文使用的語言

六、請求方法

HTTP1.0中定義了三種請求方法：GET,POST,HEAD方法。

HTTP1.1中新加了五種請求方法：OPTIONS,PUT,DELETE,TRACE,CONNECT

常見的請求方法

序號方法描述

1	GET	請求指定的頁面信息，并返回實體主體
2	HEAD	類似于GET請求，只不過返回的響應(yīng)中沒有具體的內(nèi)容，用于獲取報頭
3	POST	向指定的資源提交數(shù)據(jù)進行處理請求。數(shù)據(jù)被包含在請求體中，POST請求可能會導(dǎo)致新資源的建立或已有資源的修改。
4	PUT	從客戶端向服務(wù)器傳送的數(shù)據(jù)取代指定的文檔內(nèi)容。
5	DELETE	請求服務(wù)器刪除指定的頁面。
6	CONNECT	HTTP/1.1協(xié)議中預(yù)留該能夠?qū)⑦B接改為管道方式的代理服務(wù)器
7	OPTIONS	允許客戶端查看服務(wù)器的性能
8	TRACE	回顯服務(wù)器收到的請求，主要用于測試或診斷

七、GET與POST比較

本質(zhì)區(qū)別：

get是從指定資源中獲取數(shù)據(jù)

post是向指定資源中提交將要被處理的數(shù)據(jù)

1、生成方式

get可以直接在URL地址欄中輸入URL，還可以網(wǎng)頁中的超鏈接生成

post只知道一種，就是將html中的form標簽的method屬性改為post

2、數(shù)據(jù)的傳輸方式

GET和POST只是HTTP協(xié)議中的兩種請求方式，而HTTP是基于TCP/IP的應(yīng)用層協(xié)議，所以用的都是同一個傳輸層的協(xié)議，所以在傳輸上沒有區(qū)別。

在報文格式上，不帶參數(shù)時最大的區(qū)別就是第一行方法名不同：POST方法請求報文第一行是這樣的POST/url HTTP/1.1 GET方法請求報文第一行是這樣的 GET/url HTTP/1.1

帶參數(shù)的區(qū)別是GET請求的數(shù)據(jù)會附加在URL之后，以**？**分割URL，多個參數(shù)使用&連接，URL的編碼格式采用的是ASCII編碼，也就是說所有的非ASCII字符都要編碼之后才可以傳輸，POST請求：POST請求會把請求的數(shù)據(jù)放置在HTTP請求包的包體中。所以說GET請求的數(shù)據(jù)會暴露在地址欄中，但是POST請求不會，所以POST相對于GET來說相對安全，但是如果是使用HTTP，那么他們都是不安全的，因為HTTP是明文傳輸，沒有對數(shù)據(jù)進行加密，也就是說POST請求的數(shù)據(jù)也是可見的，但是使用HTTPS，POST的數(shù)據(jù)就是安全的。

3、傳輸數(shù)據(jù)的大小

在HTTP規(guī)范中，沒有對URL的長度和傳輸?shù)臄?shù)據(jù)進行限制，但是在實際的開發(fā)中特定的瀏覽器和服務(wù)器對URL的長度是有限制的，所以在使用GET請求的時候傳輸?shù)臄?shù)據(jù)就會受URL的長度限制，一般是不超過2KB，但是對于POST來說，理論上來說并不會受到URL的限制，但是實際上各個服務(wù)器都會規(guī)定對POST提交的數(shù)據(jù)大小進行限制。

在實際開發(fā)中對URL的長度進行限制是因為對于服務(wù)器來說URL長了是一種負擔，如果一個沒有多少數(shù)據(jù)的會話，但是被人惡意的構(gòu)造了一個幾M大小的URL，并且不停的訪問服務(wù)器，那么服務(wù)器的并發(fā)數(shù)顯然就會下降。還有一種攻擊就是將Content-Length設(shè)置為一個很大的數(shù)，然后只給服務(wù)器發(fā)送很短的數(shù)據(jù)，這時候服務(wù)器就會進行等待，只有等待超時了服務(wù)器才可以繼續(xù)做其他的，這樣也會降低服務(wù)器的效率，所以要給URL的長度進行限制。

GET在瀏覽器回退時是無害的，POST會再次提交請求。。

GET請求只能進行url編碼，而POST支持多種編碼方式。

GET請求參數(shù)會被完整保留在瀏覽器歷史記錄里，而POST中的參數(shù)不會被保留。

GET只接受ASCII字符的參數(shù)的數(shù)據(jù)類型，而POST沒有限制

八、HTTP1.0和HTTP1.1的區(qū)別

主要有五個方面的區(qū)別：長連接、HOST域、寬帶優(yōu)化、消息傳遞、緩存

1、長連接

長連接指的是傳輸完成了保持TCP連接不斷開，等待在同域名下繼續(xù)用這個通道傳輸數(shù)據(jù)，反之就是短連接。

HTTP1.1支持長連接和請求的流水線處理，并且默認使用長連接，只有介入“connection：close”才斷開連接。

HTTP1.0默認使用短連接，規(guī)定客戶端和服務(wù)器只能保持短暫的連接，客戶端的每次請求都需要與到服務(wù)端建立一個TCP連接，服務(wù)器完成請求處理后立即斷開TCP連接，服務(wù)器不跟蹤客戶端也不記錄之前的請求。

如果HTTP1.0想要建立長連接，可以在請求消息中包含Connection：Keep-Alive頭域，如果服務(wù)器想要維持這條連接，在相應(yīng)的消息中也會包含一個Connection：Keep-Alive的頭域。

2、HOST域

HTTP1.1在Request消息頭里多了一個Host域，并且是必須傳的，HTTP1.0中沒有這個域。

在HTTP1.0中認為每個服務(wù)器都綁定唯一一個IP地址，所以在請求消息中的URL并沒有傳遞主機名。但隨著虛擬主機技術(shù)的發(fā)展，在一臺物理服務(wù)器上可以存在多個虛擬主機，并且他們共享一個IP地址。

HTTP1.1的請求小和響應(yīng)消息都應(yīng)支持Host頭域，且請求消息中如果沒有Host頭域匯報稿一個錯誤（狀態(tài)碼400），并且服務(wù)器應(yīng)該接受一絕對路徑標記的資源請求。

3、帶寬優(yōu)化

HTTP1.0中，存在一些浪費寬帶的現(xiàn)象 ，比如說客戶端只是需要某個對象的一部分資源，但是服務(wù)器將整個對象都傳送過來了。又比如下載大文件時不支持斷點續(xù)傳功能，所以在發(fā)生斷鏈后不得不重新下載完整的包。

HTTP1.1中在請求消息中引入了range頭域，它支持之請求資源的某個部分。他在響應(yīng)消息中Content-Range頭域聲明了返回的這部分對象的偏移值和長度。如果服務(wù)器相應(yīng)地反悔了對象所請求范圍的內(nèi)容，則響應(yīng)狀態(tài)碼為206，它可以防止Cache將響應(yīng)誤以為是完整的一個對象。

HTTP支持只發(fā)送header信息，如果服務(wù)器認為客戶端有權(quán)限請求服務(wù)器，則返回100，否則返回401，只有客戶端接收到了100，才開始把請求body發(fā)送到服務(wù)器。如果接收到401，客戶端就可以不用發(fā)送請求body了，這樣可以節(jié)約帶寬。

4、消息傳遞

HTTP消息中可以包含任意長度的尸體，通常他們使用Content-Length來給出消息結(jié)束的標志。但是對于很多動態(tài)產(chǎn)生的響應(yīng)，只能通過緩沖完整的消息來判斷消息的大小，但這樣會加大延遲。如果不適用長連接，還可以通過連接關(guān)閉的信號來判定一個消息的結(jié)束。

HTTP1.1zongoing引入了Chunke來解決上面的這個問題，發(fā)送方將消息分割成若干個任意大小的數(shù)據(jù)塊，每個數(shù)據(jù)塊在發(fā)送時都會附上塊的長度，最右用一個零長度的塊作為消息的結(jié)束標志。這種方法允許發(fā)送方只緩沖消息的一個片段，還可以避免緩沖整個消息帶來的過載。

在HTTP1.0中，有一個Content-MD5的頭域，要計算這個頭域需要發(fā)送方緩沖完整個消息后才能進行，這在HTTP1.1中，采用chunked分塊傳遞的消息在最后一個塊結(jié)束后會再傳遞一個拖尾，它包含一個或多個頭域，這些頭域是發(fā)送方在傳遞完所有塊之后在計算出的值。

5、緩存

HTTP1.0中使用Expire頭域來判斷資源是否是新資源，并使用條件請求來判斷資源是否仍然有效。

HTTP1.1在1.0的基礎(chǔ)上加入了一些新特性，當緩存對象的生命超過了周期編程stale的時候，不需要直接拋棄stale對象，而是與源服務(wù)器進行重新激活。

九、HTTP流水線技術(shù)

HTTP流水線技術(shù)指的是在一個TCP鏈接內(nèi)，多個HTTP請求可以并行，客戶端不用等待上一次請求的結(jié)果返回，就可以發(fā)出下一次的請求，但是服務(wù)器必須要按照接收到客戶端的請求的順序依次會送響應(yīng)的結(jié)果，以保證客戶端可以區(qū)分出每次請求響應(yīng)的內(nèi)容。使用HTTP流水線技術(shù)必須要求客戶端和服務(wù)端都要支持，目前有部分瀏覽器完全支持，而服務(wù)端的支持僅需要按照HTTP請求順序正確返回，也就是先來先服務(wù)模式，只要服務(wù)器能夠正確處理使用流水線技術(shù)的客戶端的請求，那么服務(wù)器就算是支持了HTTP流水線技術(shù)。

GET 用于獲取信息，是無副作用的，是冪等的，且可緩存 POST 用于修改服務(wù)器上的數(shù)據(jù)，有副作用，非冪等，不可緩存

十、HTTP無狀態(tài)問題

http是無狀態(tài)協(xié)議，無狀態(tài)也就是對于十五處理沒有記憶能力。缺少狀態(tài)意味著如果后續(xù)處理需要之前的信息。使用cookie和session來解決無狀態(tài)問題。

十一、cookie和session的區(qū)別

cookie

是客戶端技術(shù)，程序把每個用戶的數(shù)據(jù)以cookie的形式寫給用戶各自的瀏覽器。當用戶使用瀏覽器再去訪問服務(wù)器的時候，就會帶著各自的數(shù)據(jù)過去，這樣就服務(wù)器就知道當前是哪個用戶，并處理對應(yīng)的數(shù)據(jù)。會話cookie保存在瀏覽器的內(nèi)存中，瀏覽器關(guān)閉后cookie就消失了，持久化cookie是保存在本地的磁盤上，一般會有一定的過期時間。

session

是服務(wù)器技術(shù)，利用這個技術(shù)，服務(wù)器可以為每個用戶的瀏覽器創(chuàng)建一個獨立的session對象，并且每個session都有自己唯一對應(yīng)的ID，可以把各自的數(shù)據(jù)保存在自己的session中，這樣當用戶再去訪問服務(wù)器的時候，服務(wù)器就可以用當前用戶的session中取出數(shù)據(jù)為之服務(wù)。session都有過期時間，如果一段時間沒有更新數(shù)據(jù)庫，就會消失。

區(qū)別

1、cookie和session都是會話技術(shù)，cookie數(shù)據(jù)存放在客戶端，session的數(shù)據(jù)存放在服務(wù)器。

2、cookie不是很安全，可以對本地存放的cookie進行cookie欺騙，考慮到安全應(yīng)該使用session。

3、session會在一定的時間內(nèi)保存在服務(wù)器中，當訪問增多，會比較占用服務(wù)器性能，所有考慮到減輕服務(wù)器的負載，應(yīng)該使用cookie

4、登陸注冊等重要信息要存放在session中，其他的信息可以保存在cookie中

5、Cookie 只能保存ASCII字符串，如果是Unicode字符或者二進制數(shù)據(jù)需要先進行編碼。Session能夠存取很多類型的數(shù)據(jù)，包括String、Integer、List、Map等。

十九、怎么讓客戶端和服務(wù)端一直保持連接

通情況下tcp的連接是一直保持很長時間，但是有可能這個鏈接會一直空閑著，這樣會造成資源浪費，所以TCP就提供了保活機制和心跳報文

保活機制

也就是keepalive，在客戶端和服務(wù)端都可以設(shè)置，通常是服務(wù)端設(shè)置的。保活時長一般是2小時，如果這個tcp連接空閑了兩個小時，這個保活計時器超時，服務(wù)端會向客戶端發(fā)送一個探測報文，這時客戶端通常處于這么幾個狀態(tài)。

1、客戶端處于正常狀態(tài)，收到探測報文后發(fā)送了響應(yīng)報文，服務(wù)端知道客戶端是正常的，將保活計時器復(fù)位。

2、客戶端已經(jīng)崩潰，正在關(guān)機或者重啟，沒有響應(yīng)服務(wù)端的探測報文， 服務(wù)端由于沒有收到回復(fù)，會每個75秒發(fā)送一個探測報文，如果連續(xù)發(fā)送10探測報文都沒有響應(yīng)，就會認為客戶端掛了，會關(guān)閉TCP連接。

3、客戶端已經(jīng)重啟，并且正常運行了，但是在重啟之前關(guān)閉了tcp，這個客戶端收到探測報文，回應(yīng)一個RST，服務(wù)端收到這個報文將TCP連接關(guān)閉。

4、客戶端正常運行，但是接收不到服務(wù)端的報文，可以說是和情況2是一樣的，服務(wù)端并不能去放是網(wǎng)絡(luò)問題還是客戶端的問題，所以同樣會將連接關(guān)閉。

心跳報文

每隔一段時間向?qū)Χ税l(fā)送一個較小的數(shù)據(jù)包，通知對方自己在線，并傳送一些可能必要的數(shù)據(jù)包，并且定時檢測對端返回的數(shù)據(jù)，如果連續(xù)幾次沒有在規(guī)定的時間中收到回復(fù)，則判斷對端已經(jīng)掉線，然后做進一步處理，這個方法適合客戶端，在應(yīng)用層開一個線程發(fā)送心跳包，檢測對端情況。

總結(jié)

以上是生活随笔為你收集整理的C++校招常见面试题（2019年校招总结）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。