Why does vector comparison with < operator compare each item twice?

Question

In this example comparing two vectors with < operator results in operator <, defined on the Integer class, being called twice for each element. However, this doesn't happen when comparing two vectors with == operator.

#include<iostream>
#include<vector>

class Integer {
    public:
        Integer(int value) : m_value(value) {}
        friend bool operator<(const Integer& lhs, const Integer& rhs);
        friend bool operator==(const Integer& lhs, const Integer& rhs);

    private:
        int m_value;

}; 
bool operator<(const Integer& lhs, const Integer& rhs) {
            std::cout << lhs.m_value << " < " << rhs.m_value << '\n';
            return lhs.m_value < rhs.m_value;
}
bool operator==(const Integer& lhs, const Integer& rhs) {
            std::cout << lhs.m_value << " == " << rhs.m_value << '\n';
            return lhs.m_value == rhs.m_value;
}


int main()
{
    std::vector<Integer> ivec1 {1,2,3};
    std::vector<Integer> ivec2 {1,2,3};
    std::cout << (ivec1 < ivec2) << '\n';
    std::cout << (ivec1 == ivec2) << std::endl;
    return 0;
}

This code prints:

1 < 1
1 < 1
2 < 2
2 < 2
3 < 3
3 < 3
0
1 == 1
2 == 2
3 == 3
1

Why is that so?

Answer 1

This is due to a flaw in the design of how C++ currently handles comparison. They are fixing it in c++2a; I don't know if it will get to vector, but the fundamental problem will be fixed.

First, the problem.

std::vector's < is based off of each elements <. But < is a poor tool for this job.

If you have two elements a and b, to lexographically order the tuple a,b you need to do:

if (self.a < other.a)
  return true;
if (other.a < self.a)
  return false;
return self.b < other.b;

in general, this requires 2N-1 calls to < if you want to lexographicaly order a collection of N elements.

This has been known for a long time, and is why strcmp returns an integer with 3 kinds of values: -1 for less, 0 for equal and +1 for greater (or, in general, a value less than, equal to or greater than zero).

With that you can do:

auto val = compare( self.a, other.a );
if (val != 0) return val;
return compare( self.b, other.b );

this requires up to N calls to compare per element in the collection.

Now, the fix.

c++2a adds the spaceship comparison operator <=>. It returns a type which can be compared greater than or less than zero, and whose exact type advertises what guarantees the operation provides.

This acts like C's strcmp, but works on any type that supports it. Further, there are std functions which use <=> if available and otherwise use < and == and the like to emulate it.

Assuming vector's requirements are rewritten to use <=>, types with <=> will avoid the double-compare and just be <=>'d at most once each to do the lexographic ordering of std::vector when < is called.