1、寫出完整版的strcpy函數

char * strcpy( char *strDest, const char *strSrc ) 
{
 assert( (strDest != NULL) && (strSrc != NULL) );
 char *address = strDest; 
 while( (*strDest++ = * strSrc++) != ‘\0’ ); 
 return address;
}

要點：

使用assert斷言函數，判斷參數是否為NULL；

遇'\0'則停止賦值；

返回新的字符串的首地址。

2、指出代碼錯誤

void Test( void )
{
 char *str = (char *) malloc( 100 );
 strcpy( str, "hello" );
 free( str ); 
 ... //省略的其它語句
}

錯誤有二：

使用malloc分配內存后，應判斷是否分配成功；

free之后，應置str為NULL，防止變成野指針。

PS：malloc函數

malloc函數是一種分配長度為num_bytes字節(jié)的內存塊的函數，可以向系統申請分配指定size個字節(jié)的內存空間。malloc的全稱是memory allocation，中文叫動態(tài)內存分配，當無法知道內存具體位置的時候，想要綁定真正的內存空間，就需要用到動態(tài)的分配內存。

第一、malloc 函數返回的是 void * 類型。

對于C++，如果你寫成：p = malloc (sizeof(int)); 則程序無法通過編譯，報錯：“不能將 void* 賦值給 int * 類型變量”。

所以必須通過 (int *) 來將強制轉換。而對于C，沒有這個要求，但為了使C程序更方便的移植到C++中來，建議養(yǎng)成強制轉換的習慣。

第二、函數的實參為 sizeof(int) ，用于指明一個整型數據需要的大小。

在Linux中可以有這樣：malloc(0),這是因為Linux中malloc有一個下限值16Bytes，注意malloc(-1)是禁止的；但是在某些系統中是不允許malloc(0)的。

malloc 只管分配內存，并不能對所得的內存進行初始化，所以得到的一片新內存中，其值將是隨機的。

3、分別給出BOOL，int，float，指針變量 與“零值”比較的 if 語句

BOOL型變量：if(!var)  

int型變量： if(var==0)  

float型變量：  

const float EPSINON = 0.00001;  

