這篇C++萬(wàn)字長(zhǎng)文，幫你拿下字節(jié)面試

shared_ptr 指針的實(shí)現(xiàn)

template<typename T> class Shared_ptr {private: T *ptr; int *use_count; // 用指針保證指向同一塊地址public: Shared_ptr() { ptr = nullptr; use_count = nullptr; cout << "Created" << endl; } Shared_ptr(T *p){ ptr = p; use_count = new int(1); cout << "Created" << endl; } Shared_ptr(const Shared_ptr &other) { ptr = other.ptr; ++(*other.use_count); use_count = other.use_count; cout << "Created" << endl; } Shared_ptr& operator=(const Shared_ptr &other) { if(this == &other) return *this; (*other.use_count)++; if(ptr && --(*use_count) == 0) { delete ptr; delete use_count; } ptr = other.ptr; use_count = other.use_count; return *this; } T& operator*() { // 返回指針的引用 return *ptr; } T* operator->() { return ptr; } int get_use_count() { if(use_count == nullptr) return 0; return *use_count; } ~Shared_ptr() { if(ptr && --(*use_count) == 0) { delete ptr; delete use_count; cout << "Destroy" << endl; } }};

構(gòu)造函數(shù)不可以是虛函數(shù)

1. 從存儲(chǔ)空間角度，虛函數(shù)對(duì)應(yīng)一個(gè)虛函數(shù)表，而指向虛函數(shù)表的虛函數(shù)指針是存儲(chǔ)區(qū)對(duì)象內(nèi)存內(nèi)的。如果構(gòu)造函數(shù)是虛函數(shù)，則需要通過(guò)虛函數(shù)表來(lái)調(diào)用，而對(duì)象還沒(méi)有構(gòu)造出來(lái)，無(wú)法找到虛函數(shù)表。
2. 從使用角度，虛函數(shù)主要用于信息不全的情況下，使子類(lèi)重寫(xiě)的函數(shù)能得到對(duì)應(yīng)的調(diào)用。構(gòu)造函數(shù)本身就是要初始化對(duì)象，所以用虛函數(shù)沒(méi)有意義。

平衡樹(shù)(AVL)、伸展樹(shù)(Splay)、紅黑樹(shù)

1. 平衡樹(shù)：
1. 優(yōu)點(diǎn)：查找、插入、刪除最壞復(fù)雜度都是 O(logN)。操作簡(jiǎn)單。
2. 缺點(diǎn)：插入、刪除的旋轉(zhuǎn)成本不菲。刪除操作后，最多旋轉(zhuǎn) O(logN) 次，若頻繁進(jìn)行插入、刪除操作，得不償失
2. 伸展樹(shù)
1. 優(yōu)點(diǎn)：局部性強(qiáng): 1)剛剛訪問(wèn)過(guò)的節(jié)點(diǎn)，可能在不久后再次被訪問(wèn)到。2) 將要訪問(wèn)的節(jié)點(diǎn)，可能在不久之前剛剛被訪問(wèn)的節(jié)點(diǎn)附近。
2. 缺點(diǎn)：不能保證單次最壞情況的出現(xiàn)，不適用于敏感場(chǎng)合。復(fù)雜度不好分析，均攤 O(logN)。
3. 紅黑樹(shù)
1. 優(yōu)點(diǎn)：查找、插入、刪除的復(fù)雜度都是 O(logN)。插入之后最多旋轉(zhuǎn) 2 次，刪除之后最多旋轉(zhuǎn) 1 次能夠再次達(dá)到平衡狀態(tài)。
2. 缺點(diǎn)：左右子樹(shù)高度相差比 AVL 大。

AVL 和 紅黑樹(shù)比較

AVL 是嚴(yán)格的平衡樹(shù)，因此在插入/刪除節(jié)點(diǎn)時(shí)，根據(jù)不同的情況，旋轉(zhuǎn)的次數(shù)比紅黑樹(shù)多。

紅黑樹(shù)是弱平衡的，用非嚴(yán)格的平衡換取插入/刪除節(jié)點(diǎn)時(shí)旋轉(zhuǎn)次數(shù)的降低。

兩者都是平衡樹(shù)，那么查找的時(shí)候，查找效率就會(huì)和樹(shù)的高度有關(guān)，所以 AVL 會(huì)比紅黑樹(shù)更優(yōu)。

有了 AVL 為什么還要紅黑樹(shù)

雖然 AVL 解決的二叉查找樹(shù)退化成鏈表的情況，但是平衡樹(shù)要求每個(gè)節(jié)點(diǎn)左子樹(shù)和右子樹(shù)高度相差最多為 1。這個(gè)要求太嚴(yán)格了，導(dǎo)致插入/刪除的時(shí)候需要不斷的旋轉(zhuǎn)來(lái)達(dá)到這個(gè)要求。而紅黑樹(shù)不會(huì)頻繁的破壞規(guī)則，不用頻繁的調(diào)整，紅黑樹(shù)是一種不大嚴(yán)格的平衡樹(shù)，但是換來(lái)了效率的提高，是一種折中的方案。

紅黑樹(shù)

面試常問(wèn)：什么是紅黑樹(shù)?

wiki紅黑樹(shù)

紅黑樹(shù)性質(zhì)

1. 節(jié)點(diǎn)一定是紅色或黑色。
2. 根節(jié)點(diǎn)是黑色。
3. 每個(gè)葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)(NIL)。
4. 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色。
5. 從任一節(jié)點(diǎn)到其每個(gè)葉子節(jié)點(diǎn)的所有路徑上都包含相同的黑色節(jié)點(diǎn)數(shù)。

