Re: [問題] Dynamic Array

[ric2k1 (Ric)]

※ 引述《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
→ telgniw:我想她要問的是說當size減少到一定程度的時候
→ telgniw:capacity不會跟著減少嗎?
→ ric2k1:我的認知是, 不會吧... 這樣的 overhead 可能是不值得的
推 anfranion:耶還是一樓懂我 - w -
→ anfranion:不過也許我知道的是純理論的東西，實作時可能不會 XD
→ anfranion:                                              這樣做