CODEWITHSUNDEEP
c++structsetfindstd
Peter King
Peter King

Reputation: 46

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

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

I want to use the find function to find an element of graph with a certain id. Something like Node n = graph.find(3) that would return an iterator to the element with id 3, x 4, y 5, z 6. Currently the find function will only accept an initialized Node as an argument.

Upvotes: 1

Views: 823

Answers (2)

Eugene
Eugene

Reputation: 7488

What you are trying to use is set<Node>::find() rather than std::find(). You could easily do what you want with a function similar to std::find() - std::find_if():

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

The problem with this solution is that std::find() and std::find_if() have O(n) computational complexity (where n is the number of elements in the range), while using set<Node>::find() requires only O(log(n)) complexity. You can achieve that if you slightly change your design (and you are using at least C++14).

First, use non-member operator< for struct Node, and add more comparison operators:

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

Next, you need to use a set with transparent comparator:

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

Now, what you are trying should work:

auto iter = graph.find(3)

Upvotes: 2

eerorika
eerorika

Reputation: 238351

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.

Strictly speaking, std::find doesn't have such requirement exactly. You can pass an object of any type that is comparable with the element type. That said, you may use std::find_if instead of std::find.

Note that std::find_if (like std::find) has linear complexity. If you want a data structure where finding an element based on related integer is efficient, then you'll want to use an associative map rather than a set.

Upvotes: 0

Related Questions