這些性質(zhì)強(qiáng)制了紅黑樹(shù)從根到葉子的最長(zhǎng)路徑不會(huì)超過(guò)最短路徑的兩倍。性質(zhì) 4 導(dǎo)致了路徑不能有兩個(gè)相連的紅色節(jié)點(diǎn)，最短的可能路徑都是黑色節(jié)點(diǎn)，最長(zhǎng)的可能路徑有交替的紅色和黑色節(jié)點(diǎn)。因?yàn)楦鶕?jù)性質(zhì) 5 所有最長(zhǎng)的路徑都有相同數(shù)目的黑色節(jié)點(diǎn)，這就表明了沒(méi)有路徑能多于任何其他路徑的兩倍長(zhǎng)。

紅黑樹(shù)的擴(kuò)展

可以給每個(gè)階段加上 size 域，表示以節(jié)點(diǎn) x 為根的子樹(shù)的節(jié)點(diǎn)數(shù)。

size[x] = size[x->left]+size[x->right]

通過(guò) size 就可以獲得比 x 小的節(jié)點(diǎn)數(shù)目和第 x 小的節(jié)點(diǎn)。

i++ 和 ++i 的區(qū)別

++i 返回對(duì)象的引用，i++ 必須產(chǎn)生一個(gè)臨時(shí)對(duì)象保存更改前對(duì)象的值并返回，所以導(dǎo)致在大對(duì)象的時(shí)候產(chǎn)生的比較大的復(fù)制開(kāi)銷(xiāo)，效率較低。

// ++iint& int::operator++() { *this += 1; return *this;}// i++const int int::operator++(int) { int old_value = *this; ++(*this); return old_value;}

拷貝構(gòu)造函數(shù)

Node a;Node b(a);Node c = a;

這里的 b 和 c 都是一開(kāi)始是不存在的，是通過(guò) a 對(duì)象來(lái)構(gòu)造和初始化的。

拷貝構(gòu)造函數(shù)重載形式:

Node (const Node &other) { 
}

如果用戶沒(méi)有自定義拷貝構(gòu)造函數(shù)并且用到了拷貝構(gòu)造函數(shù)，則編譯器會(huì)生成默認(rèn)的拷貝構(gòu)造函數(shù)。

在 C++ 中，這三種情況下拷貝構(gòu)造函數(shù)會(huì)被使用：

1. 一個(gè)對(duì)象以值傳遞的形式傳入函數(shù)內(nèi)。
2. 一個(gè)對(duì)象以值傳遞的形式從函數(shù)返回。
3. 一個(gè)對(duì)象通過(guò)另一個(gè)對(duì)象初始化。

優(yōu)點(diǎn)：可以很容易的復(fù)制對(duì)象。

缺點(diǎn)：對(duì)象的隱式拷貝是 C++ 中是錯(cuò)誤和性能問(wèn)題的來(lái)源之一。它也降低了代碼的可讀性，并使得對(duì)象子程序中的傳遞和改變變得難以跟蹤。

賦值函數(shù)

Node a;Node b;b = a;

這里的 b 已經(jīng)存在的，在通過(guò) a 賦值給 b。

賦值函數(shù)重載形式：

Node& operator=(const Node &other) {
}

拷貝構(gòu)造函數(shù)和賦值函數(shù)區(qū)別

1. 拷貝構(gòu)造函數(shù)是在對(duì)象初始化時(shí)，分配一塊空間并初始化，而賦值函數(shù)是對(duì)已經(jīng)分配空間的對(duì)象進(jìn)行賦值操作。
2. 實(shí)現(xiàn)上，拷貝構(gòu)造函數(shù)是構(gòu)造函數(shù)，通過(guò)參數(shù)的對(duì)象初始化產(chǎn)生一個(gè)對(duì)象。賦值函數(shù)則是把一個(gè)對(duì)象賦值給另一個(gè)對(duì)象，需要先判斷兩個(gè)對(duì)象是否是同一個(gè)對(duì)象，若是則什么都不做，直接返回，若不是則需要先釋放原對(duì)象內(nèi)存，在賦值。(可以參考 shared_ptr 實(shí)現(xiàn))

總結(jié)：

• 對(duì)象不存在，沒(méi)有通過(guò)別的對(duì)象來(lái)初始化，就是構(gòu)造函數(shù)。
• 對(duì)象不存在，通過(guò)別的對(duì)象來(lái)初始化，就是拷貝構(gòu)造函數(shù)。
• 對(duì)象存在，通過(guò)別的對(duì)象來(lái)初始化，就是賦值函數(shù)。

虛函數(shù)和內(nèi)聯(lián)函數(shù)

內(nèi)聯(lián)函數(shù)通常就是將它在調(diào)用處 "內(nèi)斂的" 展開(kāi)，消除反復(fù)調(diào)用的額外開(kāi)銷(xiāo)，但是如果函數(shù)太長(zhǎng)，會(huì)使代碼臃腫，反而降低效率。

虛函數(shù)可以是內(nèi)聯(lián)函數(shù)，無(wú)論是顯式還是隱式，inline 都只是一個(gè)申請(qǐng)，最終由編譯器決定是否內(nèi)聯(lián)。所以可以用 inline 修飾虛函數(shù)，但虛函數(shù)表現(xiàn)多態(tài)性時(shí)，不可以內(nèi)聯(lián)，只有當(dāng)知道調(diào)用哪個(gè)類(lèi)的函數(shù)時(shí)，才可以是內(nèi)聯(lián)。