if ((x >= - EPSINON) && (x <= EPSINON)  

指針變量：if(var==NULL)  

4、以下為Windows NT下的32位C++程序，請計算sizeof的值

void Func ( char str[100] )
{
 sizeof( str ) = ?
}
void *p = malloc( 100 );
sizeof ( p ) = ?
sizeof( str ) = 4   
sizeof ( p ) = 4   

Func ( char str[100] )函數中數組名作為函數形參時，在函數體內，數組名失去了本身的內涵，僅僅只是一個指針；在失去其內涵的同時，它還失去了其常量特性，可以作自增、自減等操作，可以被修改。

但是數組名在不作形參時，仍然代表整個數組，這時的sizeof應返回數組長度。

sizeof返回的單位是字節(jié)。對于結構體，sizeof返回可能會有字節(jié)填充。結構體的總大小為結構體最寬基本類型成員大小的整數倍。

5、寫一個“標準”宏MIN，這個宏輸入兩個參數并返回較小的一個。另外，當你寫下面的代碼時會發(fā)生什么事？  

least = MIN(*p++, b); 

答案：

#define MIN(A,B) ((A) <= (B) ? (A) : (B))

四個注意點：

宏定義中，左側為宏名和參數，右側為宏的實現；

在宏的實現中，所有參數應用括號括起來；

整個宏的實現的外面也要用括號括起來；

最后沒有分號。

寫下如上代碼會導致p自增兩次。

6、ifndef、extern的用法

條件指示符#ifndef 的最主要目的是防止頭文件的重復包含和編譯。

extern修飾變量的聲明。

如果文件a.c需要引用b.c中變量int v，就可以在a.c中聲明extern int v，然后就可以引用變量v。

這里需要注意的是，被引用的變量v的鏈接屬性必須是外鏈接（external）的，也就是說a.c要引用到v，不只是取決于在a.c中聲明extern int v，還取決于變量v本身是能夠被引用到的。

7、請說出static和const關鍵字盡可能多的作用

static:

1. 修飾普通變量，修改變量的存儲區(qū)域和生命周期，使變量存儲在靜態(tài)區(qū)，在main函數運行前就分配了空間，如果有初始值就用初始值初始化它，如果沒有初始值系統用默認值初始化它。在每次調用時，其值為上一次調用后改變的值，調用結束后不釋放空間。此變量只在聲明變量的文件內可見。

2. 修飾普通函數，表明函數的作用范圍，僅在定義該函數的文件內才能使用。在多人開發(fā)項目時，為了防止與他人命令函數重名，可以將函數定義為static。

3. 修飾成員變量，修飾成員變量使所有的對象只保存一個該變量，而且不需要生成對象就可以訪問該成員。

4. 修飾成員函數，修飾成員函數使得不需要生成對象就可以訪問該函數，但是在static函數內不能訪問非靜態(tài)成員。

const:

1. 修飾變量，說明該變量不可以被改變；

2. 修飾指針，分為指向常量的指針和指針常量；

3. 常量引用，經常用于形參類型，即避免了拷貝，又避免了函數對值的修改；

4. 修飾成員函數，說明該成員函數內不能修改成員變量。

8、請說一下C/C++ 中指針和引用的區(qū)別？

1.指針有自己的一塊空間，而引用只是一個別名；

2.使用sizeof看一個指針的大小是4，而引用則是被引用對象的大?。?/p>

3.指針可以被初始化為NULL，而引用必須被初始化且必須是一個已有對象 的引用；

4.作為參數傳遞時，指針需要被解引用才可以對對象進行操作，而直接對引用的修改都會改變引用所指向的對象；

5.可以有const指針，但是沒有const引用；

6.指針在使用中可以指向其它對象，但是引用只能是一個對象的引用，不能被改變；

7.指針可以有多級指針（**p），而引用只有一級；

8.指針和引用使用++運算符的意義不一樣；

9.如果返回動態(tài)內存分配的對象或者內存，必須使用指針，引用可能引起內存泄露。

9、給定三角形ABC和一點P(x,y,z)，判斷點P是否在ABC內，給出思路并手寫代碼

根據面積法，如果P在三角形ABC內，那么三角形ABP的面積+三角形BCP的面積+三角形ACP的面積應該等于三角形ABC的面積。

10、野指針是什么？

野指針就是指向一個已刪除的對象或者未申請訪問受限內存區(qū)域的指針。

11、為什么析構函數必須是虛函數？為什么C++默認的析構函數不是虛函數？

將可能會被繼承的父類的析構函數設置為虛函數，可以保證當我們new一個子類，然后使用基類指針指向該子類對象，釋放基類指針時可以釋放掉子類的空間，防止內存泄漏。

C++默認的析構函數不是虛函數是因為虛函數需要額外的虛函數表和虛表指針，占用額外的內存。而對于不會被繼承的類來說，其析構函數如果是虛函數，就會浪費內存。因此C++默認的析構函數不是虛函數，而是只有當需要當作父類時，設置為虛函數。

PS：C++類的六個默認成員函數：

• 構造函數：一個特殊的成員函數，名字與類名相同，創(chuàng)建類類型對象的時候，由編譯器自動調用，在對象的生命周期內只且調用一次，以保證每個數據成員都有一個合適的初始值。
• 拷貝構造函數：只有單個形參，而且該形參是對本類類型對象的引用（常用const修飾），這樣的構造函數稱為拷貝構造函數?？截悩嬙旌瘮凳翘厥獾臉嬙旌瘮?，創(chuàng)建對象時使用已存在的同類對象來進行初始化，由編譯器自動調用。
• 析構函數：與構造函數功能相反，在對象被銷毀時，由編譯器自動調用，完成類的一些資源清理和收尾工作。
• 賦值運算符重載：對于類類型的對象我們需要對‘=’重載，以完成類類型對象之間的賦值。
• 取址操作符重載：函數返回值為該類型的指針，無參數。
• const修飾的取址運算符重載。
   

12、C++中析構函數的作用？

析構函數與構造函數對應，當對象結束其生命周期，如對象所在的函數已調用完畢時，系統會自動執(zhí)行析構函數。

析構函數名也應與類名相同，只是在函數名前面加一個位取反符~，例如~stud( )，以區(qū)別于構造函數。它不能帶任何參數，也沒有返回值（包括void類型）。只能有一個析構函數，不能重載。

如果用戶沒有編寫析構函數，編譯系統會自動生成一個缺省的析構函數（即使自定義了析構函數，編譯器也總是會為我們合成一個析構函數，并且如果自定義了析構函數，編譯器在執(zhí)行時會先調用自定義的析構函數再調用合成的析構函數），它也不進行任何操作。所以許多簡單的類中沒有用顯式的析構函數。

如果一個類中有指針，且在使用的過程中動態(tài)的申請了內存，那么最好顯示構造析構函數在銷毀類之前，釋放掉申請的內存空間，避免內存泄漏。

類析構順序：1）派生類本身的析構函數；2）對象成員析構函數；3）基類析構函數。

13、map和set有什么區(qū)別，分別又是怎么實現的？

map和set都是C++的關聯容器，其底層實現都是紅黑樹（RB-Tree）。由于 map 和set所開放的各種操作接口，RB-tree 也都提供了，所以幾乎所有的 map 和set的操作行為，都只是轉調 RB-tree 的操作行為。

map和set區(qū)別在于：

（1）map中的元素是key-value（關鍵字—值）對：關鍵字起到索引的作用，值則表示與索引相關聯的數據；Set與之相對就是關鍵字的簡單集合，set中每個元素只包含一個關鍵字。

（2）set的迭代器是const的，不允許修改元素的值；map允許修改value，但不允許修改key。其原因是因為map和set是根據關鍵字排序來保證其有序性的，如果允許修改key的話，那么首先需要刪除該鍵，然后調節(jié)平衡，再插入修改后的鍵值，調節(jié)平衡，如此一來，嚴重破壞了map和set的結構，導致iterator失效，不知道應該指向改變前的位置，還是指向改變后的位置。所以STL中將set的迭代器設置成const，不允許修改迭代器的值；而map的迭代器則不允許修改key值，允許修改value值。

（3）map支持下標操作，set不支持下標操作。map可以用key做下標，map的下標運算符[ ]將關鍵碼作為下標去執(zhí)行查找，如果關鍵碼不存在，則插入一個具有該關鍵碼和mapped_type類型默認值的元素至map中，因此下標運算符[ ]在map應用中需要慎用，const_map不能用，只希望確定某一個關鍵值是否存在而不希望插入元素時也不應該使用，mapped_type類型沒有默認值也不應該使用。如果find能解決需要，盡可能用find。

14、C++中類成員的訪問權限有哪些？

C++通過 public、protected、private 三個關鍵字來控制成員變量和成員函數的訪問權限，它們分別表示公有的、受保護的、私有的，被稱為成員訪問限定符。在類的內部（定義類的代碼內部），無論成員被聲明為 public、protected 還是 private，都是可以互相訪問的，沒有訪問權限的限制。在類的外部（定義類的代碼之外），只能通過對象訪問成員，并且通過對象只能訪問 public 屬性的成員，不能訪問 private、protected 屬性的成員。

private和protected的區(qū)別是，子類的對象也可以訪問private，但只有本類的對象可以訪問protected。

15、C++中struct和class的區(qū)別？

在C++中，可以用struct和class定義類，都可以繼承。區(qū)別在于：struct的默認繼承權限和默認訪問權限是public，而class的默認繼承權限和默認訪問權限是private。

16、一個C++源文件從文本到可執(zhí)行文件經歷的過程？

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

• 預處理階段：對源代碼文件中文件包含關系（頭文件）、預編譯語句（宏定義）進行分析和替換，生成預編譯文件。
• 編譯階段：將經過預處理后的預編譯文件轉換成特定匯編代碼，生成匯編文件
• 匯編階段：將編譯階段生成的匯編文件轉化成機器碼，生成可重定位目標文件

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

17、include頭文件的順序以及雙引號””和尖括號<>的區(qū)別？

Include頭文件的順序：對于include的頭文件來說，如果在文件a.h中聲明一個在文件b.h中定義的變量，而不引用b.h。那么要在a.c文件中引用b.h文件，并且要先引用b.h，后引用a.h,否則匯報變量類型未聲明錯誤。

雙引號和尖括號的區(qū)別：編譯器預處理階段查找頭文件的路徑不一樣。

對于使用雙引號包含的頭文件，查找頭文件路徑的順序為：

當前頭文件目錄

編譯器設置的頭文件路徑（編譯器可使用-I顯式指定搜索路徑）

系統變量CPLUS_INCLUDE_PATH/C_INCLUDE_PATH指定的頭文件路徑

對于使用尖括號包含的頭文件，查找頭文件的路徑順序為：

編譯器設置的頭文件路徑（編譯器可使用-I顯式指定搜索路徑）

系統變量CPLUS_INCLUDE_PATH/C_INCLUDE_PATH指定的頭文件路徑

18、malloc的原理，另外brk系統調用和mmap系統調用的作用分別是什么？

Malloc函數用于動態(tài)分配內存。為了減少內存碎片和系統調用的開銷，malloc其采用內存池的方式，先申請大塊內存作為堆區(qū)，然后將堆區(qū)分為多個內存塊，以塊作為內存管理的基本單位。當用戶申請內存時，直接從堆區(qū)分配一塊合適的空閑塊。Malloc采用隱式鏈表結構將堆區(qū)分成連續(xù)的、大小不一的塊，包含已分配塊和未分配塊；同時malloc采用顯示鏈表結構來管理所有的空閑塊，即使用一個雙向鏈表將空閑塊連接起來，每一個空閑塊記錄了一個連續(xù)的、未分配的地址。

當進行內存分配時，Malloc會通過隱式鏈表遍歷所有的空閑塊，選擇滿足要求的塊進行分配；當進行內存合并時，malloc采用邊界標記法，根據每個塊的前后塊是否已經分配來決定是否進行塊合并。

Malloc在申請內存時，一般會通過brk或者mmap系統調用進行申請。其中當申請內存小于128K時，會使用系統函數brk在堆區(qū)中分配；而當申請內存大于128K時，會使用系統函數mmap在映射區(qū)分配。

19、C++的內存管理是怎樣的？

在C++中，虛擬內存分為代碼段、數據段、BSS段、堆區(qū)、文件映射區(qū)以及棧區(qū)六部分。

代碼段:包括只讀存儲區(qū)和文本區(qū)，其中只讀存儲區(qū)存儲字符串常量，文本區(qū)存儲程序的機器代碼。

數據段：存儲程序中已初始化的全局變量和靜態(tài)變量

bss 段：存儲未初始化的全局變量和靜態(tài)變量（局部+全局），以及所有被初始化為0的全局變量和靜態(tài)變量。

堆區(qū)：調用new/malloc函數時在堆區(qū)動態(tài)分配內存，同時需要調用delete/free來手動釋放申請的內存。

映射區(qū):存儲動態(tài)鏈接庫以及調用mmap函數進行的文件映射

棧區(qū)：使用?？臻g存儲函數的返回地址、參數、局部變量、返回值

20、如何判斷內存泄漏？

內存泄漏通常是由于調用了malloc/new等內存申請的操作，但是缺少了對應的free/delete。為了判斷內存是否泄露，我們一方面可以使用linux環(huán)境下的內存泄漏檢查工具Valgrind,另一方面我們在寫代碼時可以添加內存申請和釋放的統計功能，統計當前申請和釋放的內存是否一致，以此來判斷內存是否泄露。

21、什么時候會發(fā)生段錯誤？

段錯誤通常發(fā)生在訪問非法內存地址的時候，具體來說分為以下幾種情況：

使用野指針

試圖修改字符串常量的內容

22、new和malloc的區(qū)別？

1、new分配內存按照數據類型進行分配，malloc分配內存按照指定的大小分配；

2、new返回的是指定對象的指針，而malloc返回的是void*，因此malloc的返回值一般都需要進行類型轉化。

3、new不僅分配一段內存，而且會調用構造函數，malloc不會。

4、new分配的內存要用delete銷毀，malloc要用free來銷毀；delete銷毀的時候會調用對象的析構函數，而free則不會。

5、new是一個操作符可以重載，malloc是一個庫函數。

6、malloc分配的內存不夠的時候，可以用realloc擴容。擴容的原理？new沒用這樣操作。

7、new如果分配失敗了會拋出bad_malloc的異常，而malloc失敗了會返回NULL。

8、申請數組時： new[]一次分配所有內存，多次調用構造函數，搭配使用delete[]，delete[]多次調用析構函數，銷毀數組中的每個對象。而malloc則只能sizeof(int) * n。

23、A* a = new A; a->i = 10;在內核中的內存分配上發(fā)生了什么？

1）A *a：a是一個局部變量，類型為指針，故而操作系統在程序棧區(qū)開辟4/8字節(jié)的空間（0x000m），分配給指針a。

2）new A：通過new動態(tài)的在堆區(qū)申請類A大小的空間（0x000n）。

3）a = new A：將指針a的內存區(qū)域填入棧中類A申請到的地址的地址。即*（0x000m）=0x000n。

4）a->i：先找到指針a的地址0x000m，通過a的值0x000n和i在類a中偏移offset，得到a->i的地址0x000n + offset，進行*(0x000n + offset) = 10的賦值操作，即內存0x000n + offset的值是10。

24、一個類，里面有static，virtual，之類的，來說一說這個類的內存分布？

1、static修飾符

1）static修飾成員變量

對于非靜態(tài)數據成員，每個類對象都有自己的拷貝。而靜態(tài)數據成員被當做是類的成員，無論這個類被定義了多少個，靜態(tài)數據成員都只有一份拷貝，為該類型的所有對象所共享(包括其派生類)。所以，靜態(tài)數據成員的值對每個對象都是一樣的，它的值可以更新。

因為靜態(tài)數據成員在全局數據區(qū)分配內存，屬于本類的所有對象共享，所以它不屬于特定的類對象，在沒有產生類對象前就可以使用。

2）static修飾成員函數

與普通的成員函數相比，靜態(tài)成員函數由于不是與任何的對象相聯系，因此它不具有this指針。從這個意義上來說，它無法訪問屬于類對象的非靜態(tài)數據成員，也無法訪問非靜態(tài)成員函數，只能調用其他的靜態(tài)成員函數。

Static修飾的成員函數，在代碼區(qū)分配內存。

2、C++繼承和虛函數

C++多態(tài)分為靜態(tài)多態(tài)和動態(tài)多態(tài)。靜態(tài)多態(tài)是通過重載和模板技術實現，在編譯的時候確定。動態(tài)多態(tài)通過虛函數和繼承關系來實現，執(zhí)行動態(tài)綁定，在運行的時候確定。

動態(tài)多態(tài)實現有幾個條件：

(1) 虛函數；

(2) 一個基類的指針或引用指向派生類的對象；

基類指針在調用成員函數(虛函數)時，就會去查找該對象的虛函數表。虛函數表的地址在每個對象的首地址。查找該虛函數表中該函數的指針進行調用。

每個對象中保存的只是一個虛函數表的指針，C++內部為每一個類維持一個虛函數表，該類的對象的都指向這同一個虛函數表。

虛函數表中為什么就能準確查找相應的函數指針呢？因為在類設計的時候，虛函數表直接從基類也繼承過來，如果覆蓋了其中的某個虛函數，那么虛函數表的指針就會被替換，因此可以根據指針準確找到該調用哪個函數。

3、virtual修飾符

如果一個類是局部變量則該類數據存儲在棧區(qū)，如果一個類是通過new/malloc動態(tài)申請的，則該類數據存儲在堆區(qū)。

如果該類是virutal繼承而來的子類，則該類的虛函數表指針和該類其他成員一起存儲。虛函數表指針指向只讀數據段中的類虛函數表，虛函數表中存放著一個個函數指針，函數指針指向代碼段中的具體函數。

如果類中成員是virtual屬性，會隱藏父類對應的屬性。

25、靜態(tài)變量什么時候初始化？

靜態(tài)變量存儲在虛擬地址空間的數據段和bss段，C語言中其在代碼執(zhí)行之前初始化，屬于編譯期初始化。而C++中由于引入對象，對象生成必須調用構造函數，因此C++規(guī)定全局或局部靜態(tài)對象當且僅當對象首次用到時進行構造。

26、TCP怎么保證可靠性？

TCP保證可靠性：

（1）序列號、確認應答、超時重傳

數據到達接收方，接收方需要發(fā)出一個確認應答，表示已經收到該數據段，并且確認序號會說明了它下一次需要接收的數據序列號。如果發(fā)送發(fā)遲遲未收到確認應答，那么可能是發(fā)送的數據丟失，也可能是確認應答丟失，這時發(fā)送方在等待一定時間后會進行重傳。這個時間一般是2*RTT(報文段往返時間）+一個偏差值。

（2）窗口控制與高速重發(fā)控制/快速重傳（重復確認應答）

TCP會利用窗口控制來提高傳輸速度，意思是在一個窗口大小內，不用一定要等到應答才能發(fā)送下一段數據，窗口大小就是無需等待確認而可以繼續(xù)發(fā)送數據的最大值。如果不使用窗口控制，每一個沒收到確認應答的數據都要重發(fā)。

使用窗口控制，如果數據段1001-2000丟失，后面數據每次傳輸，確認應答都會不停地發(fā)送序號為1001的應答，表示我要接收1001開始的數據，發(fā)送端如果收到3次相同應答，就會立刻進行重發(fā)；但還有種情況有可能是數據都收到了，但是有的應答丟失了，這種情況不會進行重發(fā)，因為發(fā)送端知道，如果是數據段丟失，接收端不會放過它的，會瘋狂向它提醒......

（3）擁塞控制

如果把窗口定的很大，發(fā)送端連續(xù)發(fā)送大量的數據，可能會造成網絡的擁堵（大家都在用網，你在這狂發(fā)，吞吐量就那么大，當然會堵），甚至造成網絡的癱瘓。所以TCP在為了防止這種情況而進行了擁塞控制。

慢啟動：定義擁塞窗口，一開始將該窗口大小設為1，之后每次收到確認應答（經過一個rtt），將擁塞窗口大小*2。

擁塞避免：設置慢啟動閾值，一般開始都設為65536。擁塞避免是指當擁塞窗口大小達到這個閾值，擁塞窗口的值不再指數上升，而是加法增加（每次確認應答/每個rtt，擁塞窗口大小+1），以此來避免擁塞。

將報文段的超時重傳看做擁塞，則一旦發(fā)生超時重傳，我們需要先將閾值設為當前窗口大小的一半，并且將窗口大小設為初值1，然后重新進入慢啟動過程。

快速重傳：在遇到3次重復確認應答（高速重發(fā)控制）時，代表收到了3個報文段，但是這之前的1個段丟失了，便對它進行立即重傳。

然后，先將閾值設為當前窗口大小的一半，然后將擁塞窗口大小設為慢啟動閾值+3的大小。

這樣可以達到：在TCP通信時，網絡吞吐量呈現逐漸的上升，并且隨著擁堵來降低吞吐量，再進入慢慢上升的過程，網絡不會輕易的發(fā)生癱瘓。

27、紅黑樹和AVL樹的定義，特點，以及二者區(qū)別

平衡二叉樹（AVL樹）：

平衡二叉樹又稱為AVL樹，是一種特殊的二叉排序樹。其左右子樹都是平衡二叉樹，且左右子樹高度之差的絕對值不超過1。一句話表述為：以樹中所有結點為根的樹的左右子樹高度之差的絕對值不超過1。將二叉樹上結點的左子樹深度減去右子樹深度的值稱為平衡因子BF，那么平衡二叉樹上的所有結點的平衡因子只可能是-1、0和1。只要二叉樹上有一個結點的平衡因子的絕對值大于1，則該二叉樹就是不平衡的。

紅黑樹：

紅黑樹是一種二叉查找樹，但在每個節(jié)點增加一個存儲位表示節(jié)點的顏色，可以是紅或黑（非紅即黑）。通過對任何一條從根到葉子的路徑上各個節(jié)點著色的方式的限制，紅黑樹確保沒有一條路徑會比其它路徑長出兩倍，因此，紅黑樹是一種弱平衡二叉樹，相對于要求嚴格的AVL樹來說，它的旋轉次數少，所以對于搜索，插入，刪除操作較多的情況下，通常使用紅黑樹。

性質：

1. 每個節(jié)點非紅即黑

2. 根節(jié)點是黑的;

3. 每個葉節(jié)點（葉節(jié)點即樹尾端NULL指針或NULL節(jié)點）都是黑的;

4. 如果一個節(jié)點是紅色的，則它的子節(jié)點必須是黑色的。

5. 對于任意節(jié)點而言，其到葉子點樹NULL指針的每條路徑都包含相同數目的黑節(jié)點;

區(qū)別：

AVL 樹是高度平衡的，頻繁的插入和刪除，會引起頻繁的rebalance，導致效率下降；紅黑樹不是高度平衡的，算是一種折中，插入最多兩次旋轉，刪除最多三次旋轉。

28、map和unordered_map優(yōu)點和缺點

對于map，其底層是基于紅黑樹實現的，優(yōu)點如下：

1)有序性，這是map結構最大的優(yōu)點，其元素的有序性在很多應用中都會簡化很多的操作

2)map的查找、刪除、增加等一系列操作時間復雜度穩(wěn)定，都為logn

