MAP and Set

[ak16]

1. Diff between set and map? and where should use which set/map?
2. Map is implemented by which data structure?

[TwilightSpectre]

1. Map is a key-value pair, with keys unique, while set is just a list of unique keys.
2. As far as I can remember, that is not defined. However, typically a map is implemented as a binary search tree.

http://www.cplusplus.com/reference/map/map/
http://www.cplusplus.com/reference/set/set/

[ak16]

thank you NT3 for reply.

but I still am not clear where should use which set/map?

please relate it with an example if you can please?

[TwilightSpectre]

You should try thinking about it. The most obvious use for a map is when you have a bunch of objects that have data associated with them, for example in a resource system for a game you might have a map with keys of the identifier and values of the resource (e.g. std::map<std::string, Texture>). On the other hand, a set could be for if you just needed a list of unique objects. Apart from the 'uniqueness' aspect, they are actually very different.

[ak16]

yes i am.

thank you for the reply.

Set:-
dictionary of words
set<string>

Map:-
word and its count
map<string,int>

from the above example I am clear the use and situation have to use set or map.

but what in the term of complexity which one is more efficient n why?

[Peter87]

A map element has a key and a mapped value. A set element only has the key but no mapped value. They are implemented pretty much the same way, the elements are stored in such a way that makes it efficient to lookup an element by it's key value, so performance is nothing you should think about when choosing between set and map.

[keskiverto]

More efficient in what use?

The reference documentation describes the complexity of their member functions and iterators.


It could make more sense to compare set to vector than to map. You can create a vector that contains unique, sorted values. Again, efficiency is determined by how the container will be used.