Почему сравнение векторов с помощью оператора <сравнивает каждый элемент дважды?

Question

В этом примере сравнение двух векторов с оператором <приводит к оператору <, определенному в классе Integer, который вызывается дважды для каждого элемента. Однако этого не происходит при сравнении двух векторов с оператором ==. </p>

#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

Чтобы найти лексикографический порядок ivec1 и ivec2, реализация ищет первый индекс i, для которого ivec1[i] < ivec2[i] или ivec2[i] < ivec1[i], так как это определит порядок.

Обратите внимание, что для этого нужно два сравнения, если ivec1[i] < ivec2[i] равно false. В частности, вышеупомянутый случай оставляет две возможности, а именно «ivec1[i] и ivec2[i] сравнить эквивалент» и «ivec2[i] < ivec1[i]». В этом решении необходимо второе сравнение.

---

Как только такой индекс i найден, реализация может остановить сравнение; но так как все записи сравниваются в вашем примере, необходимо выполнить два сравнения для каждой пары записей.

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;

В общем, для этого требуется 2N-1 вызовов <, если вы хотите лексографически упорядочить коллекцию из N элементов.

Это известно давно, и поэтому 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 при < называется.

Answer 3

Если 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

[Живой пример]