什么是數(shù)組？ 簡單來說數(shù)組代表一塊連續(xù)的內(nèi)存，內(nèi)部包含連續(xù)的一排相同的對象， 因為內(nèi)存分布連續(xù)且對象大小相同，所以我們可以高效的根據(jù)索引隨機訪問和賦值。
數(shù)組是我們平時用的最多的數(shù)據(jù)結(jié)構(gòu)， 因為它很符合我們程序運行時的平坦內(nèi)存布局，使用起來簡單而高效。可以這樣說，只要恰當?shù)氖褂茫瑪?shù)組可以滿足我們工作中的大部分需要。
數(shù)組包括靜態(tài)數(shù)組和動態(tài)數(shù)組， C/C++語言內(nèi)置支持數(shù)組， 我們平時一般這樣用：
void test()
{
int ar[5] = {1, 2, 3, 4, 5};
int v = a[2];
int* pAr = new int[3];
pAr[1] = v;
delete []pAar;
}
其中ar是靜態(tài)數(shù)組，它分配在該線程的堆棧上， 而pAr是動態(tài)分配的，它內(nèi)存分配在堆上， 詳細內(nèi)存分配可以看我這篇
《C++中new和delete的背后》。
上面我們討論的動態(tài)數(shù)組是C++語言內(nèi)置支持的， 但是因為內(nèi)置數(shù)組大小固定且容易越界， 另外還有上面的多態(tài)問題， C++標準庫為我們提供了另一種封裝vector， 我們可以這樣用：
void test()
{
vector<int> ar;
ar.push_back(1);
ar.push_back(2);
int d = ar[1];
ar[2] = 10;
}
我們可以看到， vector使用起來非常方便， 一方面我們可以像內(nèi)置數(shù)組一樣使用， 另一方面我們不用再擔心容量問題， 因為它會在大小不夠時自動增加。
vector雖然簡單，但是實際上它有 不少陷井和技巧， 下面列舉一些常見問題：
1。小心迭代器失效
void test()
{
vector<int> ar;
ar.push_back(1);
vector<int>::iterator itr = ar.begin();
for(int i=0; i<100; ++i)
{
ar.push_back(i);
}
int d = *itr;
}
你看出上面代碼的問題了嗎？
不錯， 可能在我們push_back過程中， 內(nèi)存重新分配了， 導致我們原先記錄的迭代器itr已經(jīng)失效， 后面再重新訪問就出錯了。
這種bug有時很難定位，參見
《一次痛苦的Coredump定位過程》2。防止內(nèi)存多次分配
我們知道在push_back過程中， 當數(shù)組容量不夠時， 我們就會重新分配內(nèi)存， 然后將已有的元素進行拷貝， 效率很低。
所以最好的方法是用reserve()方法對需要的大小進行正確的估計，然后預留足夠的空間， 防止重新內(nèi)存分配。
3。釋放已分配空間
有些時候某個vector對象已經(jīng)分配了挺大空間，當用的差不多時， 我們需要釋放這些空間， 但是要保留該對象，要怎么做？
有人可能會說用成員函數(shù)clear(), 但那只能清除內(nèi)容卻不會釋放空間, 這里有個挺實用的swap技巧：
vector<int> vec;
void test()
{
for(int i=0; i<10000; ++i)
vec.push_back(i);
vector<int> temp;
vec.swap(temp);
}
4。刪除某些符合條件的元素
void test()
{
vector<int> ar;
for(int i=0; i<100; ++i)
{
ar.push_back(i);
}
vector<int>::iterator itr = ar.begin();
for(;itr != ar.end();)
{
if(*itr > 10)
{
itr = ar.erase(itr);
}
else
{
++itr;
}
}
}
上面的代碼刪除數(shù)組中大于10的所有item, 實際上我們可以下面更簡單的方法替代：
ar.erase(remove_if(ar.begin(), ar.end(), bind2nd(greater<int>(), 10)), ar.end());
從上面的一些技巧，我們可以看到， 只有真正理解了vector的內(nèi)部實現(xiàn)原理， 我們才能規(guī)避一些使用陷井， 更簡單而高效的開發(fā)程序。
上面我們討論的vector主要針對的模擬C++內(nèi)置的動態(tài)數(shù)組部分， 而對于靜態(tài)數(shù)組部分，我們是不是也有相應的類?
是的，C++11里新增的array就是做這個事的， 我們可以這樣用：
void test()
{
std::array<int, 10> ar = {1, 2, 3, 4};
ar[5] = 33;
}
其中array<int, 10>在內(nèi)部存儲實際上是int data[10]；
最后， 簡單總結(jié)下，我們從C++的內(nèi)置數(shù)組講到標準庫提供的vector， 最后談到C++11新增的array, 數(shù)組這個最基本的數(shù)據(jù)結(jié)構(gòu)在C++中終于有了完整的支持。