用C实现一个变长数组需要记录几个数据

dorodaloo

用C实现一个变长数组需要记录几个数据

一般的变长数组( vector )的实现，需要记录三个数据：

• 数据空间的地址，
• 空间大小，
• 数组里已存在的元素个数。
  

最近看云风的BLOG
云风同学说

其实并不需要三个变量来维持 vector 结构，两个就够了。那个表识容量大小的变量是多余的
struct vector { int *data; int size; };

用C实现一个变长数组需要记录几个数据??

yulihua49

dorodaloo 发表于 2017-12-04 14:25
用C实现一个变长数组需要记录几个数据

一般的变长数组( vector )的实现，需要记录三个数据：

一般情况云风同学是对的。
特殊的，例如string，可以增加一个有效数据长度，因为他是从头连续运用的。

bruceteen

那假如我删掉一个元素时，他是将 size 减一，还是重新分配一个 size-1 的内存然后将数据拷贝进去？
如果是后者，那效率太低了；如果是前者，我再增加一个元素时，他怎么知道不需要重新分配内存？

通过非标函数 _msize/malloc_usable_size 可以取得实际内存大小，但用户的内存可未必是依标准方式来的，有可能使用了内存池。

lxyscls

没有capacity，怎么知道int *data的界限在哪里？

ouyixq

If you want to change something, start with babysteps. Take a small action - any action - and growfrom there.

cokeboL

原帖在这里 https://blog.codingnow.com/2008/06/variable_length_array.html
说的是2倍的分配策略，这种策略下，新的size大于老的size才去触发，而且由于每次都是2倍的策略，
所以每次都会去判断空间够不够用，不需要直接与容量比较，所以就不需要容量这个参数了，所以这种
位操作是可以的。
但是实际场景是，容量到达一定大小后就不会去2倍了，比如内存到达一半，所以这个技巧就没用了

windoze

如果你的增长策略是固定的话，比如起始16个然后每次乘2，那么从当前元素个数就可以算出数组容量了，此时那个表示数组容量的变量是多余的，比如数组中有17个元素，那么当前容量显然是32。
不过这么做有个地方有问题，如果你的数组可以删元素的话就要多做一些事，比如当前17个，删除掉一个，你就必须把多余的空间还回去，要不然就错了。
但如果你能保证数组使用连续的内存空间的话其实也不用麻烦，因为free一段内存并不需要知道这段内存有多大，无非就是你会做一些无用的realloc，比如从17减到16再增长到17，如果你知道数组实际容量的话是不需要重新分配内存的，但如果你不知道的话就需要做一次realloc减半，再做一次realloc加倍。

目前std::vector的实现是记录了数组容量的，因为vector里可以删元素。

dorodaloo

回复 2# yulihua49
例如string，可以增加一个有效数据长度，因为他是从头连续运用的。

push_back函数代码
push_back 在实际编程中是非常重要的

dorodaloo

回复 6# cokeboL

cokeboL老师


是
值得学习和能够给大家带来一定正确知识的有能力人

cokeboL

猫哥这种才配称为偶像级别的存在，我的偶像是猫哥