Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » List or Vector

Credits go to Jonatan Hedborg for helping out!
This thread is locked; no one can reply to it. rss feed Print
 1   2 
List or Vector
LennyLen
Member #5,313
December 2004
avatar

I thought I might start learning some more C++, since it's changed a lot since I last used it (pre-STL).

I want a dynamic storage structure to hold enemies and projectiles, and it looks like Lists or Vectors are what I'm after.

What are the essential differences between the two, and which would be more suitable for such a task?

Jonatan Hedborg
Member #4,886
July 2004
avatar

List is a linked list. It's good for when you need to remove items from any place in the list (ie test each item in the list and remove those that fail for example). Vectors are good at random access (which lists are not) and removal at end. However, you could use a vector and copy-on-delete (that is, copy the last element over the one you want to remove and pop the last element).

LennyLen
Member #5,313
December 2004
avatar

Thanks, I think a list suits my needs better, since I won't ever be accessing members by index, and items will be removed from all over.

Felix-The-Ghost
Member #9,729
April 2008
avatar

I had never heard of programming lists in my life until recently. Are they in the native C++ or Allegro or another header file? Maybe I'll google them to learn more about them though. It sounds like an array, but I guess not all of the same type like a vector.

==========================
<--- The ghost with the most!
---------------------------
[Website] [Youtube]

StevenVI
Member #562
July 2000
avatar

Felix-The-Ghost:

The C++ Standard Template Library will come with any modern C++ compiler.

I'd suggest looking into a book on data structures. You'll learn all sorts of useful things. The book I used in my class is called Classic Data Structures in Java, though the author also has a book titled Classic Data Structures in C++, which may be more up your alley.

__________________________________________________
Skoobalon Software
[ Lander! v2.5 ] [ Zonic the Hog v1.1 ] [ Raid 2 v1.0 ]

gnolam
Member #2,030
March 2002
avatar

Felix: Please, please get a C++ reference. Or any kind of C++ book. There are even good free ones available. Seriously. I believe I'm speaking for everyone here. :P

--
Move to the Democratic People's Republic of Vivendi Universal (formerly known as Sweden) - officially democracy- and privacy-free since 2008-06-18!

Felix-The-Ghost
Member #9,729
April 2008
avatar

...but I have one...and it mentions lists nowhere in it...
I'm just asking my questions out loud that others would probably google.
I'm not that bad :( I just didn't know which library used it, and Harry told me. :)

==========================
<--- The ghost with the most!
---------------------------
[Website] [Youtube]

Speedo
Member #9,783
May 2008

Felix-The-Ghost
Member #9,729
April 2008
avatar

Oh, alright. See I haven't done much with container class templates.

==========================
<--- The ghost with the most!
---------------------------
[Website] [Youtube]

Schyfis
Member #9,752
May 2008
avatar

forehead slap
And here I was working on my own double linked list class. I guess it was good experience.

________________________________________________________________________________________________________
[freedwill.us]
[unTied Games]

StevenVI
Member #562
July 2000
avatar

Schyfis said:

And here I was working on my own double linked list class. I guess it was good experience.

It is. I would suggest that everyone write their own implementations before using the STL, just because it is excellent experience and you will get a much better idea of the concept. This is useful for knowing which structure will be most efficient for a given situation.

__________________________________________________
Skoobalon Software
[ Lander! v2.5 ] [ Zonic the Hog v1.1 ] [ Raid 2 v1.0 ]

Speedo
Member #9,783
May 2008

Quote:

It is. I would suggest that everyone write their own implementations before using the STL, just because it is excellent experience and you will get a much better idea of the concept. This is useful for knowing which structure will be most efficient for a given situation.

I would suggest the exact opposite. The entire point of the STL (and indeed C++ as a whole) is to be able to use code without having to understand every detail of how it works. It's an utter waste of time spending days trying to implement your own containers when you could be doing something useful with proven, reliable containers that already exist.

