set::find 找到一个不存在的元素

Question

我有以下 Edgeclass:

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;
}
};

重写 < 运算符的要点是当我尝试 find 集合中的一条边 Edge(0, 1) 应该等于 Edge(1, 0) 时。但是，以下测试代码无法做到这一点并且 std::find returns 甚至不存在的边缘：

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++ 的新手，感谢任何帮助。

Answer 1

您目前没有 std::set 的有效 Compare，因此您的程序有未定义的行为。

这是一个与您的==

兼容的

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);
}

Answer 2

您的代码中有两个问题。

首先，你不检查test.find()是否是returns一条有效边；请注意 find returns end() 如果没有找到元素。

其次，您的 <-operator 没有实现严格的排序，它实际上只是定义了一个 !=。为了克服这个问题，我将对每条边进行归一化，以便始终将较低的节点视为起点；然后根据起始节点决定，只有它们相等，才考虑目的节点：

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

set::find 找到一个不存在的元素

set::find finds an element that does not exist

c++

std

stdset

c++11