大家好，我是小林。

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

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

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

一、介紹一下webserver項目

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

二、select、poll、epoll的選擇

select缺點(diǎn)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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)指出，不允許一個對象（當(dāng)然包括類對象）的大小為0，不同的對象不能具有相同的地址；
3. 帶有虛函數(shù)的C++類大小不為1，因為每一個對象會有一個vptr指向虛函數(shù)表，具體大小根據(jù)指針大小確定；
4. C++中要求對于類的每個實例都必須有獨(dú)一無二的地址,那么編譯器自動為空類分配一個字節(jié)大小，這樣便保證了每個實例均有獨(dú)一無二的內(nèi)存地址。

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

空類的實例大小就是類的大小，所以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;
}

因為有虛函數(shù)的類對象中都有一個虛函數(shù)表指針 __vptr，其大小是4字節(jié)

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

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

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

4.只含有一個靜態(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)存儲區(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個字節(jié)

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

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

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

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

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

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

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

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

static

• 不考慮類的情況

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

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

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

• 考慮類的情況

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

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

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

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

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

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

const

• 不考慮類的情況

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

• 考慮類的情況

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

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

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

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

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

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

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