Переполнение кучи внутри пользовательской функции сортировки

Question

Привет, я боролся с простой программой, которая выполняет сортировку по массиву целых чисел

(полная программа здесь: https://pastebin.com/UMqEP62n)

Запуск сортировки на достаточно большойвектор целых чисел приводит к появлению случайных чисел в массиве, а затем зависит от данных, вызывающих segfault.

sort(nums.begin(), nums.end(), lex_compare);

Функция для сравнения:

bool lex_compare(const int &a, const int &b) {
    int ap = a, bp = b;
    vector<int> da, db;

    if (ap == 0) da.insert(da.begin(), ap%10);
    while (ap > 0) {
        da.insert(da.begin(), ap%10);
        ap /= 10;
    }
    if (bp == 0) db.insert(db.begin(), bp%10);
    while (bp > 0) {
        db.insert(db.begin(), bp%10);
        bp /= 10;
    }
    size_t size;
    if (da.size() < db.size()) {
        size = da.size();
    } else {
        size = db.size();
    }

    for (size_t i = 0; i < size; ++i)
        if (da[i] > db[i])
            return true;
        else if (da[i] < db[i])
            return false;
        else
            continue;

    if (da.size() > db.size())
        return false;
    else
        return true;
}

В основном, когда массив слишком длинный, повреждение памяти показываетдо переполнения буфера кучи.При компиляции с адресом Sanitizer он показывает, что:

==4097==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6140000001d0 at pc 0x00010aa396fe bp 0x7ffee51c5c50 sp 0x7ffee51c5c48
READ of size 4 at 0x6140000001d0 thread T0
#0 0x10aa396fd in lex_compare(int const&, int const&) main.cpp:8  

Что, по сути, является первой строкой функции lex_compare:

int ap = a, bp = b;

Я не могу понять, какая здесь ошибка, которая вызывает такое поведение?Это связано с размером функции сравнения?или у меня какая-то очевидная ошибка чтения из памяти?Я работаю с clang 4.2.1, но другие платформы также вызывают такое же поведение, поэтому я предполагаю, что что-то не так с функцией сортировки.

Answer 1

Ваша проблема в том, что вы нарушаете требование сравнения , которому должна следовать функция сравнения, переданная в std::sort.

Требование сравнения требует, чтобы если comp(a,b)==true, то comp(b,a)==falseно ваша функция сравнения не делает этого.например, если a = 0 и b = 0, то comp(a, b) приведет вас к

if (da.size() > db.size())
    return false;
else
    return true;

части вашей функции сравнения.Поскольку размеры равны, возвращается true.когда мы переворачиваем его и оцениваем comp(b, a), мы попадаем в тот же блок и возвращаем true.

Вам нужно вернуть false, когда a == b, а вы этого не делаете.