如何使用 std::find 查找具有结构成员值的集合元素？

Question

struct Node{
    int id;
    float x;
    float y;
    float z;
    Node(int newId,float newX,float newY,float newZ){id=newId;x=newX;y=newY;z=newZ;}
    bool operator<(const Node& rhs)const {return id < rhs.id;}
};

set<Node> graph;
Node a(1,2,3,4);
Node b(2,1,2,3);
Node c(3,4,5,6);
graph.insert(a);
graph.insert(b);
graph.insert(c);

我想使用查找函数查找 graph 中具有特定 id 的元素。像 Node n = graph.find(3) 这样的东西会 return 一个指向 id 为 3, x 4, y 5, z 6 的元素的迭代器。目前 find 函数只接受一个初始化的节点作为参数。

Answer 1

How do I use the std::find to find a set element with a struct member value?

Currently the find function will only accept an initialized Node as an argument.

严格来说，std::find并没有这样的要求。您可以传递与元素类型相当的任何类型的对象。也就是说，您可以使用 std::find_if 而不是 std::find。

请注意 std::find_if（类似于 std::find）具有线性复杂度。如果您想要一种数据结构，可以高效地根据相关整数查找元素，那么您需要使用关联映射而不是集合。

Answer 2

您尝试使用的是 set<Node>::find() 而不是 std::find()。您可以使用类似于 std::find() - std::find_if():

的函数轻松地做您想做的事

auto iter = std::find_if( graph.begin(), graph.end(), [](const Node& node){return node.id==3;});

此解决方案的问题是 std::find() 和 std::find_if() 具有 O(n) 计算复杂度（其中 n 是范围内的元素数），同时使用set<Node>::find() 只需要 O(log(n)) 复杂度。如果你稍微改变你的设计（并且你至少使用 C++14），你就可以实现。

首先对struct Node使用non-member operator<，并增加比较运算符：

struct Node{
    int id;
    float x;
    float y;
    float z;
    Node(int newId,float newX,float newY,float newZ){id=newId;x=newX;y=newY;z=newZ;}
};

bool operator<(const Node& lhs, const Node& rhs)const {return lhs.id < rhs.id;}
bool operator<(const Node& lhs, int rhs)const {return lhs.id < rhs;}
bool operator<(int lhs, const Node& rhs)const {return lhs < rhs.id;}

接下来，您需要使用带有透明比较器的集合：

std::set<Node, std::less<>> graph;

现在，您正在尝试的应该有效：

auto iter = graph.find(3)

如何使用 std::find 查找具有结构成员值的集合元素？

How do I use the std::find to find a set element with a struct member value?

c++

struct

std

set

find