自定义Node对象的set集合查找正确性咨询：MinCost排序下的疑问

Great question! Let's break this down based on how C++'s std::set operates, because the behavior here depends entirely on how your comparison class defines "equality" for elements in the set.

First, How std::set Determines Element Equality #

Unlike some other containers, std::set does not use operator== to check if two elements are the same. Instead, it uses your custom comparator (MinCost in this case) to define equivalence:

Two elements a and b are considered equal if both comp(a, b) and comp(b, a) return false.

Analyzing Your MinCost Comparator #

Your comparator only checks the f value:

class MinCost { 
    bool operator()(const Node &x, const Node &y) { 
        return x.f < y.f; 
    } 
};

This means:

• If two Node objects have different f values, the comparator will correctly order them, and they'll be treated as distinct.
• If two Node objects have the same f value, both comp(x, y) and comp(y, x) will return false. The set will then consider these two nodes as equivalent—even if their node, g, or parent members are completely different.

The Problem for find() #

When you call frontier.find(target_node), the set will search for any element that is "equivalent" to target_node using the above rule. If there's another node in the set with the same f value as target_node (but different node/g/parent), the set might return that node instead of your intended one. Worse, if you tried to insert multiple nodes with the same f value, the set would reject duplicates because it thinks they're identical.

Since you stated your Node objects are unique (via other members), this comparator will not let find() work as expected.

Fixing the Issue #

To make find() correctly identify unique Node objects while still sorting by f, you need to adjust your comparator to break ties between nodes with the same f value using their unique identifiers. For example, if node is the unique key for each Node, modify the comparator like this:

class MinCost { 
    bool operator()(const Node &x, const Node &y) { 
        // First sort by f value (your original priority)
        if (x.f != y.f) {
            return x.f < y.f;
        }
        // If f is equal, sort by the unique node ID to distinguish elements
        return x.node < y.node; 
    } 
};

This way, two nodes with the same f will only be considered equivalent if their node values are also the same—matching your requirement that each Node is unique.

Key Takeaway #

Always remember that std::set's equivalence logic is tied directly to its sorting comparator. If you need to distinguish elements that have the same sort key, your comparator must include additional criteria to break those ties.

内容的提问来源于stack exchange，提问作者Atul Ramkrishnan