提问者:小点点

set::find查找不存在的元素


我有以下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++的新手。


共2个答案

匿名用户

您当前没有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