缺點如下：

        1）查找、刪除、增加等操作平均時間復雜度較慢，與n相關

        對于unordered_map來說，其底層是一個哈希表，優(yōu)點如下：

查找、刪除、添加的速度快，時間復雜度為常數級O(c)

缺點如下：

因為unordered_map內部基于哈希表，以（key,value）對的形式存儲，因此空間占用率高

Unordered_map的查找、刪除、添加的時間復雜度不穩(wěn)定，平均為O(c)，取決于哈希函數。極端情況下可能為O(n)

29、Top(K)問題

1、直接全部排序（只適用于內存夠的情況）

當數據量較小的情況下，內存中可以容納所有數據。則最簡單也是最容易想到的方法是將數據全部排序，然后取排序后的數據中的前K個。

這種方法對數據量比較敏感，當數據量較大的情況下，內存不能完全容納全部數據，這種方法便不適應了。即使內存能夠滿足要求，該方法將全部數據都排序了，而題目只要求找出top K個數據，所以該方法并不十分高效，不建議使用。

2、快速排序的變形 （只使用于內存夠的情況）

這是一個基于快速排序的變形，因為第一種方法中說到將所有元素都排序并不十分高效，只需要找出前K個最大的就行。

這種方法類似于快速排序，首先選擇一個劃分元，將比這個劃分元大的元素放到它的前面，比劃分元小的元素放到它的后面，此時完成了一趟排序。如果此時這個劃分元的序號index剛好等于K，那么這個劃分元以及它左邊的數，剛好就是前K個最大的元素；如果index  > K，那么前K大的數據在index的左邊，那么就繼續(xù)遞歸的從index-1個數中進行一趟排序；如果index < K，那么再從劃分元的右邊繼續(xù)進行排序，直到找到序號index剛好等于K為止。再將前K個數進行排序后，返回Top K個元素。這種方法就避免了對除了Top K個元素以外的數據進行排序所帶來的不必要的開銷。