空類(lèi)的大小

在 C++ 中規(guī)定類(lèi)的大小不為 0，空類(lèi)大小為 1，當(dāng)類(lèi)不包含虛函數(shù)和非靜態(tài)成員時(shí)，其對(duì)象大小也為 1。若存在虛函數(shù)，則需要存儲(chǔ)一個(gè)虛函數(shù)指針大小，在 32 位上為 4 字節(jié)。

結(jié)構(gòu)體字節(jié)對(duì)齊

class A {};class B{public: A x;};sizeof(B) = 1
class B{public: inline virtual fun() { }};sizeof(B) = 4
class B{public: A x; inline virtual fun() { }};sizeof(B) = 8

可以發(fā)現(xiàn)最后一個(gè)的 sizeof 并不是單純的 1+4=5，而直接變成了 8，因?yàn)榇嬖诮Y(jié)構(gòu)體的字節(jié)對(duì)齊規(guī)則。

結(jié)構(gòu)體字節(jié)對(duì)齊的根本原因：1) 移植性更好，某些平臺(tái)只能在特定的地址訪問(wèn)特定的數(shù)據(jù)。2) 提高存取數(shù)據(jù)的速度，CPU 通常按塊讀取數(shù)據(jù)會(huì)更加快速。

結(jié)構(gòu)體字節(jié)對(duì)齊原則：

1. 無(wú) #pragma pack
1. 結(jié)構(gòu)內(nèi)部各成員首地址必然是自身大小的整數(shù)倍。
2. sizeof 最終結(jié)果必然是結(jié)構(gòu)內(nèi)部最大成員的整數(shù)倍，不夠補(bǔ)齊
2. 有 #pragma pack(n)
1. 結(jié)構(gòu)內(nèi)部各成員首地址必然是 min(n, 自身大小) 的整數(shù)倍。
2. sizeof 最終結(jié)果必然是 min(n, 結(jié)構(gòu)內(nèi)部最大成員) 的整數(shù)倍，不夠補(bǔ)齊。

#includeusing namespace std;
class A { char a; int b; short c;};class B { int a; char b; short c;};
int main() { cout << sizeof(A) << endl; // 12 cout << sizeof(B) << endl; // 8 return 0;}

造成不同結(jié)果的原理在于：

• 對(duì)于 class A 來(lái)說(shuō)，內(nèi)部字節(jié)為

• 對(duì)于 class B 來(lái)說(shuō)，內(nèi)部字節(jié)為

有 static、virtual 之類(lèi)的一個(gè)類(lèi)的內(nèi)存分布

• static 修飾成員變量
• 靜態(tài)成員變量在 全局存儲(chǔ)區(qū) 分配內(nèi)存，本類(lèi)的所有對(duì)象共享，在還沒(méi)生成類(lèi)對(duì)象之前也可以使用。
• static 修飾成員函數(shù)
• 靜態(tài)成員函數(shù)在 代碼區(qū) 分配內(nèi)存。靜態(tài)成員函數(shù)和非靜態(tài)成員函數(shù)的區(qū)別在于非靜態(tài)成員函數(shù)存在 this 指針，而靜態(tài)成員函數(shù)不存在，所以靜態(tài)成員函數(shù)沒(méi)有類(lèi)對(duì)象也可以調(diào)用。
• virtual
• 虛函數(shù)表存儲(chǔ)在常量區(qū)，也就是只讀數(shù)據(jù)段
• 虛函數(shù)指針存儲(chǔ)在對(duì)象內(nèi)，如果對(duì)象是局部變量，則存儲(chǔ)在棧區(qū)內(nèi)。

使用宏定義求結(jié)構(gòu)體成員偏移量

#include#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE*)0)->MEMBER)/*(TYPE*)0 將零轉(zhuǎn)型成 TYPE 類(lèi)型指針((TYPE*)0->MEMBER) 訪問(wèn)結(jié)構(gòu)體中的成員&((TYPE*)0->MEMBER) 取出數(shù)據(jù)成員地址，也就是相對(duì)于零的偏移量(size_t) & ((TYPE*)0)->MEMBER) 將結(jié)果轉(zhuǎn)換成 size_t 類(lèi)型。*/
struct Node { char a; short b; double c; int d;};
int main() { printf("%d\n", offsetof(Node, a)); printf("%d\n", offsetof(Node, b)); printf("%d\n", offsetof(Node, c)); printf("%d\n", offsetof(Node, d)); return 0;}

size_t 在可以理解成 unsigned\ \ int，在不同平臺(tái)下被 typedef 成不同類(lèi)型。

C++ 中哪些函數(shù)不可以是虛函數(shù)

1. 普通函數(shù)(非成員函數(shù))：普通函數(shù)不屬于類(lèi)成員，不能被繼承。普通函數(shù)只能被重載，不能被重寫(xiě)，因此聲明成虛函數(shù)沒(méi)有意義。
2. 構(gòu)造函數(shù)：構(gòu)造函數(shù)本來(lái)就是為了初始化對(duì)象而存在的，沒(méi)有定義為虛函數(shù)的必要。而且對(duì)象還沒(méi)構(gòu)造出來(lái)，不存在虛函數(shù)指針，也無(wú)法成為虛函數(shù)。
3. 內(nèi)聯(lián)成員函數(shù)：內(nèi)聯(lián)函數(shù)是為了在代碼中直接展開(kāi)，減少調(diào)用函數(shù)的代價(jià)，是在編譯的時(shí)候展開(kāi)。而虛函數(shù)需要?jiǎng)討B(tài)綁定，這不可能統(tǒng)一。只有當(dāng)編譯器知道調(diào)用的是哪個(gè)類(lèi)的函數(shù)時(shí)，才可以展開(kāi)。
4. 靜態(tài)成員函數(shù)：對(duì)于所有對(duì)象都共享一個(gè)函數(shù)，沒(méi)有動(dòng)態(tài)綁定的必要。
5. 友元函數(shù)：C++ 不支持友元函數(shù)的繼承，自然不能是虛函數(shù)。

