Jump to content
  • Advertisement
Sign in to follow this  
Ehrys

std::vector vs Linked List

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

Which is faster? I am currently implementing a manager class containing 300+ objects of the same class with a draw method. Would it be faster to contain all 300+ objects in an std::vector<> and iterate through each one. Or should I create a linked list that returns a pointer to the next object? Speed is of the essence so everything down to compiler optimisation is a bonus. Example of first method:
std::vector<Object*>::iterator ObjectIterator;
for(ObjectIterator = ObjectVector.begin(); ObjectIterator != ObjectVector.end(); ++ObjectIterator)
{
ObjectIterator->draw();
}




Example of second method
Object* Object::draw()
{
// Code to do drawing of VBO/Vertex List
return _nextObject;
}

// Assume ObjectManager holds a pointer to the First object of the LL
void ObjectManager::Draw()
{
currentObject = firstObject->draw();
while(currentObject)
{
currentObject = currentObject->draw();
}
}




Thanks for any advice EDIT: Just realised I didn't fully explain. Obviously with the second method, you would presume ObjectManager wouldn't contain any information regarding other Objects than the first. However I will need access to them. Therefor, I'm already storing a vector of the Objects. So memory management is not a deciding factor. [Edited by - Sneftel on November 25, 2008 8:41:43 AM]

Share this post


Link to post
Share on other sites
Advertisement
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).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
  • 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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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));

Share this post


Link to post
Share on other sites
Yep, sorry I was rushing.

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

Thanks :)

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!