Archived

This topic is now archived and is closed to further replies.

dave

Manual Linked Lists Vs STL List templates!

Recommended Posts

dave    2187
In the past hour i have learned how STL linked lists work. Is it possible and/or practical to implement my own linked list solution to store all my global memory allocations like objects etc? Or isit best to use and maybe never fullly understand STL? regards, ACE

Share this post


Link to post
Share on other sites
Fruny    1658
In my opinion, you''re better off using the STL in real applications. There are people whose job it is to make sure the library works correctly and with good performance. Generally, they do a good job at it (except in the case of VC6, as everybody knows), and widely used libraries get more and more polished as time goes. That''s the purpose of libraries.

In my case, I know how linked lists work in principle: I''ve had to implement some for my data structure classes. And I know for a fact that I wouldn''t want to use that specific code of mine, especially when a library with a better interface does exist.

I don''t know all the implementation details of the STL lists in particular, just their specification and usage (what operations are ''fast'', when to use lists, etc). If I really wanted to know the details, I''d go and read the source. Sure, the conventions used in the library code isn''t necessarily what you''re used to, but with a bit of effort, you can understand their logic, and then it makes sense.

I also do use the various components of the Boost library, because they make my life easier. I do not pretend to be able to reimplement them on my own - there''s way too much magic involved - but that doesn''t stop me from using them.

What you really have to understand isn''t how a library is implemented, it''s how to use it to the best effect. Learn what it is good at and where other solutions are better.

Share this post


Link to post
Share on other sites
Extrarius    1412
In general, for ''real'' programs, you''ll use the built-in classes most often. Once in a while though, you can take advantage of specialized information about what will be in the list or some other such information to make a better list customized for a specific purpose.

If you don''t understand enough to be able recreate a basic templated linked list, then you might want to work on it and then use your custom version for a while just to get the concepts down. Knowing data structures and the pros/cons of various ones is fairly important.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
oh - classic question

actually It takes 20 lines of code to implement your own stack, linked list or qeue. Those 20 lines of code are written in 2 minutes for your own specific data. Besides that you can have your own linked list and then just copy and paste code & change a few names to adapt you list for your very specific data.

obs - it is simple for some basic operations like inserting and retrievingi data (pushing & popping for stacks & qeues). Most of the time I need lists and such only for those basic things.

If i need some additional functionality then I use STL indeed. I found that own lists and stacks are much faster then using STL. Run your app that uses STL through debugger and see how much it does behind curtains ... a lot of job - that is frankly overhead most of the time - but neccessary if it will be as generic as possible has so many functionality at it has etc ...

Share this post


Link to post
Share on other sites
_the_phantom_    11250
yes, in debug mode the STL stuff is mentaly slow, however in release mode alot of that stuff is removed and you end up with a lean and very fast library, the debug times are very misleading with regards to performance

Share this post


Link to post
Share on other sites
markr    1692
quote:
Original post by Anonymous Poster
actually It takes 20 lines of code to implement your own stack, linked list or qeue. Those 20 lines of code are written in 2 minutes for your own specific data. Besides that you can have your own linked list and then just copy and paste code & change a few names to adapt you list for your very specific data.



Yet, each time you change those lines slightly, you stand a chance of putting a small bug in. Have you added up the hours spent trying to find that elusive bug in something which should have been easy?

Of course having "Your own specific data" does not seem like much of an advantage - STL is a TEMPLATE LIBRARY. This is what templates are for. It is as specific as you want it to be.

If I suddenly need a std::list<std:air<int,bool>> , I can make one as easily as that.

quote:

Run your app that uses STL through debugger and see how much it does behind curtains ... a lot of job - that is frankly overhead most of the time...



Which should be optimised out when the compiler inlines the code, as it should for an optimised build. There should be no extra fluff inside an STL implementation (provided you used the right one, correctly).

Use the right template, and you should not be able to write more efficient code.

Especially once hardware-specific STL implementations start filtering into mainstream use (Currently, I believe there is one on Macos X, PPC hardware)

quote:

- but neccessary if it will be as generic as possible has so many functionality at it has etc ...


You''ve got it totally wrong. STL containers are not at all generic. They are entirely specific. They are just templated. They don''t do anything extra that isn''t needed (at runtime anyway). Functionality you don''t use disappears at compile time.

Mark

Share this post


Link to post
Share on other sites
petewood    819
quote:
Original post by Anonymous Poster
Run your app that uses STL through debugger and see how much it does behind curtains ... a lot of job - that is frankly overhead most of the time


the overhead is removed in release builds. the design is such that it can be well optimised.

STLPort adds all kinds of things to help catch programmer errors in the debug build. But the release build doesn''t have any of that.

The type system that templates use enables optimisations to be made. The use of inlining also has enormnous benefits. For example std::sort takes a function object and can inline the comparision function, whereas the c-style sort has to call the compare function through a pointer and has little chance of inlining it. The difference is significant. Try it for yourself.

quote:
from Bjarne Stroustrup:
The only code faster than the fastest code is no code. By abstracting to matrix manipulation operations, you give the compiler enough type information to enable it to eliminate many operations. If you were writing the code at the level of arrays, you would not eliminate those operations unless you were smarter than just about everybody. So you''d not only have to write ten times as much code if you used arrays instead of the matrix library, but you''d also have to accept a program that runs more slowly. By operating at the level where we can understand things, sometimes you can also operate at the level where we can analyze the code—we being compilers in the second case—and get better code.

My two favorite examples of this phenomenon are matrix times vector operations, where C++ on a good day can beat Fortran, and simple sorts, where C++ on a good day can beat C. The reason in both cases is you''ve expressed the program so directly, so cleanly, that the type system can help in generating better code—and you can''t do that unless you have a suitable level of abstraction. You get this beautiful case where your code gets clearer, shorter, and faster. It doesn''t happen all the time, of course, but it is so beautiful when it does.


Share this post


Link to post
Share on other sites