Jump to content
  • Advertisement
Sign in to follow this  
Mizipzor

Speed in lists

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

Im going to handle quite a few datainstances at once. And Im not sure on how to send them all to the function. I could do one of these "linked lists" (I think theyre called that). Each instance has all the data and a pointer to the next instance. Then I loop through all of them until the "nextpointer" is null.
struct foo 
{
   int   data;
   foo*  next;
};
Or I can just use the std::list. I heard theyre faster than std::vector when I dont need to access random elements in the list (which I wont need). Which of them is the faster one? Are there any more alternatives?

Share this post


Link to post
Share on other sites
Advertisement
I suggest you to give a try. std::list vs. std::vector is easy to set up. Using your own list structure might be also quite easy to do, but remember that while you may get faster results with your structure, the code will likely be less robust and more error prone. This is to take into account when you'll make your tests.

Regards,

Share this post


Link to post
Share on other sites
Lists need to be built and maintained, and for that purpose I believe the std containers would easily get the upper hand. They also are a good idea because they separate responsibilities (list storage versus whatever the object does outside the list).

Other than that, a vector allocates memory contiguously by default, so unless you use a custom allocator for your list, a vector will be more cache-friendly (this assumes that the objects are stored in the vector, instead of being pointed-to by vector-contained pointers). This means that a vector will get you better performance than a list if the objects are iterated through several times.

Share this post


Link to post
Share on other sites
The std::list class really is the most efficient it can possibly be, for what it does. If you *must* have a linked-list implementation, and you also only need to iterate forwards and *just can't afford* to waste a second pointer per node, you may be interested in the STL slist; this did not make it into the C++ standard library (it's only an SGI extension) but you should be able to find an implementation somewhere. If you find an apparent inefficiency somewhere, then it's either a tradeoff where the compiler vendor didn't agree with you, or you need to find a better implementation; but in general, it's a bad idea to trust your own coding skills versus those of *the people who are providing you with the compiler*. Else you would have their job ;)

As for list versus vector, either could be better-performing depending on the context, which is why the standard library provides both. There are actually quite a few factors that can influence the decision. And those aren't even your only choices from the standard library: consider also std::deque.

Share this post


Link to post
Share on other sites
Quote:
Original post by Mizipzor
Im going to handle quite a few datainstances at once. And Im not sure on how to send them all to the function.

I could do one of these "linked lists" (I think theyre called that). Each instance has all the data and a pointer to the next instance. Then I loop through all of them until the "nextpointer" is null.
struct foo 
{
int data;
foo* next;
};

Or I can just use the std::list. I heard theyre faster than std::vector when I dont need to access random elements in the list (which I wont need).

Which of them is the faster one? Are there any more alternatives?
"faster" all depends on what you're doing with it. Lists are certainly faster for insertion and removal (when there are enough items), but for pure iteration, vectors have less overhead and are more cache friendly.
It doesn't matter what you pass to the function. What matters is how you store and manipulate the bunch of items outside of this function.
All you have to ask yourself is: Do I need to perform insertions and removals?

Actually it matters whether or not the items need to be ordered too, or if they can be in any order. Which is it?

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!