advantages of std::set vs vectors or maps

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.

Answers


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.


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.

  • 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.

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.


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.


Need Your Help

How to force an index on inner joined tables?

mysql inner-join

How do I force indexes on a query similar to this. I need to force an index on foo and bar individually.

What must be wrapped in then() statements in CasperJS? How to determine execution order of sync/async functions?

javascript asynchronous casperjs

I'm having something of a hard time determining what is asynchronous and what is not while running CasperJS, what must be wrapped in then() statements, and what is going to be evaluated when.