Menu
This may be a stupid question, I am quite new to C++ and programming in general. I wish to understand the use of several STL containers and with that in mind, I was wondering what the advantages are of using std::set vs for example using vectors or maps? I can't seem to find an explicit answer to this question. I noticed that sets use maps, but then why not always use maps or always use sets. Instead 2 quite similar containers are provided. Thanks in advance.
712
A vector has constant time lookup, while std::map is usually implemented as a RB tree, which has a O(log n) look-up time, and even a hash map (such as TR1 unordered_map) usually has a worse complexity, because the index (or a hash thereof) will be mapped to a bucket that can contain multiple values.
Set isn't faster, the map is!! @ArmenTsirunyan I wouldn't waste time on that. Best you can do is benchmark both solutions on your machine and see if the performance of map really is better than set. Otherwise it is better to focus on the actual solution.
The difference is set is used to store only keys while map is used to store key value pairs. For example consider in the problem of printing sorted distinct elements, we use set as there is value needed for a key. While if we change the problem to print frequencies of distinct sorted elements, we use map.
Vector is faster for insertion and deletion of elements at the end of the container. Set is faster for insertion and deletion of elements at the middle of the container.
Both std::set and std::map are associative containers. The difference is that std::sets contain only the key, while in std::map there is an associated value. Choosing one over the other depends mainly on what the task at hand is. If you want to build a dictionary of all the words that appear in a text, you could use a std::set<std::string>, but if you also want to count how many times each word appeared (i.e. associate a value to the key) then you would need an std::map<std::string,int>. If you don't need to associate that count, it does not make sense to have the int that is unnecessary.
138
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
