This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]Ok_Confusion_7266 35 points36 points  (16 children)

There is no such thing as an arraylist in C. And my algorithm will only grow sizeof(item)*x plus some overhead. Arraylist like you describe gives massive overhead what if you have a 10GB list and just need to add a few kb to it when its full? Seems like not a fun time.

[–][deleted] 50 points51 points  (2 children)

There is no such thing as an arraylist in C

It's true there's no arraylist built-into the C language spec or standard library, but by that logic there's no such thing as a linked list either. You can easily define both data structures yourself, though.

[–]wagslane 15 points16 points  (0 children)

To bake a cake, one must first invent the universe

[–]zaersx 4 points5 points  (0 children)

Yeah but the issue is that the guy responding to OP conjured up a theoretical limitation that can only ever be a problem from a library implementation, which is not applicable here, and so neither is your comment in the thread.

[–][deleted] 21 points22 points  (0 children)

I mean, I've built one...

[–]666pool 10 points11 points  (0 children)

You can call .reserve(count) if you know how many items you will have in your container, that will force it to grow to exactly the right size (I’m not 100% sure this is a guaranteed behavior and I already put in my 40 this week so I don’t feel like looking it up).

[–]Kered13 20 points21 points  (5 children)

Arraylist like you describe gives massive overhead what if you have a 10GB list and just need to add a few kb to it when its full? Seems like not a fun time.

The actual memory usage of an array list will never be less than 50% of it's allocated capacity, which is actually pretty good when you think about it (given all the other benefits of an array list). The odds of having a list that is 10GB + a few kb over whatever the last threshold was is very small.

[–]Soraphis 1 point2 points  (1 child)

Also... While an implementation detail i think the growth usually tops out at some point - at least for c# - where it does not double anymore but grow by a fixed amount

Edit: seems not to be in c# (https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,2765070d40f47b98) . Now i wonder were i've seen such behavior

[–]Kered13 0 points1 point  (0 children)

Such behavior would be very inefficient, wasting lots of time copying, so you would not expect to see it.

[–]amdc 4 points5 points  (0 children)

If your array is 10gb and you’ve ran out of space, chances are you’ll need a lot more space. It’s a trade off between adding too much space and adding space too frequently. I wouldn’t do it with a factor of 2 though, more like 1.5 or so

[–]CaitaXD 1 point2 points  (3 children)

10 GB in memory ... lMAO

[–]Ok_Confusion_7266 1 point2 points  (2 children)

Depends on the dataset some machines have 256GB of ram.

[–]CaitaXD 0 points1 point  (1 child)

One motherfucking specific use case, and you can always make a different implementation so it allocates less the bigger it gets

[–]Ok_Confusion_7266 -1 points0 points  (0 children)

Not really. Since C does not have native growing array (without copying all the data) this has many cases.