C++ 煉氣期之陣列探幽

1. 陣列概念

變數是記憶體中的一個儲存塊，大小由宣告時的資料型別決定。

陣列可以認為是變數的集合，在記憶體中表現為一片連續的儲存區域，其特點為：

同型別多個變數的集合。
每一個變數沒有自己的名字。
陣列會為每一個變數分配一個位置編號。
可以通過變數在陣列中的位置編號（下標）使用變數。

C++中稱陣列為複合型別，複合型別指除了基本型別之外或通過基本型別組合而成的新型別。如類、結構體、列舉……

陣列是一種資料結構，與棧、佇列、樹、圖……這類數結構不同，陣列是實體資料結構，有自己的實體記憶體描述。棧、佇列、樹……是抽象資料結構，或者說是一種資料儲存思想，沒有對應的物理儲存方案，需開發者自行設計邏輯儲存方案。

什麼時候使用陣列？

在需要儲存大量同型別資料的應用場景下可以考慮選擇陣列。因陣列中的變數是相鄰的，如同一條藤上的瓜（順藤摸瓜），存取起來非常方便快捷。

大部分抽象資料結構的底層都可藉助陣列來實現。

連續儲存的優點一眼可知，但是連續也會帶來新的問題，程式執行過程中，會產生記憶體碎片，當陣列需要的空間較大時，底層邏輯可能無法騰出一大片連續空間來。

當需要考慮充分利用空間時，連結串列當是首選。

下面，通過陣列的使用流程，讓我們全方面瞭解陣列。

2. 建立陣列

根據陣列在記憶體中的儲存位置，有 2 種建立方式：

靜態建立。
動態建立。

2.1 靜態建立

2.1.1 語法

建立陣列時需要指定 3 方面資訊：

陣列名：陣列名就是變數名，只是這個名稱指的是一片連續區域。
資料型別：陣列用來儲存什麼樣型別的資料。
陣列長度：編譯器需要根據陣列大小開闢空間。

int num[10];

如上語法，建立了可以儲存 10 個整型資料的陣列。

建立陣列後，怎麼存取陣列中的變數？

編譯器會為陣列中的 10 個 int 儲存塊從 0開始編號。編號從 0開始，到陣列長度-1結束，編號也稱為下標。如果需要存取陣列中的第一個變數中的資料，則如下程式碼可實現：

int num[10]; 
cout<<num[0]<<endl;

正因為陣列的下標屬性，陣列通常藉助迴圈語法結構進行整體遍歷。

建立陣列後是否存在資料？

遍歷一次陣列，便可以看到陣列中所有的資料資訊。

int num[10]; 
for(int i=0;i<10;i++){
	cout<<num[i]<<endl;
}

輸出結果可能會讓你摸不著頭。這是啥意思？

建立陣列後，陣列中會有資料資訊，是記憶體中相應位置曾經儲存過的或由編譯器隨機生成的資料。對於建立陣列初衷（儲存自己的資料）的你而言，這都是垃圾資料。

亂資料：每一次執行上述程式碼，結果可能都不一樣。

所以，必須對陣列進行初始化，這樣陣列中的資料才會有意義。

2.1.2 初始化

初始化指建立陣列後為陣列中的變數指定初始值。

初始化語法：

建立後通過迴圈語法結構賦值。

int num[10];
for(int i=0; i<10; i++) {
	num[i]=i*10;
}

單個變數賦值。

int num[10];
num[0]=10;

邊建立邊賦值，{}符號可以用來表示陣列字面常數。

//正確
int num[10]={1,3,4,9};

在賦值時，實際指定的值可以少於陣列的長度。如果反過來，如下程式碼則行不通。

//錯誤
int num[3]={1,3,4,9};

上述賦值程式碼，實際值超過陣列建立時的長度約束，語法上不能通過。如果邊建立、邊賦值分成 2 行，也是不行的。如下程式碼是錯誤的。

int num[3];
//錯誤
num=={1,3,4,9};

如下程式碼，省略陣列長度也是可以的，編譯器會根據給定的值判斷出陣列長度。

int num[]={1,3,4,9};

全部初始化為 0。如下程式碼，初始化時只指定一個值且為 0 時，這裡的語意不是指給陣列中的第一個變數賦值，而是為陣列中的所有變數指定初始值為 0。

int num[5]={0}; 
//輸出陣列所有值
for(int i=0; i<5; i++) {
	cout<<num[i]<<endl;
}

輸出結果：

如果用下面的程式碼進行初始化，語意是：陣列的第一個變數賦值為 1，其餘變數賦值都為 0。

