C++

Forum

 
is this ok as a less than operator for a map?

rozick1 (218)
I have a map of the following type:

1
2
3
4
5
6
 
  struct MyType
  {
     size_t layerPos, posInLayer, prevPos;

  };
  std::map<MyType, string> myMap;


std::map needs a less than operator to be defined for the key. I have written the following:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 

struct MyTypeCompare
{
    bool operator() (const MyType& lhs, const MyType& rhs) const
    {
        if(lhs.layerPos < rhs.layerPos)
        {
            return true;
        }
        if (rhs.layerPos > lhs.layerPos)
        {
            return false;
        }

        if (lhs.posInLayer < rhs.posInLayer)
        {
            return true;
        }
        if (rhs.posInLayer > lhs.posInLayer)
        {
            return true;
        }
        return lhs.prevPos < rhs.prevPos;
    }
};


and then:

1
2
 
std::map<MyType, std::string, MyTypeCompare>;


Is my less than function correct?

Thanks

Peter87 (11235)
No it's not correct.

Take a look at the first two if statements:
1
2
3
4
5
6
7
8
 
if(lhs.layerPos < rhs.layerPos)
{
    return true;
}
if (rhs.layerPos > lhs.layerPos)
{
    return false;
}

If we rewrite the second if condition using < it would look like the following:
1
2
3
4
5
6
7
8
 
if (lhs.layerPos < rhs.layerPos)
{
    return true;
}
if (lhs.layerPos < rhs.layerPos)
{
    return false;
}

As you can see the condition is the same in both cases. If the condition is true it will return true from the first if statement. The second if statement doesn't matter because it will never be reached when the condition is true.

The same could be said about the next two if statements.

In other words, your code is equivalent to the following:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
struct MyTypeCompare
{
    bool operator() (const MyType& lhs, const MyType& rhs) const
    {
        if(lhs.layerPos < rhs.layerPos)
        {
            return true;
        }
        
        if (lhs.posInLayer < rhs.posInLayer)
        {
            return true;
        }
        
        return lhs.prevPos < rhs.prevPos;
    }
};

What you could do to fix this is to either use lhs on the left hand side and rhs on the right hand side consistently
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
struct MyTypeCompare
{
    bool operator() (const MyType& lhs, const MyType& rhs) const
    {
        if (lhs.layerPos < rhs.layerPos)
        {
            return true;
        }
        if (lhs.layerPos > rhs.layerPos)
        {
            return false;
        }

        if (lhs.posInLayer < rhs.posInLayer)
        {
            return true;
        }
        if (lhs.posInLayer > rhs.posInLayer)
        {
            return false; // Note that this should be false!
        }

        return lhs.prevPos < rhs.prevPos;
    }
};

Or use < everywhere.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
struct MyTypeCompare
{
    bool operator() (const MyType& lhs, const MyType& rhs) const
    {
        if (lhs.layerPos < rhs.layerPos)
        {
            return true;
        }
        if (rhs.layerPos < lhs.layerPos)
        {
            return false;
        }

        if (lhs.posInLayer < rhs.posInLayer)
        {
            return true;
        }
        if (rhs.posInLayer < lhs.posInLayer)
        {
            return false; // Note that this should be false!
        }

        return lhs.prevPos < rhs.prevPos;
    }
};

Though, my preferred way to write this sort of logic is to check if the values are different and in that case return the result of the < operator.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
struct MyTypeCompare
{
    bool operator() (const MyType& lhs, const MyType& rhs) const
    {
        if (lhs.layerPos != rhs.layerPos)
        {
            return lhs.layerPos < rhs.layerPos;
        }
        
        if (lhs.posInLayer != rhs.posInLayer)
        {
            return lhs.posInLayer < rhs.posInLayer;
        }
        
        return lhs.prevPos < rhs.prevPos;
    }
};
Last edited on
rozick1 (218)
ah great, thanks so much
JLBorges (13770)
1
2
3
4
5
6
7
8
9
10
 
struct MyType
{
    std::size_t layerPos = 0 ;
    std::size_t posInLayer = 0 ;
    std::size_t prevPos = 0 ;

    // three-way comparison operator: generates support for all the six two-way comparison operators ==, !=, <, <=, >, =>
    // https://en.cppreference.com/w/cpp/language/default_comparisons#Defaulted_three-way_comparison
    friend auto operator <=>( const MyType&, const MyType& ) noexcept = default ;
};

Topic archived. No new replies allowed.