c++ - 如何使用我的用户定义类型正确重载 operator< 以便在 std::map 中使用？

Question

我有一个名为 set 的类，它是一个在内部动态分配的数组，充当具有所需重载运算符的容器。这个数组 (1D) 存储(有时是天文数字)数量的整数，当整个集合插入到这个数组中时，我用 std::sort 排序(比使用 std::set 快得多)。这些集合被放入 std::map 中，它们充当 double 值的键，当 std::map 已经具有该集合并且如果当前集合不在 std::map 容器中则它被插入与计数器“0”。我试图重载 operator< 因为 std::map 需要它。但它导致了段错误。数组的第一个成员(名为 arr)存储集合中的整数个数，也就是数组总长度为 arr[0]+1。

我不使用 vector 或新数组类型的原因是因为我很快就用完了 RAM (64GB)，这些集合在峰值时刻(生成子集)的大小为 2^10 到 2^11，所以我想以最小的空间开销创建我自己的 vector 版本。

bool operator<(const set& s1, const set& s2)
{
    if (s1.arr[0] < s2.arr[0])
        return true;
    else if (s1.arr[0] > s2.arr[0])
        return false;

    if (s1.arr[0] == s2.arr[0])
    {
        for (int i = 1; i < s1.arr[0]+1; i++)
        {
            if (s1.arr[i] > s2.arr[i]) return false;
        }
    }
    return true;

Answer 1

你应该改变你的内循环比较类似于你的长度比较:

    for (int i = 1; i < s1.arr[0]+1; i++)
    {
        if (s1.arr[i] < s2.arr[i])
            return true;
        else if (s1.arr[i] > s2.arr[i])
            return false;
    }

这样，您的比较运算符将实现严格的弱排序。例如，您的原始运营商没有 (2 0 2)与(2 1 1)无可比拟, (2 1 1)与(2 0 3)无可比拟，但是 (2 0 2) < (2 0 3)这打破了等价的传递性。