# 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.

## 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 on other sites
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 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}

?

Definitely.

##### Share on other sites
Quote:
 Original post by smart_idiotDefinitely.

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 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 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 on other sites
Quote:
 Original post by smart_idiotI'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 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 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.

1. 1
Rutin
41
2. 2
3. 3
4. 4
5. 5

• 9
• 12
• 10
• 13
• 104
• ### Forum Statistics

• Total Topics
632983
• Total Posts
3009705
• ### Who's Online (See full list)

There are no registered users currently online

×