Fastest container
Author
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?
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.
Speed differences are for sorting, searching, deleting and inserting. But you always get O(n) if you iterate over every element.
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.
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
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
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.
The only thing he'd have to watch for is making sure the array had enough room tagged to grow into.
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
Quote:Original post by godsenddeath...Which, perhaps, is the reason why he mentioned exactly what he needs the container to be able to do.
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
Quote:Original post by SneftelQuote:Original post by godsenddeath...Which, perhaps, is the reason why he mentioned exactly what he needs the container to be able to do.
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
I'm aware, I was just elaborating a bit
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
