What's the difference between set<pair> and map in C++?

Question

There are two ways in which I can easily make a key,value attribution in C++ STL: maps and sets of pairs. For instance, I might have

map<key_class,value_class>

or

set<pair<key_class,value_class> >

In terms of algorithm complexity and coding style, what are the differences between these usages?

Solution 1

Set elements cannot be modified while they are in the set. set's iterator and const_iterator are equivalent. Therefore, with set<pair<key_class,value_class> >, you cannot modify the value_class in-place. You must remove the old value from the set and add the new value. However, if value_class is a pointer, this doesn't prevent you from modifying the object it points to.

With map<key_class,value_class>, you can modify the value_class in-place, assuming you have a non-const reference to the map.

Solution 2

They are semantically different. Consider:

#include <set>
#include <map>
#include <utility>
#include <iostream>

using namespace std;

int main() {
  pair<int, int> p1(1, 1);
  pair<int, int> p2(1, 2);
  set< pair<int, int> > s;
  s.insert(p1);
  s.insert(p2);
  map<int, int> m;
  m.insert(p1);
  m.insert(p2);
  cout << "Set size = " << s.size() << endl;
  cout << "Map size = " << m.size() << endl;
}

http://ideone.com/cZ8Vjr

Output:

Set size = 2
Map size = 1

Solution 3

map<key_class,value_class> will sort on key_class and allow no duplicates of key_class.
set<pair<key_class,value_class> > will sort on key_class and then value_class if the key_class instances are equal, and will allow multiple values for key_class

Solution 4

std::map acts as an associative data structure. In other words, it allows you to query and modify values using its associated key.

A std::set<pair<K,V> > can be made to work like that, but you have to write extra code for the query using a key and more code to modify the value (i.e. remove the old pair and insert another with the same key and a different value). You also have to make sure there are no more than two values with the same key (you guessed it, more code).

In other words, you can try to shoe-horn a std::set to work like a std::map, but there is no reason to.

Solution 5

Visualising that semantic difference Philipp mentioned after stepping through the code, note how map key is a const int and how p2 was not inserted into m:

View more solutions