手撕堆排序

[堆排序的思路以及代碼的實(shí)現(xiàn)

](https://blog.csdn.net/qq_36573828/article/details/80261541)

令 k = log_2n

初始化堆復(fù)雜度 O(N) 。分析：假設(shè)每一次都到葉子的父節(jié)點(diǎn)

排序重建堆復(fù)雜度 。分析：假設(shè)每一次都到葉子節(jié)點(diǎn)。

void adjust(vector<int>& nums, int i, int n) { while(2*i+1 < n) { int j = 2*i+1; if(j+11]) j++; if(nums[i] > nums[j]) break; swap(nums[i], nums[j]); i = j; }}
vector<int> sortArray(vector<int>& nums) { if(nums.size() <= 1) return nums; int n = nums.size(); for(int i=n/2-1; i>=0; i--) adjust(nums, i, n); // 初始化堆 for(int i=n-1; i>0; i--) { // 排序重建堆 swap(nums[i], nums[0]); adjust(nums, 0, i); } return nums;}

main 函數(shù)前后還會(huì)執(zhí)行什么

全局對(duì)象的構(gòu)造在 main 函數(shù)之前完成，全局對(duì)象的析構(gòu)在 main 函數(shù)之后完成。

const 和 define

1. define 在預(yù)編譯階段起作用，const 在編譯、運(yùn)行的時(shí)候起作用。
2. define 只是簡(jiǎn)單的替換功能，沒(méi)有類(lèi)型檢查功能，const 有類(lèi)型檢查功能，可以避免一些錯(cuò)誤。
3. define 在預(yù)編譯階段就替換掉了，無(wú)法調(diào)試，const 可以通過(guò)集成化工具調(diào)試。

inline 和 define

1. inline 在編譯時(shí)展開(kāi)，define 在預(yù)編譯時(shí)展開(kāi)。
2. inline 可以進(jìn)行類(lèi)型安全檢查，define 只是簡(jiǎn)單的替換。
3. inline 是函數(shù)，define 不是函數(shù)。
4. define 最好用括號(hào)括起來(lái)，不然會(huì)產(chǎn)生二義性，inline 不會(huì)。
5. inline 是一個(gè)建議，可以不展開(kāi)，define 一定要展開(kāi)。

inline 函數(shù)的要求

1. 含有遞歸調(diào)用的函數(shù)不能設(shè)置為 inline
2. 循環(huán)語(yǔ)句和 switch 語(yǔ)句，無(wú)法設(shè)置為 inline
3. inline 函數(shù)內(nèi)的代碼應(yīng)很短小。最好不超過(guò)５行

聲明和定義

• 變量定義：為變量分配空間，還可以為變量指定初始值。
• 變量聲明：向程序表明變量的類(lèi)型和名字，但不分配空間?？梢酝ㄟ^(guò) extern 關(guān)鍵字來(lái)聲明而不定義，extern 告訴編譯器變量在別的地方定義了。

1. 定義也是聲明，聲明不是定義。例如：

• extern int i 聲明且不定義 i 變量， int i 聲明且定義了 i 變量。

• extern int i=10 此時(shí)看成定義了 i 變量。

面向過(guò)程和面向?qū)ο?/span>

面向過(guò)程就是分析出解決問(wèn)題所需要的步驟，然后用函數(shù)把步驟一步一步的實(shí)現(xiàn)。優(yōu)點(diǎn)在于性能高。

面向?qū)ο缶褪菢?gòu)成問(wèn)題事務(wù)分解成各個(gè)對(duì)象，建立對(duì)象的目的不是為了完成一個(gè)步驟，而是為了描述某個(gè)對(duì)象在整個(gè)解決問(wèn)題的步驟中的行為。優(yōu)點(diǎn)在于易維護(hù)、易復(fù)用、易擴(kuò)展，使系統(tǒng)更加靈活。

堆區(qū)和自由存儲(chǔ)區(qū)

基本上所有的 C++ 編譯器默認(rèn)使用堆來(lái)實(shí)現(xiàn)自由存儲(chǔ)，也就是缺省的 new/delete 是通過(guò) malloc/free 方式來(lái)實(shí)現(xiàn)的，這時(shí)候可以說(shuō)他從堆上分配內(nèi)存，也可以說(shuō)他從自由存儲(chǔ)區(qū)分配內(nèi)存。但程序員可以通過(guò)重載操作符，改用其他內(nèi)存實(shí)現(xiàn)自由存儲(chǔ)。

堆區(qū)是操作系統(tǒng)維護(hù)的一塊內(nèi)存，而自由存儲(chǔ)區(qū)是 C++ 中用于 new/delete 動(dòng)態(tài)分配和釋放對(duì)象的 抽象概念。

堆區(qū)和棧區(qū)

#ifndef 和 #endif 的作用