3、最小堆法

這是一種局部淘汰法。先讀取前K個數，建立一個最小堆。然后將剩余的所有數字依次與最小堆的堆頂進行比較，如果小于或等于堆頂數據，則繼續(xù)比較下一個；否則，刪除堆頂元素，并將新數據插入堆中，重新調整最小堆。當遍歷完全部數據后，最小堆中的數據即為最大的K個數。

4、分治法

將全部數據分成N份，前提是每份的數據都可以讀到內存中進行處理，找到每份數據中最大的K個數。此時剩下N*K個數據，如果內存不能容納N*K個數據，則再繼續(xù)分治處理，分成M份，找出每份數據中最大的K個數，如果M*K個數仍然不能讀到內存中，則繼續(xù)分治處理。直到剩余的數可以讀入內存中，那么可以對這些數使用快速排序的變形或者歸并排序進行處理。

5、Hash法

如果這些數據中有很多重復的數據，可以先通過hash法，把重復的數去掉。這樣如果重復率很高的話，會減少很大的內存用量，從而縮小運算空間。處理后的數據如果能夠讀入內存，則可以直接排序；否則可以使用分治法或者最小堆法來處理數據。

30、棧和堆的區(qū)別，以及為什么棧要快？

堆和棧的區(qū)別：

堆是由低地址向高地址擴展；棧是由高地址向低地址擴展

