need fast container but don't need key values
Author
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!
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.
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.
Author
so this:
would be as fast/faster than as 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}?
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?.
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.
It can make a whole lot of differance and is why a sorted vector sometimes is to prefer over a set.
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.
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.
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]
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
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
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
