大家好，我是小林。

今天分享一位百度春招面經(jīng)，讀者的技術(shù)棧是C++。

這次的面經(jīng)，主要都是問(wèn)操作系統(tǒng)、網(wǎng)絡(luò)編程、C++ 這三大方向。

能明顯感覺(jué)到，C++面試和Java或者Go面試重點(diǎn)，Java/Go主要是問(wèn)MySQL、Redis。

一、介紹一下webserver項(xiàng)目

1. 服務(wù)器開(kāi)始運(yùn)行，創(chuàng)建（初始化）線程池（IO密集型，線程數(shù)n+1）；
2. 創(chuàng)建 epoll 對(duì)連接進(jìn)行監(jiān)聽(tīng)
3. 監(jiān)聽(tīng)到連接事件，調(diào)用線程池線程處理 http 請(qǐng)求
4. 讀取 http 請(qǐng)求并對(duì)其進(jìn)行解析 （空格，\r\n字段提?。?/li>
5. 返回解析結(jié)果

二、select、poll、epoll的選擇

select缺點(diǎn)：

1. select() 檢測(cè)數(shù)量有限制，最大值通常為 1024（bit），每一個(gè)比特位對(duì)應(yīng)一個(gè)監(jiān)聽(tīng)的文件描述符
2. fd_set被內(nèi)核修改后，不可以重用，每次都需要重置
3. 每次調(diào)用select，都需要把fd集合從用戶態(tài)拷貝到內(nèi)核態(tài)，這個(gè)開(kāi)銷在fd很多時(shí)會(huì)很大
4. 每次調(diào)用select都需要在內(nèi)核遍歷傳遞進(jìn)來(lái)的所有fd，這個(gè)開(kāi)銷在fd很多時(shí)也很大（((時(shí)間復(fù)雜度是O(n)))）

poll缺點(diǎn)：select第三四條缺點(diǎn)沒(méi)有解決

1. 每次調(diào)用select，都需要把**fd集合從用戶態(tài)拷貝到內(nèi)核態(tài)，這個(gè)開(kāi)銷在fd很多時(shí)會(huì)很大
2. 每次調(diào)用select都需要在內(nèi)核遍歷傳遞進(jìn)來(lái)的所有fd，這個(gè)開(kāi)銷在fd很多時(shí)也很大（((時(shí)間復(fù)雜度是O(n)))）

epoll優(yōu)點(diǎn)：epoll底層數(shù)據(jù)結(jié)構(gòu)

• 紅黑樹增刪改綜合效率高
• 就緒的描述符的鏈表。當(dāng)有的連接就緒的時(shí)候，內(nèi)核會(huì)把就緒的連接放到 rdllist 鏈表里。這樣應(yīng)用進(jìn)程只需要判斷鏈表就能找出就緒進(jìn)程，而不用去遍歷整棵樹。

三、線程和進(jìn)程的區(qū)別？使用線程的心得？

1. 進(jìn)程是資源（包括內(nèi)存、打開(kāi)的文件等）分配的單位，線程是 CPU 調(diào)度的單位；
2. （關(guān)鍵詞：進(jìn)程獨(dú)立空間、線程之前共享空間資源）進(jìn)程擁有一個(gè)獨(dú)立完整的資源平臺(tái)，不和其他進(jìn)程共享；而線程只獨(dú)享必不可少的資源，如寄存器和棧，而一個(gè)進(jìn)程里可以有多個(gè)線程，彼此共享同一個(gè)地址空間。
3. 線程同樣具有就緒、阻塞、執(zhí)行三種基本狀態(tài)，同樣具有狀態(tài)之間的轉(zhuǎn)換關(guān)系；
4. 線程能減少并發(fā)執(zhí)行的時(shí)間和空間開(kāi)銷

對(duì)于，線程相比進(jìn)程能減少開(kāi)銷，體現(xiàn)在：