在大的軟件工程中，可能多個(gè)文件包含同一個(gè)頭文件，當(dāng)這些文件鏈接成可執(zhí)行文件的時(shí)候，就會(huì)造成大量的 "重定義" 錯(cuò)誤，可以通過(guò) #ifndef 來(lái)避免這個(gè)錯(cuò)誤。

#ifndef _A_H#define _A_H
#endif

這樣就可以保證 a.h 被定義一次。

explicit 關(guān)鍵字

類(lèi)的構(gòu)造函數(shù)存在隱式轉(zhuǎn)換，如果想要避免這個(gè)功能，就可以通過(guò) explicit 關(guān)鍵字來(lái)將構(gòu)造函數(shù)聲明成顯式的。

菱形繼承

class A { public: void fun() { cout << "!!!" << endl; }};class B : public A{};class C : public A{};class D : public B, public C {};

int main() { // freopen("in", "r", stdin); D d; d.fun();; return 0;}

像上面的繼承關(guān)系，當(dāng)繼承關(guān)系形成菱形時(shí)，D 中保存了兩份 A，在調(diào)用 d.fun() 時(shí)就會(huì)出現(xiàn)調(diào)用不明確的問(wèn)題。

這種情況由兩種解決方法：

1. 使用域限定訪問(wèn)的函數(shù)。也就是將 d.fun 修改成 d.B::fun 或者 d.C::fun。
2. 第二種方法就是使用虛繼承。虛繼承解決了從不同途徑繼承來(lái)的同名數(shù)據(jù)成員在內(nèi)存中有不同的拷貝造成數(shù)據(jù)不一致的問(wèn)題，將共同基類(lèi)設(shè)置成虛基類(lèi)，這時(shí)從不同路徑繼承過(guò)來(lái)的同名數(shù)據(jù)成員在內(nèi)存中就只有一個(gè)拷貝。操作方法就是在 B 和 C 的繼承處加上 virtual 修飾。

虛繼承底層實(shí)現(xiàn)一般通過(guò)虛基類(lèi)指針和虛基類(lèi)表實(shí)現(xiàn)。每個(gè)虛繼承的子類(lèi)都有一個(gè)虛基類(lèi)指針和一個(gè)虛基類(lèi)表，虛表中記錄了虛基類(lèi)與本類(lèi)的偏移地址。通過(guò)偏移地址，這樣就找到了虛基類(lèi)成員，節(jié)省了存儲(chǔ)空間。

weak_ptr 指向的對(duì)象被銷(xiāo)毀

首先 weak_ptr 是一種不控制對(duì)象生存周期的智能指針，它指向一個(gè) shared_ptr 管理的對(duì)象。一旦最后一個(gè)指向?qū)ο蟮?shared_ptr 被銷(xiāo)毀，那么無(wú)論是否有 weak_ptr 指向該對(duì)象，都會(huì)釋放資源。

weak_ptr 不能直接指向?qū)ο?，需要先調(diào)用 lock，而 lock 會(huì)先判斷該對(duì)象是否還存在。

如果存在 lock 就會(huì)返回一個(gè)指向該對(duì)象的 shared_ptr，并且該對(duì)象的 shared_ptr 的引用計(jì)數(shù)加一。

如果在 weak_ptr 獲得過(guò)程中，原本的所有 shared_ptr 被銷(xiāo)毀，那么該對(duì)象的生命周期會(huì)延長(zhǎng)到這個(gè)臨時(shí) shared_ptr 銷(xiāo)毀為止。

lambda 表達(dá)式

lambda 表達(dá)式定義一個(gè)匿名函數(shù)，并且可以捕獲一定范圍內(nèi)的變量，基本格式如下：

[capture](params) mutable ->ReturnType {statement}

• [capture]：捕獲列表，可以捕獲上下文的變量來(lái)供 lambda 函數(shù)使用
• [var]：值傳遞的方式捕獲 var
• [&var]：引用傳遞的方式捕獲 var
• [=]：值傳遞的方式捕獲父作用域的所有變量。
• [&]：引用傳遞的方式捕獲父作用域的所有變量。
• [this]：值傳遞的方式捕獲當(dāng)前 this 指針。
• (params)：參數(shù)列表，和普通函數(shù)參數(shù)列表一致，如果不傳參數(shù)可以和 () 一起忽略。
• mutable 修飾符號(hào)，默認(rèn)情況下，lambda 表達(dá)式是一個(gè) const 函數(shù)，可以用 mutable 取消他的常量性。若使用 mutable 修飾，參數(shù)列表不可省略。
• **->**ReturnType：返回值類(lèi)型。若是 void，可以省略。
• {statement}：函數(shù)主體，和普通函數(shù)一樣。

lambda 表達(dá)式優(yōu)點(diǎn)在于代碼簡(jiǎn)潔，容易進(jìn)行并行計(jì)算。缺點(diǎn)在于在非并行計(jì)算中，效率未必有 for 循環(huán)快，并且不容易調(diào)試，對(duì)于沒(méi)學(xué)過(guò)的程序員來(lái)說(shuō)可讀性差。

#includeusing namespace std;
int main() { vector<int> g{9, 2, 1, 2, 5, 6, 2}; int ans = 1; sort(g.begin(), g.end(), [](int a, int b) ->bool{return a>b;}); for_each(g.begin(), g.end(), [&ans](int x){cout << x << " ", ans = ans*x;}); cout << "\nmul = " << ans << endl; return 0;}/*9 6 5 2 2 2 1mul = 2160*/

