std :: sort вызывает ошибку сегментации в операторе - PullRequest
Новая
       5

std :: sort вызывает ошибку сегментации в операторе

0 голосов
/ 26 мая 2020

Я пытаюсь отсортировать список (std::vector) трехмерных целочисленных векторов (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());
}

Я могу предоставить вам набор данных; однако сначала я хотел увидеть, есть ли у меня в коде большая концептуальная ошибка или ошибка, которую я не вижу. Я обнаружил, что проблема связана с c в этом наборе данных. Если я пропущу одну запись, Segfault не произойдет. Я считаю, что это довольно странно, поскольку такая ошибка должна быть более очевидной и иметь отношение к управлению памятью. Также обратите внимание на то, что использование целых чисел для x, y и z не вызывает никаких проблем.

Здесь - версия кода с фиксацией на кресте.

Вот связанный вопрос SO . Однако я думаю, что в моем коде нет того же недостатка, который вызвал эту ошибку. Я думаю, что мое отношение порядка "строго <". </s>

1 Ответ

10 голосов
/ 26 мая 2020

Логи вашего оператора c не работает (не удовлетворяет строгим требованиям слабого заказа). В последнем предложении также требуется lhs.z == rhs.z. В противном случае lhs.z может быть > rhs.z, но вы все равно получите положительный результат, что приведет к несогласованному упорядочиванию.

Алгоритмы стандартной библиотеки возлагают на вас бремя ответственности, чтобы сделать это правильно, и нарушение полученных предположений может легко приводят к хаосу (читай: неопределенному поведению), например к ошибкам сегментации.

Представьте себе комментарий внутри реализации, говорящий что-то вроде «на данный момент мы знаем, что a меньше b, поэтому мы не нужно выполнять проверку диапазона / границ на b ". Когда a неожиданно больше , чем b, отсутствие проверки границ может вызвать плохой доступ к памяти. Результат, однако, может быть гораздо более тонким и вызывать странные ошибки в дальнейшем, поэтому важно делать все правильно.

Вы могли бы sh рассмотреть возможность использования более короткого и менее подверженного ошибкам метода реализации. этот порядок: 

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

Использование operator< в кортеже (что дает вам std::tie) автоматически (и правильно!) выполняет лексикографию c за вас .

На странице cppreference для std::tie есть хороший пример этого, демонстрирующий, что это обычное дело.

...