• （1. 創(chuàng)建時(shí)間少）線程的創(chuàng)建時(shí)間比進(jìn)程快，因?yàn)檫M(jìn)程在創(chuàng)建的過(guò)程中，還需要資源管理信息，比如內(nèi)存、文件管理信息切換虛擬地址空間，切換內(nèi)核棧和硬件上下文，頁(yè)表切換開(kāi)銷很大，而線程在創(chuàng)建的過(guò)程中，不會(huì)涉及這些信息，而是共享它們，只需保存和設(shè)置少量寄存器內(nèi)容，因此開(kāi)銷很??；
• （2. 終止時(shí)間少）線程的終止時(shí)間比進(jìn)程快，因?yàn)榫€程釋放的資源相比進(jìn)程少很多；
• （3. 不需要切換頁(yè)表，切換時(shí)間塊）同一個(gè)進(jìn)程內(nèi)的線程切換比進(jìn)程切換快，因?yàn)榫€程具有相同的地址空間（虛擬內(nèi)存共享），這意味著同一個(gè)進(jìn)程的線程都具有同一個(gè)頁(yè)表，那么在切換的時(shí)候不需要切換頁(yè)表。而對(duì)于進(jìn)程之間的切換，切換的時(shí)候要把頁(yè)表給切換掉，而頁(yè)表的切換過(guò)程開(kāi)銷是比較大的；
• （4. 共享、線程之間數(shù)據(jù)傳遞效率高）由于同一進(jìn)程的各線程間共享內(nèi)存和文件資源，那么在線程之間數(shù)據(jù)傳遞的時(shí)候，就不需要經(jīng)過(guò)內(nèi)核了，這就使得線程之間的數(shù)據(jù)交互效率更高了；

所以，不管是時(shí)間效率，還是空間效率線程比進(jìn)程都要高

心得：線程使用有一定難度，需要處理數(shù)據(jù)一致性問(wèn)題，比如要使用互斥鎖和條件變量等同步機(jī)制保證線程安全（原子性操作）

四、C++ 空類的大?。恳粋€(gè)只包含int 變量的空class和只包含int變量的空struct的內(nèi)存各占多大？

關(guān)鍵詞：空類和空結(jié)構(gòu)體都大小為1，這樣可以確保兩個(gè)不同的對(duì)象，擁有不同的地址。

1.空類

class A {};
int main(){
  cout<<sizeof(A)<<endl;// 輸出 1;
  A a; 
  cout<<sizeof(a)<<endl;// 輸出 1;
  return 0;
}

1. C++空類的大小不為0，不同編譯器設(shè)置不一樣，vs和lg++都是設(shè)置為1；
2. C++標(biāo)準(zhǔn)指出，不允許一個(gè)對(duì)象（當(dāng)然包括類對(duì)象）的大小為0，不同的對(duì)象不能具有相同的地址；
3. 帶有虛函數(shù)的C++類大小不為1，因?yàn)槊恳粋€(gè)對(duì)象會(huì)有一個(gè)vptr指向虛函數(shù)表，具體大小根據(jù)指針大小確定；
4. C++中要求對(duì)于類的每個(gè)實(shí)例都必須有獨(dú)一無(wú)二的地址,那么編譯器自動(dòng)為空類分配一個(gè)字節(jié)大小，這樣便保證了每個(gè)實(shí)例均有獨(dú)一無(wú)二的內(nèi)存地址。

在C++中空類會(huì)占一個(gè)字節(jié)，這是為了讓對(duì)象的實(shí)例能夠相互區(qū)別。具體來(lái)說(shuō)，空類同樣可以被實(shí)例化，并且每個(gè)實(shí)例在內(nèi)存中都有獨(dú)一無(wú)二的地址，因此，編譯器會(huì)給空類隱含加上一個(gè)字節(jié)，這樣空類實(shí)例化之后就會(huì)擁有獨(dú)一無(wú)二的內(nèi)存地址。當(dāng)該空白類作為基類時(shí)，該類的大小就優(yōu)化為0了，子類的大小就是子類本身的大小。這就是所謂的空白基類最優(yōu)化。

空類的實(shí)例大小就是類的大小，所以sizeof(a)=1字節(jié)**,如果a是指針，則sizeof(a)就是指針的大小，即4字節(jié)。**

2.含有虛函數(shù)的類的大小

class A { virtual Fun(){} };
int main(){
  cout<<sizeof(A)<<endl;// 輸出 4(32位機(jī)器)/8(64位機(jī)器);
  A a; 
  cout<<sizeof(a)<<endl;// 輸出 4(32位機(jī)器)/8(64位機(jī)器);
  return 0;
}

因?yàn)橛刑摵瘮?shù)的類對(duì)象中都有一個(gè)虛函數(shù)表指針 __vptr，其大小是4字節(jié)

3.只含有一個(gè)int成員變量的類的大?。?）

class A { int a; };
int main(){
  cout<<sizeof(A)<<endl;// 輸出 4;
  A a; 
  cout<<sizeof(a)<<endl;// 輸出 4;
  return 0;
}

只是一個(gè)int變量的大小——4字節(jié)