存在全局變量和局部變量時(shí)，訪問(wèn)全局變量

可以通過(guò)全局作用符號(hào) :: 來(lái)完成

int a = 10;
int main() { // freopen("in", "r", stdin); int a = 20; cout << a << endl; cout << ::a << endl; return 0;}

全局變量的初始化的順序

同一文件中的全局變量按照聲明順序，不同文件之間的全局變量初始化順序不確定。

如果要保證初始化次序的話，需要通過(guò)在函數(shù)使用靜態(tài)局部變量并返回來(lái)實(shí)現(xiàn)。

class FileSystem{...};FileSystem & tfs(){ static FileSystem fs;//定義并初始化一個(gè)static對(duì)象 return fs;}

淺拷貝和深拷貝

• 淺拷貝：源對(duì)象和拷貝對(duì)象共用一份實(shí)體，僅僅是引用的變量名不同。對(duì)其中任意一個(gè)修改，都會(huì)影響另一個(gè)對(duì)象。
• 深拷貝：源對(duì)象和拷貝對(duì)象相互獨(dú)立。對(duì)其中一個(gè)對(duì)象修改，不會(huì)影響另一個(gè)對(duì)象。
• 兩個(gè)對(duì)象指向同塊內(nèi)存，當(dāng)析構(gòu)函數(shù)釋放內(nèi)存時(shí)，會(huì)引起錯(cuò)誤。

從這個(gè)例子可以看出，b 通過(guò)默認(rèn)拷貝函數(shù)進(jìn)行初始化，然而進(jìn)行的是淺拷貝，導(dǎo)致對(duì) a 進(jìn)行修改的時(shí)候，b 的存儲(chǔ)值也被修改。

struct Node { char* s; Node(char *str) { s = new char[100]; strcpy(s, str); } /* 手動(dòng)實(shí)現(xiàn)拷貝構(gòu)造函數(shù) Node(const Node &other) { s = new char[100]; strcpy(s, other.s); } */};
int main() { // freopen("in", "r", stdin); Node a("hello"); Node b(a); cout << b.s << endl; strcpy(a.s, "bad copy"); cout << b.s << endl; return 0;}

正確的寫(xiě)法應(yīng)該自己寫(xiě)一個(gè)拷貝函數(shù)，而不是用默認(rèn)的，應(yīng)該盡量的避免淺拷貝。

如何控制一個(gè)類(lèi)只能在堆或棧上創(chuàng)建對(duì)象

在 C++ 中創(chuàng)建對(duì)象的方法有兩種，一種是靜態(tài)建立，一個(gè)是動(dòng)態(tài)建立。

• 靜態(tài)建立由編譯器為對(duì)象分配內(nèi)存，通過(guò)調(diào)用構(gòu)造函數(shù)實(shí)現(xiàn)。這種方法創(chuàng)建的對(duì)象會(huì)在棧上。
• 靜態(tài)建立由用戶為對(duì)象分配內(nèi)存，通過(guò) new 來(lái)實(shí)現(xiàn)，間接調(diào)用構(gòu)造函數(shù)。這種方法創(chuàng)建的對(duì)象會(huì)在堆上。

只能從堆上分配對(duì)象：

當(dāng)建立的對(duì)象在棧上時(shí)，由編譯器分配內(nèi)存，因此會(huì)涉及到構(gòu)造函數(shù)和析構(gòu)函數(shù)。那么如果無(wú)法調(diào)用析構(gòu)函數(shù)呢？也就是說(shuō)析構(gòu)函數(shù)是 private 的，編譯器會(huì)先檢查析構(gòu)函數(shù)的訪問(wèn)性，由于無(wú)法訪問(wèn)，也就防止了靜態(tài)建立。

但這種方法存在一種缺點(diǎn)，就是把析構(gòu)函數(shù)設(shè)成 private 后，如果這個(gè)類(lèi)要作為基類(lèi)的話，析構(gòu)函數(shù)應(yīng)該設(shè)成虛函數(shù)，而設(shè)成 private 后子類(lèi)就無(wú)法重寫(xiě)析構(gòu)函數(shù)，所以應(yīng)該把析構(gòu)函數(shù)設(shè)成 protected。然后額外設(shè)置一個(gè)接口來(lái) delete。

class Node {public: Node(){}; void Destroy() { delete this; }protected: ~Node(){};};

此時(shí)解決了靜態(tài)建立的過(guò)程，但使用時(shí)，通過(guò) new 創(chuàng)建對(duì)象，通過(guò) Destroy 函數(shù)釋放對(duì)象，為了統(tǒng)一，可以把構(gòu)造函數(shù)和析構(gòu)函數(shù)都設(shè)成 protected，重寫(xiě)函數(shù)完成構(gòu)造和析構(gòu)過(guò)程。

class Node {public: static Node* Create() { return new Node(); } void Destroy() { delete this; }protected: Node(){}; ~Node(){};};

只能從棧上分配對(duì)象：

同樣的道理，只需要禁止通過(guò)動(dòng)態(tài)建立對(duì)象就可以實(shí)現(xiàn)在棧上分配對(duì)象，所以可以重載 new 和 delete 并設(shè)為 private，使用戶只能靜態(tài)建立對(duì)象。

class Node {public: Node(){}; ~Node(){};private: void* operator new(size_t t){} void operator delete(void* p){}};

memcpy 和 memmove 的實(shí)現(xiàn)

memcpy 可以直接通過(guò)指針自增賦值，但要求源地址和目的地址無(wú)重合。

void mymemmove1(void* s, const void* t, size_t n) {char *ps = static_cast<char*>(s);const char *pt = static_cast<const char*>(t);while(n--) {*ps++ = *pt++;}}

如果源地址和目的地址存在重合，會(huì)因?yàn)榈刂返闹睾蠈?dǎo)致數(shù)據(jù)被覆蓋，所以要通過(guò) memmove 來(lái)實(shí)現(xiàn)，需要從末尾往前自減賦值。

為了加快速度還可以使用 4 字節(jié)賦值的方式

// 直接按字節(jié)進(jìn)行 copyvoid mymemmove1(void* s, const void* t, size_t n) { char *ps = static_cast<char*>(s); const char *pt = static_cast<const char*>(t); if(ps<=pt && pt<=ps+n-1) { ps = ps+n-1; pt = pt+n-1; while(n--) { *ps-- = *pt--; } } else { while(n--) { *ps++ = *pt++; } }}
// 加快速度，每次按 4 字節(jié)進(jìn)行 copyvoid mymemmove2(void *s, const void *t, size_t n) { int *ts = static_cast<int*>(s); const int *tt = static_cast<const int*>(t); char *ps = static_cast<char*>(s); const char *pt = static_cast<const char*>(t); int x = n/4, y = n%4; if(ps<=pt && pt<=ps+n-1) { ps = ps+n-1; pt = pt+n-1; while(y--) { *ps-- = *pt--; } ps++, pt++; ts = reinterpret_cast<int*>(ps); tt = reinterpret_cast<const int*>(pt); ts--, tt--; while(x--) { *ts-- = *tt--; } } else { while(y--) { *ps++ = *pt++; } ts = reinterpret_cast<int*>(ps); tt = reinterpret_cast<const int*>(pt); while(x--) { *ts++ = *tt++; } }}

通過(guò)重載 new/delete 來(lái)檢測(cè)內(nèi)存泄漏的簡(jiǎn)易實(shí)現(xiàn)

講每次 new 產(chǎn)生的內(nèi)存記錄，并在 delete 的時(shí)候刪去記錄，那么最后剩下的就是發(fā)生內(nèi)存泄漏的代碼。

#include using namespace std;
class TraceNew {public: class TraceInfo { private: const char* file; size_t line; public: TraceInfo(); TraceInfo(const char *File, size_t Line); ~TraceInfo(); const char* File() const; size_t Line(); }; TraceNew(); ~TraceNew(); void Add(void*, const char*, size_t); void Remove(void*); void Dump();private: map<void*, TraceInfo> mp;} trace;
TraceNew::TraceInfo::TraceInfo() {}
TraceNew::TraceInfo::TraceInfo(const char *File, size_t Line) : file(File), line(Line) {}
TraceNew::TraceInfo::~TraceInfo() { delete file;}
const char* TraceNew::TraceInfo::File() const { return file;}
size_t TraceNew::TraceInfo::Line() { return line;}
TraceNew::TraceNew() { mp.clear();}
TraceNew::~TraceNew() { Dump(); mp.clear();}
void TraceNew::Add(void *p, const char *file, size_t line) { mp[p] = TraceInfo(file, line);}
void TraceNew::Remove(void *p) { auto it = mp.find(p); if(it != mp.end()) mp.erase(it);}
void TraceNew::Dump() { for(auto it : mp) { cout << it.first << " " << "memory leak on file: " << it.second.File() << " line: " << it.second.Line() << endl; }}
void* operator new(size_t size, const char *file, size_t line) { void* p = malloc(size); trace.Add(p, file, line); return p;}
void* operator new[](size_t size, const char *file, size_t line) { return operator new(size, file, line);}
void operator delete(void *p) { trace.Remove(p); free(p);}
void operator delete[](void *p) { operator delete(p); }
#define new new(__FILE__,__LINE__)
int main() { int *p = new int; int *q = new int[10]; return 0;}
/*0xa71850 memory leak on file: a.cpp line: 900xa719b8 memory leak on file: a.cpp line: 91*/

垃圾回收機(jī)制

之前使用過(guò)，但現(xiàn)在不再使用或者沒(méi)有任何指針再指向的內(nèi)存空間就稱為 "垃圾"。而將這些 "垃圾" 收集起來(lái)以便再次利用的機(jī)制，就被稱為“垃圾回收”。

垃圾回收機(jī)制可以分為兩大類(lèi)：

1. 基于引用計(jì)數(shù)的垃圾回收器

• 系統(tǒng)記錄對(duì)象被引用的次數(shù)。當(dāng)對(duì)象被引用的次數(shù)變?yōu)?0 時(shí)，該對(duì)象即可被視作 "垃圾" 而回收。但難以處理循環(huán)引用的情況。

