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

There are two ways in which I can easily m开发者_StackOverflow中文版ake 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?

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

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.

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

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.

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.

To understand algorithmic complexity, you first need to understand the implementation.

std::map is implemented using RB-tree where as hash_map are implemented using arrays of linked list. std::map provides O(log(n)) for insert/delete/search operation, hash_map is O(1) is best case and o(n) in worst case depending upon hash collisions.

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: