Archived

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

doodah2001

STL vs your own

Recommended Posts

I''m just curious as to how many people use the STL for such things as lists, maps, and vectors vs. creating their own customized list or vector class and I was also wondering why ya''ll choose one type over the other. Thanks.

Share this post


Link to post
Share on other sites
I use the STL because it works. I''ve written about a zillion linked list implementations in my life and don''t ever want to again

Actually, I think everyone should write there own list classes at least once in their lifetime. Write a single linked list, doubly linked list, array, and hash table class, and use it in a project. It''s good practice and you can really see some of the time/space tradeoffs.

Share this post


Link to post
Share on other sites
I use the STL containers almost exclusively. They have many great features and chances are that even if you''re a professional programmer, the STL is probably written better than what you would right, especially if you wanted all of the features the STL provides.

I''ve seen lots of tests showing that the STL containers are just as fast as their non-STL counterparts (i.e. vector<> is as fast as an array).

I would say that the only time you need to write your own data structure is when you need a feature that the STL does not provide for you.

Russell

Share this post


Link to post
Share on other sites
Just why would you waste time to reimplement something that already exists and works ?

As to choosing vector or list. Well, unless you REALLY need to be able to insert elements in the middle of your structure, go for the vector.

Share this post


Link to post
Share on other sites
I use the standard C++ library unless I can''t (e.g. kernel-mode code). That''s pretty much the only reason not to use a standard class -- assuming, of course, that an appropriate standard class exists. Oh, I also use the various hashed containers that many library implementations have.

The well-defined interfaces and thoroughly tested code are a boon.

Share this post


Link to post
Share on other sites
I prefer to use home-made classes, mainly for 2 reasons:
1- STL syntax is crappy
2- I can customize my own classes to do exactly what i want them to do, and to be optimized for the use i have. For example, in the game im working on, I always access the first, same or next element of a list, so I''ve build a simple multi- linked list that garanteed those 3 access operations to be done in O(1).



Share this post


Link to post
Share on other sites
quote:
For example, in the game im working on, I always access the first, same or next element of a list, so I''ve build a simple multi- linked list that garanteed those 3 access operations to be done in O(1).

What the hell are you on about?

Accessing the next, previous, or same item in a list is a constant-time operation anyway.

@_@.





As for which container to pick, it''s almost always obvious, because the containers all have different properties.

Share this post


Link to post
Share on other sites
I use the STL because it works and its fast (most STL implementations are extremely efficient, so unless you have ridiculously specific needs for containers/iterators/string class/etc you''re unlikely to write code that surpasses their efficiency without putting in a ton of work, years of debuggin, etc).

It is somewhat annoying that it doesnt fit with my standard syntax usage (I tend to use upper-case-first class names like Vector..not vector), but no biggie; that''s always a potential issue with any API.

...

I second OldGuy''s claim that people should try implementing the classic data structures and algorithms STL abstracts just to be sure they know what''s going on ''underneath the hood''. In most cases, however, once you get them working I think you should just toss them out and go with the STL implementations.

Share this post


Link to post
Share on other sites
STL all the way
But, I would suggest to anyone who doesn't know how to code a linked list, stack, queue, hash table, etc. I have created my own classes for those abstract data types at one time or another. It is a GREAT learning experience, so do it!!

Good Luck!

EDIT: Forgot to say why I use STL mainly for:

  • It's thoroughly tested

  • It's probably more optimized than the ones I have made

  • It's a standard

  • Very robust

  • It fits my needs

  • I don't want to completely reinvent the wheel; just learn how it works



Edited by - Floppy on January 31, 2002 10:51:30 PM

Share this post


Link to post
Share on other sites
I prefer to not use STL.

Its naming convention completely conflicts with my normal one, and writing a wrapper to get around this would be a lot of overkill for little gain. But that''s not the main reason.

The main reason is that I prefer to have simple data structure templates which, while not necessarily QUITE as optimal performance-wise as STL, are more tailored to my needs on all levels, including interface, behavior, and storage. This tailoring means I can create data structure classes which are lightweight, being only as complex as I need them to be and nothing more.

