set <pair>和C++中的map之间有什么区别？

Question

我可以通过两种方式轻松地在C++ STL中创建一个关键的值属性:映射和对的集合.例如,我可能有

map<key_class,value_class>

要么

set<pair<key_class,value_class> >

在算法复杂性和编码风格方面,这些用法有何不同？

Answer 1

它们在语义上是不同的.考虑:

#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

输出:

设置大小= 2
地图大小= 1

Answer 2

设置元素在集合中时无法修改.set的iterator和const_iterator是等价的.因此,set<pair<key_class,value_class> >您无法修改value_class就地.您必须从集中删除旧值并添加新值.但是,如果value_class是指针,则不会阻止您修改它指向的对象.

使用map<key_class,value_class>,您可以修改value_class就地,假设您有对地图的非const引用.

Answer 3

基本区别在于,对于集合,键是对,而对于映射,键是key_class - 这使得通过key_class查找内容,这是您想要对映射执行的操作,对于集合来说很难.

两者通常使用相同的数据结构(通常是红黑平衡二叉树)实现,因此两者的复杂性应该相同.

Answer 4

map<key_class,value_class>将对key_class进行排序,并且不允许重复key_class.
set<pair<key_class,value_class> >如果key_class实例相等,将对key_class和value_class进行排序,并允许key_class的多个值