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.
5 Answers
Both std::set
and std::map
are associative containers. The difference is that std::set
s 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.
-
Thank you all very much, that is pretty much all I needed to know– brunoddCommented Apr 29, 2013 at 19:46
-
If you want to check if a value exist in
set
, is it as fast as checking if a key exist inmap
?– thomthomCommented Jan 4, 2014 at 13:24 -
@thomthom: The requirements are the same, and most implementations use the same underlying data structure (RB-tree) so the answer is that both from the theoretical point and in practice the cost is the same. Commented Jan 4, 2014 at 21:59
-
worth noting unordered_set/map gives faster access if you don't want everything sorted by key Commented Dec 25, 2018 at 3:27
a set is useful for storing unique things like an enum for "typeOfFruits"
std::set<typeOfFruits> fruits;
fruits.insert (banana);
fruits.insert (apple);
fruits.insert (pineapple);
//it's fast to know if my store sells a type of fruit.
if (fruits.find (pear) == fruits.end())
{ std::cout<<"i don't have pear"; }
a map is useful for storing unique things, plus a 'value'
std::map<typeOfFruits, double /*unit price*/> fruits;
fruits[banana] = 1.05;
fruits[apple] = 0.85;
fruits[pineapple] = 3.05;
//repeating pineapple will replace the old price (value)
fruits[pineapple] = 3.35;
//it's fast to know how much a fruit costs.
std::map<typeOfFruits, double /*unit price*/> itr = fruits.find(pineapple);
if (itr != fruits.end())
{ std::cout<<"pineapples costs: $" <<itr->second; }
a vector is useful for storing things where the sequence is ordered (push_back()). imagine you are scanning your fruits in a checkout, and the program tracks this scanning.
std::vector<typeOfFruits> fruits;
fruits.push_back(apple);
fruits.push_back(apple);
fruits.push_back(apple);
fruits.push_back(banana);
fruits.push_back(banana);
fruits.push_back(pineapple);
//i scanned 3 apples, 2 bananas and 1 pineapple.
-
2
if (fruits.find (pear) == fruits.end())
can also be expressed more simply asif ( !fruits.count(pear) )
, sinceset
(et al.) can only contain 0 or 1 of any given value, and any half-decent library implementor will realise this and implementcount()
in terms offind() != end
for us (i.e. won't keep iterating after finding), saving us having to write the verbose code. (This is true forlibstdc++
8 anyway) Commented Sep 22, 2018 at 12:27 -
No body has mentioned the facts that std::set
is actually immutable. You should not change the value of any element in it. std::set
does not track over changes so when you edit a element in it you go behind its back and are likely to change its inner ordering. This is a risky behavior. Therefore use std::map
if you want to edit elements after you put them into the container. Make sure you use key
to induce ordering and everything you need to change afterwards into value
.
-
-
-
Hm, but isn't the order of elements nonexistent when using sets and maps (dicts) ?– DanielCommented Jun 4, 2018 at 15:23
-
Nobody mentioned that because it's obvious.
set
returns elements through const_iterators and thus effectively by value, not reference. So: "You should not change the value of any element in it." How could we? Not without subverting the language and thus invoking undefined behaviour, so it's not interesting to discuss what might happen if you do that. Commented Sep 22, 2018 at 12:42 -
@Daniel It sounds like you're coming from Python and assuming - without basis and dangerously - that its terms translate 1:1 to C++. They do not. In C++,
set
andmap
are ordered at all times. If you only want uniqueness and do not care about the order, you would instead useunordered_set
andunordered_map
. Commented Sep 22, 2018 at 13:00
vector
is faster for insertions and deletions at the back of the container. You can access the elements via the operator [].dequeue
is similar tovector
but it features front insertion and deletion.set
only has the key whilemap
has apair
. Both of these containers are faster for insertion and deletion in the middle of the container. You can also access elements via find with the STL algorithms.
It comes down to the complexity guarantees that are most desired for your application, with respect to insertion, removal, retrieval, etc. I highly recommend Scott Meyers' Effective STL.
std::set
is similar to anstd::map
with no value, and completely unrelated tostd::vector
...