shared_ptr 指針的實現(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. 從存儲空間角度，虛函數(shù)對應一個虛函數(shù)表，而指向虛函數(shù)表的虛函數(shù)指針是存儲區(qū)對象內(nèi)存內(nèi)的。如果構(gòu)造函數(shù)是虛函數(shù)，則需要通過虛函數(shù)表來調(diào)用，而對象還沒有構(gòu)造出來，無法找到虛函數(shù)表。
2. 從使用角度，虛函數(shù)主要用于信息不全的情況下，使子類重寫的函數(shù)能得到對應的調(diào)用。構(gòu)造函數(shù)本身就是要初始化對象，所以用虛函數(shù)沒有意義。

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

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

AVL 和 紅黑樹比較

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

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

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

有了 AVL 為什么還要紅黑樹

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

紅黑樹

面試常問：什么是紅黑樹?

wiki紅黑樹

紅黑樹性質(zhì)

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

這些性質(zhì)強制了紅黑樹從根到葉子的最長路徑不會超過最短路徑的兩倍。性質(zhì) 4 導致了路徑不能有兩個相連的紅色節(jié)點，最短的可能路徑都是黑色節(jié)點，最長的可能路徑有交替的紅色和黑色節(jié)點。因為根據(jù)性質(zhì) 5 所有最長的路徑都有相同數(shù)目的黑色節(jié)點，這就表明了沒有路徑能多于任何其他路徑的兩倍長。

紅黑樹的擴展

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

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

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

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

++i 返回對象的引用，i++ 必須產(chǎn)生一個臨時對象保存更改前對象的值并返回，所以導致在大對象的時候產(chǎn)生的比較大的復制開銷，效率較低。

// ++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 都是一開始是不存在的，是通過 a 對象來構(gòu)造和初始化的。

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

Node (const Node &other) { 
}

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

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

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

優(yōu)點：可以很容易的復制對象。

缺點：對象的隱式拷貝是 C++ 中是錯誤和性能問題的來源之一。它也降低了代碼的可讀性，并使得對象子程序中的傳遞和改變變得難以跟蹤。

賦值函數(shù)

Node a;Node b;b = a;

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

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

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

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

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

總結(jié)：

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

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

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

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

空類的大小

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

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

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)最后一個的 sizeof 并不是單純的 1+4=5，而直接變成了 8，因為存在結(jié)構(gòu)體的字節(jié)對齊規(guī)則。

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

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

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

#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é)果的原理在于：

• 對于 class A 來說，內(nèi)部字節(jié)為

• 對于 class B 來說，內(nèi)部字節(jié)為

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

• static 修飾成員變量
• 靜態(tài)成員變量在 全局存儲區(qū) 分配內(nèi)存，本類的所有對象共享，在還沒生成類對象之前也可以使用。
• 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ù)沒有類對象也可以調(diào)用。
• virtual
• 虛函數(shù)表存儲在常量區(qū)，也就是只讀數(shù)據(jù)段
• 虛函數(shù)指針存儲在對象內(nèi)，如果對象是局部變量，則存儲在棧區(qū)內(nèi)。

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

#include#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE*)0)->MEMBER)/*(TYPE*)0 將零轉(zhuǎn)型成 TYPE 類型指針((TYPE*)0->MEMBER) 訪問結(jié)構(gòu)體中的成員&((TYPE*)0->MEMBER) 取出數(shù)據(jù)成員地址，也就是相對于零的偏移量(size_t) & ((TYPE*)0)->MEMBER) 將結(jié)果轉(zhuǎn)換成 size_t 類型。*/
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，在不同平臺下被 typedef 成不同類型。

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

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

手撕堆排序

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

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

令 k = log_2n

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

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

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ù)前后還會執(zhí)行什么

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

const 和 define

1. define 在預編譯階段起作用，const 在編譯、運行的時候起作用。
2. define 只是簡單的替換功能，沒有類型檢查功能，const 有類型檢查功能，可以避免一些錯誤。
3. define 在預編譯階段就替換掉了，無法調(diào)試，const 可以通過集成化工具調(diào)試。

inline 和 define

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

inline 函數(shù)的要求

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

聲明和定義

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

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

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

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

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

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

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

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

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

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

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

#ifndef 和 #endif 的作用

在大的軟件工程中，可能多個文件包含同一個頭文件，當這些文件鏈接成可執(zhí)行文件的時候，就會造成大量的 "重定義" 錯誤，可以通過 #ifndef 來避免這個錯誤。

#ifndef _A_H#define _A_H
#endif

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

explicit 關(guān)鍵字

類的構(gòu)造函數(shù)存在隱式轉(zhuǎn)換，如果想要避免這個功能，就可以通過 explicit 關(guān)鍵字來將構(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)系，當繼承關(guān)系形成菱形時，D 中保存了兩份 A，在調(diào)用 d.fun() 時就會出現(xiàn)調(diào)用不明確的問題。

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

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

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

weak_ptr 指向的對象被銷毀

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

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

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

如果在 weak_ptr 獲得過程中，原本的所有 shared_ptr 被銷毀，那么該對象的生命周期會延長到這個臨時 shared_ptr 銷毀為止。

lambda 表達式

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

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

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

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

#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*/

存在全局變量和局部變量時，訪問全局變量

可以通過全局作用符號 :: 來完成

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

全局變量的初始化的順序

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

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

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

淺拷貝和深拷貝

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

從這個例子可以看出，b 通過默認拷貝函數(shù)進行初始化，然而進行的是淺拷貝，導致對 a 進行修改的時候，b 的存儲值也被修改。

struct Node { char* s; Node(char *str) { s = new char[100]; strcpy(s, str); } /* 手動實現(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;}

正確的寫法應該自己寫一個拷貝函數(shù)，而不是用默認的，應該盡量的避免淺拷貝。

如何控制一個類只能在堆或棧上創(chuàng)建對象

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

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

只能從堆上分配對象：

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

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

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

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

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

只能從棧上分配對象：

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

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

memcpy 和 memmove 的實現(xiàn)

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

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++;}}

如果源地址和目的地址存在重合，會因為地址的重合導致數(shù)據(jù)被覆蓋，所以要通過 memmove 來實現(xiàn)，需要從末尾往前自減賦值。

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

// 直接按字節(jié)進行 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é)進行 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++; } }}

通過重載 new/delete 來檢測內(nèi)存泄漏的簡易實現(xiàn)

講每次 new 產(chǎn)生的內(nèi)存記錄，并在 delete 的時候刪去記錄，那么最后剩下的就是發(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*/

垃圾回收機制

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

垃圾回收機制可以分為兩大類：

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

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

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

通過位運算實現(xiàn)加減乘除取模

• 加法操作

對于每一位而言，在不考慮進位的情況下，可以得到

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

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

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

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

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

• 減法操作

減法操作可以看成

同樣可以通過加法式得到

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

• 乘法操作

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

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

而這個當乘數(shù)只有一個 1 時，可以通過二進制的左移操作實現(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，通過左移來得到乘積并減去。先從大的開始找，如果有一位是 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é)果，那么取模操作也很容易實現(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)));}

為什么子類對象可以賦值給父類對象而反過來卻不行

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

為什么 free 時不需要傳指針大小

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

手寫鏈表實現(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;