In my case, the small speed gains and increased "standardness" of moving over to the STL are not worth the sacrifice I incur in terms of control. Working with third-party libraries for certain pieces of functionality is one thing, and when such libraries serve a specific problem domain and have a solid well-defined interface, I wholeheartedly endorse that. But the STL falls into the land of glue code, and that''s a completely different story as far as I''m concerned.

The STL is a very powerful and very efficient template library, but it''s a massive thing since it''s intended to be all things to all people. In contrast, I use a set of lightweight data structures that are entirely contained in a single header of less than 1000 lines, they perform decently and I have complete control over them. They fit my code better than the STL does, and that''s what matters.

To put it another way, yes reinventing the wheel is generally a bad idea, but it''s also a bad idea to use a truck tire when you don''t own a truck.

I don''t want to turn this into a religious war, since I''m fine with people either choosing to use the STL or choosing not to use it; everyone has their reasons. So by the same token, it''d be really nice if some people on this board (and elsewhere) would stop treating anyone who deliberately chooses not to use the STL as if they were somehow inferior.

Library choice, like language choice, is up to personal preference.

- Chris

Share this post


Link to post
Share on other sites
I use the STL, but I''ve only started doing so recently (past month or two). Prior to that, I used MFC''s CString, CList and others. Compared to that, STL is actually quite a breather

I use it mainly because I''m lazy, and I''m not about to write the umpteenth string or map class. I use them in high-level code (I''d never even THINK of using them in performance-critical code, without thoroughly testing first).

However, I can see why some people would prefer not to use STL. The concept of iterators is still a bit iffy to me, and the help that''s provided in the MSDN is not a lot of help really. (Thank goodness for Stroustrup''s books).

In fact, using the STL is violating one of my personal, experience-taught rules: NEVER use someone elses code if you don''t understand fully what it does. In my last big project (250.000+ Lines of code) all the really big, really nasty, really hard to find bugs were caused by code that we hadn''t written ourselves, but we were assured that they worked 100% perfectly! Then, try to debug a few thousand lines of code that are badly formatted and commented if you don''t even know how it works!

However, enough people use the STL to be reasonably sure that for any "light" usage it should do exactly what it says.


People might not remember what you said, or what you did, but they will always remember how you made them feel.

Share this post


Link to post
Share on other sites
quote:
I don''t want to turn this into a religious war, since I''m fine with people either choosing to use the STL or choosing not to use it; everyone has their reasons. So by the same token, it''d be really nice if some people on this board (and elsewhere) would stop treating anyone who deliberately chooses not to use the STL as if they were somehow inferior.

They are inferior, though.

If you can use the Standard C++ Library, and it has an appropriate class (obviously, if you want a B*-tree you''re going to have to write your own, because it doesn''t have one, and you can''t be faulted for that), not using it is folly.

BTW, your complaint of "lack of control" seems a bit silly, given that the few dozen headers I have sitting here contain all the implementation details and would, it seems, manage to give me precisely that.

Share this post


Link to post
Share on other sites
quote:
Original post by DrPizza
They are inferior, though.



They are not, if they are absolute overkill for what you need to be doing.

Calling people names isn''t going to make you any friends either.




People might not remember what you said, or what you did, but they will always remember how you made them feel.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I use both STL and customized lists:

I prefer STL when I have a fixed size of list. The code is simple (even when you need to sort). Of course it is more difficult to debug since if you do not use STL according to the instructions of your compiler you end up with weird bugs: the only solution is to debug with a log file to help you understanding the working of the algorithm.

I use a customized list when the size of the list varies greatly with erasure anywhere in the list of elements:
e.g. I have developped my own list for my dirty rectangles. I store them in the list, then collapse and erase them each frame (I may store between 5 and 1000 dirty rectangles): the STL can provide some solutions to implement that kind of list but not as fast as I wish in that case.

Both approach yield good performance, STL is just better with lists that do not vary much while customized approach is better when the list varies greatly with erasure anywhere inside the list.

Red.

PS: When using STL, if you wish to make a list of objects, do not forget to make nice class else you may have weird bugs:

class foo: //this class is nice
{
public:
foo(void);
foo(const foo& MyFoo); //copy constructor for the vector
foo& operator= (const foo& MyFoo);
int operator< (const foo& MyFoo) const; //mandatory for the sorting algorithms
int operator== (const foo& MyFoo) const;
int operator!= (const foo& MyFoo) const;
~foo(void);

... // your member variables and functions here. They may be private, protected or public.
};

