Jump to content
  • Advertisement
Sign in to follow this  
paul23

Fastest container

This topic is 3476 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

Hi everyone, I'm programming in C++, and for this thing I would like to know the "fastest container".. - I know that I'll probably will get more speed increases elsewhere thanks to being a bad programmer, but I still like to know what's the fastest container for my case. In my "game" I need to iterate through a large number of objects: However the order is completely irrelevant I just need to be able to call a member function "for each" object. - So random access iterators aren't needed... I need however to be able to quickly add objects.. And preferable als to remove quickly, but removing is currently only being done at "ends", where it clears the whole container. So, what's the fastest container to do such things - or are they all the same speed?

Share this post


Link to post
Share on other sites
Advertisement
If you iterate over every Object and call a method from every object the complexity is O(n) where n is the number of Elements in the container.

Speed differences are for sorting, searching, deleting and inserting. But you always get O(n) if you iterate over every element.

Share this post


Link to post
Share on other sites
Quote:
Original post by megamoscha
If you iterate over every Object and call a method from every object the complexity is O(n) where n is the number of Elements in the container.

Speed differences are for sorting, searching, deleting and inserting. But you always get O(n) if you iterate over every element.


True in theory, but in practice run-time formula is: k*O(n) + C.

For various reasons, linked lists have (sometimes considerably) higher k and C than vector/array for iteration.

Commonly, k and C are hard to guess in advance, which is why profiling is still needed. The cost of function call, for example, can be so high that performance characteristics of container simply doesn't matter.

Share this post


Link to post
Share on other sites
Is this really a bottlneck? I'd start with a std::list or std::vector (probably the later) and not worry about the "fastest container" until this proves to be a choke point in your profiler.

If it is the choke point, then what are your constraints. Is memory tight (console?), what is the cost of creating/deleting these objects? How many is "large number"? 100, 1000, 1 million? If memory isn't a concern, then I would just pre-allocate all the memory and treat it like a stack, adding and removing from one end only, not to exceed the memory allocated.

Cheers,

Bob

Share this post


Link to post
Share on other sites
I would've thought that an std::vector would be best since it avoids any overhead from the std::list iterator, while still giving the ability to grow the array as needs arise.

The only thing he'd have to watch for is making sure the array had enough room tagged to grow into.

Share this post


Link to post
Share on other sites
Quote:
Original post by paul23
Hi everyone,

I'm programming in C++, and for this thing I would like to know the "fastest container".. - I know that I'll probably will get more speed increases elsewhere thanks to being a bad programmer, but I still like to know what's the fastest container for my case.


In my "game" I need to iterate through a large number of objects: However the order is completely irrelevant I just need to be able to call a member function "for each" object. - So random access iterators aren't needed...

I need however to be able to quickly add objects.. And preferable als to remove quickly, but removing is currently only being done at "ends", where it clears the whole container.

So, what's the fastest container to do such things - or are they all the same speed?




This isn't really the question you want to be asking, as different containers are faster at different things, which is the reason there are a bunch of them.

Array types and tend to be the quickest for accessing any value, but they're expensive to resize.

Look up some stuff on Data structures and you'll see that the reason there are so many is that they all have strengths and weaknesses, and there is no one great one that will solve all your problems

Share this post


Link to post
Share on other sites
Quote:
Original post by godsenddeath
Look up some stuff on Data structures and you'll see that the reason there are so many is that they all have strengths and weaknesses, and there is no one great one that will solve all your problems
...Which, perhaps, is the reason why he mentioned exactly what he needs the container to be able to do.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
Quote:
Original post by godsenddeath
Look up some stuff on Data structures and you'll see that the reason there are so many is that they all have strengths and weaknesses, and there is no one great one that will solve all your problems
...Which, perhaps, is the reason why he mentioned exactly what he needs the container to be able to do.


I'm aware, I was just elaborating a bit

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!