If you get to the point where std::list (or whatever you're using) is inadequate for your needs, then start worrying about implementing custom containers.

LennyLen
Member #5,313
December 2004
avatar

In any case, using STL's list instead of my own linked list implementation has definitely reduced the ammount of code.

SiegeLord
Member #7,827
October 2006
avatar

Quote:

If you get to the point where std::list (or whatever you're using) is inadequate for your needs, then start worrying about implementing custom containers.

Yeah, I'll second that. If the only thing you care about is functionality, then look for things that are already made. STL is very big and does a lot of stuff already, so looking through a reference will help you. It only takes a few minutes of directed internet searches, and it will save you a lot of time. Also, you'll know exactly what can't be done with STL (e.g. it has no double-ended vectors), but you can't know that if you don't know what is already there.

Speedo's link should be sufficient for most uses, so no need to buy anything I'd think.

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

Thomas Fjellstrom
Member #476
June 2000
avatar

Quote:

would suggest the exact opposite.

I think its extremely important for a programmer to know the basics. That includes the basic data containers, and algorithms. Its hard to know how to fix a problem if you don't know whats actually going on.

I will agree though that black box containers are very useful.

--
Thomas Fjellstrom - [website] - [email] - [Allegro Wiki] - [Allegro TODO]
"If you can't think of a better solution, don't try to make a better solution." -- weapon_S
"The less evidence we have for what we believe is certain, the more violently we defend beliefs against those who don't agree" -- https://twitter.com/neiltyson/status/592870205409353730

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

Jonatan Hedborg
Member #4,886
July 2004
avatar

Quote:

I would suggest the exact opposite. The entire point of the STL (and indeed C++ as a whole) is to be able to use code without having to understand every detail of how it works. It's an utter waste of time spending days trying to implement your own containers when you could be doing something useful with proven, reliable containers that already exist.

If you get to the point where std::list (or whatever you're using) is inadequate for your needs, then start worrying about implementing custom containers.

Implementing a basic linked list only takes a few hours (if that), and is well worth it. Of course, you won't actually be USING it. But it's nice to have a general idea of what's going on behind the scenes...

That being said... STL is great. Use it.

nonnus29
Member #2,606
August 2002
avatar

Quote:

is to be able to use code without having to understand every detail of how it works

Funny, that's what Java programmers say... :P

STL is a huge time saver, but there are a couple of 'gotcha's' like copy constructors. Chris Barry's tutorials were really good, whatever happened to 'em?

gnolam
Member #2,030
March 2002
avatar

http://www.allegro.cc/files/attachment/596901

--
Move to the Democratic People's Republic of Vivendi Universal (formerly known as Sweden) - officially democracy- and privacy-free since 2008-06-18!

MiquelFire
Member #3,110
January 2003
avatar

Awesome flow chart. I need to keep a copy of that.

---
Febreze (and other air fresheners actually) is just below perfumes/colognes, and that's just below dead skunks in terms of smells that offend my nose.
MiquelFire.red
If anyone is of the opinion that there is no systemic racism in America, they're either blind, stupid, or racist too. ~Edgar Reynaldo

Tobias Dammers
Member #2,604
August 2002
avatar

Quote:

...but I have one...and it mentions lists nowhere in it...

Probably because STL isn't seen as part of the C++ language, traditionally. The language works without STL, just like (or even more than) C works without libc - but since both languages are practically feature-less by themselves, the standard libraries are so important that they have become a de-facto part of the language itself.
Also, the STL is such a vast topic by itself that it's worth a book of its own - but adding the basics to a C++ book is still a good idea IMO.

---
Me make music: Triofobie
---
"We need Tobias and his awesome trombone, too." - Johan Halmén

Karadoc ~~
Member #2,749
September 2002
avatar

That flow chart is pretty good, gnolam. There is one link I'm a bit hazy about though: why are deques better than vectors when "size will vary widely"?

Speedo said:

I would suggest the exact opposite. The entire point of the STL (and indeed C++ as a whole) is to be able to use code without having to understand every detail of how it works. It's an utter waste of time spending days trying to implement your own containers when you could be doing something useful with proven, reliable containers that already exist.

I don't think that being able to program stuff without understanding it is point of STL or C++.

I think that the best way to learn which STL data structure is best for which situation is to learn how those data types are implemented. Creating the data structures oneself is a good way to learn how they work and thus understand how each of them will perform in any given situation.

-----------

Speedo
Member #9,783
May 2008

Quote:

I don't think that being able to program stuff without understanding it is point of STL or C++.

So, when someone asks for a 2d graphics library, do you recommend allegro to them and then say "but write your own library first, it's good experience and will help you understand the concepts behind it"? Of course not - the idea is pretty silly.

Jonatan Hedborg
Member #4,886
July 2004
avatar

STL is not allegro. It's a template library filled with well written, common, algorithms and data structures. The basic principle behind them is very useful, and is needed when you want to write more sophisticated data structures anyway (trees and graphs for example).

Speedo
Member #9,783
May 2008

Quote:

STL is not allegro. It's a template library filled with well written, common, algorithms and data structures. The basic principle behind them is very useful, and is needed when you want to write more sophisticated data structures anyway (trees and graphs for example).

And that's something you learn when you need to.

 1   2 


Go to: