提问人:DinoStray 提问时间:3/31/2019 最后编辑:Lightness Races in OrbitDinoStray 更新时间:4/2/2019 访问量:85
std::set 的重载运算符<让我感到困惑
overloading operator < for std::set confused me
问:
我知道我必须重载 std::set 的运算符<。
我用两个类重载运算符<:“UniqueID”和“UniqueIDWithBug”。
唯一的区别是“UniqueID”在比较时添加了代码。this->unique_id_a_ == t.unique_id_a_
然后我把相同的元素放到两个集合中。 最后,我在集合中找到了一个元素。 一组可以找到它,另一组找不到。 这个问题困扰了我很长一段时间。
struct UniqueID {
uint64_t unique_id_a_{0};
uint64_t unique_id_b_{0};
bool operator<(const UniqueID &t) const {
if (this->unique_id_a_ < t.unique_id_a_) {
return true;
}
if (this->unique_id_a_ == t.unique_id_a_ &&
this->unique_id_b_ < t.unique_id_b_) {
return true;
}
return false;
}
};
struct UniqueIDWithBug {
uint64_t unique_id_a_{0};
uint64_t unique_id_b_{0};
bool operator<(const UniqueIDWithBug &t) const {
if (this->unique_id_a_ < t.unique_id_a_) {
return true;
}
return (this->unique_id_b_ < t.unique_id_b_);
}
};
// init data
std::set<UniqueID> _set = {
{17303934402126834534u, 2922971136},
{8520106912500150839u, 3118989312},
{9527597377742531532u, 2171470080},
{10912468396223017462u, 3972792320},
};
std::set<UniqueIDWithBug> _set_with_bug = {
{17303934402126834534u, 2922971136},
{8520106912500150839u, 3118989312},
{9527597377742531532u, 2171470080},
{10912468396223017462u, 3972792320}};
UniqueID _unique_id = {10912468396223017462u, 3972792320};
UniqueIDWithBug _unique_id_with_bug = {10912468396223017462u, 3972792320};
if (_set.find(_unique_id) == _set.end()) {
std::cout << "_set not find" << std::endl;
}
if (_set_with_bug.find(_unique_id_with_bug) == _set_with_bug.end()) {
std::cout << "_set_with_bug not find" << std::endl;
}
输出: _set_with_bug未找到
答:
5赞
Lightness Races in Orbit
3/31/2019
#1
您定义为用于(和其他)的 less-than 运算必须是有效的严格弱排序。std::set
您的 UniqueIDWithBug 排序不是。
例如,请考虑:
UniqueIDWithBug a{1, 10};
UniqueIDWithBug b{2, 5};
现在观察两者 和 都是真的。这只是一个快速的演示,表明您没有严格的弱排序;事实上,这根本不是命令!a < b
b < a
因此,您的程序具有未定义的行为。该机制的内部假定有有效的排序,但您的则不是。在本例中,可观察的结果是“未找到元素”。它可能是“做披萨”。std::set
构建一个好的严格弱排序可能很困难,但你已经完成了艰苦的工作,因为 UniqueID 的排序是正确的。
或者,完全放弃排序,定义一个哈希函数,然后切换到 。unordered_set
评论
UniqueIDWithBug
UniqueIDWithBug a{1, 10}
UniqueIDWithBug b{2,5}
a < b
b < a
true
unordered_set
?std::tie
使正确地执行此操作变得更加容易。 是你所需要的一切。想象一下,扩展您的正确版本以手动处理 4 个变量。return std::tie(unique_id_a_, unique_id_b_) < std::tie(t.unique_id_a_, t.unique_id_b_);
operator<