Jump to content
  • Advertisement
Sign in to follow this  
lXciD

stl::list vs custom made linked list (any differences)

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

Recently just pick up about what linked list are. I notice that STL had list. Could anyone help me with these questions? Whats the different in them? If there is not different which one is better? and which one is faster? A simple example of stl::list for game? showing traversing through the list, adding and removing. thanks alot! ;)

Share this post


Link to post
Share on other sites
Advertisement
A custom implementation can be faster, but most people would recommend you stick with std::list because it's well tested, fast, and reliable. I share that opinion myself as well. Use std::list until you have proven it to be a problem with profiling(which is very unlikely to happen without misusing it).

Share this post


Link to post
Share on other sites


list<Sprite*> sprite;

void add(Sprite *s){
sprite.push_front(s);
}

void draw_list(list<Sprite*> &l){
list<Sprite*>::iterator itr=l.begin();
while(itr!=l.end()){
Sprite *s =*itr;
s->draw();
++itr;
}
}

void draw(){
draw_list(sprite);
}

Share this post


Link to post
Share on other sites
Whats the different in them?
One is already written by professionals, bug-free, portable, usable and optimized. The other is currently unwritten, and won't be bug-free, portable, usable and optimized unless you spend even more time doing it (assuming you can, which isn't necessarily the case).

If there is not different which one is better?
std::list is usually smaller in terms of memory, increases productivity by having a clean interface and interacting correctly with SC++L algorithms, and besides, it's already written.

and which one is faster?
Quite possibly std::list, unless you spend weeks optimizing your own.


showing traversing through the list, adding and removing.


std::list<int> list;

// Adding
list.push_back(5);
list.push_back(3);

// Removing
list.remove(5);

// Traversing by hand
for(std::list<int>::iterator i = list.begin(); i != list.end(); ++i) {
std::cout << *i << " ";
}

// Traversing using the SC++L
std::copy(
list.begin(),
list.end(),
std::ostream_iterator<int>(std::cout," "));


Share this post


Link to post
Share on other sites
Quote:
Original post by _Sigma
In your example ^^, why are you doing ++i and not i++?


i++ returns the old value of i, which forces the compiler to create a copy of the object before doing the increment, and then returning the copy. This is pointless, unless you need the old value, which you don't.

So, ++i increments the original and returns the new value, which does not require a copy. Saving a copy on complex types, such as iterators, is a good idea.

Share this post


Link to post
Share on other sites
Quote:
Original post by _Sigma
In your example ^^, why are you doing ++i and not i++?


Postincrement involves the creation of a temporary to save the "current value" for ues in complex expressions.

In this case as the value returned from the increment operator is not being saved so using ++i is the same as using i++.

So basically its a small optimisation.

Share this post


Link to post
Share on other sites
Quote:
Original post by rip-off
In this case as the value returned from the increment operator is not being saved so using ++i is the same as using i++.


Not really. Since the user may define i++ and ++i to do different things, the compiler is not allowed to substitute one for the other. And so, the postincrement code for the iterator will be executed, which may have an unusual effect, such as temporary creation.

Share this post


Link to post
Share on other sites
Also dont forget to check out std:vector! My fav for most uses personally... Also check if u singly or doubly.

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
Quote:
Original post by rip-off
In this case as the value returned from the increment operator is not being saved so using ++i is the same as using i++.


Not really. Since the user may define i++ and ++i to do different things, the compiler is not allowed to substitute one for the other. And so, the postincrement code for the iterator will be executed, which may have an unusual effect, such as temporary creation.


Of course they can (the user making some custom class)[smile]

But im talking about us, client users of the SC++L. std::list::iterator::operator++ and std::list::iterator::operator++(int) are the same for our purposes (return values noted).

I'm not suggesting the compiler could allow such an optimisation, if the compiler could do such an operation then the whole point would be moot as no-one would care if you use ++i over i++ (again: unless the return value was important).

I don't know where you got that impression from my post [smile]

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!