堆中的內存需要手動申請和手動釋放；棧中內存是由OS自動申請和自動釋放，存放著參數、局部變量等內存

堆中頻繁調用malloc和free,會產生內存碎片，降低程序效率；而棧由于其先進后出的特性，不會產生內存碎片

堆的分配效率較低，而棧的分配效率較高

棧的效率高的原因：

棧是操作系統提供的數據結構，計算機底層對棧提供了一系列支持：分配專門的寄存器存儲棧的地址，壓棧和入棧有專門的指令執(zhí)行；而堆是由C/C++函數庫提供的，機制復雜，需要一系列分配內存、合并內存和釋放內存的算法，因此效率較低。

31、寫個函數在main函數執(zhí)行前先運行

__attribute((constructor))void before()
{
    printf("before main\n");
}

32、extern“C”的作用？

C++調用C函數需要extern C，因為C語言沒有函數重載。

33、STL迭代器刪除元素

1.對于序列容器vector,deque來說，使用erase(itertor)后，后邊的每個元素的迭代器都會失效，但是后邊每個元素都會往前移動一個位置，但是erase會返回下一個有效的迭代器；

2.對于關聯容器map set來說，使用了erase(iterator)后，當前元素的迭代器失效，但是其結構是紅黑樹，刪除當前元素的，不會影響到下一個元素的迭代器，所以在調用erase之前，記錄下一個元素的迭代器即可。

