std::map 具有非唯一键排序但唯一比较
std::map with non-unique key ordering but unique comparison
考虑以下代码:
#include <iostream>
#include <map>
#include <utility>
struct Key{
int attr1, attr2;
Key(int attr1, int attr2) : attr1(attr1), attr2(attr2) {}
friend bool operator== (const Key& s1, const Key& s2);
friend bool operator< (const Key& s1, const Key& s2);
};
bool operator== (const Key& s1, const Key& s2){
return ((s1.attr1 == s2.attr1) && (s1.attr2 == s2.attr2));
}
bool operator< (const Key& s1, const Key& s2){
return (s1.attr1 < s2.attr1);
}
int main(void){
std::map<Key, int> mmap;
mmap.insert(std::make_pair(Key(10, 10), 5));
mmap.insert(std::make_pair(Key(10, 20), 5));
std::cout << mmap.size() << std::endl;
}
输出是 1
,我希望它是 2
。这似乎是因为在 operator<
中只比较了 attr1
。但是,如果我是正确的,则比较不一定是强排序,而弱排序就足够了。这里是否还有其他错误,或者我是否必须为
定义一个 operator<
Key1 !< Key2 && Key2 !< Key1
implies that Key1 == Key2
成立吗?
std::map
在比较元素时根本不使用 operartor ==
。默认情况下,在这种情况下,它使用 std::less
,它使用您的 operator <
。由于您的 operator <
仅比较 attr1
,并且两个对象具有相同的 attr1
,因此它们被认为是等价的,因此您在地图中只有一个对象。
要解决此问题,您需要检查两个成员,并且您可以使用 std::tie
技巧来制作一个元组来为您执行此操作
bool operator< (const Key& s1, const Key& s2){
return std::tie(s1.attr1, s1.attr2) < std::tie(s2.attr1, s2.attr2);
}
另一种选择是使用 std::unordered_map
,它使用散列算法和相等运算符。使用它你只能散列 attr1
,但是让相等运算符同时检查 attr1
和 attr2
以确保没有添加真正的重复项。
if I am correct, the comparison does not have to be a strong ordering, but rather having a weak ordering is sufficient.
你是对的。
The output is 1 where I would expect it to be 2.
您的期望是错误的,因为根据您提供的弱排序关系,这些键被认为是相等的。
Is there some other bug here
没有
do I have to define an operator<
for which
Key1 !< Key2 && Key2 !< Key1 implies that Key1 == Key2
holds true?
如果您希望操作产生一个排序,当且仅当 Key1 == Key2
时键被认为是相等的,那么是的,您确实需要定义这样的运算符。
或者您可以使用 multi-map,其中可能包含 non-unique 个键。
考虑以下代码:
#include <iostream>
#include <map>
#include <utility>
struct Key{
int attr1, attr2;
Key(int attr1, int attr2) : attr1(attr1), attr2(attr2) {}
friend bool operator== (const Key& s1, const Key& s2);
friend bool operator< (const Key& s1, const Key& s2);
};
bool operator== (const Key& s1, const Key& s2){
return ((s1.attr1 == s2.attr1) && (s1.attr2 == s2.attr2));
}
bool operator< (const Key& s1, const Key& s2){
return (s1.attr1 < s2.attr1);
}
int main(void){
std::map<Key, int> mmap;
mmap.insert(std::make_pair(Key(10, 10), 5));
mmap.insert(std::make_pair(Key(10, 20), 5));
std::cout << mmap.size() << std::endl;
}
输出是 1
,我希望它是 2
。这似乎是因为在 operator<
中只比较了 attr1
。但是,如果我是正确的,则比较不一定是强排序,而弱排序就足够了。这里是否还有其他错误,或者我是否必须为
operator<
Key1 !< Key2 && Key2 !< Key1
implies thatKey1 == Key2
成立吗?
std::map
在比较元素时根本不使用 operartor ==
。默认情况下,在这种情况下,它使用 std::less
,它使用您的 operator <
。由于您的 operator <
仅比较 attr1
,并且两个对象具有相同的 attr1
,因此它们被认为是等价的,因此您在地图中只有一个对象。
要解决此问题,您需要检查两个成员,并且您可以使用 std::tie
技巧来制作一个元组来为您执行此操作
bool operator< (const Key& s1, const Key& s2){
return std::tie(s1.attr1, s1.attr2) < std::tie(s2.attr1, s2.attr2);
}
另一种选择是使用 std::unordered_map
,它使用散列算法和相等运算符。使用它你只能散列 attr1
,但是让相等运算符同时检查 attr1
和 attr2
以确保没有添加真正的重复项。
if I am correct, the comparison does not have to be a strong ordering, but rather having a weak ordering is sufficient.
你是对的。
The output is 1 where I would expect it to be 2.
您的期望是错误的,因为根据您提供的弱排序关系,这些键被认为是相等的。
Is there some other bug here
没有
do I have to define an
operator<
for whichKey1 !< Key2 && Key2 !< Key1 implies that Key1 == Key2
holds true?
如果您希望操作产生一个排序,当且仅当 Key1 == Key2
时键被认为是相等的,那么是的,您确实需要定义这样的运算符。
或者您可以使用 multi-map,其中可能包含 non-unique 个键。