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?

Answer 1

The basic difference is that for the set the key is the pair, whereas for the map the key is key_class - this makes looking things up by key_class, which is what you want to do with maps, difficult for the set.

Both are typically implemented with the same data structure (normally a red-black balanced binary tree), so the complexity for the two should be the same.

Answer 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() << "\nMap size = " << m.size() << endl;
}

Answer 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

Answer 4

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.

Answer 5

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.