3.對于list來說，它使用了不連續(xù)分配的內存，并且它的erase方法也會返回下一個有效的iterator。

34、vector和list的區(qū)別與應用有哪些？

1、概念：

1）Vector

連續(xù)存儲的容器，動態(tài)數組，在堆上分配空間

底層實現：數組

兩倍容量增長：

vector 增加（插入）新元素時，如果未超過當時的容量，則還有剩余空間，那么直接添加到最后（插入指定位置），然后調整迭代器。

如果沒有剩余空間了，則會重新配置原有元素個數的兩倍空間，然后將原空間元素通過復制的方式初始化新空間，再向新空間增加元素，最后析構并釋放原空間，之前的迭代器會失效。

性能：

訪問：O(1)

插入：在最后插入（空間夠）：很快

在最后插入（空間不夠）：需要內存申請和釋放，以及對之前數據進行拷貝。

在中間插入（空間夠）：內存拷貝

在中間插入（空間不夠）：需要內存申請和釋放，以及對之前數據進行拷貝。

刪除：在最后刪除：很快

在中間刪除：內存拷貝

適用場景：經常隨機訪問，且不經常對非尾節(jié)點進行插入刪除。

2、List

動態(tài)鏈表，在堆上分配空間，每插入一個元數都會分配空間，每刪除一個元素都會釋放空間。

