std::使用没有排序的键进行映射

Question

如果我想要一个使用用户定义对象作为键的std::map，应该采取哪种方法？

让我们考虑一下这个最小的错误代码(它可以编译，但不能正确运行(：

#include <map>
class Object
{
public:
int x, y;
Object(int x, int y) : x(x), y(y) {};
bool operator<(const Object& o) const { return 1;};   // bogus just to make compiler happy
};
int main()
{
Object o1(1, 2), o2(3, 4);
std::map<Object, int> objmap;
objmap.insert(std::make_pair(o1, 11));
objmap.insert(std::make_pair(o2, 22));
}

为了能够在std::map中使用对象作为键，我们需要一个<运算符。

到目前为止还不错，但如果不能从"更少"或"更大"的角度来比较对象，而只能从"不同"的角度进行比较，该怎么办？

Answer 1

您的对象必须遵守严格的总顺序。这意味着，最重要的是，你的<关系必须是不可伸缩的和可传递的。在您的情况下，考虑只使用std:：tuple，它已经提供了一个具有字典排序功能的operator<。

这将是"一个"正确的排序，但很可能根本不是你想要的：

friend bool operator<(Object const& a, Object const& b) {
return a.x < b.x; // probably not what you want, but legal
}

因为这意味着Object{1,100}和Object{1,101}将导致std::map，前提是它们是相同的密钥(除非您想要(。

然而，如果您提供以下内容，您实际上可以破坏地图：

friend bool operator<(Object const& a, Object const& b) {
return a.x <= b.x; // this will break map
}

因为它不是不可伸缩的(即，x<x不会产生假(。

通常，您必须考虑对象的所有属性，以避免混叠(即贴图认为两个不同的对象相等(。除非您向我们展示您的Object，否则无法向您展示如何实现正确的operator<。

---

在大多数情况下，std::unordered_map是更好(更有效(的选择。

Answer 2

到目前为止还不错，但如果不能用"更少"或"更大"来比较对象，而只能用"不同"来比较，该怎么办？

您通常可以合成一个排序，例如

bool operator<(const Object& o) const { return std::tie(a, b) < std::tie(o.a, o.b); }

顺便说一句，这个构造是C++20的默认比较将使用的。

auto operator<=>(const Object& o) const = default;

Answer 3

由于这里Objects之间没有总顺序关系，一种可能性是使用unorded_map而不是map。

因此，object类至少需要一个重载的==运算符和一个自定义散列函数：

#include <unordered_map>
#include <iostream>
class Object
{
public:
int x, y;
Object(int x, int y) : x(x), y(y) {};
bool operator==(const Object& o) const
{
std::cout << "equal hashes, using == operator on (" << x << "," << y << ")n";
auto isequal = x == o.x && y == o.y;
std::cout << "objects are " << (isequal ? "" : "not ") << "equaln";
return isequal;
};
friend std::ostream& operator<<(std::ostream& os, const Object& o);
};
std::ostream& operator<<(std::ostream& os, const Object & o)
{
os << "(" << o.x << "," << o.y << ")";
return os;
}
struct ObjectHash {
size_t operator()(const Object& o) const
{
std::cout << "hashing (" << o.x << "," << o.y << ")n";;
return o.x + o.y;  // purposly bad hash function, so we get collisions
// (o.x * 127) ^ o.y  would be better, still not ideal
}
};

int main()
{
Object o1(1, 2);
Object o2(3, 4);  // different from o1, o3 and o4
Object o3(1, 2);  // equal to o1
Object o4(2, 1);  // different from o1, o2 and o3 but same hash as o1
std::unordered_map<Object, int, ObjectHash> objmap;
std::cout << "Inserting " << o1 << "n"; objmap.insert(std::make_pair(o1, 11));
std::cout << "Inserting " << o2 << "n"; objmap.insert(std::make_pair(o2, 22));
std::cout << "Inserting " << o3 << "n"; objmap.insert(std::make_pair(o3, 33));
std::cout << "Inserting " << o4 << "n"; objmap.insert(std::make_pair(o4, 33));
}

std::cout用于说明。

输出：

Inserting (1,2)
hashing (1,2)
Inserting (3,4)
hashing (3,4)
Inserting (1,2)
hashing (1,2)
equal hashes, using == operator on (1,2)
objects are equal
Inserting (2,1)
hashing (2,1)
equal hashes, using == operator on (2,1)
objects are not equal