C++中的SET>配对>和映射有什么区别?

集合元素在集合中时不能修改。 set 的 iterator 和 const_iterator 是等价的。因此 set<pair<key_class,value_class> > ,不能修改 value_class 价值等级 是指针,这不会阻止您修改它指向的对象。

map<key_class,value_class> ,可以修改 价值等级 假设对地图有一个非常量引用。

语义上

#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

map<key_class,value_class> 将按key\u类排序,并且不允许key\u类重复。
set<pair<key_class,value_class> > 如果键类实例相等,将按键类排序,然后按值类排序,并允许键类有多个值

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

std::map 充当关联数据结构。换句话说,它允许您使用其关联键查询和修改值。

A std::set<pair<K,V> > 可以这样做,但是您必须为查询编写额外的代码,使用一个键和更多的代码来修改值(即删除旧的对,插入另一个具有相同键和不同值的对)。您还必须确保同一个键的值不超过两个(您猜到了,更多的代码)。

std::set 像警察一样工作 标准::地图

要理解算法的复杂性,首先需要理解实现。

可视化Philipp在逐步完成代码后提到的语义差异,注意map key如何是const int,p2如何没有插入到 米 :