为什么我的这个std::sort会排序数组之外的一个元素?

Question

为什么我的这个std::sort会排序数组之外的一个元素?

这是我用vector存储的自定义类型,数据部分包括2个指针和1个数字.

class Diff
{
    public:
        Diff (Pic *p1,Pic *p2);
        void cal_diff();
        int  get_diff_value()const;
        bool usable() const;

    public:
        Pic * p1;
        Pic * p2;
        int  diff_value;
        bool operator < (const Diff & diff);
};

我实现了它的比较函数用来排序.

bool Diff::operator<(const Diff &diff)
{
    if(this->usable() == false)
        return false;
    if(diff.usable() == false)
        return true;
    return this->get_diff_value() <= diff.get_diff_value();
}

但,我一用sort对存储它的vector数组进行排序就会崩溃,我debug了一下,发现.

比方说,这是崩溃时,operator<函数里的变量的存储内容.
两个值的地址的后4位分别是4160,6128.

但,我再检查这个数组的占用空间就会发现.

这是数组开头,第1个成员的地址后4位是4160.

这是数组结尾,最后1个成员的地址后4位是6110.

...也就是说,崩溃时,sort在拿数组结尾之外的内存空间当作存在的对象来进行比较.
这是为什么?我的sort函数的调用很普通,不应该有这种情况啊?

    std::sort(v_diff.begin(),v_diff.end());

c++stl

阅读 2.5k

AI BotBETA

### 回答

这个问题很可能是由于 `std::vector` 中存储的 `Diff` 对象在排序过程中被移动或复制到了未初始化或已释放的内存区域导致的。在你的 `Diff` 类中，包含了两个指针 `Pic *p1` 和 `Pic *p2`，这两个指针在 `Diff` 对象被移动或复制时不会自动处理（即不会自动更新或释放旧指针，也不会为新的 `Diff` 实例重新分配 `Pic` 对象）。这可能导致指针指向无效的内存位置，尤其是当 `std::sort` 使用诸如堆排序等算法时，可能会暂时将元素移动到数组之外的内存位置（尽管最终它们会被移回原数组）。

此外，你的比较函数 `operator<` 中对 `usable()` 的调用可能返回 `false` 对于某些 `Diff` 对象，这可能导致比较函数不遵循严格弱序（strict weak ordering）的要求。严格弱序要求对于任何元素 `a`, `b`, `c`，如果 `a < b` 为真，则 `b < a` 必须为假，且如果 `a < b` 和 `b < c` 都为真，则 `a < c` 也必须为真。如果 `usable()` 的结果影响了这些关系，则可能导致未定义行为，包括排序算法访问无效内存。

**解决方案**：

1. **确保 `Diff` 类支持移动语义**：为你的 `Diff` 类实现移动构造函数和移动赋值运算符，确保当对象被移动时，指针被正确管理。

2. **修正比较函数**：确保比较函数在任何情况下都返回一个严格弱序。如果 `usable()` 返回 `false`，你可能需要决定这些对象如何与其他对象比较（例如，总是认为它们大于所有其他对象）。

3. **使用稳定的排序算法或自定义排序**：如果 `Diff` 对象的顺序在排序过程中不应该改变（即，如果两个 `Diff` 对象 `a` 和 `b` 满足 `!(a < b) && !(b < a)`，则它们在排序后的相对位置应与排序前相同），考虑使用 `std::stable_sort` 代替 `std::sort`。

4. **调试和内存检查**：使用工具如 Valgrind 或 AddressSanitizer 来检查内存访问错误和未定义行为。

通过这些步骤，你应该能够诊断并解决排序过程中出现的崩溃问题。

1 个回答

得票最新

fefe

18.2k122632

发布于
1 月 2 日北京

✓ 已被采纳

sort 要求 a<a 返回 false 。你这里在usable == true 的情况下会返回 true 。

撰写回答