• 標(biāo)記-清除：對(duì)所有存活對(duì)象進(jìn)行一次全局遍歷來(lái)確定哪些對(duì)象可以回收。從根出發(fā)遍歷一遍找到所有可達(dá)對(duì)象(活對(duì)象)，其它不可達(dá)的對(duì)象就是垃圾對(duì)象，可被回收。
• 標(biāo)記-縮并：直接清除對(duì)象會(huì)造成大量的內(nèi)存碎片，所以調(diào)整所有活的對(duì)象縮并到一起，所有垃圾縮并到一起，然后一次清除。
• 標(biāo)記-拷貝：堆空間分為兩個(gè)部分 From 和 To。剛開(kāi)始系統(tǒng)只從 From 的堆空間里面分配內(nèi)存，當(dāng) From 分配滿的時(shí)候系統(tǒng)就開(kāi)始垃圾回收：從 From 堆空間找出所有的活對(duì)象，拷貝到 To 的堆空間里。這樣一來(lái)，F(xiàn)rom 的堆空間里面就全剩下垃圾了。而對(duì)象被拷貝到 To 里之后，在 To 里是緊湊排列的。接下來(lái)是需要將 From 和 To 交換一下角色，接著從新的 From 里面開(kāi)始分配。

通過(guò)位運(yùn)算實(shí)現(xiàn)加減乘除取模

