时间戳

首页 > 解决方案 > std::sort 导致运算符中的分段错误<

c++ - std::sort 导致运算符中的分段错误<

问题描述

我正在尝试对std::vector3D 整数向量 ( IntVec) 的列表 ( ) 进行排序。不知何故，std::sort导致operator<. IntVec这是我的代码：

#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>

struct IntVec
{
public:
    long x;
    long y;
    long z; // Using ints does not cause the Segmentation Fault ?!

    friend bool operator<(const IntVec &lhs, const IntVec &rhs)
    {
        return (lhs.z < rhs.z) ||  // Segmentation Fault happens here
                    ((lhs.z == rhs.z) && (lhs.y < rhs.y))
                        || ((lhs.y == rhs.y) && (lhs.x < rhs.x));
    }
};

int main(void)
{
    std::vector<IntVec> vec;

    const int N = 2178;
    std::ifstream s("res.txt");
    for (int i = 0; i < N; i++)
    {
        IntVec t;
        s >> t.x;
        s >> t.y;
        s >> t.z;
        vec.push_back(t);
    }

    // Using vec.begin() and vec.end() does not change anything
    std::sort(vec.data(), vec.data() + vec.size());
}

我可以为您提供数据集；但是，我首先想看看我的代码中是否有一些重大的概念错误或我没有看到的一些错误。我发现问题是特定于该数据集的。如果我遗漏一个条目，则不会发生 Segfault。我认为这很奇怪，因为这样的错误应该更明显并且与内存管理有关。另请注意，对x,y和使用整数z不会导致任何问题。

这是代码的godbolt版本。

这是一个相关的 SO question。但是，我认为我的代码没有导致此错误的相同缺陷。我认为我的排序关系是“严格<”。

标签： c++sortingsegmentation-fault

解决方案

您的操作员的逻辑被破坏（不满足严格的弱排序要求）。最后一个子句lhs.z == rhs.z也需要一个。否则，lhs.z可以，> rhs.z但您仍然会得到肯定的结果，从而导致排序不一致。

标准库算法让您有责任做到这一点，打破由此产生的假设很容易导致混乱（阅读：未定义的行为），例如分段错误。

想象一下实现中的注释，说类似“此时，我们知道a小于b，所以我们不需要对范围/边界检查b”。当a出乎意料地大于时b，缺少边界检查可能会导致错误的内存访问。然而，结果可能更加微妙，并导致奇怪的错误，因此正确处理很重要。

您可能希望考虑使用更短、更不容易出错的方法来实现此排序：

return std::tie(lhs.z, lhs.y, lhs.x) < std::tie(rhs.z, rhs.y, rhs.x);

在元组上使用operator<（这是std::tie给你的）自动（并且正确！）为你执行字典分解。

在 cppreference 页面std::tie上实际上有一个很好的例子，表明这是很常见的事情。

推荐阅读