int num[5]={1,0}; 
for(int i=0; i<5; i++) {
	cout<<num[i]<<endl;
}

輸出結果：

理解上述語法的語意後，以此類推，對於下面的程式碼，想必很容易猜到輸出結果：

int num[5]={1,2,0}; 
for(int i=0; i<5; i++) {
	cout<<num[i]<<endl;
}

C++11中提供更清晰、簡潔、安全的初始化語法。如下語法，是不是很簡潔、驚豔。陣列和{}之間可以不用等於號，太體貼了，生怕你多敲一個字母，會手痛。且為陣列中的每一個變數賦值 0。沒有多餘的廢話。

int num[5] {};
for(int i=0; i<5; i++) {
	cout<<num[i]<<endl;
}

當然，你一定要加一個等於號讓程式碼符合你曾經的認知也是可以的。

int num[5]= {};

除此之外，對陣列初始化時，禁止型別宿窄轉換。如下程式碼，會有編譯警告提示，2.5是浮點型別，儲存存到 int型別陣列中，是型別縮窄。C++11是禁止的。

int num[5] ={3,2.5};

2.1.3 越界問題

C++中使用陣列，沒有存取越界一說。所謂存取越界，指下標超過陣列建立時指定的大小範圍。

越界在Java語言中認定是語法錯誤。

int num[5];
//理論是越界的
num[6]=20;
for(int i=0; i<7; i++) {
    //輸出了 7 個資料
	cout<<num[i]<<endl;
}

上述程式碼，建立陣列時，確定了陣列長度為 5，其有效下標應該是0~4。但 num[6]=20能正確執行且迴圈輸出時居然能得到 20。

C++並不會阻止你的存取超過陣列邊界，但是，開發者需要從源頭上切斷這種行為。類似於相鄰兩家，關係很好，相互之間不設阻隔牆，但不意味著你能隨意出入對方家裡。

2.2.4 陣列與指標

陣列在記憶體中的儲存結構有 2 個部分：

儲存陣列資料的記憶體區域。
儲存陣列首地址的記憶體變數。

陣列名本質是指標變數，儲存著陣列的首地址，也是第一個儲存位置。

int num[5]={4,1,8,2,6};
cout<<"陣列的地址："<<num<<endl;
//輸出結果：
//陣列的地址：0x70fe00 16進位制描述的記憶體地址

如果要得到陣列第一個位置的資料，則需要使用*運運算元。

int num[5]={4,1,8,2,6};
cout<<"陣列中的第一個位置的資料："<<*num<<endl;
//陣列中的第一個位置的資料：4

除了使用*運運算元，還可以使用[下標]語法。兩者語法上有差異，但是語意是一樣的。可以認為[下標]存取語法是指標存取語法的簡化版。

int num[5]={4,1,8,2,6};
cout<<"陣列中的第一個位置的資料："<<num[0]<<endl;
//陣列中的第一個位置的資料：4

如果要存取其它位置的資料，可以通過移動指標實現。

Tip： num+1可以讓指標移到陣列的下一個變數位置。這裡的1具體移動多少，由建立陣列時指定的資料型別決定，如本文陣列是 int型別，1便是移動 4 位元組。

int num[5]={4,1,8,2,6};
cout<<"陣列中第二個位置的資料："<<*(num+1)<<endl;
//陣列中第二個位置的資料：1

當然，完全可以使用[下標]替代。

int num[5]={4,1,8,2,6};
cout<<"陣列中第二個位置的資料："<<num[1]<<endl;

指標是C++語言的一大特色，能夠讓開發者直接操作記憶體地址（屬於直接硬體操作），正因為此原因，編譯器無法干涉，所以指標移動的範圍只受限於實體記憶體大小的影響。如下程式碼能正常執行。

int num[5]={4,1,8,2,6};
//完全超界，但人家就是能執行 ，指標的手能伸到天涯海角
for(int i=0;i<1000000;i++){
	cout<<*(num+i)<<endl;
}

瞭解指標的特性後，也就不會奇怪為什麼存取陣列時能夠越界。使用指標時務必謹慎，需要靠個人行為對之約束。

2.2.5 小結

通過靜態建立語法建立的陣列，稱為靜態陣列，其特點如下：

在編譯時，就需要為陣列指定大小，或說陣列大小在編碼時就必須給定。
靜態建立陣列時不能使用 auto關鍵字。

//錯誤語法
auto  num[5];

陣列名中儲存有陣列大小的資訊。如下程式碼可以獲取到陣列長度。

int num[10];
//sizeof得到num實際佔用的記憶體空間，以位元組為單位
int len=sizeof(num)/4;
cout<<len;
//輸出：10

