我有以下edge
类:
class Edge {
public:
int src, dest;
bool operator== (const Edge &edge) const {
return ((src == edge.src) && (dest == edge.dest)) || ((src == edge.dest) && (dest == edge.src));
}
bool operator<(const Edge& edge) const {
return !(((src == edge.src) && (dest == edge.dest)) || ((src == edge.dest) && (dest == edge.src)));
}
Edge(int src, int dest) {
this->src = src;
this->dest = dest;
}
};
重写<
运算符的要点是,当我尝试查找
集中的边时,edge(0,1)
应该等于edge(1,0)
。 但是,下面的测试代码无法做到这一点,std::find
返回一个甚至不存在的边缘:
Edge edge(0, 3);
set<Edge> test;
test.insert(Edge(3, 1));
test.insert(Edge(3, 0));
auto a = test.find(edge);
cout << a->src << " " << a->dest << endl;
这将奇怪地打印出2.0
。 我不知道为什么,而且我是C++的新手。
您当前没有std::set
的有效比较,因此您的程序具有未定义的行为。
下面是一个与您的==
兼容的
bool operator<(const Edge& edge) const {
return std::minmax(src, dest) < std::minmax(edge.src, edge.dest);
}
这也可以用来简化您的==
bool operator==(const Edge& edge) const {
return std::minmax(src, dest) == std::minmax(edge.src, edge.dest);
}
您的代码中有两个问题。
首先,不检查test.find()
是否返回有效的边缘; 请注意,如果没有找到元素,find
将返回end()
。
其次,您的<
-运算符没有实现严格的排序,它实际上只是定义了一个!=
。 为了克服这个问题,我将每个边归一化,以便始终将较低的节点作为起始节点; 然后根据起始节点决定,并且只有当它们相等时,才考虑目标节点:
class Edge {
public:
int src, dest;
bool operator== (const Edge &edge) const {
return ((src == edge.src) && (dest == edge.dest)) || ((src == edge.dest) && (dest == edge.src));
}
bool operator<(const Edge& edge) const {
// return !(((src == edge.src) && (dest == edge.dest)) || ((src == edge.dest) && (dest == edge.src)));
int thisSrc = std::min(src,dest);
int thisDest = std::max(src,dest);
int eSrc = std::min(edge.src,edge.dest);
int eDest = std::max(edge.src,edge.dest);
if (thisSrc < eSrc) {
return true;
} else if (thisSrc > eSrc) {
return false;
} else {
return thisDest < eDest;
}
}
Edge(int src, int dest) {
this->src = src;
this->dest = dest;
}
};
#include <set>
int main() {
Edge edge(0, 3);
std::set<Edge> test;
test.insert(Edge(3, 1));
test.insert(Edge(3, 0));
auto a = test.find(edge);
if (a == test.end()) {
std::cout << "edge not found." << std::endl;
} else {
std::cout << a->src << " " << a->dest << std::endl;
}
}
输出:
3 0