Be also watchful when using pointers inside an object included in a vector list (simplified ...):

#include <vector.h>
#include <algorithm.h>

typedef vector<Model> vModel; //useful, if you need to change the behaviour, just modify here

class Sprite:
{
public:
Sprite(char* Srite_Pool_Address, int w, int h); //initialises the characteristics of the Sprite
Draw(int x, int y); //Draws the sprite to the buffer

private:
char* Bits; //address of the first sprite pixel in the buffer
int width, height; //width and height of the sprite
};

class Model:
{
public:
Model(void): DrawSprite(NULL);
Model(const Model& MyModel) {world_x = MyModel.worldx;
world_y = MyModel.worldy;
DrawSprite = MyModel.DrawSprite};
Model& operator= (const Model& MyModel); //same as constructor + return *this at the end
//I will sort my Models by world_y ...
int operator< (const Model& MyModel) const {return world_y < MyModel.world_y;};
int operator== (const Model& MyModel) const {return world_y == MyModel.world_y;};
int operator!= (const Model& MyModel) const {return world_y != MyModel.world_y;};
~Model(void) {if (DrawSprite!=NULL) delete DrawSprite;}; //Normal housekeeping here ...
//the object takes care of itself.
int world_x, world_y;

SetSprite(Sprite* MySprite) {DrawSprite = MySprite;};
void Action(void); //any kind of action like move or bounce
void DrawSprite(int x, int y);

protected:
Sprite* DrawSprite; //each model has its own sprite with its own drawing specs
}

main {

vModel Model_list;

// Initialise 10 random Model with its Sprite ...
...

// Main loop
while (true) {
vModel::iterator ivModel = Model_list.begin();
vModel::iterator ivLastModel = Model_list.end(); // the end points on the next element after the last of the list
do {
(*ivModel).Action();
ivModel ++;
} while (ivModel != ivLastModel);

sort(MyAgents.Agents.begin(), MyAgents.Agents.end());

ivModel = Model_list.begin();
ivLastModel = Model_list.end();
do {
(*ivModel).DrawSprite(x, y); //the program will not go farther than here !
ivModel ++;
} while (ivModel != ivLastModel);
}
}

You will find out the program will crash in the DrawSprite. Why ? Because when the vector is sorted it copies after iv_LastModel all the objects in the desired order. When the object is copied, the original is erased (call to the destructor) thus deleting your sprite object !
Three hard lessons here:
1- know your containers (It does not crash when using a list since the list swaps index pointers)
2- be careful when deleting in the destructor ! (see 1)
3- be aware that you will need to delete the Sprite object at the end of your program, else you will have a memory leak.
Bonus lesson: when using a vector you need to sort, to avoid a decrease of performance at the first iteration reserve a size that is twice the number of stored objects !

It took me 7 days to find out that one (I was also quite tired, but it is frustrating when it happens). I hope I have not been too long. Have a nice day.
Red.

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
It took me 7 days to find out that one (I was also quite tired, but it is frustrating when it happens).
Red.


Yep, that''s exactly the kind of bug that I''m talking about. Code tends to have side-effects that you don''t know about. Bad, very bad design, but you never know if you didn''t write the code yourself.




People might not remember what you said, or what you did, but they will always remember how you made them feel.

Share this post


Link to post
Share on other sites
quote:

I would say that the only time you need to write your own data structure is when you need a feature that the STL does not provide for you.



And ideally, you want to write that as a template if you can, so you don't have to rewrite it next time.

quote:

In fact, using the STL is violating one of my personal, experience-taught rules: NEVER use someone elses code if you don't understand fully what it does.



Agreed. I've got a pretty good book (The C++ Standard Library Tutorial and Reference, by Nicolai Josuttis) that does a pretty good job of dissecting each template. I shied away from STL for a long time for just that reason: it was tough looking at those header files and figuring out what the heck that was supposed to be doing. But I've grown more comfortable with it, and use STL all the time.

Take care,
Bill

Edited by - Siebharinn on February 1, 2002 9:25:33 AM

