作者ric2k1 (Ric)
看板EE_DSnP
標題Re: [問題] Dynamic Array
時間Wed Nov 25 23:42:54 2009
※ 引述《anfranion (南‧生命的意義是經歷)》之銘言：
: 聽一聽其實有點疑惑，因為老師的Dynamic Array
: 好像和我認知中的Dynamic Array有點差異
原理上是差不多的, 只是有一些是針對我們的作業所做的改變.
: 第一個是，老師的Dynamic Array好像只會長大？
: 我知道的Dynamic Array是也會變小的
如同 goodword 所說的, 妳是不是將 capacity 想成 size 了?
Dynamic array, 像是 STL 裏面的 vector, 它的 size 是會長大與變小,
但是 capacity 只會長大.
看下面的例子:
vector<int> arr(4); // _M_start = 0x504010, _M_finish = 0x504020,
// _M_end_of_storage = 0x504020
arr.resize(2); // _M_start = 0x504010,
_M_finish = 0x504018,
// _M_end_of_storage = 0x504020
==> size 變小, capacity 不變
arr.reserve(2); // _M_start = 0x504010, _M_finish = 0x504018,
// _M_end_of_storage = 0x504020
==> 什麼都沒有變
arr.reserve(8); //
_M_start = 0x504030, _M_finish = 0x504038,
//
_M_end_of_storage = 0x504050
==> size 不變, capacity 變大, memory copy 到別的地方,
arr.resize(6); // _M_start = 0x504030,
_M_finish = 0x504048,
// _M_end_of_storage = 0x504050
==> size 變大, capacity 不變
: 第二個是，老師好像沒有特別細講erase這個操作？ (vector有支援)
: 我覺得這個部份還滿困難的，現在我也還沒有想到一個可以只用array來實作的方法
: 因為如果直接複製的話，這樣deletion的時間複雜度就會變成O(n)
: 其實上兩個還滿有關係的，如果不能erase的話就也不會變小
: 不知道老師的意思是什麼@@"
erase() 會讓 size 減一, 但不會更改 capacity.
所以直接就把 erase 之後的 elements 往前移動一格 (O(n)).
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.224.42.181
1F：→ telgniw:我想她要問的是說當size減少到一定程度的時候 11/26 11:33
2F：→ telgniw:capacity不會跟著減少嗎? 11/26 11:33
3F：→ ric2k1:我的認知是, 不會吧... 這樣的 overhead 可能是不值得的 11/26 16:51
4F：推 anfranion:耶還是一樓懂我 - w - 11/26 21:43
5F：→ anfranion:不過也許我知道的是純理論的東西，實作時可能不會 XD 11/26 21:43
6F：→ anfranion: 這樣做 11/26 21:44