## 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 on other sites
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 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 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;// Addinglist.push_back(5);list.push_back(3);// Removinglist.remove(5);// Traversing by handfor(std::list<int>::iterator i = list.begin(); i != list.end(); ++i) {  std::cout << *i << " ";}// Traversing using the SC++Lstd::copy(  list.begin(),  list.end(),  std::ostream_iterator<int>(std::cout," "));

##### Share on other sites
In your example ^^, why are you doing ++i and not i++?

##### Share on other sites
Quote:
 Original post by _SigmaIn 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 on other sites
Quote:
 Original post by _SigmaIn 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 on other sites
Quote:
 Original post by rip-offIn 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 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 on other sites
Quote:
Original post by ToohrVyk
Quote:
 Original post by rip-offIn 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 on other sites
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 on other sites
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 on other sites
thats an error for not declaring a static member

##### Share on other sites
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 on other sites
Quote:
 Original post by lXciDPeople 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 on other sites
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

## Create an account

Register a new account

• ## Partner Spotlight

• ### Forum Statistics

• Total Topics
627680
• Total Posts
2978609

• 13
• 12
• 10
• 12
• 22