底層：雙向鏈表

性能：

訪問：隨機訪問性能很差，只能快速訪問頭尾節(jié)點。

插入：很快，一般是常數開銷

刪除：很快，一般是常數開銷

適用場景：經常插入刪除大量數據

2、區(qū)別：

1）vector底層實現是數組；list是雙向 鏈表。

2）vector支持隨機訪問，list不支持。

3）vector是順序內存，list不是。

4）vector在中間節(jié)點進行插入刪除會導致內存拷貝，list不會。

5）vector一次性分配好內存，不夠時才進行2倍擴容；list每次插入新節(jié)點都會進行內存申請。

6）vector隨機訪問性能好，插入刪除性能差；list隨機訪問性能差，插入刪除性能好。

3、應用

vector擁有一段連續(xù)的內存空間，因此支持隨機訪問，如果需要高效的隨即訪問，而不在乎插入和刪除的效率，使用vector。

list擁有一段不連續(xù)的內存空間，如果需要高效的插入和刪除，而不關心隨機訪問，則應使用list。

35、STL里resize和reserve的區(qū)別？

resize()：改變當前容器內含有元素的數量(size())，eg: vector<int>v; v.resize(len);v的size變?yōu)閘en,如果原來v的size小于len，那么容器新增（len-size）個元素，元素的值為默認為0.當v.push_back(3);之后，則是3是放在了v的末尾，即下標為len，此時容器是size為len+1；
reserve()：改變當前容器的最大容量（capacity）,它不會生成元素，只是確定這個容器允許放入多少對象，如果reserve(len)的值大于當前的capacity()，那么會重新分配一塊能存len個對象的空間，然后把之前v.size()個對象通過copy construtor復制過來，銷毀之前的內存。

36、源碼到可執(zhí)行文件的過程？

1）預編譯

主要處理源代碼文件中的以“#”開頭的預編譯指令。處理規(guī)則見下

1、刪除所有的#define，展開所有的宏定義。

2、處理所有的條件預編譯指令，如“#if”、“#endif”、“#ifdef”、“#elif”和“#else”。

