使用自定义 less 运算符实现迭代 std::map 会得到它包含的更少元素
Iterating over std::map with custom less operator implementation gives less elements that it contains
假设我有以下简单程序 (http://cpp.sh/5sygh):
#include <map>
#include <iostream>
using Key = std::pair<unsigned long, unsigned long long>;
struct KeyLess {
bool operator()(const Key& lhs, const Key& rhs) {
if (lhs.first < rhs.first) {
return true;
}
if (lhs.second < rhs.second) {
return true;
}
return false;
}
};
int main() {
std::map< Key , int, KeyLess> m;
m[Key{2, 169}] = 1;
m[Key{1, 255}] = 2;
m[Key{1, 391}] = 3;
m[Key{1, 475}] = 4;
std::cout << "Elements in map: " << m.size() << std::endl;
for(const auto &x: m) {
std::cout <<"Value: "<< x.second << std::endl;
}
}
输出仅包含 2 个项目,而不是地图中的 4 个项目:
Elements in map: 4
Value: 2
Value: 1
我在这里想念什么?
你的 less 运算符应该是:
struct KeyLess {
bool operator()(const Key& lhs, const Key& rhs) {
if (lhs.first < rhs.first) {
return true;
}
if (lhs.first == rhs.first && lhs.second < rhs.second) {
return true;
}
return false;
}
};
比较具有多个元素的结构时,将结构视为单词,将元素视为字符可能会有所帮助。
通过此修改,less 运算符按字典顺序工作,即在排序时比较两个相同长度的单词的方式:继续比较下一个位置,而单词在当前位置具有相同的字符,并且决定当前位置的字符何时不同。如果您到达两个单词的末尾,则单词相等。
您的比较功能不符合strict weak ordering的要求。
在 SWO 中,如果 A < B,且 B < C,则 A 必须小于 C。还通过查看两个值是否不小于彼此来检查键是否相等。如果 (!(a<b) && !(b<a))
则 a == b
。两个键不能都小于对方。
对于你的钥匙和使用你的比较功能
Key{2, 169} < Key{1, 255} // this is true because 169 < 255
Key{1, 255} < Key{2, 169} // this is also true because 1 < 2
显然这是个问题,因为使用您的比较器,这两个键的比较结果都比彼此差。
我建议的解决方案:由于您的键是 std::pair
,因此您不需要定义新的比较器。 std::pair
已经默认使用字典顺序比较。
您可以通过使用 std::tie
.
隐藏比较器的复杂性并解决错误(@MarkoMahnič 已解释)
bool operator()(const Key& lhs, const Key& rhs)
{
return std::tie(lhs.first, lhs.second) < std::tie(rhs.first, rhs.second);
}
您的比较器不符合std::map
的要求,需要提供一个strict weak ordering。幸运的是,如果您需要比较多个值,std::tuple
会为您实现此功能:
struct KeyLess {
bool operator()(const Key& lhs, const Key& rhs) {
return std::tie(lhs.first, lhs.second) < std::tie(rhs.first, rhs.second);
}
};
在您的情况下,您实际上根本不需要自定义比较器,因为 std::pair
的 <
运算符已经具有相同的行为。
您的 KeyLess
代码导致不正确的比较:
KeyLess cmp;
std::cout << cmp(Key{2, 169},Key{1, 391})<< std::endl; // yields true
std::cout << cmp(Key{1, 391},Key{2, 169})<< std::endl; // yields true
当两个比较都为假时,这意味着键是相等的,当它们为真时,映射迭代器的行为未定义。这与地图对其元素进行排序有关。
请注意,operator()
需要const
,否则程序可能无法使用标准 C++17 及更高版本进行编译。作为可能的变体:
#include <map>
#include <iostream>
using Key = std::pair<unsigned long, unsigned long long>;
struct KeyLess {
bool operator()(const Key& lhs, const Key& rhs) const {
if (lhs.first < rhs.first) {
return true;
}
else if (lhs.first > rhs.first)
return false;
if (lhs.second < rhs.second) {
return true;
}
return false;
}
};
int main()
{
std::map< Key , int, KeyLess > m;
m[Key{2, 169}] = 1;
m[Key{1, 255}] = 2;
m[Key{1, 391}] = 3;
m[Key{1, 475}] = 4;
std::cout << "Elements in map: " << m.size() << std::endl;
for(const auto &[key, value]: m) {
std::cout << "Key: " << key.first << ", " << key.second << " Value: "<< value << std::endl;
}
}
假设我有以下简单程序 (http://cpp.sh/5sygh):
#include <map>
#include <iostream>
using Key = std::pair<unsigned long, unsigned long long>;
struct KeyLess {
bool operator()(const Key& lhs, const Key& rhs) {
if (lhs.first < rhs.first) {
return true;
}
if (lhs.second < rhs.second) {
return true;
}
return false;
}
};
int main() {
std::map< Key , int, KeyLess> m;
m[Key{2, 169}] = 1;
m[Key{1, 255}] = 2;
m[Key{1, 391}] = 3;
m[Key{1, 475}] = 4;
std::cout << "Elements in map: " << m.size() << std::endl;
for(const auto &x: m) {
std::cout <<"Value: "<< x.second << std::endl;
}
}
输出仅包含 2 个项目,而不是地图中的 4 个项目:
Elements in map: 4
Value: 2
Value: 1
我在这里想念什么?
你的 less 运算符应该是:
struct KeyLess {
bool operator()(const Key& lhs, const Key& rhs) {
if (lhs.first < rhs.first) {
return true;
}
if (lhs.first == rhs.first && lhs.second < rhs.second) {
return true;
}
return false;
}
};
比较具有多个元素的结构时,将结构视为单词,将元素视为字符可能会有所帮助。
通过此修改,less 运算符按字典顺序工作,即在排序时比较两个相同长度的单词的方式:继续比较下一个位置,而单词在当前位置具有相同的字符,并且决定当前位置的字符何时不同。如果您到达两个单词的末尾,则单词相等。
您的比较功能不符合strict weak ordering的要求。
在 SWO 中,如果 A < B,且 B < C,则 A 必须小于 C。还通过查看两个值是否不小于彼此来检查键是否相等。如果 (!(a<b) && !(b<a))
则 a == b
。两个键不能都小于对方。
对于你的钥匙和使用你的比较功能
Key{2, 169} < Key{1, 255} // this is true because 169 < 255
Key{1, 255} < Key{2, 169} // this is also true because 1 < 2
显然这是个问题,因为使用您的比较器,这两个键的比较结果都比彼此差。
我建议的解决方案:由于您的键是 std::pair
,因此您不需要定义新的比较器。 std::pair
已经默认使用字典顺序比较。
您可以通过使用 std::tie
.
bool operator()(const Key& lhs, const Key& rhs)
{
return std::tie(lhs.first, lhs.second) < std::tie(rhs.first, rhs.second);
}
您的比较器不符合std::map
的要求,需要提供一个strict weak ordering。幸运的是,如果您需要比较多个值,std::tuple
会为您实现此功能:
struct KeyLess {
bool operator()(const Key& lhs, const Key& rhs) {
return std::tie(lhs.first, lhs.second) < std::tie(rhs.first, rhs.second);
}
};
在您的情况下,您实际上根本不需要自定义比较器,因为 std::pair
的 <
运算符已经具有相同的行为。
您的 KeyLess
代码导致不正确的比较:
KeyLess cmp;
std::cout << cmp(Key{2, 169},Key{1, 391})<< std::endl; // yields true
std::cout << cmp(Key{1, 391},Key{2, 169})<< std::endl; // yields true
当两个比较都为假时,这意味着键是相等的,当它们为真时,映射迭代器的行为未定义。这与地图对其元素进行排序有关。
请注意,operator()
需要const
,否则程序可能无法使用标准 C++17 及更高版本进行编译。作为可能的变体:
#include <map>
#include <iostream>
using Key = std::pair<unsigned long, unsigned long long>;
struct KeyLess {
bool operator()(const Key& lhs, const Key& rhs) const {
if (lhs.first < rhs.first) {
return true;
}
else if (lhs.first > rhs.first)
return false;
if (lhs.second < rhs.second) {
return true;
}
return false;
}
};
int main()
{
std::map< Key , int, KeyLess > m;
m[Key{2, 169}] = 1;
m[Key{1, 255}] = 2;
m[Key{1, 391}] = 3;
m[Key{1, 475}] = 4;
std::cout << "Elements in map: " << m.size() << std::endl;
for(const auto &[key, value]: m) {
std::cout << "Key: " << key.first << ", " << key.second << " Value: "<< value << std::endl;
}
}