4.只含有一個(gè)靜態(tài)成員變量的類的大?。?）

class A { static int a; };
int main(){
  cout<<sizeof(A)<<endl;// 輸出 1;
  A a; 
  cout<<sizeof(a)<<endl;// 輸出 1;
  return 0;
}

靜態(tài)成員存放在靜態(tài)存儲(chǔ)區(qū)，不占用類的大小, 普通函數(shù)也不占用類大小

class A { static int a; int b; };;
int main(){
  cout<<sizeof(A)<<endl;// 輸出 4;
  A a; 
  cout<<sizeof(a)<<endl;// 輸出 4;
  return 0;
}

靜態(tài)成員a不占用類的大小，所以類的大小就是b變量的大小 即4個(gè)字節(jié)

五、為什么一般構(gòu)造函數(shù)定義為虛函數(shù)？析構(gòu)函數(shù)不定義為虛函數(shù)？

為什么析構(gòu)函數(shù)一般寫為虛函數(shù)？

如果析構(gòu)函數(shù)不被聲明成虛函數(shù)，則編譯器實(shí)施靜態(tài)綁定，在刪除基類指針時(shí)，只會(huì)調(diào)用基類的析構(gòu)函數(shù)而不調(diào)用派生類析構(gòu)函數(shù)，這樣就會(huì)造成派生類對(duì)象析構(gòu)不完全，造成內(nèi)存泄漏。

所以在實(shí)現(xiàn)多態(tài)時(shí)，當(dāng)用基類操作派生類，在析構(gòu)時(shí)防止只析構(gòu)基類而不析構(gòu)派生類的狀況發(fā)生，要將基類的析構(gòu)函數(shù)聲明為虛函數(shù)。

為什么構(gòu)造函數(shù)不寫為虛函數(shù)？

從存儲(chǔ)空間角度：虛函數(shù)對(duì)應(yīng)一個(gè)vtable，可是這個(gè)vtable其實(shí)是存儲(chǔ)在對(duì)象的內(nèi)存空間的。問(wèn)題出來(lái)了，如果構(gòu)造函數(shù)是虛的，就需要通過(guò) vtable來(lái)調(diào)用，可是對(duì)象還沒(méi)有實(shí)例化，也就是內(nèi)存空間還沒(méi)有，無(wú)法找到vtable，所以構(gòu)造函數(shù)不能是虛函數(shù)。

從使用角度：虛函數(shù)的作用在于通過(guò)父類的指針或者引用來(lái)調(diào)用它的時(shí)候能夠變成調(diào)用子類的那個(gè)成員函數(shù)。而構(gòu)造函數(shù)是在創(chuàng)建對(duì)象時(shí)自動(dòng)調(diào)用的，不可能通過(guò)父類的指針或者引用去調(diào)用，因此也就規(guī)定構(gòu)造函數(shù)不能是虛函數(shù)。

六、static的作用（作用域限制）

static

• 不考慮類的情況

?有時(shí)候希望某些全局變量或者函數(shù)只在本文件中被使用，而不能被其他外部文件引用，這個(gè)時(shí)候可以在全局變量前加一個(gè)static說(shuō)明，這樣不同的人編寫不同的變量或者函數(shù)時(shí)不用擔(dān)心重名的問(wèn)題，即使重名了也互不干擾

默認(rèn)初始化為0，包括未初始化的全局靜態(tài)變量與局部靜態(tài)變量，都存在全局未初始化區(qū)

靜態(tài)變量在函數(shù)內(nèi)定義，始終存在，且只進(jìn)行一次初始化，具有記憶性，其作用范圍與局部變量相同，函數(shù)退出后仍然存在，但不能使用?

• 考慮類的情況

• static成員變量：只與類關(guān)聯(lián)，不與類的對(duì)象關(guān)聯(lián)。定義時(shí)要分配空間，不能在類聲明中初始化，必須在類定義體外部初始化，初始化時(shí)不需要標(biāo)示為static；可以被非static成員函數(shù)任意訪問(wèn)。

• static成員函數(shù)：不具有this指針，無(wú)法訪問(wèn)類對(duì)象的非static成員變量和非static成員函數(shù)；不能被聲明為const、虛函數(shù)和volatile；可以被非static成員函數(shù)任意訪問(wèn)

靜態(tài)局部變量：