• 加法操作

對(duì)于每一位而言，在不考慮進(jìn)位的情況下，可以得到

0+0 = 0\\
0+1 = 1\\
1+0 = 1\\
1+1 = 0

顯然，上面的情況符合 異或 操作且只有第四種情況發(fā)生了進(jìn)位，進(jìn)位情況符合 與 操作。在所有發(fā)生進(jìn)位處，應(yīng)該在更高的一位處加一，這個(gè)值可以通過(guò) 左移 操作實(shí)現(xiàn)。那么就可以得到

x+y = x \oplus y + (x \& y)<<1

可以發(fā)現(xiàn)，后面的式子變成了一個(gè)新的加法式，那么只要遞歸計(jì)算即可。當(dāng) (x & y)<<1 == 0 時(shí)，就消除了加法式。

ll add(ll x, ll y) { ll newx = x^y; ll newy = (x&y)<<1; if(newy == 0) return newx; return add(newx, newy);}

• 減法操作

減法操作可以看成

同樣可以通過(guò)加法式得到

ll sub(ll x, ll y) { return add(x, add(~y, 1));}

• 乘法操作

假設(shè) y=1010，則可以關(guān)注于二進(jìn)制上的 1 位，那么可以將 x*y 做出拆解

\begin{aligned} xy &= x1010\ &= x1000 + x0010
\end{aligned}

而這個(gè)當(dāng)乘數(shù)只有一個(gè) 1 時(shí)，可以通過(guò)二進(jìn)制的左移操作實(shí)現(xiàn)。

ll mul(ll x, ll y) { ll ans = 0; int flag = x^y; x = x<0 ? add(~x, 1) : x; y = y<0 ? add(~y, 1) : y; for(int i=0; (1ll< if(y&(1ll< ans = add(ans, x< } } return flag<0 ? add(~ans, 1) : ans;}

• 除法操作

和乘法操作思想一樣，枚舉答案每一位是否為 1，通過(guò)左移來(lái)得到乘積并減去。先從大的開(kāi)始找，如果有一位是 1，那么就在答案將這一位設(shè)成 1。

ll divide(ll x, ll y) { ll ans = 0; int flag = x^y; x = x<0 ? add(~x, 1) : x; y = y<0 ? add(~y, 1) : y; for(int i=31; i>=0; i--) { if(x >= (1ll*y< ans |= (1ll< x = sub(x, 1ll*y< } } return flag<0 ? add(~ans, 1) : ans;}

• 取模操作

已經(jīng)得到了除法的結(jié)果，那么取模操作也很容易實(shí)現(xiàn)了

ll mod(ll x, ll y) { x = x<0 ? add(~x, 1) : x; y = y<0 ? add(~y, 1) : y; return sub(x, mul(y, divide(x, y)));}

為什么子類(lèi)對(duì)象可以賦值給父類(lèi)對(duì)象而反過(guò)來(lái)卻不行

• 子類(lèi)繼承于父類(lèi)，它含有父類(lèi)的部分，又做了擴(kuò)充。如果子類(lèi)對(duì)象賦值給父類(lèi)變量，則使用該變量只能訪問(wèn)子類(lèi)的父類(lèi)部分。
• 如果反過(guò)來(lái)，這個(gè)子類(lèi)變量如果去訪問(wèn)它的擴(kuò)充成員變量，就會(huì)訪問(wèn)不到，造成內(nèi)存越界。

為什么 free 時(shí)不需要傳指針大小

free 要做的事是歸還 malloc 申請(qǐng)的內(nèi)存空間，而在 malloc 的時(shí)候已經(jīng)記錄了申請(qǐng)空間的大小，所以不需要傳大小，直接傳指針就可以。

手寫(xiě)鏈表實(shí)現(xiàn) LRU

class LRU {private: struct Node { int val; Node *pre, *suf; Node() { pre = suf = nullptr; } Node(int _val) { val = _val; pre = suf = nullptr; } }; int size; int capacity; Node *head; unordered_map<int, Node*> mp; Node* find(int val) { if(mp.count(val)) { return mp[val]; } else { return nullptr; } } void del(Node *node) { if(node == nullptr) return ; node->pre->suf = node->suf; node->suf->pre = node->pre; mp.erase(node->val); if(node == head) head = head->suf; size--; } void add(Node *node) { if(head == nullptr) { head = node; head->suf = head; head->pre = head; mp[node->val] = node; } else { node->suf = head; node->pre = head->pre; head->pre = node; node->pre->suf = node; mp[node->val] = node; head = node; } size++; }public: LRU() { mp.clear(); head = nullptr; size = capacity = 0; } void reverse(int _capacity) { capacity = _capacity; } void insert(int val) { Node *node = new Node(val); Node *selectnode = find(val); del(selectnode); if(size == capacity) { del(head->pre); } add(node); } void view() { Node *p = head; do { cout << p->val << " "; p = p->suf; } while(p != head); cout << endl; }}lru;