Jump to content
  • Advertisement
Sign in to follow this  
Wabiskay

C++ 'growing' arrays

This topic is 2499 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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);

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);**
}

**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
Advertisement
Hi,

As siavash suggested, use std::vector. Or better yet, if you know that you will need to add a lot of elements dynamically, use a linked list. You can use std::list, 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
if you know that you will need to add a lot of elements dynamically, use a linked list.


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

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.


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

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.


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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!