国产一级a片免费看高清,亚洲熟女中文字幕在线视频,黄三级高清在线播放,免费黄色视频在线看

打開APP
userphoto
未登錄

開通VIP,暢享免費(fèi)電子書等14項(xiàng)超值服

開通VIP
重磅干貨:五萬字長文總結(jié):C/C 知識(上篇)
結(jié)識更多同行,共同討論“嵌入式”技術(shù)。歡迎添加社區(qū)客服微信,備注發(fā)送“電源+公司名(學(xué)校)+職位(專業(yè))”拉您入群。
目錄
C/C++
STL
數(shù)據(jù)結(jié)構(gòu)
算法
Problems
操作系統(tǒng)
計(jì)算機(jī)網(wǎng)絡(luò)
網(wǎng)絡(luò)編程
數(shù)據(jù)庫
設(shè)計(jì)模式
鏈接裝載庫
海量數(shù)據(jù)處理
音視頻
其他
C/C++
const
作用
修飾變量,說明該變量不可以被改變;
修飾指針,分為指向常量的指針和指針常量;
常量引用,經(jīng)常用于形參類型,即避免了拷貝,又避免了函數(shù)對值的修改;
修飾成員函數(shù),說明該成員函數(shù)內(nèi)不能修改成員變量。
使用
// 類
class A
{
private:
const int a;                // 常對象成員,只能在初始化列表賦值
public:
// 構(gòu)造函數(shù)
A() { };
A(int x) : a(x) { };        // 初始化列表
// const可用于對重載函數(shù)的區(qū)分
int getValue();             // 普通成員函數(shù)
int getValue() const;       // 常成員函數(shù),不得修改類中的任何數(shù)據(jù)成員的值
};
void function()
{
// 對象
A b;                        // 普通對象,可以調(diào)用全部成員函數(shù)
const A a;                  // 常對象,只能調(diào)用常成員函數(shù)、更新常成員變量
const A *p = &a;            // 常指針
const A &q = a;             // 常引用
// 指針
char greeting[] = 'Hello';
char* p1 = greeting;                // 指針變量,指向字符數(shù)組變量
const char* p2 = greeting;          // 指針變量,指向字符數(shù)組常量
char* const p3 = greeting;          // 常指針,指向字符數(shù)組變量
const char* const p4 = greeting;    // 常指針,指向字符數(shù)組常量
}
// 函數(shù)
void function1(const int Var);           // 傳遞過來的參數(shù)在函數(shù)內(nèi)不可變
void function2(const char* Var);         // 參數(shù)指針?biāo)竷?nèi)容為常量
void function3(char* const Var);         // 參數(shù)指針為常指針
void function4(const int& Var);          // 引用參數(shù)在函數(shù)內(nèi)為常量
// 函數(shù)返回值
const int function5();      // 返回一個(gè)常數(shù)
const int* function6();     // 返回一個(gè)指向常量的指針變量,使用:const int *p = function6();
int* const function7();     // 返回一個(gè)指向變量的常指針,使用:int* const p = function7();
static
作用
修飾普通變量,修改變量的存儲(chǔ)區(qū)域和生命周期,使變量存儲(chǔ)在靜態(tài)區(qū),在 main 函數(shù)運(yùn)行前就分配了空間,如果有初始值就用初始值初始化它,如果沒有初始值系統(tǒng)用默認(rèn)值初始化它。
修飾普通函數(shù),表明函數(shù)的作用范圍,僅在定義該函數(shù)的文件內(nèi)才能使用。在多人開發(fā)項(xiàng)目時(shí),為了防止與他人命令函數(shù)重名,可以將函數(shù)定位為 static。
修飾成員變量,修飾成員變量使所有的對象只保存一個(gè)該變量,而且不需要生成對象就可以訪問該成員。
修飾成員函數(shù),修飾成員函數(shù)使得不需要生成對象就可以訪問該函數(shù),但是在 static 函數(shù)內(nèi)不能訪問非靜態(tài)成員。
this 指針
this 指針是一個(gè)隱含于每一個(gè)非靜態(tài)成員函數(shù)中的特殊指針。它指向正在被該成員函數(shù)操作的那個(gè)對象。
當(dāng)對一個(gè)對象調(diào)用成員函數(shù)時(shí),編譯程序先將對象的地址賦給 this 指針,然后調(diào)用成員函數(shù),每次成員函數(shù)存取數(shù)據(jù)成員時(shí),由隱含使用 this 指針。
當(dāng)一個(gè)成員函數(shù)被調(diào)用時(shí),自動(dòng)向它傳遞一個(gè)隱含的參數(shù),該參數(shù)是一個(gè)指向這個(gè)成員函數(shù)所在的對象的指針。
this 指針被隱含地聲明為: ClassName const this`,這意味著不能給 `this` 指針賦值;在 `ClassName` 類的 `const` 成員函數(shù)中,`this` 指針的類型為:`const ClassName const,這說明不能對 this 指針?biāo)赶虻倪@種對象是不可修改的(即不能對這種對象的數(shù)據(jù)成員進(jìn)行賦值操作);
this 并不是一個(gè)常規(guī)變量,而是個(gè)右值,所以不能取得 this 的地址(不能 &this)。
在以下場景中,經(jīng)常需要顯式引用 this 指針:
為實(shí)現(xiàn)對象的鏈?zhǔn)揭茫?div style="height:15px;">
為避免對同一對象進(jìn)行賦值操作;
在實(shí)現(xiàn)一些數(shù)據(jù)結(jié)構(gòu)時(shí),如 `list`。
inline 內(nèi)聯(lián)函數(shù)
特征
相當(dāng)于把內(nèi)聯(lián)函數(shù)里面的內(nèi)容寫在調(diào)用內(nèi)聯(lián)函數(shù)處;
相當(dāng)于不用執(zhí)行進(jìn)入函數(shù)的步驟,直接執(zhí)行函數(shù)體;
相當(dāng)于宏,卻比宏多了類型檢查,真正具有函數(shù)特性;
不能包含循環(huán)、遞歸、switch 等復(fù)雜操作;
在類聲明中定義的函數(shù),除了虛函數(shù)的其他函數(shù)都會(huì)自動(dòng)隱式地當(dāng)成內(nèi)聯(lián)函數(shù)。
使用
// 聲明1(加 inline,建議使用)
inline int functionName(int first, int secend,...);
// 聲明2(不加 inline)
int functionName(int first, int secend,...);
// 定義
inline int functionName(int first, int secend,...) {/****/};
// 類內(nèi)定義,隱式內(nèi)聯(lián)
class A {
int doA() { return 0; }         // 隱式內(nèi)聯(lián)
}
// 類外定義,需要顯式內(nèi)聯(lián)
class A {
int doA();
}
inline int A::doA() { return 0; }   // 需要顯式內(nèi)聯(lián)
編譯器對 inline 函數(shù)的處理步驟
將 inline 函數(shù)體復(fù)制到 inline 函數(shù)調(diào)用點(diǎn)處;
為所用 inline 函數(shù)中的局部變量分配內(nèi)存空間;
將 inline 函數(shù)的的輸入?yún)?shù)和返回值映射到調(diào)用方法的局部變量空間中;
如果 inline 函數(shù)有多個(gè)返回點(diǎn),將其轉(zhuǎn)變?yōu)?inline 函數(shù)代碼塊末尾的分支(使用 GOTO)。
優(yōu)缺點(diǎn)
優(yōu)點(diǎn)
內(nèi)聯(lián)函數(shù)同宏函數(shù)一樣將在被調(diào)用處進(jìn)行代碼展開,省去了參數(shù)壓棧、棧幀開辟與回收,結(jié)果返回等,從而提高程序運(yùn)行速度。
內(nèi)聯(lián)函數(shù)相比宏函數(shù)來說,在代碼展開時(shí),會(huì)做安全檢查或自動(dòng)類型轉(zhuǎn)換(同普通函數(shù)),而宏定義則不會(huì)。
在類中聲明同時(shí)定義的成員函數(shù),自動(dòng)轉(zhuǎn)化為內(nèi)聯(lián)函數(shù),因此內(nèi)聯(lián)函數(shù)可以訪問類的成員變量,宏定義則不能。
內(nèi)聯(lián)函數(shù)在運(yùn)行時(shí)可調(diào)試,而宏定義不可以。
缺點(diǎn)
代碼膨脹。內(nèi)聯(lián)是以代碼膨脹(復(fù)制)為代價(jià),消除函數(shù)調(diào)用帶來的開銷。如果執(zhí)行函數(shù)體內(nèi)代碼的時(shí)間,相比于函數(shù)調(diào)用的開銷較大,那么效率的收獲會(huì)很少。另一方面,每一處內(nèi)聯(lián)函數(shù)的調(diào)用都要復(fù)制代碼,將使程序的總代碼量增大,消耗更多的內(nèi)存空間。
inline 函數(shù)無法隨著函數(shù)庫升級而升級。inline函數(shù)的改變需要重新編譯,不像 non-inline 可以直接鏈接。
是否內(nèi)聯(lián),程序員不可控。內(nèi)聯(lián)函數(shù)只是對編譯器的建議,是否對函數(shù)內(nèi)聯(lián),決定權(quán)在于編譯器。
虛函數(shù)(virtual)可以是內(nèi)聯(lián)函數(shù)(inline)嗎?
Are 'inline virtual' member functions ever actually 'inlined'?
答案:http://www.cs.technion.ac.il/users/yechiel/c++-faq/inline-virtuals.html
虛函數(shù)可以是內(nèi)聯(lián)函數(shù),內(nèi)聯(lián)是可以修飾虛函數(shù)的,但是當(dāng)虛函數(shù)表現(xiàn)多態(tài)性的時(shí)候不能內(nèi)聯(lián)。
內(nèi)聯(lián)是在編譯器建議編譯器內(nèi)聯(lián),而虛函數(shù)的多態(tài)性在運(yùn)行期,編譯器無法知道運(yùn)行期調(diào)用哪個(gè)代碼,因此虛函數(shù)表現(xiàn)為多態(tài)性時(shí)(運(yùn)行期)不可以內(nèi)聯(lián)。
inline virtual 唯一可以內(nèi)聯(lián)的時(shí)候是:編譯器知道所調(diào)用的對象是哪個(gè)類(如 Base::who()),這只有在編譯器具有實(shí)際對象而不是對象的指針或引用時(shí)才會(huì)發(fā)生。
虛函數(shù)內(nèi)聯(lián)使用
#include <iostream>
using namespace std;
class Base
{
public:
inline virtual void who()
{
cout << 'I am Base\n';
}
virtual ~Base() {}
};
class Derived : public Base
{
public:
inline void who()  // 不寫inline時(shí)隱式內(nèi)聯(lián)
{
cout << 'I am Derived\n';
}
};
int main()
{
// 此處的虛函數(shù) who(),是通過類(Base)的具體對象(b)來調(diào)用的,編譯期間就能確定了,所以它可以是內(nèi)聯(lián)的,但最終是否內(nèi)聯(lián)取決于編譯器。
Base b;
b.who();
// 此處的虛函數(shù)是通過指針調(diào)用的,呈現(xiàn)多態(tài)性,需要在運(yùn)行時(shí)期間才能確定,所以不能為內(nèi)聯(lián)。
Base *ptr = new Derived();
ptr->who();
// 因?yàn)锽ase有虛析構(gòu)函數(shù)(virtual ~Base() {}),所以 delete 時(shí),會(huì)先調(diào)用派生類(Derived)析構(gòu)函數(shù),再調(diào)用基類(Base)析構(gòu)函數(shù),防止內(nèi)存泄漏。
delete ptr;
ptr = nullptr;
system('pause');
return 0;
}
assert()
斷言,是宏,而非函數(shù)。assert 宏的原型定義在 <assert.h>(C)、<cassert>(C++)中,其作用是如果它的條件返回錯(cuò)誤,則終止程序執(zhí)行??梢酝ㄟ^定義 NDEBUG 來關(guān)閉 assert,但是需要在源代碼的開頭,include <assert.h> 之前。
使用
#define NDEBUG          // 加上這行,則 assert 不可用
#include <assert.h>
assert( p != NULL );    // assert 不可用
sizeof()
sizeof 對數(shù)組,得到整個(gè)數(shù)組所占空間大小。
sizeof 對指針,得到指針本身所占空間大小。
#pragma pack(n)
設(shè)定結(jié)構(gòu)體、聯(lián)合以及類成員變量以 n 字節(jié)方式對齊
使用
#pragma pack(push)  // 保存對齊狀態(tài)
#pragma pack(4)     // 設(shè)定為 4 字節(jié)對齊
struct test
{
char m1;
double m4;
int m3;
};
#pragma pack(pop)   // 恢復(fù)對齊狀態(tài)
位域
Bit mode: 2;    // mode 占 2 位
類可以將其(非靜態(tài))數(shù)據(jù)成員定義為位域(bit-field),在一個(gè)位域中含有一定數(shù)量的二進(jìn)制位。當(dāng)一個(gè)程序需要向其他程序或硬件設(shè)備傳遞二進(jìn)制數(shù)據(jù)時(shí),通常會(huì)用到位域。
位域在內(nèi)存中的布局是與機(jī)器有關(guān)的
位域的類型必須是整型或枚舉類型,帶符號類型中的位域的行為將因具體實(shí)現(xiàn)而定
取地址運(yùn)算符(&)不能作用于位域,任何指針都無法指向類的位域
volatile
volatile int i = 10;
volatile 關(guān)鍵字是一種類型修飾符,用它聲明的類型變量表示可以被某些編譯器未知的因素(操作系統(tǒng)、硬件、其它線程等)更改。所以使用 volatile 告訴編譯器不應(yīng)對這樣的對象進(jìn)行優(yōu)化。
volatile 關(guān)鍵字聲明的變量,每次訪問時(shí)都必須從內(nèi)存中取出值(沒有被 volatile 修飾的變量,可能由于編譯器的優(yōu)化,從 CPU 寄存器中取值)
const 可以是 volatile (如只讀的狀態(tài)寄存器)
指針可以是 volatile
extern 'C'
被 extern 限定的函數(shù)或變量是 extern 類型的
被 extern 'C' 修飾的變量和函數(shù)是按照 C 語言方式編譯和連接的
extern 'C' 的作用是讓 C++ 編譯器將 extern 'C' 聲明的代碼當(dāng)作 C 語言代碼處理,可以避免 C++ 因符號修飾導(dǎo)致代碼不能和C語言庫中的符號進(jìn)行鏈接的問題。
'C' 使用
#ifdef __cplusplus
extern 'C' {
#endif
void *memset(void *, int, size_t);
#ifdef __cplusplus
}
#endif
struct 和 typedef struct
C 中
// c
typedef struct Student {
int age;
} S;
等價(jià)于
// c
struct Student {
int age;
};
typedef struct Student S;
此時(shí) S 等價(jià)于 struct Student,但兩個(gè)標(biāo)識符名稱空間不相同。
另外還可以定義與 struct Student 不沖突的 void Student() {}。
C++ 中
由于編譯器定位符號的規(guī)則(搜索規(guī)則)改變,導(dǎo)致不同于C語言。
一、如果在類標(biāo)識符空間定義了 struct Student {...};,使用 Student me; 時(shí),編譯器將搜索全局標(biāo)識符表,Student 未找到,則在類標(biāo)識符內(nèi)搜索。
即表現(xiàn)為可以使用 Student 也可以使用 struct Student,如下:
// cpp
struct Student {
int age;
};
void f( Student me );       // 正確,'struct' 關(guān)鍵字可省略
二、若定義了與 Student 同名函數(shù)之后,則 Student 只代表函數(shù),不代表結(jié)構(gòu)體,如下:
typedef struct Student {
int age;
} S;
void Student() {}           // 正確,定義后 'Student' 只代表此函數(shù)
//void S() {}               // 錯(cuò)誤,符號 'S' 已經(jīng)被定義為一個(gè) 'struct Student' 的別名
int main() {
Student();
struct Student me;      // 或者 'S me';
return 0;
}
C++ 中 struct 和 class
總的來說,struct 更適合看成是一個(gè)數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)體,class 更適合看成是一個(gè)對象的實(shí)現(xiàn)體。
區(qū)別
最本質(zhì)的一個(gè)區(qū)別就是默認(rèn)的訪問控制
默認(rèn)的繼承訪問權(quán)限。struct 是 public 的,class 是 private 的。
struct 作為數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)體,它默認(rèn)的數(shù)據(jù)訪問控制是 public 的,而 class 作為對象的實(shí)現(xiàn)體,它默認(rèn)的成員變量訪問控制是 private 的。
union 聯(lián)合
聯(lián)合(union)是一種節(jié)省空間的特殊的類,一個(gè) union 可以有多個(gè)數(shù)據(jù)成員,但是在任意時(shí)刻只有一個(gè)數(shù)據(jù)成員可以有值。當(dāng)某個(gè)成員被賦值后其他成員變?yōu)槲炊x狀態(tài)。聯(lián)合有如下特點(diǎn):
默認(rèn)訪問控制符為 public
可以含有構(gòu)造函數(shù)、析構(gòu)函數(shù)
不能含有引用類型的成員
不能繼承自其他類,不能作為基類
不能含有虛函數(shù)
匿名 union 在定義所在作用域可直接訪問 union 成員
匿名 union 不能包含 protected 成員或 private 成員
全局匿名聯(lián)合必須是靜態(tài)(static)的
使用
#include<iostream>
union UnionTest {
UnionTest() : i(10) {};
int i;
double d;
};
static union {
int i;
double d;
};
int main() {
UnionTest u;
union {
int i;
double d;
};
std::cout << u.i << std::endl;  // 輸出 UnionTest 聯(lián)合的 10
::i = 20;
std::cout << ::i << std::endl;  // 輸出全局靜態(tài)匿名聯(lián)合的 20
i = 30;
std::cout << i << std::endl;    // 輸出局部匿名聯(lián)合的 30
return 0;
}
C 實(shí)現(xiàn) C++ 類
C 語言實(shí)現(xiàn)封裝、繼承和多態(tài):
http://dongxicheng.org/cpp/ooc/
explicit(顯式)構(gòu)造函數(shù)
explicit 修飾的構(gòu)造函數(shù)可用來防止隱式轉(zhuǎn)換
explicit 使用
class Test1
{
public:
Test1(int n)            // 普通構(gòu)造函數(shù)
{
num=n;
}
private:
int num;
};
class Test2
{
public:
explicit Test2(int n)   // explicit(顯式)構(gòu)造函數(shù)
{
num=n;
}
private:
int num;
};
int main()
{
Test1 t1=12;            // 隱式調(diào)用其構(gòu)造函數(shù),成功
Test2 t2=12;            // 編譯錯(cuò)誤,不能隱式調(diào)用其構(gòu)造函數(shù)
Test2 t2(12);           // 顯式調(diào)用成功
return 0;
}
friend 友元類和友元函數(shù)
能訪問私有成員
破壞封裝性
友元關(guān)系不可傳遞
友元關(guān)系的單向性
友元聲明的形式及數(shù)量不受限制
using
using 聲明
一條 using 聲明 語句一次只引入命名空間的一個(gè)成員。它使得我們可以清楚知道程序中所引用的到底是哪個(gè)名字。如:
using namespace_name::name;
構(gòu)造函數(shù)的 using 聲明【C++11】
在 C++11 中,派生類能夠重用其直接基類定義的構(gòu)造函數(shù)。
class Derived : Base {
public:
using Base::Base;
/* ... */
};
如上 using 聲明,對于基類的每個(gè)構(gòu)造函數(shù),編譯器都生成一個(gè)與之對應(yīng)(形參列表完全相同)的派生類構(gòu)造函數(shù)。生成如下類型構(gòu)造函數(shù):
derived(parms) : base(args) { }
using 指示
using 指示 使得某個(gè)特定命名空間中所有名字都可見,這樣我們就無需再為它們添加任何前綴限定符了。如:
using namespace_name name;
盡量少使用 `using 指示` 污染命名空間
一般說來,使用 using 命令比使用 using 編譯命令更安全,這是由于它只導(dǎo)入了制定的名稱。如果該名稱與局部名稱發(fā)生沖突,編譯器將發(fā)出指示。using編譯命令導(dǎo)入所有的名稱,包括可能并不需要的名稱。如果與局部名稱發(fā)生沖突,則局部名稱將覆蓋名稱空間版本,而編譯器并不會(huì)發(fā)出警告。另外,名稱空間的開放性意味著名稱空間的名稱可能分散在多個(gè)地方,這使得難以準(zhǔn)確知道添加了哪些名稱。
using 使用
盡量少使用 using 指示
using namespace std;
應(yīng)該多使用 using 聲明
int x;
std::cin >> x ;
std::cout << x << std::endl;
或者
using std::cin;
using std::cout;
using std::endl;
int x;
cin >> x;
cout << x << endl;
:: 范圍解析運(yùn)算符
分類
全局作用域符(::name):用于類型名稱(類、類成員、成員函數(shù)、變量等)前,表示作用域?yàn)槿置臻g
類作用域符(class::name):用于表示指定類型的作用域范圍是具體某個(gè)類的
命名空間作用域符(namespace::name):用于表示指定類型的作用域范圍是具體某個(gè)命名空間的
:: 使用
int count = 0;        // 全局(::)的 count
class A {
public:
static int count; // 類 A 的 count(A::count)
};
int main() {
::count = 1;      // 設(shè)置全局的 count 的值為 1
A::count = 2;     // 設(shè)置類 A 的 count 為 2
int count = 0;    // 局部的 count
count = 3;        // 設(shè)置局部的 count 的值為 3
return 0;
}
enum 枚舉類型
限定作用域的枚舉類型
enum class open_modes { input, output, append };
不限定作用域的枚舉類型
enum color { red, yellow, green };
enum { floatPrec = 6, doublePrec = 10 };
decltype
decltype 關(guān)鍵字用于檢查實(shí)體的聲明類型或表達(dá)式的類型及值分類。語法:
decltype ( expression )
使用
// 尾置返回允許我們在參數(shù)列表之后聲明返回類型
template <typename It>
auto fcn(It beg, It end) -> decltype(*beg)
{
// 處理序列
return *beg;    // 返回序列中一個(gè)元素的引用
}
// 為了使用模板參數(shù)成員,必須用 typename
template <typename It>
auto fcn2(It beg, It end) -> typename remove_reference<decltype(*beg)>::type
{
// 處理序列
return *beg;    // 返回序列中一個(gè)元素的拷貝
}
引用
左值引用
常規(guī)引用,一般表示對象的身份。
右值引用
右值引用就是必須綁定到右值(一個(gè)臨時(shí)對象、將要銷毀的對象)的引用,一般表示對象的值。
右值引用可實(shí)現(xiàn)轉(zhuǎn)移語義(Move Sementics)和精確傳遞(Perfect Forwarding),它的主要目的有兩個(gè)方面:
消除兩個(gè)對象交互時(shí)不必要的對象拷貝,節(jié)省運(yùn)算存儲(chǔ)資源,提高效率。
能夠更簡潔明確地定義泛型函數(shù)。
引用折疊
X& &、X& &&、X&& & 可折疊成 X&
X&& && 可折疊成 X&&
宏定義可以實(shí)現(xiàn)類似于函數(shù)的功能,但是它終歸不是函數(shù),而宏定義中括弧中的“參數(shù)”也不是真的參數(shù),在宏展開的時(shí)候?qū)?“參數(shù)” 進(jìn)行的是一對一的替換。
成員初始化列表
好處
更高效:少了一次調(diào)用默認(rèn)構(gòu)造函數(shù)的過程。
有些場合必須要用初始化列表:
常量成員,因?yàn)槌A恐荒艹跏蓟荒苜x值,所以必須放在初始化列表里面
引用類型,引用必須在定義的時(shí)候初始化,并且不能重新賦值,所以也要寫在初始化列表里面
沒有默認(rèn)構(gòu)造函數(shù)的類類型,因?yàn)槭褂贸跏蓟斜砜梢圆槐卣{(diào)用默認(rèn)構(gòu)造函數(shù)來初始化,而是直接調(diào)用拷貝構(gòu)造函數(shù)初始化。
initializer_list 列表初始化【C++11】
用花括號初始化器列表列表初始化一個(gè)對象,其中對應(yīng)構(gòu)造函數(shù)接受一個(gè) std::initializer_list 參數(shù).
initializer_list 使用
#include <iostream>
#include <vector>
#include <initializer_list>
template <class T>
struct S {
std::vector<T> v;
S(std::initializer_list<T> l) : v(l) {
std::cout << 'constructed with a ' << l.size() << '-element list\n';
}
void append(std::initializer_list<T> l) {
v.insert(v.end(), l.begin(), l.end());
}
std::pair<const T*, std::size_t> c_arr() const {
return {&v[0], v.size()};  // 在 return 語句中復(fù)制列表初始化
// 這不使用 std::initializer_list
}
};
template <typename T>
void templated_fn(T) {}
int main()
{
S<int> s = {1, 2, 3, 4, 5}; // 復(fù)制初始化
s.append({6, 7, 8});      // 函數(shù)調(diào)用中的列表初始化
std::cout << 'The vector size is now ' << s.c_arr().second << ' ints:\n';
for (auto n : s.v)
std::cout << n << ' ';
std::cout << '\n';
std::cout << 'Range-for over brace-init-list: \n';
for (int x : {-1, -2, -3}) // auto 的規(guī)則令此帶范圍 for 工作
std::cout << x << ' ';
std::cout << '\n';
auto al = {10, 11, 12};   // auto 的特殊規(guī)則
std::cout << 'The list bound to auto has size() = ' << al.size() << '\n';
//    templated_fn({1, 2, 3}); // 編譯錯(cuò)誤!“ {1, 2, 3} ”不是表達(dá)式,
// 它無類型,故 T 無法推導(dǎo)
templated_fn<std::initializer_list<int>>({1, 2, 3}); // OK
templated_fn<std::vector<int>>({1, 2, 3});           // 也 OK
}
面向?qū)ο?div style="height:15px;">
面向?qū)ο蟪绦蛟O(shè)計(jì)(Object-oriented programming,OOP)是種具有對象概念的程序編程典范,同時(shí)也是一種程序開發(fā)的抽象方針。
面向?qū)ο筇卣?div style="height:15px;">
面向?qū)ο笕筇卣?—— 封裝、繼承、多態(tài)
封裝
把客觀事物封裝成抽象的類,并且類可以把自己的數(shù)據(jù)和方法只讓可信的類或者對象操作,對不可信的進(jìn)行信息隱藏。
關(guān)鍵字:public, protected, friendly, private。不寫默認(rèn)為 friendly。
關(guān)鍵字當(dāng)前類包內(nèi)子孫類包外
public√√√√
protected√√√×
friendly√√××
private√×××
繼承
基類(父類)——> 派生類(子類)
多態(tài)
多態(tài),即多種狀態(tài),在面向?qū)ο笳Z言中,接口的多種不同的實(shí)現(xiàn)方式即為多態(tài)。
C++ 多態(tài)有兩種:靜態(tài)多態(tài)(早綁定)、動(dòng)態(tài)多態(tài)(晚綁定)。靜態(tài)多態(tài)是通過函數(shù)重載實(shí)現(xiàn)的;動(dòng)態(tài)多態(tài)是通過虛函數(shù)實(shí)現(xiàn)的。
多態(tài)是以封裝和繼承為基礎(chǔ)的。
靜態(tài)多態(tài)(早綁定)
函數(shù)重載
class A
{
public:
void do(int a);
void do(int a, int b);
};
動(dòng)態(tài)多態(tài)(晚綁定)
虛函數(shù):用 virtual 修飾成員函數(shù),使其成為虛函數(shù)
注意:
普通函數(shù)(非類成員函數(shù))不能是虛函數(shù)
靜態(tài)函數(shù)(static)不能是虛函數(shù)
構(gòu)造函數(shù)不能是虛函數(shù)(因?yàn)樵谡{(diào)用構(gòu)造函數(shù)時(shí),虛表指針并沒有在對象的內(nèi)存空間中,必須要構(gòu)造函數(shù)調(diào)用完成后才會(huì)形成虛表指針)
內(nèi)聯(lián)函數(shù)不能是表現(xiàn)多態(tài)性時(shí)的虛函數(shù),解釋見:虛函數(shù)(virtual)可以是內(nèi)聯(lián)函數(shù)(inline)嗎?:http://t.cn/E4WVXSP
動(dòng)態(tài)多態(tài)使用
class Shape                     // 形狀類
{
public:
virtual double calcArea()
{
...
}
virtual ~Shape();
};
class Circle : public Shape     // 圓形類
{
public:
virtual double calcArea();
...
};
class Rect : public Shape       // 矩形類
{
public:
virtual double calcArea();
...
};
int main()
{
Shape * shape1 = new Circle(4.0);
Shape * shape2 = new Rect(5.0, 6.0);
shape1->calcArea();         // 調(diào)用圓形類里面的方法
shape2->calcArea();         // 調(diào)用矩形類里面的方法
delete shape1;
shape1 = nullptr;
delete shape2;
shape2 = nullptr;
return 0;
}
虛析構(gòu)函數(shù)
虛析構(gòu)函數(shù)是為了解決基類的指針指向派生類對象,并用基類的指針刪除派生類對象。
虛析構(gòu)函數(shù)使用
class Shape
{
public:
Shape();                    // 構(gòu)造函數(shù)不能是虛函數(shù)
virtual double calcArea();
virtual ~Shape();           // 虛析構(gòu)函數(shù)
};
class Circle : public Shape     // 圓形類
{
public:
virtual double calcArea();
...
};
int main()
{
Shape * shape1 = new Circle(4.0);
shape1->calcArea();
delete shape1;  // 因?yàn)镾hape有虛析構(gòu)函數(shù),所以delete釋放內(nèi)存時(shí),先調(diào)用子類析構(gòu)函數(shù),再調(diào)用基類析構(gòu)函數(shù),防止內(nèi)存泄漏。
shape1 = NULL;
return 0;
}
純虛函數(shù)
純虛函數(shù)是一種特殊的虛函數(shù),在基類中不能對虛函數(shù)給出有意義的實(shí)現(xiàn),而把它聲明為純虛函數(shù),它的實(shí)現(xiàn)留給該基類的派生類去做。
virtual int A() = 0;
虛函數(shù)、純虛函數(shù)
CSDN . C++ 中的虛函數(shù)、純虛函數(shù)區(qū)別和聯(lián)系:http://t.cn/E4WVQBI
類里如果聲明了虛函數(shù),這個(gè)函數(shù)是實(shí)現(xiàn)的,哪怕是空實(shí)現(xiàn),它的作用就是為了能讓這個(gè)函數(shù)在它的子類里面可以被覆蓋,這樣的話,這樣編譯器就可以使用后期綁定來達(dá)到多態(tài)了。純虛函數(shù)只是一個(gè)接口,是個(gè)函數(shù)的聲明而已,它要留到子類里去實(shí)現(xiàn)。
虛函數(shù)在子類里面也可以不重載的;但純虛函數(shù)必須在子類去實(shí)現(xiàn)。
虛函數(shù)的類用于 “實(shí)作繼承”,繼承接口的同時(shí)也繼承了父類的實(shí)現(xiàn)。當(dāng)然大家也可以完成自己的實(shí)現(xiàn)。純虛函數(shù)關(guān)注的是接口的統(tǒng)一性,實(shí)現(xiàn)由子類完成。
帶純虛函數(shù)的類叫抽象類,這種類不能直接生成對象,而只有被繼承,并重寫其虛函數(shù)后,才能使用。抽象類和大家口頭常說的虛基類還是有區(qū)別的,在 C# 中用 abstract 定義抽象類,而在 C++ 中有抽象類的概念,但是沒有這個(gè)關(guān)鍵字。抽象類被繼承后,子類可以繼續(xù)是抽象類,也可以是普通類,而虛基類,是含有純虛函數(shù)的類,它如果被繼承,那么子類就必須實(shí)現(xiàn)虛基類里面的所有純虛函數(shù),其子類不能是抽象類。
虛函數(shù)指針、虛函數(shù)表
虛函數(shù)指針:在含有虛函數(shù)類的對象中,指向虛函數(shù)表,在運(yùn)行時(shí)確定。
虛函數(shù)表:在程序只讀數(shù)據(jù)段(.rodata section,見:目標(biāo)文件存儲(chǔ)結(jié)構(gòu):http://t.cn/E4WVBeF),存放虛函數(shù)指針,如果派生類實(shí)現(xiàn)了基類的某個(gè)虛函數(shù),則在虛表中覆蓋原本基類的那個(gè)虛函數(shù)指針,在編譯時(shí)根據(jù)類的聲明創(chuàng)建。
虛繼承
虛繼承用于解決多繼承條件下的菱形繼承問題(浪費(fèi)存儲(chǔ)空間、存在二義性)。
底層實(shí)現(xiàn)原理與編譯器相關(guān),一般通過虛基類指針和虛基類表實(shí)現(xiàn),每個(gè)虛繼承的子類都有一個(gè)虛基類指針(占用一個(gè)指針的存儲(chǔ)空間,4字節(jié))和虛基類表(不占用類對象的存儲(chǔ)空間)(需要強(qiáng)調(diào)的是,虛基類依舊會(huì)在子類里面存在拷貝,只是僅僅最多存在一份而已,并不是不在子類里面了);當(dāng)虛繼承的子類被當(dāng)做父類繼承時(shí),虛基類指針也會(huì)被繼承。
實(shí)際上,vbptr 指的是虛基類表指針(virtual base table pointer),該指針指向了一個(gè)虛基類表(virtual table),虛表中記錄了虛基類與本類的偏移地址;通過偏移地址,這樣就找到了虛基類成員,而虛繼承也不用像普通多繼承那樣維持著公共基類(虛基類)的兩份同樣的拷貝,節(jié)省了存儲(chǔ)空間。
虛繼承、虛函數(shù)
相同之處:都利用了虛指針(均占用類的存儲(chǔ)空間)和虛表(均不占用類的存儲(chǔ)空間)
不同之處:
虛函數(shù)不占用存儲(chǔ)空間
虛函數(shù)表存儲(chǔ)的是虛函數(shù)地址
虛基類依舊存在繼承類中,只占用存儲(chǔ)空間
虛基類表存儲(chǔ)的是虛基類相對直接繼承類的偏移
虛繼承
虛函數(shù)
模板類、成員模板、虛函數(shù)
模板類中可以使用虛函數(shù)
一個(gè)類(無論是普通類還是類模板)的成員模板(本身是模板的成員函數(shù))不能是虛函數(shù)
抽象類、接口類、聚合類
抽象類:含有純虛函數(shù)的類
接口類:僅含有純虛函數(shù)的抽象類
聚合類:用戶可以直接訪問其成員,并且具有特殊的初始化語法形式。滿足如下特點(diǎn):
所有成員都是 public
沒有有定于任何構(gòu)造函數(shù)
沒有類內(nèi)初始化
沒有基類,也沒有 virtual 函數(shù)
內(nèi)存分配和管理
malloc、calloc、realloc、alloca
malloc:申請指定字節(jié)數(shù)的內(nèi)存。申請到的內(nèi)存中的初始值不確定。
calloc:為指定長度的對象,分配能容納其指定個(gè)數(shù)的內(nèi)存。申請到的內(nèi)存的每一位(bit)都初始化為 0。
realloc:更改以前分配的內(nèi)存長度(增加或減少)。當(dāng)增加長度時(shí),可能需將以前分配區(qū)的內(nèi)容移到另一個(gè)足夠大的區(qū)域,而新增區(qū)域內(nèi)的初始值則不確定。
alloca:在棧上申請內(nèi)存。程序在出棧的時(shí)候,會(huì)自動(dòng)釋放內(nèi)存。但是需要注意的是,alloca 不具可移植性, 而且在沒有傳統(tǒng)堆棧的機(jī)器上很難實(shí)現(xiàn)。alloca 不宜使用在必須廣泛移植的程序中。C99 中支持變長數(shù)組 (VLA),可以用來替代 alloca。
malloc、free
用于分配、釋放內(nèi)存
malloc、free 使用
申請內(nèi)存,確認(rèn)是否申請成功
char *str = (char*) malloc(100);
assert(str != nullptr);
釋放內(nèi)存后指針置空
free(p);
p = nullptr;
new、delete
new / new[]:完成兩件事,先底層調(diào)用 malloc 分了配內(nèi)存,然后調(diào)用構(gòu)造函數(shù)(創(chuàng)建對象)。
delete/delete[]:也完成兩件事,先調(diào)用析構(gòu)函數(shù)(清理資源),然后底層調(diào)用 free 釋放空間。
new 在申請內(nèi)存時(shí)會(huì)自動(dòng)計(jì)算所需字節(jié)數(shù),而 malloc 則需我們自己輸入申請內(nèi)存空間的字節(jié)數(shù)。
new、delete 使用
申請內(nèi)存,確認(rèn)是否申請成功
int main()
{
T* t = new T();     // 先內(nèi)存分配 ,再構(gòu)造函數(shù)
delete t;           // 先析構(gòu)函數(shù),再內(nèi)存釋放
return 0;
}
定位 new
定位 new(placement new)允許我們向 new 傳遞額外的參數(shù)。
new (palce_address) type
new (palce_address) type (initializers)
new (palce_address) type [size]
new (palce_address) type [size] { braced initializer list }
palce_address 是個(gè)指針
initializers 提供一個(gè)(可能為空的)以逗號分隔的初始值列表
delete this 合法嗎?
Is it legal (and moral) for a member function to say delete this?
答案:http://t.cn/E4Wfcfl
合法,但:
必須保證 this 對象是通過 new(不是 new[]、不是 placement new、不是棧上、不是全局、不是其他對象成員)分配的
必須保證調(diào)用 delete this 的成員函數(shù)是最后一個(gè)調(diào)用 this 的成員函數(shù)
必須保證成員函數(shù)的 delete this 后面沒有調(diào)用 this 了
必須保證 delete this 后沒有人使用了
如何定義一個(gè)只能在堆上(棧上)生成對象的類?
如何定義一個(gè)只能在堆上(棧上)生成對象的類?
答案:http://t.cn/E4WfDhP
只能在堆上
方法:將析構(gòu)函數(shù)設(shè)置為私有
原因:C++ 是靜態(tài)綁定語言,編譯器管理?xiàng)I蠈ο蟮纳芷?,編譯器在為類對象分配??臻g時(shí),會(huì)先檢查類的析構(gòu)函數(shù)的訪問性。若析構(gòu)函數(shù)不可訪問,則不能在棧上創(chuàng)建對象。
只能在棧上
方法:將 new 和 delete 重載為私有
原因:在堆上生成對象,使用 new 關(guān)鍵詞操作,其過程分為兩階段:第一階段,使用 new 在堆上尋找可用內(nèi)存,分配給對象;第二階段,調(diào)用構(gòu)造函數(shù)生成對象。將 new 操作設(shè)置為私有,那么第一階段就無法完成,就不能夠在堆上生成對象。
智能指針
C++ 標(biāo)準(zhǔn)庫(STL)中
頭文件:#include <memory>
C++ 98
std::auto_ptr<std::string> ps (new std::string(str));
C++ 11
shared_ptr
unique_ptr
weak_ptr
auto_ptr(被 C++11 棄用)
Class shared_ptr 實(shí)現(xiàn)共享式擁有(shared ownership)概念。多個(gè)智能指針指向相同對象,該對象和其相關(guān)資源會(huì)在 “最后一個(gè) reference 被銷毀” 時(shí)被釋放。為了在結(jié)構(gòu)較復(fù)雜的情景中執(zhí)行上述工作,標(biāo)準(zhǔn)庫提供 weak_ptr、bad_weak_ptr 和 enable_shared_from_this 等輔助類。
Class unique_ptr 實(shí)現(xiàn)獨(dú)占式擁有(exclusive ownership)或嚴(yán)格擁有(strict ownership)概念,保證同一時(shí)間內(nèi)只有一個(gè)智能指針可以指向該對象。你可以移交擁有權(quán)。它對于避免內(nèi)存泄漏(resource leak)——如 new 后忘記 delete ——特別有用。
shared_ptr
多個(gè)智能指針可以共享同一個(gè)對象,對象的最末一個(gè)擁有著有責(zé)任銷毀對象,并清理與該對象相關(guān)的所有資源。
支持定制型刪除器(custom deleter),可防范 Cross-DLL 問題(對象在動(dòng)態(tài)鏈接庫(DLL)中被 new 創(chuàng)建,卻在另一個(gè) DLL 內(nèi)被 delete 銷毀)、自動(dòng)解除互斥鎖
weak_ptr
weak_ptr 允許你共享但不擁有某對象,一旦最末一個(gè)擁有該對象的智能指針失去了所有權(quán),任何 weak_ptr 都會(huì)自動(dòng)成空(empty)。因此,在 default 和 copy 構(gòu)造函數(shù)之外,weak_ptr 只提供 “接受一個(gè) shared_ptr” 的構(gòu)造函數(shù)。
可打破環(huán)狀引用(cycles of references,兩個(gè)其實(shí)已經(jīng)沒有被使用的對象彼此互指,使之看似還在 “被使用” 的狀態(tài))的問題
unique_ptr
unique_ptr 是 C++11 才開始提供的類型,是一種在異常時(shí)可以幫助避免資源泄漏的智能指針。采用獨(dú)占式擁有,意味著可以確保一個(gè)對象和其相應(yīng)的資源同一時(shí)間只被一個(gè) pointer 擁有。一旦擁有著被銷毀或編程 empty,或開始擁有另一個(gè)對象,先前擁有的那個(gè)對象就會(huì)被銷毀,其任何相應(yīng)資源亦會(huì)被釋放。
unique_ptr 用于取代 auto_ptr
auto_ptr
被 c++11 棄用,原因是缺乏語言特性如 “針對構(gòu)造和賦值” 的 std::move 語義,以及其他瑕疵。
auto_ptr 與 unique_ptr 比較
auto_ptr 可以賦值拷貝,復(fù)制拷貝后所有權(quán)轉(zhuǎn)移;unqiue_ptr 無拷貝賦值語義,但實(shí)現(xiàn)了move 語義;
auto_ptr 對象不能管理數(shù)組(析構(gòu)調(diào)用 delete),unique_ptr 可以管理數(shù)組(析構(gòu)調(diào)用 delete[] );
強(qiáng)制類型轉(zhuǎn)換運(yùn)算符
MSDN . 強(qiáng)制轉(zhuǎn)換運(yùn)算符:http://t.cn/E4WIt5W
static_cast
用于非多態(tài)類型的轉(zhuǎn)換
不執(zhí)行運(yùn)行時(shí)類型檢查(轉(zhuǎn)換安全性不如 dynamic_cast)
通常用于轉(zhuǎn)換數(shù)值數(shù)據(jù)類型(如 float -> int)
可以在整個(gè)類層次結(jié)構(gòu)中移動(dòng)指針,子類轉(zhuǎn)化為父類安全(向上轉(zhuǎn)換),父類轉(zhuǎn)化為子類不安全(因?yàn)樽宇惪赡苡胁辉诟割惖淖侄位蚍椒ǎ?div style="height:15px;">
向上轉(zhuǎn)換是一種隱式轉(zhuǎn)換。
dynamic_cast
用于多態(tài)類型的轉(zhuǎn)換
執(zhí)行行運(yùn)行時(shí)類型檢查
只適用于指針或引用
對不明確的指針的轉(zhuǎn)換將失?。ǚ祷?nullptr),但不引發(fā)異常
可以在整個(gè)類層次結(jié)構(gòu)中移動(dòng)指針,包括向上轉(zhuǎn)換、向下轉(zhuǎn)換
const_cast
用于刪除 const、volatile 和 __unaligned 特性(如將 const int 類型轉(zhuǎn)換為 int 類型 )
reinterpret_cast
用于位的簡單重新解釋
濫用 reinterpret_cast 運(yùn)算符可能很容易帶來風(fēng)險(xiǎn)。除非所需轉(zhuǎn)換本身是低級別的,否則應(yīng)使用其他強(qiáng)制轉(zhuǎn)換運(yùn)算符之一。
允許將任何指針轉(zhuǎn)換為任何其他指針類型(如 char` 到 `int 或 One_class` 到 `Unrelated_class 之類的轉(zhuǎn)換,但其本身并不安全)
也允許將任何整數(shù)類型轉(zhuǎn)換為任何指針類型以及反向轉(zhuǎn)換。
reinterpret_cast 運(yùn)算符不能丟掉 const、volatile 或 __unaligned 特性。
reinterpret_cast 的一個(gè)實(shí)際用途是在哈希函數(shù)中,即,通過讓兩個(gè)不同的值幾乎不以相同的索引結(jié)尾的方式將值映射到索引。
bad_cast
由于強(qiáng)制轉(zhuǎn)換為引用類型失敗,dynamic_cast 運(yùn)算符引發(fā) bad_cast 異常。
bad_cast 使用
try {
Circle& ref_circle = dynamic_cast<Circle&>(ref_shape);
}
catch (bad_cast b) {
cout << 'Caught: ' << b.what();
}
運(yùn)行時(shí)類型信息 (RTTI)
dynamic_cast
用于多態(tài)類型的轉(zhuǎn)換
typeid
typeid 運(yùn)算符允許在運(yùn)行時(shí)確定對象的類型
type_id 返回一個(gè) type_info 對象的引用
如果想通過基類的指針獲得派生類的數(shù)據(jù)類型,基類必須帶有虛函數(shù)
只能獲取對象的實(shí)際類型
type_info
type_info 類描述編譯器在程序中生成的類型信息。此類的對象可以有效存儲(chǔ)指向類型的名稱的指針。type_info 類還可存儲(chǔ)適合比較兩個(gè)類型是否相等或比較其排列順序的編碼值。類型的編碼規(guī)則和排列順序是未指定的,并且可能因程序而異。
頭文件:typeinfo
typeid、type_info 使用
class Flyable                       // 能飛的
{
public:
virtual void takeoff() = 0;     // 起飛
virtual void land() = 0;        // 降落
};
class Bird : public Flyable         // 鳥
{
public:
void foraging() {...}           // 覓食
virtual void takeoff() {...}
virtual void land() {...}
};
class Plane : public Flyable        // 飛機(jī)
{
public:
void carry() {...}              // 運(yùn)輸
virtual void take off() {...}
virtual void land() {...}
};
class type_info
{
public:
const char* name() const;
bool operator == (const type_info & rhs) const;
bool operator != (const type_info & rhs) const;
int before(const type_info & rhs) const;
virtual ~type_info();
private:
...
};
class doSomething(Flyable *obj)                 // 做些事情
{
obj->takeoff();
cout << typeid(*obj).name() << endl;        // 輸出傳入對象類型('class Bird' or 'class Plane')
if(typeid(*obj) == typeid(Bird))            // 判斷對象類型
{
Bird *bird = dynamic_cast<Bird *>(obj); // 對象轉(zhuǎn)化
bird->foraging();
}
obj->land();
};
Effective C++
視 C++ 為一個(gè)語言聯(lián)邦(C、Object-Oriented C++、Template C++、STL)
寧可以編譯器替換預(yù)處理器(盡量以 const、enum、inline 替換 #define)
盡可能使用 const
確定對象被使用前已先被初始化(構(gòu)造時(shí)賦值(copy 構(gòu)造函數(shù))比 default 構(gòu)造后賦值(copy assignment)效率高)
了解 C++ 默默編寫并調(diào)用哪些函數(shù)(編譯器暗自為 class 創(chuàng)建 default 構(gòu)造函數(shù)、copy 構(gòu)造函數(shù)、copy assignment 操作符、析構(gòu)函數(shù))
若不想使用編譯器自動(dòng)生成的函數(shù),就應(yīng)該明確拒絕(將不想使用的成員函數(shù)聲明為 private,并且不予實(shí)現(xiàn))
為多態(tài)基類聲明 virtual 析構(gòu)函數(shù)(如果 class 帶有任何 virtual 函數(shù),它就應(yīng)該擁有一個(gè) virtual 析構(gòu)函數(shù))
別讓異常逃離析構(gòu)函數(shù)(析構(gòu)函數(shù)應(yīng)該吞下不傳播異常,或者結(jié)束程序,而不是吐出異常;如果要處理異常應(yīng)該在非析構(gòu)的普通函數(shù)處理)
絕不在構(gòu)造和析構(gòu)過程中調(diào)用 virtual 函數(shù)(因?yàn)檫@類調(diào)用從不下降至 derived class)
令 operator= 返回一個(gè) reference to *this (用于連鎖賦值)
在 operator= 中處理 “自我賦值”
賦值對象時(shí)應(yīng)確保復(fù)制 “對象內(nèi)的所有成員變量” 及 “所有 base class 成分”(調(diào)用基類復(fù)制構(gòu)造函數(shù))
以對象管理資源(資源在構(gòu)造函數(shù)獲得,在析構(gòu)函數(shù)釋放,建議使用智能指針,資源取得時(shí)機(jī)便是初始化時(shí)機(jī)(Resource Acquisition Is Initialization,RAII))
在資源管理類中小心 copying 行為(普遍的 RAII class copying 行為是:抑制 copying、引用計(jì)數(shù)、深度拷貝、轉(zhuǎn)移底部資源擁有權(quán)(類似 auto_ptr))
在資源管理類中提供對原始資源(raw resources)的訪問(對原始資源的訪問可能經(jīng)過顯式轉(zhuǎn)換或隱式轉(zhuǎn)換,一般而言顯示轉(zhuǎn)換比較安全,隱式轉(zhuǎn)換對客戶比較方便)
成對使用 new 和 delete 時(shí)要采取相同形式(new 中使用 [] 則 delete [],new 中不使用 [] 則 delete)
以獨(dú)立語句將 newed 對象存儲(chǔ)于(置入)智能指針(如果不這樣做,可能會(huì)因?yàn)榫幾g器優(yōu)化,導(dǎo)致難以察覺的資源泄漏)
讓接口容易被正確使用,不易被誤用(促進(jìn)正常使用的辦法:接口的一致性、內(nèi)置類型的行為兼容;阻止誤用的辦法:建立新類型,限制類型上的操作,約束對象值、消除客戶的資源管理責(zé)任)
設(shè)計(jì) class 猶如設(shè)計(jì) type,需要考慮對象創(chuàng)建、銷毀、初始化、賦值、值傳遞、合法值、繼承關(guān)系、轉(zhuǎn)換、一般化等等。
寧以 pass-by-reference-to-const 替換 pass-by-value (前者通常更高效、避免切割問題(slicing problem),但不適用于內(nèi)置類型、STL迭代器、函數(shù)對象)
必須返回對象時(shí),別妄想返回其 reference(絕不返回 pointer 或 reference 指向一個(gè) local stack 對象,或返回 reference 指向一個(gè) heap-allocated 對象,或返回 pointer 或 reference 指向一個(gè) local static 對象而有可能同時(shí)需要多個(gè)這樣的對象。)
將成員變量聲明為 private(為了封裝、一致性、對其讀寫精確控制等)
寧以 non-member、non-friend 替換 member 函數(shù)(可增加封裝性、包裹彈性(packaging flexibility)、機(jī)能擴(kuò)充性)
若所有參數(shù)(包括被this指針?biāo)傅哪莻€(gè)隱喻參數(shù))皆須要類型轉(zhuǎn)換,請為此采用 non-member 函數(shù)
考慮寫一個(gè)不拋異常的 swap 函數(shù)
盡可能延后變量定義式的出現(xiàn)時(shí)間(可增加程序清晰度并改善程序效率)
盡量少做轉(zhuǎn)型動(dòng)作(舊式:(T)expression、T(expression);新式:const_cast(expression)、dynamic_cast(expression)、reinterpret_cast(expression)、static_cast(expression)、;盡量避免轉(zhuǎn)型、注重效率避免 dynamic_casts、盡量設(shè)計(jì)成無需轉(zhuǎn)型、可把轉(zhuǎn)型封裝成函數(shù)、寧可用新式轉(zhuǎn)型)
避免使用 handles(包括 引用、指針、迭代器)指向?qū)ο髢?nèi)部(以增加封裝性、使 const 成員函數(shù)的行為更像 const、降低 “虛吊號碼牌”(dangling handles,如懸空指針等)的可能性)
為 “異常安全” 而努力是值得的(異常安全函數(shù)(Exception-safe functions)即使發(fā)生異常也不會(huì)泄露資源或允許任何數(shù)據(jù)結(jié)構(gòu)敗壞,分為三種可能的保證:基本型、強(qiáng)列型、不拋異常型)
透徹了解 inlining 的里里外外(inlining 在大多數(shù) C++ 程序中是編譯期的行為;inline 函數(shù)是否真正 inline,取決于編譯器;大部分編譯器拒絕太過復(fù)雜(如帶有循環(huán)或遞歸)的函數(shù) inlining,而所有對 virtual 函數(shù)的調(diào)用(除非是最平淡無奇的)也都會(huì)使 inlining 落空;inline 造成的代碼膨脹可能帶來效率損失;inline 函數(shù)無法隨著程序庫的升級而升級)
將文件間的編譯依存關(guān)系降至最低(如果使用 object references 或 object pointers 可以完成任務(wù),就不要使用 objects;如果能過夠,盡量以 class 聲明式替換 class 定義式;為聲明式和定義式提供不同的頭文件)
確定你的 public 繼承塑模出 is-a(是一種)關(guān)系(適用于 base classes 身上的每一件事情一定適用于 derived classes 身上,因?yàn)槊恳粋€(gè) derived class 對象也都是一個(gè) base class 對象)
避免遮掩繼承而來的名字(可使用 using 聲明式或轉(zhuǎn)交函數(shù)(forwarding functions)來讓被遮掩的名字再見天日)
區(qū)分接口繼承和實(shí)現(xiàn)繼承(在 public 繼承之下,derived classes 總是繼承 base class 的接口;pure virtual 函數(shù)只具體指定接口繼承;非純 impure virtual 函數(shù)具體指定接口繼承及缺省實(shí)現(xiàn)繼承;non-virtual 函數(shù)具體指定接口繼承以及強(qiáng)制性實(shí)現(xiàn)繼承)
考慮 virtual 函數(shù)以外的其他選擇(如 Template Method 設(shè)計(jì)模式的 non-virtual interface(NVI)手法,將 virtual 函數(shù)替換為 “函數(shù)指針成員變量”,以 tr1::function 成員變量替換 virtual 函數(shù),將繼承體系內(nèi)的 virtual 函數(shù)替換為另一個(gè)繼承體系內(nèi)的 virtual 函數(shù))
絕不重新定義繼承而來的 non-virtual 函數(shù)
絕不重新定義繼承而來的缺省參數(shù)值,因?yàn)槿笔?shù)值是靜態(tài)綁定(statically bound),而 virtual 函數(shù)卻是動(dòng)態(tài)綁定(dynamically bound)
通過復(fù)合塑模 has-a(有一個(gè))或 “根據(jù)某物實(shí)現(xiàn)出”(在應(yīng)用域(application domain),復(fù)合意味 has-a(有一個(gè));在實(shí)現(xiàn)域(implementation domain),復(fù)合意味著 is-implemented-in-terms-of(根據(jù)某物實(shí)現(xiàn)出))
明智而審慎地使用 private 繼承(private 繼承意味著 is-implemented-in-terms-of(根據(jù)某物實(shí)現(xiàn)出),盡可能使用復(fù)合,當(dāng) derived class 需要訪問 protected base class 的成員,或需要重新定義繼承而來的時(shí)候 virtual 函數(shù),或需要 empty base 最優(yōu)化時(shí),才使用 private 繼承)
明智而審慎地使用多重繼承(多繼承比單一繼承復(fù)雜,可能導(dǎo)致新的歧義性,以及對 virtual 繼承的需要,但確有正當(dāng)用途,如 “public 繼承某個(gè) interface class” 和 “private 繼承某個(gè)協(xié)助實(shí)現(xiàn)的 class”;virtual 繼承可解決多繼承下菱形繼承的二義性問題,但會(huì)增加大小、速度、初始化及賦值的復(fù)雜度等等成本)
了解隱式接口和編譯期多態(tài)(class 和 templates 都支持接口(interfaces)和多態(tài)(polymorphism);class 的接口是以簽名為中心的顯式的(explicit),多態(tài)則是通過 virtual 函數(shù)發(fā)生于運(yùn)行期;template 的接口是奠基于有效表達(dá)式的隱式的(implicit),多態(tài)則是通過 template 具現(xiàn)化和函數(shù)重載解析(function overloading resolution)發(fā)生于編譯期)
了解 typename 的雙重意義(聲明 template 類型參數(shù)是,前綴關(guān)鍵字 class 和 typename 的意義完全相同;請使用關(guān)鍵字 typename 標(biāo)識嵌套從屬類型名稱,但不得在基類列(base class lists)或成員初值列(member initialization list)內(nèi)以它作為 basee class 修飾符)
學(xué)習(xí)處理模板化基類內(nèi)的名稱(可在 derived class templates 內(nèi)通過 this-&gt; 指涉 base class templates 內(nèi)的成員名稱,或藉由一個(gè)明白寫出的 “base class 資格修飾符” 完成)
將與參數(shù)無關(guān)的代碼抽離 templates(因類型模板參數(shù)(non-type template parameters)而造成代碼膨脹往往可以通過函數(shù)參數(shù)或 class 成員變量替換 template 參數(shù)來消除;因類型參數(shù)(type parameters)而造成的代碼膨脹往往可以通過讓帶有完全相同二進(jìn)制表述(binary representations)的實(shí)現(xiàn)類型(instantiation types)共享實(shí)現(xiàn)碼)
運(yùn)用成員函數(shù)模板接受所有兼容類型(請使用成員函數(shù)模板(member function templates)生成 “可接受所有兼容類型” 的函數(shù);聲明 member templates 用于 “泛化 copy 構(gòu)造” 或 “泛化 assignment 操作” 時(shí)還需要聲明正常的 copy 構(gòu)造函數(shù)和 copy assignment 操作符)
需要類型轉(zhuǎn)換時(shí)請為模板定義非成員函數(shù)(當(dāng)我們編寫一個(gè) class template,而它所提供之 “與此 template 相關(guān)的” 函數(shù)支持 “所有參數(shù)之隱式類型轉(zhuǎn)換” 時(shí),請將那些函數(shù)定義為 “class template 內(nèi)部的 friend 函數(shù)”)
請使用 traits classes 表現(xiàn)類型信息(traits classes 通過 templates 和 “templates 特化” 使得 “類型相關(guān)信息” 在編譯期可用,通過重載技術(shù)(overloading)實(shí)現(xiàn)在編譯期對類型執(zhí)行 if…else 測試)
認(rèn)識 template 元編程(模板元編程(TMP,template metaprogramming)可將工作由運(yùn)行期移往編譯期,因此得以實(shí)現(xiàn)早期錯(cuò)誤偵測和更高的執(zhí)行效率;TMP 可被用來生成 “給予政策選擇組合”(based on combinations of policy choices)的客戶定制代碼,也可用來避免生成對某些特殊類型并不適合的代碼)
了解 new-handler 的行為(set_new_handler 允許客戶指定一個(gè)在內(nèi)存分配無法獲得滿足時(shí)被調(diào)用的函數(shù);nothrow new 是一個(gè)頗具局限的工具,因?yàn)樗贿m用于內(nèi)存分配(operator new),后繼的構(gòu)造函數(shù)調(diào)用還是可能拋出異常)
Google C++ Style Guide
英文:Google C++ Style Guide  :http://t.cn/RqhluJP
中文:C++ 風(fēng)格指南:http://t.cn/ELDTnur
Google C++ Style Guide 圖
圖片來源于:CSDN . 一張圖總結(jié)Google C++編程規(guī)范(Google C++ Style Guide)
STL
STL 索引
STL 方法含義索引:http://t.cn/E4WMXXs
STL 容器
容器的詳細(xì)說明:http://t.cn/E4WMXXs
容器底層數(shù)據(jù)結(jié)構(gòu)時(shí)間復(fù)雜度有無序可不可重復(fù)其他
array數(shù)組隨機(jī)讀改 O(1)無序可重復(fù)支持快速隨機(jī)訪問
vector數(shù)組隨機(jī)讀改、尾部插入、尾部刪除 O(1)
頭部插入、頭部刪除 O(n)無序可重復(fù)支持快速隨機(jī)訪問
list雙向鏈表插入、刪除 O(1)
隨機(jī)讀改 O(n)無序可重復(fù)支持快速增刪
deque雙端隊(duì)列頭尾插入、頭尾刪除 O(1)無序可重復(fù)一個(gè)中央控制器 + 多個(gè)緩沖區(qū),支持首尾快速增刪,支持隨機(jī)訪問
stackdeque / list頂部插入、頂部刪除 O(1)無序可重復(fù)deque 或 list 封閉頭端開口,不用 vector 的原因應(yīng)該是容量大小有限制,擴(kuò)容耗時(shí)
queuedeque / list尾部插入、頭部刪除 O(1)無序可重復(fù)deque 或 list 封閉頭端開口,不用 vector 的原因應(yīng)該是容量大小有限制,擴(kuò)容耗時(shí)
priority_queuevector + max-heap插入、刪除 O(log2n)有序可重復(fù)vector容器+heap處理規(guī)則
set紅黑樹插入、刪除、查找 O(log2n)有序不可重復(fù)
multiset紅黑樹插入、刪除、查找 O(log2n)有序可重復(fù)
map紅黑樹插入、刪除、查找 O(log2n)有序不可重復(fù)
multimap紅黑樹插入、刪除、查找 O(log2n)有序可重復(fù)
hash_set哈希表插入、刪除、查找 O(1) 最差 O(n)無序不可重復(fù)
hash_multiset哈希表插入、刪除、查找 O(1) 最差 O(n)無序可重復(fù)
hash_map哈希表插入、刪除、查找 O(1) 最差 O(n)無序不可重復(fù)
hash_multimap哈希表插入、刪除、查找 O(1) 最差 O(n)無序可重復(fù)
STL 算法
http://t.cn/aEv0DV
算法底層算法時(shí)間復(fù)雜度可不可重復(fù)
find順序查找O(n)可重復(fù)
sort內(nèi)省排序O(n*log2n)可重復(fù)
數(shù)據(jù)結(jié)構(gòu)
順序結(jié)構(gòu)
順序棧(Sequence Stack)
SqStack.cpp:http://t.cn/E4WxO0b
順序棧數(shù)據(jù)結(jié)構(gòu)和圖片
typedef struct {
ElemType *elem;
int top;
int size;
int increment;
} SqSrack;
隊(duì)列(Sequence Queue)
隊(duì)列數(shù)據(jù)結(jié)構(gòu)
typedef struct {
ElemType * elem;
int front;
int rear;
int maxSize;
}SqQueue;
非循環(huán)隊(duì)列
非循環(huán)隊(duì)列圖片
SqQueue.rear++
循環(huán)隊(duì)列
循環(huán)隊(duì)列圖片
SqQueue.rear = (SqQueue.rear + 1) % SqQueue.maxSize
順序表(Sequence List)
SqList.cpp
順序表數(shù)據(jù)結(jié)構(gòu)和圖片
typedef struct {
ElemType *elem;
int length;
int size;
int increment;
} SqList;
鏈?zhǔn)浇Y(jié)構(gòu)
LinkList.cpp
LinkList_with_head.cpp
鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList;
鏈隊(duì)列(Link Queue)
鏈隊(duì)列圖片
線性表的鏈?zhǔn)奖硎?div style="height:15px;">單鏈表(Link List)
單鏈表圖片
雙向鏈表(Du-Link-List)
雙向鏈表圖片
循環(huán)鏈表(Cir-Link-List)
循環(huán)鏈表圖片
哈希表
HashTable.cpp
概念
哈希函數(shù):H(key): K -> D , key ∈ K
構(gòu)造方法
直接定址法
除留余數(shù)法
數(shù)字分析法
折疊法
平方取中法
沖突處理方法
鏈地址法:key 相同的用單鏈表鏈接
開放定址法
線性探測法:key 相同 -> 放到 key 的下一個(gè)位置,`Hi = (H(key) + i) % m`
二次探測法:key 相同 -> 放到 `Di = 1^2, -1^2, …, ±(k)^2,(k<=m/2)`
隨機(jī)探測法:`H = (H(key) + 偽隨機(jī)數(shù)) % m`
線性探測的哈希表數(shù)據(jù)結(jié)構(gòu)
線性探測的哈希表數(shù)據(jù)結(jié)構(gòu)和圖片
typedef char KeyType;
typedef struct {
KeyType key;
}RcdType;
typedef struct {
RcdType *rcd;
int size;
int count;
bool *tag;
}HashTable;
遞歸
概念
函數(shù)直接或間接地調(diào)用自身
遞歸與分治
分治法
問題的分解
問題規(guī)模的分解
折半查找(遞歸)
歸并查找(遞歸)
快速排序(遞歸)
遞歸與迭代
迭代:反復(fù)利用變量舊值推出新值
折半查找(迭代)
歸并查找(迭代)
廣義表
頭尾鏈表存儲(chǔ)表示
廣義表的頭尾鏈表存儲(chǔ)表示和圖片
// 廣義表的頭尾鏈表存儲(chǔ)表示
typedef enum {ATOM, LIST} ElemTag;
// ATOM==0:原子,LIST==1:子表
typedef struct GLNode {
ElemTag tag;
// 公共部分,用于區(qū)分原子結(jié)點(diǎn)和表結(jié)點(diǎn)
union {
// 原子結(jié)點(diǎn)和表結(jié)點(diǎn)的聯(lián)合部分
AtomType atom;
// atom 是原子結(jié)點(diǎn)的值域,AtomType 由用戶定義
struct {
struct GLNode *hp, *tp;
} ptr;
// ptr 是表結(jié)點(diǎn)的指針域,prt.hp 和 ptr.tp 分別指向表頭和表尾
} a;
} *GList, GLNode;
擴(kuò)展線性鏈表存儲(chǔ)表示
擴(kuò)展線性鏈表存儲(chǔ)表示和圖片
// 廣義表的擴(kuò)展線性鏈表存儲(chǔ)表示
typedef enum {ATOM, LIST} ElemTag;
// ATOM==0:原子,LIST==1:子表
typedef struct GLNode1 {
ElemTag tag;
// 公共部分,用于區(qū)分原子結(jié)點(diǎn)和表結(jié)點(diǎn)
union {
// 原子結(jié)點(diǎn)和表結(jié)點(diǎn)的聯(lián)合部分
AtomType atom; // 原子結(jié)點(diǎn)的值域
struct GLNode1 *hp; // 表結(jié)點(diǎn)的表頭指針
} a;
struct GLNode1 *tp;
// 相當(dāng)于線性鏈表的 next,指向下一個(gè)元素結(jié)點(diǎn)
} *GList1, GLNode1;
二叉樹
BinaryTree.cpp
性質(zhì)
非空二叉樹第 i 層最多 2(i-1) 個(gè)結(jié)點(diǎn) (i >= 1)
深度為 k 的二叉樹最多 2k - 1 個(gè)結(jié)點(diǎn) (k >= 1)
度為 0 的結(jié)點(diǎn)數(shù)為 n0,度為 2 的結(jié)點(diǎn)數(shù)為 n2,則 n0 = n2 + 1
有 n 個(gè)結(jié)點(diǎn)的完全二叉樹深度 k = ? log2(n) ? + 1
對于含 n 個(gè)結(jié)點(diǎn)的完全二叉樹中編號為 i (1 <= i <= n) 的結(jié)點(diǎn)
若 i = 1,為根,否則雙親為 ? i / 2 ?
若 2i > n,則 i 結(jié)點(diǎn)沒有左孩子,否則孩子編號為 2i
若 2i + 1 > n,則 i 結(jié)點(diǎn)沒有右孩子,否則孩子編號為 2i + 1
存儲(chǔ)結(jié)構(gòu)
二叉樹數(shù)據(jù)結(jié)構(gòu)
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
順序存儲(chǔ)
二叉樹順序存儲(chǔ)圖片
鏈?zhǔn)酱鎯?chǔ)
二叉樹鏈?zhǔn)酱鎯?chǔ)圖片
遍歷方式
先序遍歷
中序遍歷
后續(xù)遍歷
層次遍歷
分類
滿二叉樹
完全二叉樹(堆)
大頂堆:根 >= 左 && 根 >= 右
小頂堆:根 <= 左 && 根 <= 右
二叉查找樹(二叉排序樹):左 < 根 < 右
平衡二叉樹(AVL樹):| 左子樹樹高 - 右子樹樹高 | <= 1
最小失衡樹:平衡二叉樹插入新結(jié)點(diǎn)導(dǎo)致失衡的子樹:調(diào)整:
LL型:根的左孩子右旋
RR型:根的右孩子左旋
LR型:根的左孩子左旋,再右旋
RL型:右孩子的左子樹,先右旋,再左旋
其他樹及森林
樹的存儲(chǔ)結(jié)構(gòu)
雙親表示法
雙親孩子表示法
孩子兄弟表示法
并查集
一種不相交的子集所構(gòu)成的集合 S = {S1, S2, …, Sn}
平衡二叉樹(AVL樹)
性質(zhì)
| 左子樹樹高 - 右子樹樹高 | <= 1
平衡二叉樹必定是二叉搜索樹,反之則不一定
最小二叉平衡樹的節(jié)點(diǎn)的公式:F(n)=F(n-1)+F(n-2)+1 (1 是根節(jié)點(diǎn),F(xiàn)(n-1) 是左子樹的節(jié)點(diǎn)數(shù)量,F(xiàn)(n-2) 是右子樹的節(jié)點(diǎn)數(shù)量)
平衡二叉樹圖片
最小失衡樹
平衡二叉樹插入新結(jié)點(diǎn)導(dǎo)致失衡的子樹
調(diào)整:
LL 型:根的左孩子右旋
RR 型:根的右孩子左旋
LR 型:根的左孩子左旋,再右旋
RL 型:右孩子的左子樹,先右旋,再左旋
紅黑樹
紅黑樹的特征是什么?
節(jié)點(diǎn)是紅色或黑色。
根是黑色。
所有葉子都是黑色(葉子是 NIL 節(jié)點(diǎn))。
每個(gè)紅色節(jié)點(diǎn)必須有兩個(gè)黑色的子節(jié)點(diǎn)。(從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)。)(新增節(jié)點(diǎn)的父節(jié)點(diǎn)必須相同)
從任一節(jié)點(diǎn)到其每個(gè)葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。(新增節(jié)點(diǎn)必須為紅)
調(diào)整
變色
左旋
右旋
應(yīng)用
關(guān)聯(lián)數(shù)組:如 STL 中的 map、set
紅黑樹、B 樹、B+ 樹的區(qū)別?
紅黑樹的深度比較大,而 B 樹和 B+ 樹的深度則相對要小一些
B+ 樹則將數(shù)據(jù)都保存在葉子節(jié)點(diǎn),同時(shí)通過鏈表的形式將他們連接在一起。
B 樹(B-tree)、B+ 樹(B+-tree)
B 樹、B+ 樹圖片
B 樹(B-tree)、B+ 樹(B+-tree)特點(diǎn)
一般化的二叉查找樹(binary search tree)
“矮胖”,內(nèi)部(非葉子)節(jié)點(diǎn)可以擁有可變數(shù)量的子節(jié)點(diǎn)(數(shù)量范圍預(yù)先定義好)
應(yīng)用
大部分文件系統(tǒng)、數(shù)據(jù)庫系統(tǒng)都采用B樹、B+樹作為索引結(jié)構(gòu)
區(qū)別
B+樹中只有葉子節(jié)點(diǎn)會(huì)帶有指向記錄的指針(ROWID),而B樹則所有節(jié)點(diǎn)都帶有,在內(nèi)部節(jié)點(diǎn)出現(xiàn)的索引項(xiàng)不會(huì)再出現(xiàn)在葉子節(jié)點(diǎn)中。
B+樹中所有葉子節(jié)點(diǎn)都是通過指針連接在一起,而B樹不會(huì)。
B樹的優(yōu)點(diǎn)
對于在內(nèi)部節(jié)點(diǎn)的數(shù)據(jù),可直接得到,不必根據(jù)葉子節(jié)點(diǎn)來定位。
B+樹的優(yōu)點(diǎn)
非葉子節(jié)點(diǎn)不會(huì)帶上 ROWID,這樣,一個(gè)塊中可以容納更多的索引項(xiàng),一是可以降低樹的高度。二是一個(gè)內(nèi)部節(jié)點(diǎn)可以定位更多的葉子節(jié)點(diǎn)。
葉子節(jié)點(diǎn)之間通過指針來連接,范圍掃描將十分簡單,而對于B樹來說,則需要在葉子節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)不停的往返移動(dòng)。
B 樹、B+ 樹區(qū)別來自:differences-between-b-trees-and-b-trees、B樹和B+樹的區(qū)別:
http://t.cn/RrBAaZa
http://t.cn/E4WJhmZ
八叉樹
八叉樹圖片
八叉樹(octree),或稱八元樹,是一種用于描述三維空間(劃分空間)的樹狀數(shù)據(jù)結(jié)構(gòu)。八叉樹的每個(gè)節(jié)點(diǎn)表示一個(gè)正方體的體積元素,每個(gè)節(jié)點(diǎn)有八個(gè)子節(jié)點(diǎn),這八個(gè)子節(jié)點(diǎn)所表示的體積元素加在一起就等于父節(jié)點(diǎn)的體積。一般中心點(diǎn)作為節(jié)點(diǎn)的分叉中心。
用途
三維計(jì)算機(jī)圖形
最鄰近搜索
算法
排序
http://t.cn/E4WJUGz
排序算法平均時(shí)間復(fù)雜度最差時(shí)間復(fù)雜度空間復(fù)雜度數(shù)據(jù)對象穩(wěn)定性
冒泡排序O(n2)O(n2)O(1)穩(wěn)定
選擇排序O(n2)O(n2)O(1)數(shù)組不穩(wěn)定、鏈表穩(wěn)定
插入排序O(n2)O(n2)O(1)穩(wěn)定
快速排序O(n*log2n)O(n2)O(log2n)不穩(wěn)定
堆排序O(n*log2n)O(n*log2n)O(1)不穩(wěn)定
歸并排序O(n*log2n)O(n*log2n)O(n)穩(wěn)定
希爾排序O(n*log2n)O(n2)O(1)不穩(wěn)定
計(jì)數(shù)排序O(n+m)O(n+m)O(n+m)穩(wěn)定
桶排序O(n)O(n)O(m)穩(wěn)定
基數(shù)排序O(k*n)O(n2)
穩(wěn)定
均按從小到大排列
k:代表數(shù)值中的 “數(shù)位” 個(gè)數(shù)
n:代表數(shù)據(jù)規(guī)模
m:代表數(shù)據(jù)的最大值減最小值
來自:wikipedia . 排序算法
查找
查找算法平均時(shí)間復(fù)雜度空間復(fù)雜度查找條件
順序查找O(n)O(1)無序或有序
二分查找(折半查找)O(log2n)O(1)有序
插值查找O(log2(log2n))O(1)有序
斐波那契查找O(log2n)O(1)有序
哈希查找O(1)O(n)無序或有序
二叉查找樹(二叉搜索樹查找)O(log2n)
紅黑樹O(log2n)
2-3樹O(log2n - log3n)
B樹/B+樹O(log2n)
圖搜索算法
圖搜索算法數(shù)據(jù)結(jié)構(gòu)遍歷時(shí)間復(fù)雜度空間復(fù)雜度
BFS廣度優(yōu)先搜索鄰接矩陣
鄰接鏈表O(|v|2)
O(|v|+|E|)O(|v|2)
O(|v|+|E|)
DFS深度優(yōu)先搜索鄰接矩陣
鄰接鏈表O(|v|2)
O(|v|+|E|)O(|v|2)
O(|v|+|E|)
其他算法
算法思想應(yīng)用
分治法把一個(gè)復(fù)雜的問題分成兩個(gè)或更多的相同或相似的子問題,直到最后子問題可以簡單的直接求解,原問題的解即子問題的解的合并循環(huán)賽日程安排問題、排序算法(快速排序、歸并排序)
動(dòng)態(tài)規(guī)劃通過把原問題分解為相對簡單的子問題的方式求解復(fù)雜問題的方法,適用于有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題背包問題、斐波那契數(shù)列
貪心法一種在每一步選擇中都采取在當(dāng)前狀態(tài)下最好或最優(yōu)(即最有利)的選擇,從而希望導(dǎo)致結(jié)果是最好或最優(yōu)的算法旅行推銷員問題(最短路徑問題)、最小生成樹、哈夫曼編碼
Problems
Single Problem
Chessboard Coverage Problem(棋盤覆蓋問題)
Knapsack Problem(背包問題)
Neumann Neighbor Problem(馮諾依曼鄰居問題)
Round Robin Problem(循環(huán)賽日程安排問題)
Tubing Problem(輸油管道問題)
Leetcode Problems
Github . haoel/leetcode
Github . pezy/LeetCode
劍指 Offer
Github . zhedahht/CodingInterviewChinese2
Github . gatieme/CodingInterviews
Cracking the Coding Interview 程序員面試金典
Github . careercup/ctci
牛客網(wǎng) . 程序員面試金典
??途W(wǎng)
??途W(wǎng) . 在線編程專題
操作系統(tǒng)
進(jìn)程與線程
對于有線程系統(tǒng):
進(jìn)程是資源分配的獨(dú)立單位
線程是資源調(diào)度的獨(dú)立單位
對于無線程系統(tǒng):
進(jìn)程是資源調(diào)度、分配的獨(dú)立單位
進(jìn)程之間的通信方式以及優(yōu)缺點(diǎn)
管道(PIPE)
優(yōu)點(diǎn):簡單方便
缺點(diǎn):
優(yōu)點(diǎn):可以實(shí)現(xiàn)任意關(guān)系的進(jìn)程間的通信
缺點(diǎn):
有名管道:一種半雙工的通信方式,它允許無親緣關(guān)系進(jìn)程間的通信
無名管道:一種半雙工的通信方式,只能在具有親緣關(guān)系的進(jìn)程間使用(父子進(jìn)程)
局限于單向通信
只能創(chuàng)建在它的進(jìn)程以及其有親緣關(guān)系的進(jìn)程之間
緩沖區(qū)有限
長期存于系統(tǒng)中,使用不當(dāng)容易出錯(cuò)
緩沖區(qū)有限
信號量(Semaphore):一個(gè)計(jì)數(shù)器,可以用來控制多個(gè)線程對共享資源的訪問
優(yōu)點(diǎn):可以同步進(jìn)程
缺點(diǎn):信號量有限
信號(Signal):一種比較復(fù)雜的通信方式,用于通知接收進(jìn)程某個(gè)事件已經(jīng)發(fā)生
消息隊(duì)列(Message Queue):是消息的鏈表,存放在內(nèi)核中并由消息隊(duì)列標(biāo)識符標(biāo)識
優(yōu)點(diǎn):可以實(shí)現(xiàn)任意進(jìn)程間的通信,并通過系統(tǒng)調(diào)用函數(shù)來實(shí)現(xiàn)消息發(fā)送和接收之間的同步,無需考慮同步問題,方便
缺點(diǎn):信息的復(fù)制需要額外消耗 CPU 的時(shí)間,不適宜于信息量大或操作頻繁的場合
共享內(nèi)存(Shared Memory):映射一段能被其他進(jìn)程所訪問的內(nèi)存,這段共享內(nèi)存由一個(gè)進(jìn)程創(chuàng)建,但多個(gè)進(jìn)程都可以訪問
優(yōu)點(diǎn):無須復(fù)制,快捷,信息量大
缺點(diǎn):
通信是通過將共享空間緩沖區(qū)直接附加到進(jìn)程的虛擬地址空間中來實(shí)現(xiàn)的,因此進(jìn)程間的讀寫操作的同步問題
利用內(nèi)存緩沖區(qū)直接交換信息,內(nèi)存的實(shí)體存在于計(jì)算機(jī)中,只能同一個(gè)計(jì)算機(jī)系統(tǒng)中的諸多進(jìn)程共享,不方便網(wǎng)絡(luò)通信
套接字(Socket):可用于不同及其間的進(jìn)程通信
優(yōu)點(diǎn):
缺點(diǎn):需對傳輸?shù)臄?shù)據(jù)進(jìn)行解析,轉(zhuǎn)化成應(yīng)用級的數(shù)據(jù)。
傳輸數(shù)據(jù)為字節(jié)級,傳輸數(shù)據(jù)可自定義,數(shù)據(jù)量小效率高
傳輸數(shù)據(jù)時(shí)間短,性能高
適合于客戶端和服務(wù)器端之間信息實(shí)時(shí)交互
可以加密,數(shù)據(jù)安全性強(qiáng)
線程之間的通信方式
鎖機(jī)制:包括互斥鎖/量(mutex)、讀寫鎖(reader-writer lock)、自旋鎖(spin lock)、條件變量(condition)
互斥鎖/量(mutex):提供了以排他方式防止數(shù)據(jù)結(jié)構(gòu)被并發(fā)修改的方法。
讀寫鎖(reader-writer lock):允許多個(gè)線程同時(shí)讀共享數(shù)據(jù),而對寫操作是互斥的。
自旋鎖(spin lock)與互斥鎖類似,都是為了保護(hù)共享資源。互斥鎖是當(dāng)資源被占用,申請者進(jìn)入睡眠狀態(tài);而自旋鎖則循環(huán)檢測保持著是否已經(jīng)釋放鎖。
條件變量(condition):可以以原子的方式阻塞進(jìn)程,直到某個(gè)特定條件為真為止。對條件的測試是在互斥鎖的保護(hù)下進(jìn)行的。條件變量始終與互斥鎖一起使用。
信號量機(jī)制(Semaphore)
無名線程信號量
命名線程信號量
信號機(jī)制(Signal):類似進(jìn)程間的信號處理
屏障(barrier):屏障允許每個(gè)線程等待,直到所有的合作線程都達(dá)到某一點(diǎn),然后從該點(diǎn)繼續(xù)執(zhí)行。
線程間的通信目的主要是用于線程同步,所以線程沒有像進(jìn)程通信中的用于數(shù)據(jù)交換的通信機(jī)制
進(jìn)程之間的通信方式以及優(yōu)缺點(diǎn)來源于:進(jìn)程線程面試題總結(jié)
進(jìn)程之間私有和共享的資源
私有:地址空間、堆、全局變量、棧、寄存器
共享:代碼段,公共數(shù)據(jù),進(jìn)程目錄,進(jìn)程 ID
線程之間私有和共享的資源
私有:線程棧,寄存器,程序寄存器
共享:堆,地址空間,全局變量,靜態(tài)變量
多進(jìn)程與多線程間的對比、優(yōu)劣與選擇
對比
對比維度多進(jìn)程多線程總結(jié)
數(shù)據(jù)共享、同步數(shù)據(jù)共享復(fù)雜,需要用 IPC;數(shù)據(jù)是分開的,同步簡單因?yàn)楣蚕磉M(jìn)程數(shù)據(jù),數(shù)據(jù)共享簡單,但也是因?yàn)檫@個(gè)原因?qū)е峦綇?fù)雜各有優(yōu)勢
內(nèi)存、CPU占用內(nèi)存多,切換復(fù)雜,CPU 利用率低占用內(nèi)存少,切換簡單,CPU 利用率高線程占優(yōu)
創(chuàng)建銷毀、切換創(chuàng)建銷毀、切換復(fù)雜,速度慢創(chuàng)建銷毀、切換簡單,速度很快線程占優(yōu)
編程、調(diào)試編程簡單,調(diào)試簡單編程復(fù)雜,調(diào)試復(fù)雜進(jìn)程占優(yōu)
可靠性進(jìn)程間不會(huì)互相影響一個(gè)線程掛掉將導(dǎo)致整個(gè)進(jìn)程掛掉進(jìn)程占優(yōu)
分布式適應(yīng)于多核、多機(jī)分布式;如果一臺(tái)機(jī)器不夠,擴(kuò)展到多臺(tái)機(jī)器比較簡單適應(yīng)于多核分布式進(jìn)程占優(yōu)
優(yōu)劣
優(yōu)劣多進(jìn)程多線程
優(yōu)點(diǎn)編程、調(diào)試簡單,可靠性較高創(chuàng)建、銷毀、切換速度快,內(nèi)存、資源占用小
缺點(diǎn)創(chuàng)建、銷毀、切換速度慢,內(nèi)存、資源占用大編程、調(diào)試復(fù)雜,可靠性較差
選擇
需要頻繁創(chuàng)建銷毀的優(yōu)先用線程
需要進(jìn)行大量計(jì)算的優(yōu)先使用線程
強(qiáng)相關(guān)的處理用線程,弱相關(guān)的處理用進(jìn)程
可能要擴(kuò)展到多機(jī)分布的用進(jìn)程,多核分布的用線程
都滿足需求的情況下,用你最熟悉、最拿手的方式
多進(jìn)程與多線程間的對比、優(yōu)劣與選擇來自:多線程還是多進(jìn)程的選擇及區(qū)別
Linux 內(nèi)核的同步方式
原因
在現(xiàn)代操作系統(tǒng)里,同一時(shí)間可能有多個(gè)內(nèi)核執(zhí)行流在執(zhí)行,因此內(nèi)核其實(shí)象多進(jìn)程多線程編程一樣也需要一些同步機(jī)制來同步各執(zhí)行單元對共享數(shù)據(jù)的訪問。尤其是在多處理器系統(tǒng)上,更需要一些同步機(jī)制來同步不同處理器上的執(zhí)行單元對共享的數(shù)據(jù)的訪問。
同步方式
原子操作
信號量(semaphore)
讀寫信號量(rw_semaphore)
自旋鎖(spinlock)
大內(nèi)核鎖(BKL,Big Kernel Lock)
讀寫鎖(rwlock)
大讀者鎖(brlock-Big Reader Lock)
讀-拷貝修改(RCU,Read-Copy Update)
順序鎖(seqlock)
來自:Linux 內(nèi)核的同步機(jī)制,第 1 部分、Linux 內(nèi)核的同步機(jī)制,第 2 部分
死鎖
原因
系統(tǒng)資源不足
資源分配不當(dāng)
進(jìn)程運(yùn)行推進(jìn)順序不合適
產(chǎn)生條件
互斥
請求和保持
不剝奪
環(huán)路
預(yù)防
打破互斥條件:改造獨(dú)占性資源為虛擬資源,大部分資源已無法改造。
打破不可搶占條件:當(dāng)一進(jìn)程占有一獨(dú)占性資源后又申請一獨(dú)占性資源而無法滿足,則退出原占有的資源。
打破占有且申請條件:采用資源預(yù)先分配策略,即進(jìn)程運(yùn)行前申請全部資源,滿足則運(yùn)行,不然就等待,這樣就不會(huì)占有且申請。
打破循環(huán)等待條件:實(shí)現(xiàn)資源有序分配策略,對所有設(shè)備實(shí)現(xiàn)分類編號,所有進(jìn)程只能采用按序號遞增的形式申請資源。
有序資源分配法
銀行家算法
文件系統(tǒng)
Windows:FCB 表 + FAT + 位圖
Unix:inode + 混合索引 + 成組鏈接
主機(jī)字節(jié)序與網(wǎng)絡(luò)字節(jié)序
主機(jī)字節(jié)序(CPU 字節(jié)序)
概念
主機(jī)字節(jié)序又叫 CPU 字節(jié)序,其不是由操作系統(tǒng)決定的,而是由 CPU 指令集架構(gòu)決定的。主機(jī)字節(jié)序分為兩種:
大端字節(jié)序(Big Endian):高序字節(jié)存儲(chǔ)在低位地址,低序字節(jié)存儲(chǔ)在高位地址
小端字節(jié)序(Little Endian):高序字節(jié)存儲(chǔ)在高位地址,低序字節(jié)存儲(chǔ)在低位地址
存儲(chǔ)方式
32 位整數(shù) 0x12345678 是從起始位置為 0x00 的地址開始存放,則:
內(nèi)存地址0x000x010x020x03
大端12345678
小端78563412
大端小端圖片
大端序
小端序判斷大端小端
判斷大端小端
可以這樣判斷自己 CPU 字節(jié)序是大端還是小端:
#include <iostream>
using namespace std;
int main()
{
int i = 0x12345678;
if (*((char*)&i) == 0x12)
cout << '大端' << endl;
else
cout << '小端' << endl;
return 0;
}
各架構(gòu)處理器的字節(jié)序
x86(Intel、AMD)、MOS Technology 6502、Z80、VAX、PDP-11 等處理器為小端序;
Motorola 6800、Motorola 68000、PowerPC 970、System/370、SPARC(除 V9 外)等處理器為大端序;
ARM(默認(rèn)小端序)、PowerPC(除 PowerPC 970 外)、DEC Alpha、SPARC V9、MIPS、PA-RISC 及 IA64 的字節(jié)序是可配置的。
網(wǎng)絡(luò)字節(jié)序
網(wǎng)絡(luò)字節(jié)順序是 TCP/IP 中規(guī)定好的一種數(shù)據(jù)表示格式,它與具體的 CPU 類型、操作系統(tǒng)等無關(guān),從而可以保重?cái)?shù)據(jù)在不同主機(jī)之間傳輸時(shí)能夠被正確解釋。
網(wǎng)絡(luò)字節(jié)順序采用:大端(Big Endian)排列方式。
頁面置換算法
在地址映射過程中,若在頁面中發(fā)現(xiàn)所要訪問的頁面不在內(nèi)存中,則產(chǎn)生缺頁中斷。當(dāng)發(fā)生缺頁中斷時(shí),如果操作系統(tǒng)內(nèi)存中沒有空閑頁面,則操作系統(tǒng)必須在內(nèi)存選擇一個(gè)頁面將其移出內(nèi)存,以便為即將調(diào)入的頁面讓出空間。而用來選擇淘汰哪一頁的規(guī)則叫做頁面置換算法。
分類
全局置換:在整個(gè)內(nèi)存空間置換
局部置換:在本進(jìn)程中進(jìn)行置換
算法
全局:
工作集算法
缺頁率置換算法
局部:
最佳置換算法(OPT)
先進(jìn)先出置換算法(FIFO)
最近最久未使用(LRU)算法
時(shí)鐘(Clock)置換算法
計(jì)算機(jī)網(wǎng)絡(luò)
計(jì)算機(jī)經(jīng)網(wǎng)絡(luò)體系結(jié)構(gòu):
計(jì)算機(jī)經(jīng)網(wǎng)絡(luò)體系結(jié)構(gòu)各層作用及協(xié)議
分層作用協(xié)議
物理層通過媒介傳輸比特,確定機(jī)械及電氣規(guī)范(比特 Bit)RJ45、CLOCK、IEEE802.3(中繼器,集線器)
數(shù)據(jù)鏈路層將比特組裝成幀和點(diǎn)到點(diǎn)的傳遞(幀 Frame)PPP、FR、HDLC、VLAN、MAC(網(wǎng)橋,交換機(jī))
網(wǎng)絡(luò)層負(fù)責(zé)數(shù)據(jù)包從源到宿的傳遞和網(wǎng)際互連(包 Packet)IP、ICMP、ARP、RARP、OSPF、IPX、RIP、IGRP(路由器)
運(yùn)輸層提供端到端的可靠報(bào)文傳遞和錯(cuò)誤恢復(fù)( 段Segment)TCP、UDP、SPX
會(huì)話層建立、管理和終止會(huì)話(會(huì)話協(xié)議數(shù)據(jù)單元 SPDU)NFS、SQL、NETBIOS、RPC
表示層對數(shù)據(jù)進(jìn)行翻譯、加密和壓縮(表示協(xié)議數(shù)據(jù)單元 PPDU)JPEG、MPEG、ASII
應(yīng)用層允許訪問OSI環(huán)境的手段(應(yīng)用協(xié)議數(shù)據(jù)單元 APDU)FTP、DNS、Telnet、SMTP、HTTP、WWW、NFS
物理層
傳輸數(shù)據(jù)的單位 ———— 比特
數(shù)據(jù)傳輸系統(tǒng):源系統(tǒng)(源點(diǎn)、發(fā)送器) --> 傳輸系統(tǒng) --> 目的系統(tǒng)(接收器、終點(diǎn))
通道:
單向通道(單工通道):只有一個(gè)方向通信,沒有反方向交互,如廣播
雙向交替通行(半雙工通信):通信雙方都可發(fā)消息,但不能同時(shí)發(fā)送或接收
雙向同時(shí)通信(全雙工通信):通信雙方可以同時(shí)發(fā)送和接收信息
通道復(fù)用技術(shù):
頻分復(fù)用(FDM,F(xiàn)requency Division Multiplexing):不同用戶在不同頻帶,所用用戶在同樣時(shí)間占用不同帶寬資源
時(shí)分復(fù)用(TDM,Time Division Multiplexing):不同用戶在同一時(shí)間段的不同時(shí)間片,所有用戶在不同時(shí)間占用同樣的頻帶寬度
波分復(fù)用(WDM,Wavelength Division Multiplexing):光的頻分復(fù)用
碼分復(fù)用(CDM,Code Division Multiplexing):不同用戶使用不同的碼,可以在同樣時(shí)間使用同樣頻帶通信
數(shù)據(jù)鏈路層
主要信道:
點(diǎn)對點(diǎn)信道
廣播信道
點(diǎn)對點(diǎn)信道
數(shù)據(jù)單元 ———— 幀
三個(gè)基本問題:
封裝成幀:把網(wǎng)絡(luò)層的 IP 數(shù)據(jù)報(bào)封裝成幀,SOH - 數(shù)據(jù)部分 - EOT
透明傳輸:不管數(shù)據(jù)部分什么字符,都能傳輸出去;可以通過字節(jié)填充方法解決(沖突字符前加轉(zhuǎn)義字符)
差錯(cuò)檢測:降低誤碼率(BER,Bit Error Rate),廣泛使用循環(huán)冗余檢測(CRC,Cyclic Redundancy Check)
點(diǎn)對點(diǎn)協(xié)議(Point-to-Point Protocol):
點(diǎn)對點(diǎn)協(xié)議(Point-to-Point Protocol):用戶計(jì)算機(jī)和 ISP 通信時(shí)所使用的協(xié)議
廣播信道
廣播通信:
硬件地址(物理地址、MAC 地址)
單播(unicast)幀(一對一):收到的幀的 MAC 地址與本站的硬件地址相同
廣播(broadcast)幀(一對全體):發(fā)送給本局域網(wǎng)上所有站點(diǎn)的幀
多播(multicast)幀(一對多):發(fā)送給本局域網(wǎng)上一部分站點(diǎn)的幀
來源:https://github.com/huihut/interview
本站僅提供存儲(chǔ)服務(wù),所有內(nèi)容均由用戶發(fā)布,如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,請點(diǎn)擊舉報(bào)
打開APP,閱讀全文并永久保存 查看更多類似文章
猜你喜歡
類似文章
C++中定義類的對象:用new和不用new有何區(qū)別?
《Effective C++》簡明筆記-上
C/C++常見面試題[轉(zhuǎn)帖]
C++語言學(xué)習(xí)筆記(一)
C primer第二次閱讀學(xué)習(xí)筆記(第18章:特殊工具與技術(shù):運(yùn)行時(shí)類型識別、exte...
UC頭條:[C 初階]類和對象(三)(上)
更多類似文章 >>
生活服務(wù)
分享 收藏 導(dǎo)長圖 關(guān)注 下載文章
綁定賬號成功
后續(xù)可登錄賬號暢享VIP特權(quán)!
如果VIP功能使用有故障,
可點(diǎn)擊這里聯(lián)系客服!

聯(lián)系客服