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