1. 結構體和共同體的區別。

定義：

結構體struct：把不同類型的數據組合成一個整體，自定義類型。

共同體union：使幾個不同類型的變量共同占用一段內存。

地址：

struct和union都有內存對齊，結構體的內存布局依賴于CPU、操作系統、編譯器及編譯時的對齊選項。

關于內存對齊，先讓我們看四個重要的基本概念：1.數據類型自身的對齊值：對于char型數據，其自身對齊值為1，對于short型為2，對于int,float,double類型，其自身對齊值為4，單位字節。2.結構體或者類的自身對齊值：其成員中自身對齊值最大的那個值。3.指定對齊值：#PRagma pack(n)，n=1,2,4,8,16改變系統的對齊系數4.數據成員、結構體和類的有效對齊值：自身對齊值和指定對齊值中小的那個值。
 常見數據類型及其長度：
注意long int和int一樣是4byte，long double和double一樣是8byte。
在標準c++中，int的定義長度要依靠你的機器的字長，也就是說，如果你的機器是32位的，int的長度為32位，如果你的機器是64位的，那么int的標準長度就是64位。
從上面的一段文字中，我們可以看出，首先根據結構體內部成員的自身對齊值得到結構體的自身對齊值（內部成員最大的長度），如果沒有修改系統設定的默認補齊長度4的話，取較小的進行內存補齊。
結構體struct：不同之處，stuct里每個成員都有自己獨立的地址。sizeof(struct)是內存對齊后所有成員長度的加和。
共同體union：當共同體中存入新的數據后，原有的成員就失去了作用，新的數據被寫到union的地址中。sizeof(union)是最長的數據成員的長度。
總結： struct和union都是由多個不同的數據類型成員組成, 但在任何同一時刻, union中只存放了一個被選中的成員, 而struct的所有成員都存在。在struct中，各成員都占有自己的內存空間，它們是同時存在的。一個struct變量的總長度等于所有成員長度之和。在Union中，所有成員不能同時占用它的內存空間，它們不能同時存在。Union變量的長度等于最長的成員的長度。對于union的不同成員賦值, 將會對其它成員重寫, 原來成員的值就不存在了, 而對于struct的不同成員賦值是互不影響的。
 
 
 2.static 和const分別怎么用，類里面static和const可以同時修飾成員函數嗎。
 static的作用：
對變量：
1.局部變量：
在局部變量之前加上關鍵字static，局部變量就被定義成為一個局部靜態變量。
  1）內存中的位置：靜態存儲區
  2）初始化：未經初始化的全局靜態變量會被程序自動初始化為0（自動對象的值是任意的，除非他被顯示初始化）
  3）作用域：作用域仍為局部作用域，當定義它的函數或者語句塊結束的時候，作用域隨之結束。
 注：當static用來修飾局部變量的時候，它就改變了局部變量的存儲位置（從原來的棧中存放改為靜態存儲區）及其生命周期（局部靜態變量在離開作用域之后，并沒有被銷毀，而是仍然駐留在內存當中，直到程序結束，只不過我們不能再對他進行訪問），但未改變其作用域。
2.全局變量
在全局變量之前加上關鍵字static，全局變量就被定義成為一個全局靜態變量。
1）內存中的位置：靜態存儲區（靜態存儲區在整個程序運行期間都存在）
2）初始化：未經初始化的全局靜態變量會被程序自動初始化為0（自動對象的值是任意的，除非他被顯示初始化）
3）作用域：全局靜態變量在聲明他的文件之外是不可見的。準確地講從定義之處開始到文件結尾。
注：static修飾全局變量，并為改變其存儲位置及生命周期，而是改變了其作用域，使當前文件外的源文件無法訪問該變量，好處如下：（1）不會被其他文件所訪問，修改（2）其他文件中可以使用相同名字的變量，不會發生沖突。對全局函數也是有隱藏作用。
對類中的
　　　　1.成員變量
　　　　用static修飾類的數據成員實際使其成為類的全局變量，會被類的所有對象共享，包括派生類的對象。因此，static成員必須在類外進行初始化(初始化格式： int base::var=10;)，而不能在構造函數內進行初始化，不過也可以用const修飾static數據成員在類內初始化 。
　　　　特點：
不要試圖在頭文件中定義(初始化)靜態數據成員。在大多數的情況下，這樣做會引起重復定義這樣的錯誤。即使加上#ifndef #define #endif或者#pragma once也不行。 靜態數據成員可以成為成員函數的可選參數，而普通數據成員則不可以。靜態數據成員的類型可以是所屬類的類型，而普通數據成員則不可以。普通數據成員的只能聲明為 所屬類類型的指針或引用。
2.成員函數
用static修飾成員函數，使這個類只存在這一份函數，所有對象共享該函數，不含this指針。靜態成員是可以獨立訪問的，也就是說，無須創建任何對象實例就可以訪問。base::func(5,3);當static成員函數在類外定義時不需要加static修飾符。在靜態成員函數的實現中不能直接引用類中說明的非靜態成員，可以引用類中說明的靜態成員。因為靜態成員函數不含this指針。 
不可以同時用const和static修飾成員函數。
C++編譯器在實現const的成員函數的時候為了確保該函數不能修改類的實例的狀態，會在函數中添加一個隱式的參數const this*。但當一個成員為static的時候，該函數是沒有this指針的。也就是說此時const的用法和static是沖突的。
我們也可以這樣理解：兩者的語意是矛盾的。static的作用是表示該函數只作用在類型的靜態變量上，與類的實例沒有關系；而const的作用是確保函數不能修改類的實例的狀態，與類型的靜態變量沒有關系。因此不能同時用它們。
const的作用：
 1.限定變量為不可修改。
