为什么与<运算符的矢量比较比较每个项目两次？

Question

在这个例子中,比较两个向量与<operator result in operator <,在Integer类上定义,为每个元素调用两次.但是,将两个向量与==运算符进行比较时不会发生这种情况.

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

此代码打印:

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

为什么会这样？

Answer 1

如果a < b返回false,它不会告诉您是否b < a,并且您必须测试它.那是因为逐元素排序std::vector对于一对元素可以有三个结果a, b:

• a < b,矢量比较返回true.
• b < a,矢量比较返回false.
• 以上两者都不必测试下一对元素.

所以它必须比较两个方向.通过向您的班级添加标识数据,您可以更清楚地看到这一点:

#include<iostream>
#include<vector>

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

    private:
        int m_value;
        char m_tag;

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


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

这会产生:

1 a < 1 b    
1 b < 1 a    
2 a < 2 b    
2 b < 2 a    
3 a < 3 b    
3 b < 3 a    
0    
1 a == 1 b    
2 a == 2 b    
3 a == 3 b    
1

[实例]

Answer 2

这是由于C ++当前如何处理比较的设计中的一个缺陷。他们正在c ++ 2a中修复它；我不知道它是否可以解决vector，但基本问题将得到解决。

首先是问题。

std::vector的<是各元素的基于关闭<。但是<对于这项工作而言，这是一个糟糕的工具。

如果您有两个元素a和b，以按字母顺序对元组进行排序，则a,b需要执行以下操作：

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

通常，<如果要按字典顺序订购N个元素的集合，则需要2N-1调用。

这早已为人所知，这就是为什么strcmp返回具有3种值的整数的原因：-1小于，0等于和+1大于（或通常，小于，等于或大于零的值）。

这样，您可以执行以下操作：

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

这最多需要N调用compare集合中的每个元素。

现在，解决。

c ++ 2a添加了飞船比较运算符<=>。它返回一个可以比较为大于或小于零的类型，并且其确切类型会通告该操作提供的保证。

这就像C一样strcmp，但是可以在支持它的任何类型上工作。此外，也有std其使用的功能<=>（如果可用）和以其它方式使用<和==类似效仿和。

假设矢量的要求被重写使用<=>，类型与<=>将避免双重比较和只是<=>最多一次每个“d做的排序词素文字std::vector时<被调用。