用C實(shí)現(xiàn)一個(gè)變長數(shù)組需要記錄幾個(gè)數(shù)據(jù)

dorodaloo

用C實(shí)現(xiàn)一個(gè)變長數(shù)組需要記錄幾個(gè)數(shù)據(jù)

一般的變長數(shù)組( vector )的實(shí)現(xiàn)，需要記錄三個(gè)數(shù)據(jù)：

• 數(shù)據(jù)空間的地址，
• 空間大小，
• 數(shù)組里已存在的元素個(gè)數(shù)。
  

最近看云風(fēng)的BLOG
云風(fēng)同學(xué)說

其實(shí)并不需要三個(gè)變量來維持 vector 結(jié)構(gòu)，兩個(gè)就夠了。那個(gè)表識(shí)容量大小的變量是多余的
struct vector { int *data; int size; };

用C實(shí)現(xiàn)一個(gè)變長數(shù)組需要記錄幾個(gè)數(shù)據(jù)??

yulihua49

dorodaloo 發(fā)表于 2017-12-04 14:25
用C實(shí)現(xiàn)一個(gè)變長數(shù)組需要記錄幾個(gè)數(shù)據(jù)

一般的變長數(shù)組( vector )的實(shí)現(xiàn)，需要記錄三個(gè)數(shù)據(jù)：

一般情況云風(fēng)同學(xué)是對(duì)的。
特殊的，例如string，可以增加一個(gè)有效數(shù)據(jù)長度，因?yàn)樗�是從頭連續(xù)運(yùn)用的。

bruceteen

那假如我刪掉一個(gè)元素時(shí)，他是將 size 減一，還是重新分配一個(gè) size-1 的內(nèi)存然后將數(shù)據(jù)拷貝進(jìn)去？
如果是后者，那效率太低了；如果是前者，我再增加一個(gè)元素時(shí)，他怎么知道不需要重新分配內(nèi)存？

通過非標(biāo)函數(shù) _msize/malloc_usable_size 可以取得實(shí)際內(nèi)存大小，但用戶的內(nèi)存可未必是依標(biāo)準(zhǔn)方式來的，有可能使用了內(nèi)存池。

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才去觸發(fā)，而且由于每次都是2倍的策略，
所以每次都會(huì)去判斷空間夠不夠用，不需要直接與容量比較，所以就不需要容量這個(gè)參數(shù)了，所以這種
位操作是可以的。
但是實(shí)際場(chǎng)景是，容量到達(dá)一定大小后就不會(huì)去2倍了，比如內(nèi)存到達(dá)一半，所以這個(gè)技巧就沒用了

windoze

如果你的增長策略是固定的話，比如起始16個(gè)然后每次乘2，那么從當(dāng)前元素個(gè)數(shù)就可以算出數(shù)組容量了，此時(shí)那個(gè)表示數(shù)組容量的變量是多余的，比如數(shù)組中有17個(gè)元素，那么當(dāng)前容量顯然是32。
不過這么做有個(gè)地方有問題，如果你的數(shù)組可以刪元素的話就要多做一些事，比如當(dāng)前17個(gè)，刪除掉一個(gè)，你就必須把多余的空間還回去，要不然就錯(cuò)了。
但如果你能保證數(shù)組使用連續(xù)的內(nèi)存空間的話其實(shí)也不用麻煩，因?yàn)閒ree一段內(nèi)存并不需要知道這段內(nèi)存有多大，無非就是你會(huì)做一些無用的realloc，比如從17減到16再增長到17，如果你知道數(shù)組實(shí)際容量的話是不需要重新分配內(nèi)存的，但如果你不知道的話就需要做一次realloc減半，再做一次realloc加倍。

目前std::vector的實(shí)現(xiàn)是記錄了數(shù)組容量的，因?yàn)関ector里可以刪元素。

dorodaloo

回復(fù) 2# yulihua49
例如string，可以增加一個(gè)有效數(shù)據(jù)長度，因?yàn)樗�是從頭連續(xù)運(yùn)用的。

push_back函數(shù)代碼
push_back 在實(shí)際編程中是非常重要的

dorodaloo

回復(fù) 6# cokeboL

cokeboL老師


是
值得學(xué)習(xí)和能夠給大家?guī)�來一定正確知識(shí)的有能力人

cokeboL

貓哥這種才配稱為偶像級(jí)別的存在，我的偶像是貓哥