44

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.

3
  • 1
    A std::set is similar to an std::map with no value, and completely unrelated to std::vector... Commented Apr 29, 2013 at 19:34
  • 1
    You need some good documentation. Commented Apr 29, 2013 at 19:37
  • 8
    They all do different things. Pick the one that you need to solve your problem. It's like asking why we should keep salt, butter and sugar in the kitchen and not just always use orange juice.
    – Kerrek SB
    Commented Apr 29, 2013 at 19:45

5 Answers 5

69

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.

4
  • Thank you all very much, that is pretty much all I needed to know
    – brunodd
    Commented 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 in map?
    – thomthom
    Commented 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
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
  • 2
    if (fruits.find (pear) == fruits.end()) can also be expressed more simply as if ( !fruits.count(pear) ), since set (et al.) can only contain 0 or 1 of any given value, and any half-decent library implementor will realise this and implement count() in terms of find() != end for us (i.e. won't keep iterating after finding), saving us having to write the verbose code. (This is true for libstdc++ 8 anyway) Commented Sep 22, 2018 at 12:27
  • !fruits.contains(pear) is also an option Commented Aug 14, 2021 at 13:57
6

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.

6
  • What ordering are you talking about?
    – Daniel
    Commented May 29, 2018 at 21:07
  • @Daniel, the ordering of the elements in the container.
    – Ruolin Liu
    Commented May 31, 2018 at 1:56
  • Hm, but isn't the order of elements nonexistent when using sets and maps (dicts) ?
    – Daniel
    Commented 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 and map are ordered at all times. If you only want uniqueness and do not care about the order, you would instead use unordered_set and unordered_map. Commented Sep 22, 2018 at 13:00
5
  • vector is faster for insertions and deletions at the back of the container. You can access the elements via the operator [].
  • dequeue is similar to vector but it features front insertion and deletion.
  • set only has the key while map has a pair. 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.
3

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.