第二回 關(guān)于vector和deque
vector是我最早用的stl容器,用得也最順手,它的結(jié)構(gòu)也是清晰易懂.deque就比較神秘一些,幫助上提到它的一個最顯著的特點就是可以從容器的
前端插入成員,而且效率很高.當(dāng)時覺得很神奇,不知道是怎么做的.stl的源代碼看起來太痛苦了,所以到今天也沒準確的了解它的結(jié)構(gòu).不過后來用的多了,
對它的習(xí)性也有了一定的了解,有些地方相對于vector來說其實是很有優(yōu)勢的.下面就把兩者對比著說說:
*.先說內(nèi)部結(jié)構(gòu).vector就是一塊連續(xù)的內(nèi)存,這塊連續(xù)的內(nèi)存會隨著成員的添加而不斷的re-alloc,而且在重分配的時候,分配的內(nèi)存的大小會
比實際需要的多一些,下次再添加成員時,就可以添加在這些多余的空間里,而不會導(dǎo)致每添加一個成員就需要重分配內(nèi)存.vector封裝的是一塊連續(xù)的內(nèi)
存,這是我最喜歡它的地方,因為可以把它的成員直接轉(zhuǎn)換成指針來進行訪問,很靈活.
*.deque可以根據(jù)一個索引進行隨機訪問,所以我一度也以為它內(nèi)部有一塊連續(xù)的內(nèi)存,直到有一次我真這么干的時候把程序搞當(dāng)了.才意識到這個錯誤.deque內(nèi)部應(yīng)該是由很多定長的內(nèi)存塊組成的鏈表,這是我猜的,因為似乎只有這種結(jié)構(gòu)才能和它的表現(xiàn)相符.
*.往vector,deque里添加數(shù)據(jù)應(yīng)該都是很快的吧,畢竟這是這兩個容器的賣點.這個我沒有具體測過.
*.vector的遍歷速度是很快的,應(yīng)該是到極限了,不管你用iterator來遍歷還是用一個遞增的下標進行訪問,經(jīng)過編譯器的優(yōu)化都可以有最高的效率.
*.deque的遍歷速度也不慢,如果使用iterator來遍歷,可以有接近于vector的效率,但如果直接用遞增的下標進行遍歷,好像編譯器無法優(yōu)化至最高效率,好像慢一倍左右:
std::deque<int> buf;
std::deque<int>::iterator it;
int sum=0;
for (it=buf.begin();it!=buf.end();it++) //這樣遍歷比較快
sum+=*it;
for (int i=0;i<buf.size();i++) //這樣遍歷比較慢
sum+=buf[i];
*.vector內(nèi)部分配的內(nèi)存是永不釋放的,即使你調(diào)用clear()也不會,這一點很不好,有誤導(dǎo)性.有可能一個vector只在瞬間需要很大的容
量,但大多數(shù)時間只需要很小的容量,，結(jié)果卻是長時間的占用了很大的,沒有被使用到的內(nèi)存.vector也沒有提供函數(shù)來釋放它內(nèi)部的內(nèi)存,不過有一個簡單
的辦法,前幾天在網(wǎng)上找到的:
i_math::vector<BYTE>buf;
buf.resize(100000);//分配了一塊至少100000 bytes的內(nèi)存
if (TRUE)//清空buf的內(nèi)存
{
i_math::vector<BYTE> t;
buf.swap(t);//把這塊內(nèi)存交換到一個臨時的vector里去
}
assert(buf.capacity()==0);//內(nèi)存被清空了
*.deque就不一樣了,deque永遠不會占用太多冗余的內(nèi)存,你只需要把它resize()到一個你希望的大小,它會自動釋放掉那些被多余占用的內(nèi)存
*.vector還有一個不好的地方,當(dāng)你往一個vector里添加一個成員的時候,所有指向這個vector的原來成員的指針就不能保證有效了,因為
vector會re-alloc內(nèi)存.而deque不會,無論從前面還是后面添加新成員,舊的成員都不會移動位置,這一點有時候很有用.
所以我覺得deque其實在很多地方都有優(yōu)勢,比起vector,它欠缺的就是內(nèi)存不連續(xù),使用起來不夠靈活,但它對內(nèi)存使用的更經(jīng)濟,而訪問的效率也比
vector慢不了太多,當(dāng)然,它還能從前面快速插入刪除,這是壓倒性的優(yōu)勢.總之,deque是在關(guān)鍵時候能幫上忙的那種,平時可能還是vector更
好用一些.
最后順便說說list,我一點也不喜歡list,幾乎沒怎么用過,往list里添加成員是很慢的(相對與vector,deque),好像每添加一個成員
都要分配一次內(nèi)存,它的遍歷也很慢,好像就比map的遍歷快一點,不能隨機訪問.唯一的優(yōu)勢就是可以在容器中間插入刪除,不過我覺得都是可以用
vector/deque加上一些技巧解決的。反正我在程序里很少碰到過非用list不可的情況,也許是我寫的程序類型還不夠多吧呵呵.
ps.我用的是stlport,vc的實現(xiàn)應(yīng)該也差不多吧.
|
|
|