Share this post


Link to post
Share on other sites
quote:
Original post by DrPizza
[quote]For example, in the game im working on, I always access the first, same or next element of a list, so I''ve build a simple multi- linked list that garanteed those 3 access operations to be done in O(1).

What the hell are you on about?

Accessing the next, previous, or same item in a list is a constant-time operation anyway.

@_@.





As for which container to pick, it''s almost always obvious, because the containers all have different properties.




He''s decribing the effecieny of his code in "big O" notation. Instead of looping through the list to find an entry, he has written a set of functions which obtain the entry directly.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Correction post:

Please replace in the code extract:
sort(MyAgents.Agents.begin(), MyAgents.Agents.end());

by
sort(Model_list.begin(), Model_list.end());

I concur with Siebharinn and MadkeithV. I must add that for everyone who wish to try STL, check the GameDev Articles Section: there are good starters there. Check also the compiler manual (Borland C++5.01 Manual is really good on that subject). To conclude, do not forget to look at the STL headers: do you that the sorting algorithm (in algorithm.h) uses linear sorting for lists inferior to 16 elements and quick sorting for list superior to 16 elements ?
Good Luck.
Red.

Share this post


Link to post
Share on other sites
quote:
Original post by mc_woods
He''s decribing the effecieny of his code in "big O" notation. Instead of looping through the list to find an entry, he has written a set of functions which obtain the entry directly.


Which would make it a Map, not a List




People might not remember what you said, or what you did, but they will always remember how you made them feel.

Share this post


Link to post
Share on other sites
quote:
He''s decribing the effecieny of his code in "big O" notation. Instead of looping through the list to find an entry, he has written a set of functions which obtain the entry directly.

I understand what he means by O(1). I am familiar with big O notation.

That was not my question.

He''s saying that in his list, finding the next, current, or previous item is constant-time.

It seems to me to be very hard indeed to write a doubly-linked list where this is not the case. The Standard C++ Library certainly has this trait. I haven''t seen a doubly-linked list where this is not the case.

So again, I restate my question -- what the hell is he on about? One does not have to write any special kind of list to have constant-time access to adjacent elements.


Share this post


Link to post
Share on other sites
quote:
--------------------------------------------------------------------------------
For example, in the game im working on, I always access the first, same or next element of a list, so I''ve build a simple multi- linked list that garanteed those 3 access operations to be done in O(1).
--------------------------------------------------------------------------------


What the hell are you on about?

Accessing the next, previous, or same item in a list is a constant-time operation anyway.

That is inexact from my computer science POV.
Is is always a constant time to access next, previous or same item in a list *Iterator*.


Share this post


Link to post
Share on other sites
quote:
--------------------------------------------------------------------------------
For example, in the game im working on, I always access the first, same or next element of a list, so I''ve build a simple multi- linked list that garanteed those 3 access operations to be done in O(1).
--------------------------------------------------------------------------------

---------------------
What the hell are you on about?

Accessing the next, previous, or same item in a list is a constant-time operation anyway.
-----------------------

That is inexact from my computer science POV.
Is is always a constant time to access next, previous or same item in a list *Iterator*.


Share this post


Link to post
Share on other sites
By now I have no idea who is quoting whom.

Once there was a time when all people believed in God and the church ruled. This time is called the Dark Ages.

Share this post


Link to post
Share on other sites
quote:
Original post by Oluseyi
[quote]Original post by Steadtler
Is is always a constant time to access next, previous or same item in a list *Iterator*.

Or in a doubly-linked list.

Sorry.

My point was not very clear.
Typically a chained container like a list (or tree or queue) is just what its name tell: the container. You have pointer to the first element, and two function: insert and remove. Dot.
When you want to access directly or cycle trought a container, you need an iterator. There is mainly two way:
Either you get a instance of the iterator from the list (like STL I think, but its been long since I used it) or you derivate your iterator from the list. (can only have one iteration but a lot more simple).

My point from my first post was why use complex syntax and separate iterators from Stl when Ill always access only same and next element? So I just built a simple linked-list with built-in iterator that does all that I need in perfectly optimised time and memory use.



But we still use Stl in programming contests where developping time is very limited.

Share this post


Link to post
Share on other sites