2.限定成員函數不可以修改任何數據成員。
3.const與指針：
const char *p 表示 指向的內容不能改變。
char * const p，就是將P聲明為常指針，它的地址不能改變，是固定的，但是它的內容可以改變。
 
 3.指針和引用的區別，引用可以用常指針實現嗎。
本質上的區別是，指針是一個新的變量，只是這個變量存儲的是另一個變量的地址，我們通過訪問這個地址來修改變量。
而引用只是一個別名，還是變量本身。對引用進行的任何操作就是對變量本身進行操作，因此以達到修改變量的目的。
(1)指針：指針是一個變量，只不過這個變量存儲的是一個地址，指向內存的一個存儲單元；而引用跟原來的變量實質上是同一個東西，只不過是原變量的一個別名而已。如：int a=1;int *p=&a;int a=1;int &b=a;上面定義了一個整形變量和一個指針變量p，該指針變量指向a的存儲單元，即p的值是a存儲單元的地址。而下面2句定義了一個整形變量a和這個整形a的引用b，事實上a和b是同一個東西，在內存占有同一個存儲單元。(2)可以有const指針，但是沒有const引用；(3)指針可以有多級，但是引用只能是一級（int **p；合法 而 int &&a是不合法的）(4)指針的值可以為空，但是引用的值不能為NULL，并且引用在定義的時候必須初始化；(5)指針的值在初始化后可以改變，即指向其它的存儲單元，而引用在進行初始化后就不會再改變了。(6)"sizeof引用"得到的是所指向的變量(對象)的大小，而"sizeof指針"得到的是指針本身的大小；(7)指針和引用的自增(++)運算意義不一樣；
指針傳參的時候，還是值傳遞，試圖修改傳進來的指針的值是不可以的。只能修改地址所保存變量的值。引用傳參的時候，傳進來的就是變量本身，因此可以被修改。
4.什么是多態，多態有什么用途。
定義：“一個接口，多種方法”，程序在運行時才決定調用的函數。實現：C++多態性主要是通過虛函數實現的，虛函數允許子類重寫override(注意和overload的區別，overload是重載，是允許同名函數的表現，這些函數參數列表/類型不同）。
多態與非多態的實質區別就是函數地址是早綁定還是晚綁定。如果函數的調用，在編譯器編譯期間就可以確定函數的調用地址，并生產代碼，是靜態的，就是說地址是早綁定的。而如果函數調用的地址不能在編譯器期間確定，需要在運行時才確定，這就屬于晚綁定。
3.目的：接口重用。封裝可以使得代碼模塊化，繼承可以擴展已存在的代碼，他們的目的都是為了代碼重用。而多態的目的則是為了接口重用。
4.用法：聲明基類的指針，利用該指針指向任意一個子類對象，調用相應的虛函數，可以根據指向的子類的不同而實現不同的方法。
補充一下關于重載、重寫、隱藏（總是不記得）的區別：
Overload(重載)：在C++程序中，可以將語義、功能相似的幾個函數用同一個名字表示，但參數或返回值不同（包括類型、順序不同），即函數重載。（1）相同的范圍（在同一個類中）；（2）函數名字相同；（3）參數不同；（4）virtual 關鍵字可有可無。Override(覆蓋)：是指派生類函數覆蓋基類函數，特征是：（1）不同的范圍（分別位于派生類與基類）；（2）函數名字相同；（3）參數相同；（4）基類函數必須有virtual 關鍵字。注：重寫基類虛函數的時候，會自動轉換這個函數為virtual函數，不管有沒有加virtual，因此重寫的時候不加virtual也是可以的，不過為了易讀性，還是加上比較好。Overwrite(重寫)：隱藏，是指派生類的函數屏蔽了與其同名的基類函數，規則如下：（1）如果派生類的函數與基類的函數同名，但是參數不同。此時，不論有無virtual關鍵字，基類的函數將被隱藏（注意別與重載混淆）。（2）如果派生類的函數與基類的函數同名，并且參數也相同，但是基類函數沒有virtual關鍵字。此時，基類的函數被隱藏（注意別與覆蓋混淆）。
補充一下虛函數表：
多態是由虛函數實現的，而虛函數主要是通過虛函數表（V-Table）來實現的。
如果一個類中包含虛函數（virtual修飾的函數），那么這個類就會包含一張虛函數表，虛函數表存儲的每一項是一個虛函數的地址。如下圖：
這個類的每一個對象都會包含一個虛指針（虛指針存在于對象實例地址的最前面，保證虛函數表有最高的性能），這個虛指針指向虛函數表。
注：對象不包含虛函數表，只有虛指針，類才包含虛函數表，派生類會生成一個兼容基類的虛函數表。
原始基類的虛函數表
　　下圖是原始基類的對象，可以看到虛指針在地址的最前面，指向基類的虛函數表（假設基類定義了3個虛函數）
單繼承時的虛函數（無重寫基類虛函數）
假設現在派生類繼承基類，并且重新定義了3個虛函數，派生類會自己產生一個兼容基類虛函數表的屬于自己的虛函數表。
　　Derive class 繼承了 Base class 中的三個虛函數，準確的說，是該函數實體的地址被拷貝到 Derive類的虛函數表，派生類新增的虛函數置于虛函數表的后面，并按聲明順序存放。
單繼承時的虛函數（重寫基類虛函數）
現在派生類重寫基類的x函數，可以看到這個派生類構建自己的虛函數表的時候，修改了base::x()這一項，指向了自己的虛函數。
多重繼承時的虛函數（Derived ::public Base1,public Base2）
這個派生類多重繼承了兩個基類base1，base2，因此它有兩個虛函數表。
　　
　　它的對象會有多個虛指針（據說和編譯器相關），指向不同的虛函數表。
　　多重繼承時指針的調整：
Derive b;Base1* ptr1 = &b;   // 指向 b 的初始地址Base2* ptr2 = &b;   // 指向 b 的第二個子對象
因為 Base1 是第一個基類，所以 ptr1 指向的是 Derive 對象的起始地址，不需要調整指針（偏移）。
因為 Base2 是第二個基類，所以必須對指針進行調整，即加上一個 offset，讓 ptr2 指向 Base2 子對象。
當然，上述過程是由編譯器完成的。
Base1* b1 = (Base1*)ptr2;b1->y();                   // 輸出 Base2::y()Base2* b2 = (Base2*)ptr1;b2->y();                   // 輸出 Base1::y()
其實，通過某個類型的指針訪問某個成員時，編譯器只是根據類型的定義查找這個成員所在偏移量，用這個偏移量獲取成員。由于 ptr2 本來就指向 Base2 子對象的起始地址，所以b1->y()調用到的是Base2::y()，而 ptr1 本來就指向 Base1 子對象的起始地址（即 Derive對象的起始地址），所以b2->y()調用到的是Base1::y()。
虛繼承時的虛函數表
　　虛繼承的引入把對象的模型變得十分復雜，除了每個基類（MyClassA和MyClassB）和公共基類（MyClass）的虛函數表指針需要記錄外，每個虛擬繼承了MyClass的父類還需要記錄一個虛基類表vbtable的指針vbptr。MyClassC的對象模型如圖4所示。
　　
　　　虛基類表每項記錄了被繼承的虛基類子對象相對于虛基類表指針的偏移量。比如MyClassA的虛基類表第二項記錄值為24，正是MyClass::vfptr相對于MyClassA::vbptr的偏移量，同理MyClassB的虛基類表第二項記錄值12也正是MyClass::vfptr相對于MyClassA::vbptr的偏移量。（虛函數與虛繼承深入探討）
對象模型探討：
 
1.沒有繼承情況,vptr存放在對象的開始位置,以下是Base1的內存布局
m_iData :100
 2.單繼承的情況下,對象只有一個vptr,它存放在對象的開始位置,派生類子對象在父類子對象的最后面,以下是D1的內存布局
B1:: m_iData : 100
B1::vptr : 4294800
B2::vptr : 4294776
D::m_iData :300
4. 虛擬繼承情況下,虛父類子對象會放在派生類子對象之后,派生類子對象的第一個位置存放著一個vptr,虛擬子類子對象也會保存一個vptr,以下是VD1的內存布局
 
 Unknown : 4294888
B1::vptr :4294864
VD1::vptr :        4294944
VD1::m_iData :  200
VD2::Unknown : 4294952
VD::m_iData : 500
B1::m_iData :  100
5. 棱形繼承的情況下,非虛基類子對象在派生類子對象前面,并按照聲明順序排列,虛基類子對象在派生類子對象后面
VD1::Unknown : 4294968
VD2::vptr :    4   294932
VD2::m_iData : 300
B1::vptr :       4294920
B1::m_iData :  100
 
補充一下純虛函數：
定義： 在很多情況下，基類本身生成對象是不合情理的。為了解決這個問題，方便使用類的多態性，引入了純虛函數的概念，將函數定義為純虛函數（方法：virtual ReturnType Function()= 0;）純虛函數不能再在基類中實現，編譯器要求在派生類中必須予以重寫以實現多態性。同時含有純虛擬函數的類稱為抽象類，它不能生成對象。特點：
1，當想在基類中抽象出一個方法，且該基類只做能被繼承，而不能被實例化；（避免類被實例化且在編譯時候被發現，可以采用此方法）
2，這個方法必須在派生類(derived class)中被實現；
目的：使派生類僅僅只是繼承函數的接口。補充一下純虛函數：定義：稱帶有純虛函數的類為抽象類。作用：為一個繼承體系提供一個公共的根，為派生類提供操作接口的通用語義。特點：1.抽象類只能作為基類來使用，而繼承了抽象類的派生類如果沒有實現純虛函數，而只是繼承純虛函數，那么該類仍舊是一個抽象類，如果實現了純虛函數，就不再是抽象類。　　　　　　2.抽象類不可以定義對象。補充一下多重繼承和虛繼承：多重繼承：定義：派生類繼承多個基類，派生類為每個基類（顯式或隱式地）指定了訪問級別——public、protected 或 private。
    class Panda : public Bear, public Endangered {    }
構造：
派生類的對象包含每個基類的基類子對象。派生類構造函數初始化所有基類（多重繼承中若沒有顯式調用某個基類的構造函數，則編譯器會調用該基類默認構造函數），派生類只能初始化自己的基類，并不需要考慮基類的基類怎么初始化。多重繼承時，基類構造函數按照基類構造函數在類派生列表中的出現次序調用。析構：總是按構造函數運行的逆序調用析構函數。（基類的析構函數最好寫成virtual，否則再子類對象銷毀的時候，無法銷毀子類對象部分資源。）假定所有根基類都將它們的析構函數適當定義為虛函數，那么，無論通過哪種指針類型刪除對象，虛析構函數的處理都是一致的。 拷貝構造/賦值：如果要為派生類編寫拷貝構造函數，則需要為調用基類相應拷貝構造函數并為其傳遞參數，否則只會拷貝派生類部分。
深拷貝與淺拷貝：淺拷貝：默認的復制構造函數只是完成了對象之間的位拷貝，也就是把對象里的值完全復制給另一個對象，如A=B。這時，如果B中有一個成員變量指針已經申請了內存，那A中的那個成員變量也指向同一塊內存。　　　　這就出現了問題：當B把內存釋放了（如：析構），這時A內的指針就是野指針了，出現運行錯誤。深拷貝：自定義復制構造函數需要注意，對象之間發生復制，資源重新分配，即A有5個空間，B也應該有5個空間，而不是指向A的5個空間。
虛繼承與虛基類：
定義：在多重繼承下，一個基類可以在派生層次中出現多次。（派生類對象中可能出現多個基類對象）在 C++ 中，通過使用虛繼承解決這類問題。虛繼承是一種機制，類通過虛繼承指出它希望共享其虛基類的狀態。在虛繼承下，對給定虛基類，無論該類在派生層次中作為虛基類出現多少次，只繼承一個共享的基類子對象。共享的基類子對象稱為虛基類。
用法：istream 和 ostream 類對它們的基類進行虛繼承。通過使基類成為虛基類，istream 和 ostream 指定，如果其他類（如 iostream 同時繼承它們兩個，則派生類中只出現它們的公共基類ios的一個副本。通過在派生列表中包含關鍵字 virtual 設置虛基類：
    class istream : public virtual ios { ... };    class ostream : virtual public ios { ... };    // iostream inherits only one copy of its ios base class    class iostream: public istream, public ostream { ... };
5.各個排序算法的時間復雜度和穩定性，快排的原理。
排序深入探討
插入排序
　　每次將一個待排序的數據，跟前面已經有序的序列的數字一一比較找到自己合適的位置，插入到序列中，直到全部數據插入完成。
希爾排序
　　先將整個待排元素序列分割成若干個子序列（由相隔某個“增量”的元素組成的）分別進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序。由于希爾排序是對相隔若干距離的數據進行直接插入排序，因此可以形象的稱希爾排序為“跳著插”
冒泡排序
通過交換使相鄰的兩個數變成小數在前大數在后，這樣每次遍歷后，最大的數就“沉”到最后面了。重復N次即可以使數組有序。
冒泡排序改進1：在某次遍歷中如果沒有數據交換，說明整個數組已經有序。因此通過設置標志位來記錄此次遍歷有無數據交換就可以判斷是否要繼續循環。
冒泡排序改進2：記錄某次遍歷時最后發生數據交換的位置，這個位置之后的數據顯然已經有序了。因此通過記錄最后發生數據交換的位置就可以確定下次循環的范圍了。
快速排序
“挖坑填數+分治法”，首先令i =L; j = R; 將a[i]挖出形成第一個坑，稱a[i]為基準數。然后j--由后向前找比基準數小的數，找到后挖出此數填入前一個坑a[i]中，再i++由前向后找比基準數大的數，找到后也挖出此數填到前一個坑a[j]中。重復進行這種“挖坑填數”直到i==j。再將基準數填入a[i]中，這樣i之前的數都比基準數小，i之后的數都比基準數大。因此將數組分成二部分再分別重復上述步驟就完成了排序。
選擇排序
數組分成有序區和無序區，初始時整個數組都是無序區，然后每次從無序區選一個最小的元素直接放到有序區的最后，直到整個數組變有序區。
堆排序
堆的插入就是——每次插入都是將新數據放在數組最后，而從這個新數據的父結點到根結點必定是一個有序的數列，因此只要將這個新數據插入到這個有序數列中即可。
堆的刪除就是——堆的刪除就是將最后一個數據的值賦給根結點，然后再從根結點開始進行一次從上向下的調整。調整時先在左右兒子結點中找最小的，如果父結點比這個最小的子結點還小說明不需要調整了，反之將父結點和它交換后再考慮后面的結點。相當于從根結點開始將一個數據在有序數列中進行“下沉”。
因此，堆的插入和刪除非常類似直接插入排序，只不是在二叉樹上進行插入過程。所以可以將堆排序形容為“樹上插”
歸并排序
歸并排序主要分為兩步：分數列（divide），每次把數列一分為二，然后分到只有兩個元素的小數列；合數列（Merge），合并兩個已經內部有序的子序列，直至所有數字有序。用遞歸可以實現。
基數排序（桶排序）
基數排序，第一步根據數字的個位分配到每個桶里，在桶內部排序，然后將數字再輸出（串起來）；然后根據十位分桶，繼續排序，再串起來。直至所有位被比較完，所有數字已經有序。
 　　
 
6.vector中size()和capacity()的區別。
 
size()指容器當前擁有的元素個數（對應的resize(size_type)會在容器尾添加或刪除一些元素，來調整容器中實際的內容，使容器達到指定的大小。）；capacity（）指容器在必須分配存儲空間之前可以存儲的元素總數。
 
size表示的這個vector里容納了多少個元素，capacity表示vector能夠容納多少元素，它們的不同是在于vector的size是2倍增長的。如果vector的大小不夠了，比如現在的capacity是4，插入到第五個元素的時候，發現不夠了，此時會給他重新分配8個空間，把原來的數據及新的數據復制到這個新分配的空間里。（會有迭代器失效的問題）
各容器的特點：
 
7.map和set的原理。
(map和set的四個問題)
map和set的底層實現主要是由紅黑樹實現的。
紅黑樹：
性質1 節點是紅色或黑色。性質2 根節點是黑色。性質3 每個葉節點（NIL節點，空節點）是黑色的。性質4 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)性質5 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。這些約束的好處是：保持了樹的相對平衡，同時又比AVL的插入刪除操作的復雜性要低許多。
（深入探討紅黑樹）