Wow, this is definitely some good stuff! Thanks a lot! =D Extremely helpful overview of the tradeoffs! =D

I think I will save a copy of this page on my HD for future reference! =D

-=Lohrno

This is TOTALY off topic. But please stop using that silly smiley every couple of words... It makes your post kinda hard to read...

=D
Landsknecht

LOL ok, I''ll try to use it less. I ususally use it when happy.

-=Lohrno

I wasn''t trying to be an ass aor anything. It was just so frequesnt in your posts that it made me stutter while reading. (I know that sounds stupid)

The graphic smileys tend to do that less, at least for me.

Sorry to sound like a jerk.

Landsknecht

No prob, I understood!

-=Lohrno

vector is fine. just be careful of insertion ops they are O(n)+

thats to say the bigger your vector the slower inserting in the middle gets.

remember it has a constant time subscript access its O(c) for subscript access. vector[200] is CONSTANT TIME. Now guys that say there code is better show me. Show a O(n) insertion thats a copy of every element on insertion or that expensive. with a const subscript access time. so far were talking array right? ya cept vector also has a constant time push front. no array lets you push front. no linked list lets you have constant time subscript access. it seems like a tree but the best pure tree is O(log(n)) subscript access time. is your stuff really better? i doubt it.

the only data structure ive used that i write on my own is a binary tree cause they have O(log(n)) search time with O(log(n)) insertions. well ok unless your stuff balances itself one of the above cant be O(log(n)) while the other is. but i usually go without balance taking the hit on search if i have lots of data to insert/ remove. and vice versa in the other case. lots of data does a good job of balancing itself. also you can balance independant of inserting/removing. also you dont need a perfectly balanced tree... anyway....



but i avoided your question... hehe your question is sophisticated. im not sure anyone addressed it. to get all these speed optimizations you got to use extra memory. hmmm

well if you stuff is link list compatible such that you only need to push pop and iterate then by all means. but that only takes 15 lines of code to write as good as its going to get basically. i would say use but i cant figure out why stack has O(n) insert time. that seems silly when it has no subscript access. wonder why. has constant ops associated with linked list though you would think it would have constant insert time.











[edited by - declspec on May 7, 2002 4:41:15 AM]

assuming you dont care about order too much (ie not useful):
constant time insert:
1. insert at the end
2. swap with desired pos

constant time remove (useful, cant care about order though)
1. swap item to be removed with last element
2. remove last element


so searching is slow, but due to linear access it is faster then transversing a linked list when dealing with dynamic objects when you dont care about the order of the objects.

these can be done with vector since vector has a swap() function.

after i wrote my stuff i realized that the issue wasnt speed it was the extra memory.

quote: Original post by declspec
ya cept vector also has a constant time push front.

Provided it doesn''t need to reallocate and it still has allocated memory at the front of the sequence. Otherwise it''s O(n). That kind of unpredictability is what makes list a better choice for randomly large/fluctuating amounts of data.

quote:
i would say use <stack> but i cant figure out why stack has O(n) insert time. that seems silly when it has no subscript access.

I think you''ve got some wrong numbers there. stack only permits access to the top element, which is a constant time operation. Access to arbitrary elements is thus O(n) because reaching the nth element involves n successive pops.

(It also discards the n-1 preceding elements. Accessing the nth element without loss requires a second stack/deque into which the values are pushed as they are popped off the original stack, and then pushed back into the original stack as they''re popped off the temporary. Obviously not a good choice unless there are other constraints.)

[ GDNet Start Here | GDNet Search Tool | GDNet FAQ ]
[ MS RTFM [MSDN] | SGI STL Docs | Boost ]
[ Google! | Asking Smart Questions | Jargon File ]
Thanks to Kylotan for the idea!

vector doesn''t even have push_front, you''re thinking of deque.


[Questions (STFW) | GDNet Start Here | GDNet Search | Forum FAQ | Google | Asking Smart Questions ]
[Docs (RTFM) | MSDN | SGI''s STL | OpenGL | File formats]
[C++ Must Haves (RTFS) | MinGW | Boost | Loki | FLTK | SDL ]

Stolen from Magmai Kai Holmlor, who held it from Oluseyi, who was inspired by Kylotan...