Jump to content
  • Advertisement
Sign in to follow this  
luasitdown

why need a map instead of a vector

This topic is 4683 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

Somtimes vector is enough. map<string ,node*> vector<node*> vector provide find() too. so why use map? if data is complex use map find() will speed up. or map<material*,node*> use map to indicate relation. what is reason for this occasion map<string ,node*> ?

Share this post


Link to post
Share on other sites
Advertisement
You use map because it is much faster, I'm not sure, but I think vector's find is O(n) while map's [] operator is O(ln n).

Share this post


Link to post
Share on other sites
let's say that I have a million items that I want to store in a container by name. I could make a vector of pairs, one part would be the name, the other would store the data. Then I would use find to find the thing that I want. Find starts at the first element and works its way through, because vectors are implemented using arrays. It could be the first element, it could be the last. On average it will be somewhere in the middle. So finding something will mean comparing about half a million strings.

Now let's say that I use a map. Maps are implemented using trees. My tree has half a million elements on the bottom layer, a quarter million on the next, an eighth on the next and so forth, up to the top layer. Let's say that my item is on the bottom layer (because half of the time it will be). In order to get down to it we need to work through all of the layers. However for a million elements you only have 20 layers. So we're only comparing 20 strings.

Ok tell me which is faster, 500,000 comparisons or 20 comparisons?
Thus for large amounts of data the map is so, so, so much faster. What if you don't have a large amount of data? Well then in that case both containers would be fast enough. So why not go with the one that is easier to use? The bracket syntax of map is very user friendly. So when you need a map, use a map. Don't think that there is any speed advantage to using a vector, because when it comes down to it, if speed counts the map will blow the vector out of the water.

Share this post


Link to post
Share on other sites
Quote:
Original post by luasitdown
so vector should be never used?

It always depends on what you want to accomplish.

Share this post


Link to post
Share on other sites
Quote:
Original post by luasitdown
Oh my God!!!!

so vector should be never used?


No vector is good if you want a dynamic one-dimensional array, it's just that find is really slow because it has to go through each element. If you already know the address of the element(like with an array) then it's OK.

Like if you just had a list of numbers:

vector<unsigned long> Vtr;
//push back some numbers here
for(int i=0;i<Vtr.size();i++){cout << Vtr << endl;}

That would be fine. But if you wanted to get each element based on something like a string instead of an address then map is faster.

map<string,unsigned long> Map;
Map["Bob"]=4;
cout << Map["Bob"] << endl;

is faster than:

struct Foo{string Name,unsigned long Value;}
vector<Foo> Vtr;
Vtr.push_back(Foo("Bob",4));
cout << Vtr[Vtr.find("Bob")] << endl;

(this isn't 100% correct)

Share this post


Link to post
Share on other sites
Quote:
Original post by luasitdown
Oh my God!!!!

so vector should be never used?


If you already know the index of the item you want, or your application requires processing each and every element in your container then a vector will be faster.

Share this post


Link to post
Share on other sites
hee hee, no vectors are good. They make great arrays. They just don't make great maps. All of the standard containers are good, otherwise they wouldn't be in the standard. Each has its own strengths and weaknesses. Learn when to use each container and you won't have to worry about speed. Usually the easiest container for a given job is also the most efficient. Think about it, they designed each container with its job in mind, so that container will be easy to use when doing that job.

For example if you are doing a for loop and doing something to each element of the container, vector will probably be the easiest to use, and it will be the most efficient. So that is why I always tell people to program to that the code looks pretty on the screen. Pretty code is usually good code.

Share this post


Link to post
Share on other sites
Quote:
Original post by Fred304
A hashmap would propably be even faster, however I believe there's no hashmap template in the STL :(


There are non-standard hash map classes. A standard one (std::tr1::unordered_map) is coming into the library as soon as compiler vendors update to TR1.

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!