3、處理“#include”預編譯指令，將文件內容替換到它的位置，這個過程是遞歸進行的，文件中包含其他文件。

4、刪除所有的注釋，“//”和“/**/”。

5、保留所有的#pragma 編譯器指令，編譯器需要用到他們，如：#pragma once 是為了防止有文件被重復引用。

6、添加行號和文件標識，便于編譯時編譯器產生調試用的行號信息，和編譯時產生編譯錯誤或警告是能夠顯示行號。

2）編譯

把預編譯之后生成的xxx.i或xxx.ii文件，進行一系列詞法分析、語法分析、語義分析及優(yōu)化后，生成相應的匯編代碼文件。

1、詞法分析：利用類似于“有限狀態(tài)機”的算法，將源代碼程序輸入到掃描機中，將其中的字符序列分割成一系列的記號。

2、語法分析：語法分析器對由掃描器產生的記號，進行語法分析，產生語法樹。由語法分析器輸出的語法樹是一種以表達式為節(jié)點的樹。

3、語義分析：語法分析器只是完成了對表達式語法層面的分析，語義分析器則對表達式是否有意義進行判斷，其分析的語義是靜態(tài)語義——在編譯期能分期的語義，相對應的動態(tài)語義是在運行期才能確定的語義。

4、優(yōu)化：源代碼級別的一個優(yōu)化過程。

5、目標代碼生成：由代碼生成器將中間代碼轉換成目標機器代碼，生成一系列的代碼序列——匯編語言表示。

6、目標代碼優(yōu)化：目標代碼優(yōu)化器對上述的目標機器代碼進行優(yōu)化：尋找合適的尋址方式、使用位移來替代乘法運算、刪除多余的指令等。

3）匯編

將匯編代碼轉變成機器可以執(zhí)行的指令(機器碼文件)。 匯編器的匯編過程相對于編譯器來說更簡單，沒有復雜的語法，也沒有語義，更不需要做指令優(yōu)化，只是根據匯編指令和機器指令的對照表一一翻譯過來，匯編過程有匯編器as完成。經匯編之后，產生目標文件(與可執(zhí)行文件格式幾乎一樣)xxx.o(Windows下)、xxx.obj(Linux下)。

4）鏈接

將不同的源文件產生的目標文件進行鏈接，從而形成一個可以執(zhí)行的程序。鏈接分為靜態(tài)鏈接和動態(tài)鏈接：

1、靜態(tài)鏈接：

函數和數據被編譯進一個二進制文件。在使用靜態(tài)庫的情況下，在編譯鏈接可執(zhí)行文件時，鏈接器從庫中復制這些函數和數據并把它們和應用程序的其它模塊組合起來創(chuàng)建最終的可執(zhí)行文件。

空間浪費：因為每個可執(zhí)行程序中對所有需要的目標文件都要有一份副本，所以如果多個程序對同一個目標文件都有依賴，會出現同一個目標文件都在內存存在多個副本；

更新困難：每當庫函數的代碼修改了，這個時候就需要重新進行編譯鏈接形成可執(zhí)行程序。

運行速度快：但是靜態(tài)鏈接的優(yōu)點就是，在可執(zhí)行程序中已經具備了所有執(zhí)行程序所需要的任何東西，在執(zhí)行的時候運行速度快。

2、動態(tài)鏈接：

動態(tài)鏈接的基本思想是把程序按照模塊拆分成各個相對獨立部分，在程序運行時才將它們鏈接在一起形成一個完整的程序，而不是像靜態(tài)鏈接一樣把所有程序模塊都鏈接成一個單獨的可執(zhí)行文件。

共享庫：就是即使需要每個程序都依賴同一個庫，但是該庫不會像靜態(tài)鏈接那樣在內存中存在多分，副本，而是這多個程序在執(zhí)行時共享同一份副本；

更新方便：更新時只需要替換原來的目標文件，而無需將所有的程序再重新鏈接一遍。當程序下一次運行時，新版本的目標文件會被自動加載到內存并且鏈接起來，程序就完成了升級的目標。

性能損耗：因為把鏈接推遲到了程序運行時，所以每次執(zhí)行程序都需要進行鏈接，所以性能會有一定損失。

37、tcp握手為什么兩次不可以？為什么不用四次？

兩次不可以：tcp是全雙工通信，兩次握手只能確定單向數據鏈路是可以通信的，并不能保證反向的通信正常

不用四次：
本來握手應該和揮手一樣都是需要確認兩個方向都能聯通的，本來模型應該是：
1.客戶端發(fā)送syn0給服務器
2.服務器收到syn0，回復ack(syn0+1)
3.服務器發(fā)送syn1
4.客戶端收到syn1，回復ack(syn1+1)
因為tcp是全雙工的，上邊的四部確認了數據在兩個方向上都是可以正確到達的，但是2，3步沒有沒有上下的聯系，可以將其合并，加快握手效率，所有就變成了3步握手。

  以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

最新評論