不怎樣的一本書，具體表現(xiàn)為：1）該詳細(xì)講解的地方，或者一筆帶過或者講得不全面或者講些不相關(guān)內(nèi)容；2）該略過的地方，反而詳細(xì)起來；3）有一部分錯誤，如sizeof不計算static變量的大小之類的。雖說如此，收獲還是有的——知道了在筆試中常見的知識點。這里的筆記就是對我不熟悉或者理解不全面的知識點去Google和查書而來的。
C++的關(guān)鍵字
1. 使用extern "C"的理由
函數(shù)被C編譯器編譯后不帶參數(shù)信息，被C++編譯器編譯后會帶上參數(shù)信息。這是因為C++支持函數(shù)重載。所以函數(shù)被C編譯器編譯和被C++編譯器編譯是不同的。例如：void Zero(int lin)，被C編譯后，可能得到_Zero，被C++編譯后，可能得到_Zero_int。那如果要在C++中使用被C編譯過的庫呢？使用extern "C"就可以！它會告訴C++編譯器，被它修飾的函數(shù)是以C語言的編譯方式編譯的。
2. const的作用
a. 聲明常量
b. 聲明函數(shù)形參 -> 提高自定義類型的調(diào)用效率。注意，如果是內(nèi)部類型，如int，沒必要寫成const int&
c. 聲明函數(shù)返回值
d. 修飾類成員函數(shù) -> 防止成員函數(shù)對成員變量進(jìn)行修改。注意，const成員函數(shù)內(nèi)只能調(diào)用類的其他const成員函數(shù)
備注：如果要在const成員函數(shù)修改某個成員變量，那么可以給這個變量的聲明加上mutable
3. static的作用
a. 用于函數(shù)內(nèi)部的局部變量時，能保證函數(shù)退出作用域后不回收其空間（即其值保持不變）
b. 用于全局變量時，使變量的作用域限制在一個文件內(nèi)
c. 用于函數(shù)時，使函數(shù)只在一個文件內(nèi)可見
d. 用于類成員變量時，代表該變量屬于類的（即所有對象共享這個變量）
e. 用于類成員函數(shù)時，代表該函數(shù)為整個類所有。注意，該函數(shù)不接收this指針，也意味著不能調(diào)用一般的成員函數(shù)或者變量
4. sizeof操作符
a. 作用：返回一個對象或者類型所占的內(nèi)存
b. sizeof 不計算類/結(jié)構(gòu)體的static成員 -> 因而可將a中提到所占的內(nèi)存理解為存儲某個類型的對象所需要空間
c. 對空類使用sizeof會返回1 -> 占用內(nèi)存為0，無法實例化，所以編譯器為了使空類也能實例化，就給其分配了1Byte
d. 如果類中有虛函數(shù)，那么最終結(jié)果要多加4Byte -> 此時多出一個指針，指向虛函數(shù)表
e.g:
static int a; //sizeof(a) = 4，因為這不是類內(nèi)/結(jié)構(gòu)體內(nèi)的
class Zero {
int a;
static int b;
virtual void fun() {}
}; //sizeof(Zero) = 8
class Lin {
virtual void fun() {}
}; //sizeof(Lin) = 4，由d可知其為lin至少有4Byte，所以在這個例子中規(guī)則c不成立，因而最終結(jié)果為4Byte
class Child: public Zero {
int a;
virtual void fun() {}
}; //sizeof(Child) = 12
5. inline
a. inline只是一種建議，建議編譯器將指定的函數(shù)在被調(diào)用點展開，因此編譯器是可以忽略inline的（即不展開）
b. inline以代碼膨脹（復(fù)制）為代價，省去了函數(shù)調(diào)用的開銷，從而提高函數(shù)的執(zhí)行效率
c. 每一處inline函數(shù)的調(diào)用都要復(fù)制代碼，這將使得程序的總代碼量增大，消耗更多的內(nèi)存空間
d. inline必須與函數(shù)定義放在一起才能使函數(shù)成為內(nèi)聯(lián)，僅將inline 放在函數(shù)聲明前面不起任何作用
e. 定義在類聲明之中的成員函數(shù)將自動地成為內(nèi)聯(lián)函數(shù)
6. explicit
禁止單參數(shù)構(gòu)造函數(shù)被用于隱式類型轉(zhuǎn)換
class Zero {
public:
Zero(int i): lin(i) {}
private:
int lin;
};
int Fun(Zero z) {} //如果不用explicit的話，可以這樣調(diào)用Fun(1);
-------------------------------------------------------------------------------------------
C++的規(guī)則
1. 在聲明賦值語句中，變量先聲明，然后賦值
int i = 1;
int main() {
int i = i; //這里聲明的i 覆蓋了全局變量的i，之后的賦值就是局部變量的i 給自己賦值，因而其值是未定義的
return 0;
}
2. 從右到左壓參數(shù)
int main() {
int i = 1;
printf("%d, %d\n", i, ++i); //VS2010輸出2, 2
}
其它：
雖然壓參數(shù)的順序是固定的，但計算順序是編譯器相關(guān)的，因此最后的結(jié)果與編譯器相關(guān)。
3. 寫宏時要注意
a. 括號的使用
b. 不要使用分號
e.g: 寫一個找出兩者中較小的宏
#define MIN(a, b) ( (a) < (b) ? (a) : (b) )
4. 結(jié)構(gòu)體對齊原則
a. 數(shù)據(jù)成員對齊規(guī)則：結(jié)構(gòu)(struct或union)的數(shù)據(jù)成員，第一個數(shù)據(jù)成員放在offset為0的地方，以后每個數(shù)據(jù)成員存儲的起始位置要從該成員大小的整數(shù)倍開始（e.g: int在32位機為４字節(jié)，則要從4的整數(shù)倍地址開始存儲)
b. 結(jié)構(gòu)體作為成員：如果一個結(jié)構(gòu)里有某些結(jié)構(gòu)體成員，則結(jié)構(gòu)體成員要從其內(nèi)部最大元素大小的整數(shù)倍地址開始存(e.g: struct a里存有struct b，b里有char，int，double等元素，那b應(yīng)該從8的整數(shù)倍開始存儲)
c. 結(jié)構(gòu)體的總大小，必須是內(nèi)部最大成員的整數(shù)倍，不足的要補齊
備注：設(shè)計結(jié)構(gòu)體，最好把占用空間小的類型排在前面，占用空間大的類型排在后面，這樣可以相對節(jié)約一些對齊空間
struct Zero {
char b;
int a; //a的起始位置要按4字節(jié)對齊，所以b之后要補3個字節(jié)
short c;
}; //sizeof(Zero) = 12
struct OreZ {
char b;
short c; //c的起始位置要按2字節(jié)對齊，所以b之后要補1個字節(jié)
int a;
} //sizeof(Orez) = 8
5. 結(jié)構(gòu)體位制
a. 位段成員的類型僅能夠為unsigned或者int, 并且指定的位數(shù)不能超過類型的長度
b. 存儲規(guī)則：如果下一個位段能存放在之前的存儲單元中(存儲后長度不超過類型長度)，則存儲，否則，存儲到新的存儲單元中。因為位段不能跨單元存儲
struct Zero {
unsigned short a : 4;
unsigned short b : 5;
unsigned short c : 7; //剛好16，符合unsigned short的長度，所以存放在同一單元中
}zero;
int main() {
zero.a = 2;
zero.b = 3;
int i = *((short*)&zero);
printf("%d", i); //輸出50(VS2010測試結(jié)果)，這說明先聲明的變量在低位
return 0;
}
6. C++風(fēng)格類型轉(zhuǎn)換
a. const_cast<type>(varible): 去掉變量的const或volatile屬性
b. static_cast<type>(varible): 類似C的強制轉(zhuǎn)換，但功能上有所限制(如：不能去掉const屬性) -> 常用于基本類型轉(zhuǎn)換，void指針與目標(biāo)指針轉(zhuǎn)換
c. dynamic_cast<type>(varible): 有條件轉(zhuǎn)換，運行時進(jìn)行類型安全檢查(如果失敗則返回NULL) -> 用于基類與子類之間的類型轉(zhuǎn)換(必須要有虛函數(shù))
d. reinterpret_cast<type>(varible): 僅僅重新解釋二進(jìn)制內(nèi)容 -> 常用于不同類型的指針轉(zhuǎn)換
class Base {
public:
virtual void fun() {}
};
class Zero: public Base {
public:
virtual void fun() {}
};
int main() {
Base *pb = new Base;
(dynamic_cast<Zero*>(pb)) -> fun(); //由于實際指向的是基類，所以此轉(zhuǎn)換失敗，返回NULL，導(dǎo)致運行時錯誤
delete pb;
return 0;
}
7. 指針與引用的差異
a. 初始化：指針可以不初始化；引用必須在定義時初始化
b. 非空性：指針可以為NULL，因而指針可能是無效的；引用不能為空，因而引用總是有效的
c. 內(nèi)存占用：指針要占用內(nèi)存，引用不占 -> 引用只是一個邏輯概念，通常在編譯時就優(yōu)化掉了
d. 可修改性：指針可以重新指向其它變量；引用不可以
《Effective C＋＋》：在一般情況下，引用和指針是一樣的，但是根據(jù)條款23：在返回一個對象時，盡量不要用引用，而是用指針
8. 指針與句柄(handle)
指針標(biāo)記一個內(nèi)存的地址
句柄是Windows用來標(biāo)識被應(yīng)用程序建立或使用的對象（窗口，菜單，內(nèi)存等）的唯一整數(shù)。從構(gòu)造上看，句柄是一個指針，但其不指向存儲對象的內(nèi)存位置，而是一個包含了對象所在的內(nèi)存位置的結(jié)構(gòu)（結(jié)構(gòu)的復(fù)雜度由所指的對象決定）
9. 指針與淺拷貝
淺拷貝在復(fù)制指針時，只是單純地將指針指向同一內(nèi)存，并不對所指向的內(nèi)容進(jìn)行復(fù)制。因而，當(dāng)成員變量有指針時，最好考慮是否要寫深拷貝函數(shù)和賦值函數(shù)
class Zero {
public:
Zero(): ptr(NULL) {}
~Zero() { if( ptr ) delete[] ptr; }
char* ptr;
};
int main() {
Zero z;
z.ptr = new char[100];
strcpy(z.ptr, "zero");
vector<Zero> * vz = new vector<Zero>();
vz->push_back(z);
delete vz;
return 0;
} //退出main時會出現(xiàn)運行時錯誤
由于Zero沒有定義拷貝函數(shù)，所以有一個默認(rèn)的淺拷貝函數(shù)。在main函數(shù)中，delete vz已經(jīng)釋放過一次ptr指向的內(nèi)存，然后在離開main的作用域時z的析構(gòu)函數(shù)啟動，再次釋放該內(nèi)存
10. 迭代器失效
在容器中增加/刪除元素時，可能會使部分或者全部的迭代器失效
11. C++編譯器默認(rèn)產(chǎn)生的成員函數(shù)
構(gòu)造函數(shù)，析構(gòu)函數(shù)，拷貝函數(shù)，賦值函數(shù)
12. 類中靜態(tài)成員變量與常量
a. 靜態(tài)成員變量一定要在類外初始化
b. 成員常量一定要在初始化列表初始化
c. 靜態(tài)成員常量一定要初始化，初始化時可以直接在聲明時寫上，也可以像一般的靜態(tài)成員變量那樣寫
class Zero {
public:
Zero():lin2(1) {}
private:
static int lin;
const int lin2;
static const int lin3 = 1;
};
int Zero::lin = 0;
13. 初始化列表的初始化順序根據(jù)成員變量的聲明順序執(zhí)行
class Zero { //不要寫這樣的代碼
public:
Zero(int i):lin2(i), lin1(lin2) {} //此時先初始化lin1，再初始化lin2，因而最后的結(jié)果是lin1的值是隨機數(shù)，lin2的值是i
private:
int lin1;
int lin2;
};
14. 構(gòu)造函數(shù)不可以為virtual，析造函數(shù)有時必須為virtual
虛函數(shù)在運行時動態(tài)綁定，動態(tài)綁定需要知道動態(tài)類型才能進(jìn)行綁定。而一個類的對象在沒有運行構(gòu)造函數(shù)前，其動態(tài)類型不完整，因而無法進(jìn)行動態(tài)綁定
delete指向子類對象的基類指針時，如果析構(gòu)函數(shù)不是virtual，則只會調(diào)用基類的析構(gòu)函數(shù)，從而造成內(nèi)存泄漏
15. C++編譯的程序占用的內(nèi)存
a. stack(棧區(qū)): 由OS自動分配釋放空間，主要用來存放函數(shù)的參數(shù)，局部變量等
b. heap(堆區(qū)): 一般由程序員分配釋放空間， 若程序員不釋放，程序結(jié)束時可能由OS回收
c. static(全局/靜態(tài)區(qū)): 存放全局變量和靜態(tài)變量。值得注意的是，初始化和未初始化的這兩種變量是分開存放的。
d. 文字常量區(qū): 存放常量字符串
e. 程序代碼區(qū): 存放函數(shù)的二進(jìn)制代碼
-------------------------------------------------------------------------------
雜項
1. 不用循環(huán)，判斷一個數(shù)X是否為2的N的次方(N >= 0)
X & (X - 1) //最后結(jié)果為0，則是2的N次方
分析：2，4，8的二進(jìn)制式為10, 100, 1000，當(dāng)其與1, 3, 7的二進(jìn)制式相與時，其結(jié)果為0
2. 不用判斷語句，找出兩個數(shù)中的最大值
((a + b) + abs(a - b)) / 2
3. 不用中間變量，交換兩者的值
a = a ^ b; //得到a與b的哪些位不相同（即一共有多少位不同）
b = a ^ b; //去掉b的不同位，換上a的不同位，從而得到a
a = a ^ b;
4. 寫一個宏FIND，求結(jié)構(gòu)體struc里某個變量相對struc的偏移量
#define FIND(struc, e) (size_t)&(((struc*)0)->e)
解析：(struc*)0將0強制轉(zhuǎn)換為struc*的指針類型，然后再取(struc*)0的成員e的地址，從而得到e離結(jié)構(gòu)體首地址的偏移量
5. 數(shù)組名再取地址
int a[] = {1, 2, 3};
int *ptr = (int*)(&a + 1); //&a相當(dāng)于得到二維數(shù)組指針，因而&a + 1相當(dāng)于移動一行
printf("%d\n", *(ptr - 1)); //輸出3
6. 指針的移動
int main() {
int *pi = NULL;
pi += 15;
printf("%d\n", pi); //輸出60
return 0;
}
7. 整數(shù)超范圍
如果是有符號數(shù)，那么最大正整數(shù) + 1 等于最小負(fù)整數(shù)
如果是無符號數(shù)，那么最大正整數(shù) + 1 等于零
bool IsOdd(int i) {
return (i & 1) == 1; //不要寫成(i % 2) == 1，因為這樣寫判斷負(fù)數(shù)時會出問題
}
int main() {
for(int i = 0xFFFFFFFF; i <= 0x7FFFFFFF; ++i) { //這會陷入死循環(huán)，因為最大正整數(shù) + 1 等于最小負(fù)數(shù)
cout<<i<<" is "<<IsOdd(i) ? "odd" : "even"<<endl;
}
return 0;
}
8. 基類指針與子類指針
class Base {
int a;
};
class Zero: public Base {
int b;
};
int main() {
Zero *pz = new Zero();
Base *pb = dynamic_cast<Base*>(pz);
(pz == pb) ? (cout<<"Yes\n") : (cout<<"No\n"); //VS2010輸出"Yes"
(int(pz) == int(pb)) ? (cout<<"Yes\n") : (cout<<"No\n"); //VS2010輸出"Yes"
return 0;
}
9. strcpy的寫法
char* strcpy(char* dst, const char* src) { //返回char*是為了方便鏈?zhǔn)秸{(diào)用
assert( (src != NULL) && (dst != NULL) ); //特別注意檢查
char* tmp = dst;
while( *dst++ = *src++ ); //后綴++優(yōu)先級高
return tmp;
}
10. 概率題
int main() {
int cnt = 0;
for(int i = 0; i < 10000; ++i) {
int x = rand();
int y = rand();
if( x * x + y * y < RAND_MAX * RAND_MAX ) ++cnt; //實質(zhì)上是1/4圓與正方形的面積的比較
}
printf("%d\n", cnt); //結(jié)果約為PI/4 * 10000
}
11. 以下程序在編譯時，哪句會出錯
struct Zero {
void Lin() {}
};
int main() {
Zero z(); //這樣寫會被編譯器認(rèn)為是聲明一個函數(shù)，而不是調(diào)用構(gòu)造函數(shù)
z.lin(); //這句會出錯，因為此時的z被認(rèn)為是未聲明的變量
return 0;
}
12. 各種排序總結(jié)
| 算法 | 穩(wěn)定性 | 時間復(fù)雜度 | 空間復(fù)雜度 | 備注 |
| 選擇排序 | F | O(n^2) | O(1) | |
| 插入排序 | T | O(n^2) | O(1) | 當(dāng)序列有序時，時間復(fù)雜度為O(n) |
| 冒泡排序 | T | O(n^2) | O(1) | 當(dāng)序列有序時，時間復(fù)雜度為O(n) |
| 希爾排序 | F | O(nlogn) | O(1) | 具體的時間復(fù)雜度與所選的增量序列有關(guān) |
| 歸并排序 | T | O(nlogn) | O(n) | |
| 堆排序 | F | O(nlogn) | O(1) | |
| 快速排序 | F | O(nlogn) | O(logn) | 當(dāng)序列有序時，時間復(fù)雜度惡化為O(n^2) |
| 桶排序 | T | O(n) | O(k) |
喜歡 
頂
難過
囧
圍觀
無聊
