Jump to content
  • Advertisement
Sign in to follow this  
silverphyre673

need fast container but don't need key values

This topic is 4952 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Um, I need a container like a map, but I don't need the key values. So basically, i need a vector with the speed of a map, but without the index storage/retrieval ability. Is there one? Or is it the key values that give the map its speed? Thanks!

Share this post


Link to post
Share on other sites
Advertisement
A set?

Speed of what? vector should be the fastest container for iterating, list for insertion/removal, and set for searching. It really depends on what you want.

Share this post


Link to post
Share on other sites
so this:


for (std::vector<SOMECLASS>::iterator iter = thisclass.begin();
iter != thisclass.end();
++iter)
{//some stuff
}



would be as fast/faster than as this:


fot (std::map<unsigned, SOMECLASS>::iterator iter = thatclass.begin();
iter != thatclass.end();
++iter)
{//other stuff
}



?

Share this post


Link to post
Share on other sites
Quote:
Original post by smart_idiot
Definitely.


I don't understand how either of those pieces of code is faster than the other? i would have said they both visit all elements, it's an O(N) operation so neither is faster they are both equal in terms of time complexity yes?.

Share this post


Link to post
Share on other sites
std::vector is by far the most efficent container to iterate over since its iterators are (in most cases) basicly just pointers, the iterator for a set or map has quite much logic in them.

It can make a whole lot of differance and is why a sorted vector sometimes is to prefer over a set.

Share this post


Link to post
Share on other sites
All a vector needs to do is increase a pointer by some constant value each iteration.

I'm not entirely sure how a map works internally but I imagine it's a tree of some kind which means iterating will be at least as complicated as a linked list, and probably an extra conditional.

Share this post


Link to post
Share on other sites
Quote:
Original post by smart_idiot
I'm not entirely sure how a map works internally but I imagine it's a tree of some kind which means iterating will be at least as complicated as a linked list, and probably an extra conditional.


Generally a red-black tree but its implementation dependent.

I take what i said back now i just thought about it carefully [smile].

[Edited by - snk_kid on April 1, 2005 2:33:23 AM]

Share this post


Link to post
Share on other sites
If you don't need to look objects up by key value, vector is better, because it stores less overhead information (the key).

In any case, vector is generally pretty good as it is really simple - the only thing which is going to perform badly is random element insertion/removal.

But if it's small it doesn't matter.

Vector is the container you should use until you have a reason to use some other one - it should be considered to be the "default".

Mark

Share this post


Link to post
Share on other sites
Actually, I've heard convincing arguments for preferring std::deque by default, but if you do any significant amount of dealing with C APIs then I'd say you definitely want to default to std::vector - if only because you never know when you'll need to be able to treat the data as a plain array.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!