Not able to insert different values of struct into Map

user_1256475 0
Viewed 58

I use Node to hold (x, y) of coordinator and try to insert 4 nodes into map. The following code only print 2 nodes, why?

{0,0}, 0
{1,2}, 3

If i change the code of overload operator '<' with

bool operator<(const Node &ob) const
{
    return x < ob.x or y < ob.y;
}

It prints all 4 nodes. My understanding the operator< only impact the ordering of keys.

code

#include <iostream>
#include <map>

template<typename T1, typename T2>
struct Node
{
    T1 x;
    T2 y;

    Node(T1 x, T2 y): x(x), y(y) {}

    bool operator<(const Node &ob) const
    {
        return x < ob.x and y < ob.y;
    }
    
    bool operator==(const Node &ob) const
    {
        return x == ob.x and y == ob.y;
    }
    
};

int main()
{
    std::map<Node<int, int>, int> map =
    {
        {{0, 0}, 0},
        {{0, 1}, 1},
        {{1, 0}, 2},
        {{1, 2}, 3}
    };

    for (const auto &entry: map)
    {
        auto key = entry.first;
        std::cout << "{" << key.x << "," << key.y << "}, " << entry.second << std::endl;
    }

    return 0;
}
dictionary c++
1 Answers

std::map considers two element to be equal if for two keys a and b, the comparator (in your case, the default, std::less) fulfils

!comp(a, b) && !comp(b, a)

Let's check your case:

First you insert the key Node<int, int>(0, 0), then the key Node<int, int>(0, 1). For these elements (and your operator<) the following holds:

!std::less(Node<int, int>(0, 0), Node<int, int>(0, 1))
&& !std::less(Node<int, int>(0, 0), Node<int, int>(0, 1)) 
=>
!(Node<int, int>(0, 0) < Node<int, int>(0, 1))
&& !(Node<int, int>(0, 1) < Node<int, int>(0, 0))
=>
!(0 < 0 && 0 < 1) && !(0 < 0 && 1 < 0)
=>
!(false && true) && !(false && false)
=> !false && !false
=> true

So both nodes are considered equal and no insertion happens. The same holds for Node<int, int>(1, 0).

The insertion of Node<int, int>(1, 2) works because

!(0 < 1 && 0 < 2) && !(1 < 0 && 2 < 0)
=>
!(true && true) && !(false && false)
=>
!true && !false
=>
false && true
=>
false

You can fix the problem by using another operator<, e.g., as said in the comments, by using std::tie.

user_64323220
Related