大家好，我是小林。

今天分享一位百度春招面經，讀者的技術棧是C++。

這次的面經，主要都是問操作系統、網絡編程、C++ 這三大方向。

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

一、介紹一下webserver項目

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

二、select、poll、epoll的選擇

select缺點：

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

poll缺點：select第三四條缺點沒有解決

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

epoll優點：epoll底層數據結構

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

三、線程和進程的區別？使用線程的心得？

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

對于，線程相比進程能減少開銷，體現在：

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

所以，不管是時間效率，還是空間效率線程比進程都要高

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

四、C++ 空類的大小？一個只包含int 變量的空class和只包含int變量的空struct的內存各占多大？

關鍵詞：空類和空結構體都大小為1，這樣可以確保兩個不同的對象，擁有不同的地址。

1.空類

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

1. C++空類的大小不為0，不同編譯器設置不一樣，vs和lg++都是設置為1；
2. C++標準指出，不允許一個對象（當然包括類對象）的大小為0，不同的對象不能具有相同的地址；
3. 帶有虛函數的C++類大小不為1，因為每一個對象會有一個vptr指向虛函數表，具體大小根據指針大小確定；
4. C++中要求對于類的每個實例都必須有獨一無二的地址,那么編譯器自動為空類分配一個字節大小，這樣便保證了每個實例均有獨一無二的內存地址。

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

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

2.含有虛函數的類的大小

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

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

3.只含有一個int成員變量的類的大小（4）

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

只是一個int變量的大小——4字節

4.只含有一個靜態成員變量的類的大小（1）

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

靜態成員存放在靜態存儲區，不占用類的大小, 普通函數也不占用類大小

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

靜態成員a不占用類的大小，所以類的大小就是b變量的大小 即4個字節

五、為什么一般構造函數定義為虛函數？析構函數不定義為虛函數？

為什么析構函數一般寫為虛函數？

如果析構函數不被聲明成虛函數，則編譯器實施靜態綁定，在刪除基類指針時，只會調用基類的析構函數而不調用派生類析構函數，這樣就會造成派生類對象析構不完全，造成內存泄漏。

所以在實現多態時，當用基類操作派生類，在析構時防止只析構基類而不析構派生類的狀況發生，要將基類的析構函數聲明為虛函數。

為什么構造函數不寫為虛函數？

從存儲空間角度：虛函數對應一個vtable，可是這個vtable其實是存儲在對象的內存空間的。問題出來了，如果構造函數是虛的，就需要通過 vtable來調用，可是對象還沒有實例化，也就是內存空間還沒有，無法找到vtable，所以構造函數不能是虛函數。

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

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

static

• 不考慮類的情況

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

默認初始化為0，包括未初始化的全局靜態變量與局部靜態變量，都存在全局未初始化區

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

• 考慮類的情況

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

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

靜態局部變量：

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

extern的作用（作用域擴展）

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

const

• 不考慮類的情況

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

• 考慮類的情況

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

• const成員函數：const對象不可以調用非const成員函數；非const對象都可以調用；不可以改變非mutable（用該關鍵字聲明的變量可以在const成員函數中被修改）數據的值。

七、C++ sort()函數實現

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

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

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

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