靜態陣列的資料儲存在棧中，在編譯期間進行空間分配，在生命週期結束後自動回收。

2.2 動態建立

動態建立：指陣列的大小可以在執行時動態指定，除此之外，和靜態建立的底層區別在於儲存位置的不同，動態建立的陣列的資料儲存在堆中。

堆的特點：

開發者可以根據自己的需要提出空間使用申請。
當空間不再需要時，開發者需要手動釋放空間。

先看一下建立語法：

int *num=new int[10];

程式碼解釋：

num是指標變數，用來儲存陣列的首地址。
new是運運算元，其作用是在堆中開闢空間，並把空間的首地址返回。
int[10]，指開闢空間的大小，以及儲存什麼型別的資料。

num是首地址，也是陣列中第一個位置的地址。

int *num=new int[10];
//初始化第一個位置的資料
*num=10;
cout<<"第一個位置的資料:"<<*num<<endl;

如下通過對整個陣列進行初始化：

int *num=new int[10];
for(int i=0; i<10; i++) {
	*(num+i)=i*10;
}
for(int i=0; i<10; i++) {
	cout<<*(num+i)<<endl;
}

輸出結果：

同樣可以使用[下標]語法結構，對存取陣列。

int *num=new int[10];
for(int i=0; i<10; i++) {
	num[i]=i*10;
}
for(int i=0; i<10; i++) {
	cout<<num[i]<<endl;
}

動態陣列可以在執行時改變陣列的大小。靜態建立方式是一錘定音的買賣，一旦確定後，就不能再改變。如下程式碼是正確的。

int *num=new int[10];
num=new int[20];

正因為動態陣列的動態性，無法通過程式碼獲得它的長度。

int *num=new int[10];
cout<<sizeof(num)/4<<endl; 
//輸出結果：2，並不是陣列的長度。

當動態陣列的使命結束後，開發者需要使用 delete運運算元手動釋放陣列所佔用的空間。

int *num=new int[10];
//delete num;語法上可行，會產生不確定行為
delete [] num;

這裡要注意，如果不加[]，語法上是沒有問題的，但是，會有不確定的因素存在，所以！請務必加[]。

3. 陣列效能分析

得益於陣列記憶體結構的連續性，只要知道資料的位置，便能快速存取到。查詢時間度複雜度可以達到O（1）。在查詢類的應用場景下，陣列儲存方案應該成為首選。

當在陣列中插入資料時，需要把資料向後移動為插入的資料挪出位置，且需要在建立陣列時預留足夠多的空間，否則會有資料丟失的風險。

//最後一位為預留位置
int num[10]= {1,2,3,4,5,6,7,8,9,0};
for(int i=0; i<10; i++) {
	cout<<num[i]<<"\t";
}
cout<<endl;
int newNum=0;
int pos=0;
cout<<"請輸入要插入的資料："<<endl;
cin>>newNum;
cout<<"請輸入要插入的位置："<<endl;
cin>>pos;
//從插入位置的資料向後移動
for(int i=9; i>pos-1; i--) {
	num[i]=num[i-1];
}
num[pos-1]=newNum;
for(int i=0; i<10; i++) {
	cout<<num[i]<<"\t";
}

執行結果：

1       2       3       4       5       6       7       8       9       0
請輸入要插入的資料：
13
請輸入要插入的位置：
5
1       2       3       4       13      5       6       7       8       9

刪除資料時，需要把資料刪除位置之後的資料向刪除位置移動（向前）。

int num[10]= {1,2,3,4,5,6,7,8,9,10};
for(int i=0; i<10; i++) {
	cout<<num[i]<<"\t";
}
cout<<endl;
int pos=0;
cout<<"請輸入要刪除的位置："<<endl;
cin>>pos;
//從插入位置的資料向前移動
for(int i=pos-1; pos<8; i++) {
	num[i]=num[i+1];
}
 //最後一位補 0
num[9]=0;
for(int i=0; i<10; i++) {
	cout<<num[i]<<"\t";
}

執行結果：

1       2       3       4       5       6       7       8       9       10
請輸入要刪除的位置：
4
1       2       3       5       6       7       8       9       10      0

在陣列中插入、刪除資料的時間複雜度為O（n）。

在頻繁需要插入、刪除的應用場景下，可以選擇比陣列效能更好的連結串列。

4. 總結

本文介紹了陣列的 2 種建立方式，並對陣列的操作效能做了簡單的分析。陣列遍歷時是通過底層的指標移動來實現的。指標是C系列語言的一大特點，是一把雙刃劍，用的好能禦敵千里之外，用的不好！bug滿天飛。