ключи в наборе не могут быть найдены с помощью set :: find ()

Question

Я получаю эту проблему во время эксперимента с set.

Я использую структуру с 2 целыми числами в качестве ключа:

struct Key {
    int k1;
    int k2;
};

И использовать класс для построения порядка между ключами:

struct keyComp {
    bool operator () (const struct Key& lhs, const struct Key& rhs) const {
        if (lhs.k1 < rhs.k1)
            return true;
        else if (lhs.k2 < rhs.k2)
            return true;
        else
            return false;
    }
};

Но с помощью этого компаратора набору не удалось найти некоторые существующие ключи. Например, в этой программе я храню 9 ключей в наборе, от (0, 0) до (2, 2):

Key pos;
set <Key, keyComp> aset;

// insert elements from (0, 0) to (2, 2)
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        pos.k1 = i;
        pos.k2 = j;
        aset.insert (pos);
    }
}

// now try to find each of them
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        pos.k1 = i;
        pos.k2 = j;
        set <Key, keyComp> :: iterator it = aset.find (pos);
        if (it != aset.end ())
            cout << "v "; // element found
        else
            cout << "! "; // not found
    }
    cout << endl;
}

// print the set
cout << "element in set : ";
for (set <Key, keyComp> :: iterator it = aset.begin (); it != aset.end (); it++) {
    cout << "(" << it->k1 << ", " << it->k2 << ") ";
}
cout << endl;

Я ожидаю, что он напечатает 9 v, что означает, что все ключи найдены. Но вместо этого я получил:

v v v 
! ! v 
! ! v 
element in set : (0, 0) (1, 0) (2, 0) (0, 1) (1, 1) (2, 1) (0, 2) (1, 2) (2, 2)

Некоторые ключи можно найти, но некоторые не могут даже найти их в наборе.

Кроме того, если я изменю компаратор на:

struct keyComp {
    bool operator () (const struct Key& lhs, const struct Key& rhs) const {
        // combine the two keys for comparison
        // say LARGE_NUMBER is a number bigger than all k2
        return lhs.k1 * LARGE_NUMBER + lhs.k2 < rhs.k1 * LARGE_NUMBER + rhs.k2;
    }
};

Тогда все ключи найдены.

Почему это происходит? Это потому, что исходный компаратор не смог построить порядок между ключами?

Answer 1

Ваш компаратор не обеспечивает правильное упорядочение, а это означает, что внутреннее устройство set будет делать всевозможные странные вещи (так называемое "неопределенное поведение") при попытке выяснить, куда вставлять или искать вещи.

Вам нужно что-то вроде этого:

    if (lhs.k1 < rhs.k1)
        return true;
    if (lhs.k1 > rhs.k1)
        return false;
    return (lhs.k2 < rhs.k2);

Answer 2

Ваш компаратор не определяет строгий слабый порядок. (Например, (2,1) и (1,2) дают в вашем компараторе true в обоих направлениях.) Вам нужно что-то вроде лексикографического порядка:

return (lhs.k1 < rhs.k1)  || ( !(rhs.k1 < lhs.k1) && (lhs.k2 < rhs.k2) );