C++ 中的 set<pair> 和 map 有什么区别？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3248554/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What's the difference between set<pair> and map in C++?
提问by Luís Guilherme
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
有两种方法可以在 C++ STL 中轻松创建键值属性：映射和成对集。例如，我可能有
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?
在算法复杂度和编码风格上，这些用法有什么区别？
回答by Philipp
They are semanticallydifferent. 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;
}
Output:
输出：
Set size = 2
Map size = 1
设置大小 = 2
地图大小 = 1
回答by bk1e
Set elements cannot be modified while they are in the set. set's iteratorand const_iteratorare equivalent. Therefore, with set<pair<key_class,value_class> >, you cannot modify the value_classin-place. You must remove the old value from the set and add the new value. However, if value_classis a pointer, this doesn't prevent you from modifying the object it points to.
集合元素在集合中时不能被修改。set的iterator和const_iterator是等价的。因此，使用set<pair<key_class,value_class> >，您不能value_class就地修改。您必须从集合中删除旧值并添加新值。但是，如果value_class是指针，这并不妨碍您修改它指向的对象。
With map<key_class,value_class>, you can modify the value_classin-place, assuming you have a non-const reference to the map.
使用map<key_class,value_class>，您可以value_class就地修改，假设您有对地图的非常量引用。
回答by Luís Guilherme
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.
基本的区别在于，对于集合，键是对，而对于映射，键是 key_class - 这使得通过 key_class 查找东西，这是您想要对映射执行的操作，对于集合来说很困难。
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.
两者通常使用相同的数据结构（通常是红黑平衡二叉树）实现，因此两者的复杂度应该相同。
回答by Jherico
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
map<key_class,value_class>将在 key_class 上排序并且不允许 key_class 重复。set<pair<key_class,value_class> >如果 key_class 实例相等，将在 key_class 和 value_class 上排序，并允许 key_class 有多个值
回答by MAK
std::mapacts as an associative data structure. In other words, it allows you to query and modify values using its associated key.
std::map充当关联数据结构。换句话说，它允许您使用其关联的键来查询和修改值。
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).
std::set<pair<K,V> >可以使A像那样工作，但是您必须使用键为查询编写额外的代码和更多代码来修改值（即删除旧对并插入另一个具有相同键和不同值的）。您还必须确保具有相同键的值不超过两个（您猜对了，更多代码）。
In other words, you can try to shoe-horn a std::setto work like a std::map, but there is no reason to.
换句话说，您可以尝试硬塞 astd::set像 a 一样工作std::map，但没有理由这样做。
回答by Sach
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.
std::map 是使用 RB-tree 实现的，而 hash_map 是使用链表数组实现的。std::map 为插入/删除/搜索操作提供 O(log(n)) ，hash_map 是 O(1) 是最好的情况，而在最坏的情况下是 o(n) 取决于散列冲突。
回答by Alan
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:
可视化 Philipp 在单步执行代码后提到的语义差异，注意 map 键如何是 const int 以及 p2 是如何未插入到m 中的：
