c++ - 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;
    }
};

然后找到所有的键。

为什么会这样？是不是因为原来的比较器没能构造出key之间的顺序？

Answer 1

你的比较器没有提供正确的顺序，这意味着 set 的内部在试图找出插入或插入的位置时会做各种奇怪的事情(又名“未定义的行为”)查找东西。

你需要这样的东西:

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