非标准键的映射出了什么问题？

Question

我正在尝试编写一个 std::map 容器，其中键有两个值。以下是示例：

#include <map>
#include <iostream>

using namespace std;

struct Key {
    int i1; 
    int i2; 

    struct Comparator {
        bool operator() (const Key& k1, const Key& k2) {
            if (k1.i1 < k2.i1)
                return true;
            else if (k1.i2 < k2.i2)
                return true;

            return false;
        }   
    };  
};

int main() {
    std::map<Key, int, Key::Comparator> tree;

    for (int i = 0; i < 100; ++i) {
        for (int j = 0; j < 10; ++j) {
            Key key = {i, j}; 

            tree[key] = i * j;
        }   
    }   
    cout << "tree size: " << tree.size() << endl;

    Key key = {45, 3}; 

    std::map<Key, int, Key::Comparator>::iterator it = tree.find(key);
    if (it == tree.end()) {
        cout << "nothing has found" << endl;
        return 1;
    }   

    cout << "value: " << it->second << endl;

    return 0;
}

它告诉我"未找到任何内容"。我犯了什么错误？我应该怎样编写Comparator才能使其正常工作？谢谢。

- milo

Answer 1

考虑使用您的比较器，以下两种情况都是true:

Key(1,2) < Key(2,1)
Key(2,1) < Key(1,2)

你可以使用词典序：

return (k1.i1 != k2.i1) ? (k1.i1 < k2.i1)
                        : (k1.i2 < k2.i2);

- Oliver Charlesworth

---

@milo：你要找的是所谓的字典比较。 - Oliver Charlesworth

我添加了一个词典比较的例子。希望你不介意（也希望我没有犯错 :)）。 - Niklas B.

@NiklasB：我原本想把这个留给读者作为练习，但没关系。我已经添加了括号来解决优先级问题。 - Oliver Charlesworth

@NiklasB：确实如此。这将使您的版本等同于k1.i1 != (k2.i1 ? ...)。 - Oliver Charlesworth

@Oli Charlesworth 太好了！它起作用了！这真是个愚蠢的错误 =) - milo