0

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

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

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;

}

4

1 回答 1

2

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

    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)它打破了等价的传递性。

于 2012-04-30T12:07:47.113 回答