Sign in to follow this  
lXciD

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

Recommended Posts

lXciD    122
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
DrEvil    1148
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
Kaze    948


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
ToohrVyk    1595
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
ToohrVyk    1595
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
rip-off    10976
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
ToohrVyk    1595
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
rip-off    10976
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
vetroXL    295
if you want to spend the time writing your own you can write one faster than the stl version with a little thought. The stl is designed to be generic and efficiant, however there is still some overhead. I must stress though, unless you're trying to squeeze every single last ounce of cpu power, will you ever need to write your own. The stl these days are good enough. Also know the difference in the containers... I.e. vector is really a generic array and if you're doing alot of insertions and deletions from random points, then use list instead.

Vetro

Share this post


Link to post
Share on other sites
yoshscout    116
i was actually just coming in here to talk about this so instead of a custom thread ill just continue this one, really i just wanted to ask around about difficulty debugging stl. i saved time writing a couple hundred lines and debugging pointer errors etc but now the debugger information is pretty sparse i can find my pointers to classes etc but its not like it used to be.

now im trying to do a pluggable factory for controls and i get this unresolved external symbol........

CDO error LNK2001: unresolved external symbol "protected: static class std::map<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >,class CtrlMaker *,struct std::less<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > >,class std::allocator<struct std::pair<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > const ,class CtrlMaker *> > > CtrlMaker::Registry" (?Registry@CtrlMaker@@1V?$map@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@PAVCtrlMaker@@U?$less@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@2@V?$allocator@U?$pair@$$CBV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@PAVCtrlMaker@@@std@@@2@@std@@A)

..... yah i dont even know where the problem is i think maybe the registry variable lol

STL helped the production process dramatically but the cost is coming on the debugging back end, the majority of the time when i miss a deref(*) or address of(&) i get such weird error message if i hadnt done the non stl for so long i prolly wouldnt understand the problem

Share this post


Link to post
Share on other sites
lXciD    122
Thanks guys!

I like stl::list a lot because the number of functionalities (needed or not) are already there. but i am relative new linked list user so i am afraid that doing the easy way could hurt my own development.

I have been wondering whether stl::list is of any different to a custom linked list.

Looks like they are the same...

But I guess right now bug free is more important to me so i stick to stl::list thanks!

A few more questions. heh.

People were saying that if you want to implement stl::list with classes, your class should have default constructor, copy constructor, etc. I wonder this apply to structure? or are these optional?

They also mentioned that if you wan to use sort function you gotta overload operators.

does all these apply to structure as well?

One off topic question, does class have more overhead den structures? (my guess is yes)

Share this post


Link to post
Share on other sites
Vorpy    869
Quote:
Original post by lXciD
People were saying that if you want to implement stl::list with classes, your class should have default constructor, copy constructor, etc. I wonder this apply to structure? or are these optional?

Classes and structs automatically get a default constructor that default constructs all members. They also get a default copy constructor that copy constructs all members. For many objects, this is fine. For pointers, it probably isn't. But in most cases you can either avoid pointers or use boost::shared_ptrs instead. The rules for structs and classes are exactly the same.
Quote:

They also mentioned that if you wan to use sort function you gotta overload operators.

The default stl algorithms that involve ordering use the < operator by default, but you can replace the default with another functor instead.

Quote:

does all these apply to structure as well?

One off topic question, does class have more overhead den structures? (my guess is yes)

Classes and structs in C++ are exactly the same, except that members of a struct are public by default insead of private. Besides that, structs are mainly a holdover from C and by convention are used for making plain old data types instead of types that have methods.

Share this post


Link to post
Share on other sites
Max Piano    136
Whats the different in them?
If there is not different which one is better? and which one is faster?


STL could increase your compile time (templates are sort of "compiler programming") because actually the compiler must create the code for the different lists you used before it can "compile" them.

For the speed I dont really see how you could improve STL list efficience (and in games the bottlenecks are elsewhere). STL are already implemented in the most efficent way. Probably after days of optimization, debugging and spaghetti code you could improve the overall speed by a 0,01%: is it that important?
A clean and stable code is a greater value than that (expensive) 0,01% "speed gain".

From a developer point of view there is no doubt: the answer is too clear :-D
- Bug-free data structures
- Stable, standard and clean code
- Less code
- Unification: you can switch from a vector to a list *without* change the code that use it (see iterators).

The real drawback of the STL is that you may forget how to write a linked list. :-D

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this