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