std::vector vs Linked List

std::vector would probably be very very slightly faster, since it's more likely that the objects will stay in the cache.

However, the main reason you'd choose one over the other is if you need random access (std::list doesn't have it), or fast insertion (std::vector is only fast to insert elements at the end).

If you're not sure how to benchmark this yourself, the proper question is not about std::vector vs. your own linked list, but rather std::vector vs. std::list. Try both yourself and see how they behave in your particular application. If one of them was universally better than the other, there would be no reason for the other to exist... But it does. In other words, there's no general answer to your question.

I wouldn't be using the std::list objects. I would be storing pointers to the previous object and the next object on each object themselves.

Example:
Assume I have three objects that are linked 1->2->3
Object1::_nextObject = *Object2;
Object2::_nextObject = *Object3;
Object3::_nextObject = NULL;


More like that :)

Obviously they would have _previousObject which would point the other way also.

Ideally I want the compiler to optimise the code best as possible and increase the possibility of success of branch prediction on the CPU.

I know how to benchmark, but I wanted an idea before I set to coding one or the other.

• The standard library already has a linked list: std::list - use that in preference to your own.
• Iterating over a vector is faster than a list (contiguous memory, simple increment to advance).
• Adding and removing elements anywhere except the end of a vector is *very* expensive, so make sure you don't need to do this.
• You say it needs to be very fast, but 300 is not very many objects, so either iteration will be fast, and the time taken to actually draw the objects should overshadow the iteration cost by a huge amount.

Edit: No need to mark topics as closed.

Thanks.

Exactly what I needed explaining :)

If you do go the linked list route then, as what you want is an intrusive doubly linked list which the std c++ lib doesn't supply, you might want to look at Boost's intrusive list to save you the trouble of writing your own and maintain c++ std. lib compatibility.

In my game engine I opted to use std::list for rendering tasks. Each task is inherited from a generic RenderTask interface which is set up as a tree.
Each task has a list of sub tasks that are executed and can be dynamically added/removed (note that their also reference counted too) at runtime based on how the actor manager/event system defines. Since I was unaware of the potential number of sub-tasks for any given Task I was able to use std::vector:reserve, so std::list was the best solution in my case.

My Engine Rendering Example:
Task #0 - Setup Shadow Textures
- SubTask #0 - Setup Render Target
- SubTask #1 - Setup Camera
- SubTask #2 - Draw Scene
- SubTask #3 - Apply Post FX
Task #1 - Render In Game
- SubTask #0 - Setup Camera Task (Shared with Task #0/SubTask #1)
- SubTask #1 - Draw Scene (Shared with Task #0/SubTask #2)
Task #2 - Render UI
- SubTask #0 - Draw UI

Quote:

Original post by Ehrys std::vector<Object*>::iterator ObjectIterator;for(ObjectIterator = ObjectVector.begin(); ObjectIterator != ObjectVector.end(); ++ObjectIterator){ ObjectIterator->draw();}

You mean (*ObjectIterator)->draw();, right? Because you have to dereference the iterator and the pointer. Anyway, here is real C++ code that replaces your manual iteration:

#include <algorithm>#include <functional>std::for_each(ObjectVector.begin(), ObjectVector.end(), std::mem_fun(&Object::draw));

Yep, sorry I was rushing.

for_each certainly looks tidy, I actually didn't know something like that existed in the STL.

Thanks :)

Quote:

Original post by swiftcoder Iterating over a vector is faster than a list (contiguous memory, simple increment to advance).

Unfortunately that comparison only works when comparing iteration when storing objects by value in the both a vector and a list. That, however, is not what he's doing. Instead it's iteration of a vector

Could you recommend a good profiler that I can get under either Academic license or for free?

I personally have an Intel processor, however, the target machine will be an AMD X2 4800+

So I'm not sure exactly how useful profiling it with a specific Intel one will be.

I don't see what the fuss is about...
When iterating over even 3000 pointers-to-objects, I just can't see you noticing a difference of using any kind of list or vector. If you had millions than maybe it'd be worth worrying about. At this point the question isn't important.

What matters is what will you need to do with these lists? Are you just drawing? Then pick the container that will be easiest to use. Will an event (say a collision or something) possibly cause one of these objects to be deleted? Maybe you'll want to use a list in this case since removing an object in the midst of iterating over a vector is cause for many issues needing workarounds.

I think right now the correct question is what do you need, not which is fastest.

Cheers
-Scott

What compiler are you using? Your compiler may already have a profiler (e.g. some editions of MSVC do). If using the GNU toolchain, you can use gprof as a profiler.

Ooo thanks, I had no idea MSVS had a profiler. Hah, I am blind sometimes, been using MSVS for about 4 years :D


And to answer your question pops, i could be using 300, 3,000 or 3,000,000. The numbers used are irrelevant. I simply have to use the fastest method possible, taking into account any optimisation ability in the compiler and taking advantage of CPU's branch prediction. This is vital, even if I only save a matter of 20-30ns :)

It's highly doubtful that the iteration itself is going to be a bottleneck in your program, meaning that no matter how much you optimize it you'll never see a performance difference because there's something else that's much slower which hides any different in performance. As a matter of fact, I'm willing to bet that you're going to spend enough time stalled in your draw method to mask any differences between containers.

In other words, don't sweat it :) Use the container which makes your code easiest to write and let the profiler worry about the performance when the time comes.

Quote:

Original post by Ehrys I simply have to use the fastest method possible, taking into account any optimisation ability in the compiler and taking advantage of CPU's branch prediction. This is vital, even if I only save a matter of 20-30ns :)

Why? Is someone going to pay you large sums of money if you can prove that your method is fastest?

Have you considered the possibility that what is fastest for 300 elements might not be fastest for 3,000,000?

(Also, insert jokes here about the "madness" of optimizing for a collection of 300 elements. Sparta, etc.)

Why do you worry so much about the performance of the surrounding iteration? The interesting part is what happens inside the loop:

std::for_each(ObjectVector.begin(), ObjectVector.end(), std::mem_fun(&Object::draw));

As others have already pointed out, that is where you should put your optimization efforts.