※ 引述《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