1. 靜態(tài)局部變量屬于靜態(tài)存儲(chǔ)類別，在靜態(tài)存儲(chǔ)區(qū)內(nèi)分配存儲(chǔ)單元，在整個(gè)程序運(yùn)行期間始終存在。
2. 靜態(tài)局部變量只初始化一次，并且之后再次調(diào)用函數(shù)時(shí)不再重新分配空間和賦初值，而保留上次函數(shù)調(diào)用結(jié)束時(shí)的值（而普通局部變量每調(diào)用一次就會(huì)重新分配空間并賦一次初值）
3. 靜態(tài)局部變量默認(rèn)初始化為0
4. 函數(shù)調(diào)用結(jié)束之后靜態(tài)局部變量依然存在，但是只能在該函數(shù)內(nèi)進(jìn)行使用該靜態(tài)局部變量，

extern的作用（作用域擴(kuò)展）

1. 將全局變量的作用域擴(kuò)展到其定義之前：如果全局變量不在文件的開(kāi)頭定義，其作用范圍只限定于從定義處到文件結(jié)尾，如果在定義點(diǎn)之前的函數(shù)想引用該變量，就應(yīng)該在引用之前使用extern關(guān)鍵字對(duì)該變量進(jìn)行聲明，之后該全局變量的作用域就從聲明處一直到文件結(jié)尾了
2. 將某一個(gè)源文件中全局變量的作用域擴(kuò)展到其他源文件中：一個(gè)C++項(xiàng)目很多情況是由多個(gè)源文件構(gòu)成，如果在一個(gè)文件中想引用另一個(gè)文件中已定義的全局變量，比如現(xiàn)在兩個(gè)文件都要使用到同一個(gè)全局變量int a，正確的做法應(yīng)該是：在一個(gè)文件中定義變量a，而在另一個(gè)文件中使用extern int a；對(duì)該變量進(jìn)行聲明，這樣就可以兩個(gè)文件同時(shí)使用同一個(gè)變量了

const

• 不考慮類的情況

• const常量在定義時(shí)必須初始化，之后無(wú)法更改
• const形參可以接收const和非const類型的實(shí)參，例如// i 可以是 int 型或者 const int 型void fun(const int& i){ //...}

• 考慮類的情況

• const成員變量：不能在類定義外部初始化，只能通過(guò)構(gòu)造函數(shù)初始化列表進(jìn)行初始化，并且必須有構(gòu)造函數(shù)；不同類對(duì)其const數(shù)據(jù)成員的值可以不同，所以不能在類中聲明時(shí)初始化。

• const成員函數(shù)：const對(duì)象不可以調(diào)用非const成員函數(shù)；非const對(duì)象都可以調(diào)用；不可以改變非mutable（用該關(guān)鍵字聲明的變量可以在const成員函數(shù)中被修改）數(shù)據(jù)的值。

七、C++ sort()函數(shù)實(shí)現(xiàn)

sort()源碼中采用的是一種叫做IntroSort內(nèi)省式排序的混合式排序算法，

1.首先進(jìn)行判斷排序的元素個(gè)數(shù)是否大于stl_threshold，stl_threshold是一個(gè)常量值是16，意思就是說(shuō)我傳入的元素規(guī)模小于我們的16的時(shí)候直接采用插入排序。（為什么用插入排序？因?yàn)椴迦肱判蛟诿鎸?duì)“幾近排序”的序列時(shí)，表現(xiàn)更好，而快排是通過(guò)遞歸實(shí)現(xiàn)的，會(huì)為了極小的子序列產(chǎn)生很多的遞歸調(diào)用在區(qū)間長(zhǎng)度小的時(shí)候經(jīng)常不如插入排序效率高）

2.如果說(shuō)我們的元素規(guī)模大于16，那就需要去判斷如果是不是能采用快速排序，怎么判斷呢？快排是使用遞歸來(lái)實(shí)現(xiàn)的，如果說(shuō)我們進(jìn)行判斷我們的遞歸深度有沒(méi)有到達(dá)遞歸深度的限制閾值2*lg（n），如果遞歸深度沒(méi)達(dá)到閾值就使用快速排序來(lái)進(jìn)行排序

3.如果說(shuō)大于我們的最深遞歸深度閾值的話，這個(gè)時(shí)候說(shuō)明快排復(fù)雜度退化了（比如很不巧基準(zhǔn)元素多次選取到了當(dāng)前區(qū)間中最小或最大的元素。這種情況下，每次劃分只能將區(qū)間縮小1個(gè)元素，造成遞歸深度過(guò)深），就會(huì)采用我們的堆排序，堆排序是可以保證穩(wěn)定O(nlogn)的時(shí)間復(fù)雜度的。