Sign in to follow this  
Wabiskay

C++ 'growing' arrays

Recommended Posts

So ive been doing C++ for a decent amount of time, as well as some Java and C#, but by no means am I an expert or anything like that. Im almost certain this should be possible in some shape or form, weather it uses arrays or not, im not sure. I apologize if this is something that is asked a lot. I did a few google searches for things like "Growing arrays" and nothing (I could make much sense of) came up.

Basically, I want an array to grow, something like this (Dont mind the improper syntax);
[code]
int units [5];
int emptyslot = 0;
for(int x = 0; x < units(size)**; x++){
if(units[x]==0){
emptyslot = x;
break;
}
}

if(emptyslot!=0){
units(size + 1);**
}
[/code]
**These 2 bits of code are what im trying to find out about.

Is it something I simply haven't learned yet? Or perhaps my past experience with Wc3 map editor is clouding my 'proper' programming skills?

Share this post


Link to post
Share on other sites
Sounds like vectors/dynamic memory is what you are after : [url="http://www.cplusplus.com/reference/stl/vector/push_back/"]http://www.cplusplus...ctor/push_back/[/url]

Share this post


Link to post
Share on other sites
Hi,

As siavash suggested, use [url="http://www.cplusplus.com/reference/stl/vector/"]std::vector[/url]. Or better yet, if you know that you will need to add a lot of elements dynamically, use a linked list. You can use [url="http://www.cplusplus.com/reference/stl/list/"]std::list[/url], for example, or roll your own (but that is generally not a very good idea if not for learning purposes only).

Share this post


Link to post
Share on other sites
[quote name='ArthY303' timestamp='1311336264' post='4838863']if you know that you will need to add a lot of elements dynamically, use a linked list.[/quote]

As long as you add/remove from the end of the vector a vector is often faster than a list.

Share this post


Link to post
Share on other sites
With a standard c style array resizing means making an array with the resize dimensions you want and then copying over and hopefully remembering to destroy the original array which is not desireable.

Share this post


Link to post
Share on other sites
Hello,

@Wooh: That is not true in all cases. If you have a pointer (for example) pointing to the last element of the list, adding past it is a trivial matter because you don't need to go through all the elements to get there. And std::list does have an iterator to the end of the list. In case of vector, if the number of allocated elements is not enough anymore (the capacity of the vector), when you try to add to it, it may need to allocate a new memory space, move all existing elements in that memory space, and free the old one.

Share this post


Link to post
Share on other sites
@ArthY303, std::list has additional overhead. Adding to the end, with std::list the cost is more evenly distributed but the total cost is often higher than with std::vector. But all this depends on how it is being used and what type is being stored. std::vector has random access which is valuable sometimes. std::deque is another container that is similar to std::vector but perform better on some operations.

Share this post


Link to post
Share on other sites
[quote name='ArthY303' timestamp='1311339849' post='4838881']
Hello,

@Wooh: That is not true in all cases. If you have a pointer (for example) pointing to the last element of the list, adding past it is a trivial matter because you don't need to go through all the elements to get there. And std::list does have an iterator to the end of the list. In case of vector, if the number of allocated elements is not enough anymore (the capacity of the vector), when you try to add to it, it may need to allocate a new memory space, move all existing elements in that memory space, and free the old one.
[/quote]

The problem is the final performance depends on what you will be doing with the collection of objects.

If you are adding and removing rarely, or indeed only removing from the end with little to no growth then std::vector is going to win hands down as it's much more cache friendly with it's data layout. Where as a std::list mgiht add/remove quicker but for going over the data you run the risk of massive cache misses as you jump around in memory to access the nodes.

In fact even with a vector and removing from the middle if the data doesn't need to remain 'in order' you can always swap the element you want to remove with the last element in the vector and then remove the last element.

In short; there is far more at work here than simply 'how quick it is to add/remove elements' from the containers.

There is even a case for using a std::deque instead of either a vector or list as it allows fast traversal and pretty fast removal from the middle of the data. However it lacks the contiguous memory of the vector and the flexibiliy of the list when it comes to removal locations.

Personally I always reach for vector first as in most cases the contiguous memory is going to give more of a 'win' then being able to remove from anywhere 'quickly'.

Share this post


Link to post
Share on other sites
[quote name='ArthY303' timestamp='1311339849' post='4838881']
Iif the number of allocated elements is not enough anymore (the capacity of the vector), when you try to add to it, it may need to allocate a new memory space, move all existing elements in that memory space, and free the old one.
[/quote]

With a vector you can also Reserve() memory space to make sure that doesn't happen. Or with most containers actually.

Share this post


Link to post
Share on other sites
[quote name='ArthY303' timestamp='1311339849' post='4838881']
Hello,

@Wooh: That is not true in all cases. If you have a pointer (for example) pointing to the last element of the list, adding past it is a trivial matter because you don't need to go through all the elements to get there. And std::list does have an iterator to the end of the list. In case of vector, if the number of allocated elements is not enough anymore (the capacity of the vector), when you try to add to it, it may need to allocate a new memory space, move all existing elements in that memory space, and free the old one.
[/quote]So what?! In the long run each item still only needs to be copied [i]for resizing purposes[/i] about once [b]on average[/b].
Count the number of copies that would occur with a vector initially containing one item and having say 255 more items added:
1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 = total 255 copies for 256 items. It's always roughly constant due to the way a vector grows.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this