Сравнение проблемы метода при использовании сортировки STL

Question

Рассмотрим следующий код. Предполагается отсортировать вектор векторов целых в лексикографическом порядке, то есть сначала по первому столбцу, а затем по второму и так далее. В моем приложении я забочусь только о первых 6 из 8 столбцов так было возвращено значение true в случае, когда значения равны для первых 6 столбцов.

И это вызвало проблемы (ошибка сегментации). Он работал на 1000 данных, и он потерпел крах на 1001. Пример кода - игрушка, но сортировка является частью довольно сложной программы. После долгой отладки я узнал, что это стало причиной неприятностей. Программа пытается отсортировать массив всех нулей с помощью одной (1, 0, ..., 0) записи.

Пожалуйста, любой специалист по C ++, подскажите, что не так с оригинальной (указанной) программой?

Я компилировал его на 32-битной и 64-битной Linux и Visual Studio на 32-битной Windows. Это всегда было сбой. После изменения в комментарии все кажется нормально.

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

using namespace std;

const int COLS = 8;

bool compare (const vector<int>& r1, const vector<int>& r2)
{         
   for (int i = 0; i < COLS-2; i++)
     if ( r1[ i ] != r2[ i ] )
      return (r1[ i ] < r2[ i ]);
   return true; //if true is replace by r1[ COLS-1 ] < r2[ COLS-1 ] then is OK
};

int main(int argc, char **argv) 
{       
    int Na = 20;
    vector< vector<int> > v( Na );

    for (int r = 0; r < v.size(); r++)
      v[r].resize(COLS, 0);
    v[0][0] = 1;

    cout << "Sorting\n";
    sort( v.begin(), v.end(), compare );
    cout << "Eof Sorting\n";         

    return 0;
} 

Answer 1

Ваша функция сравнения должна возвращать false, когда входы равны, а не true.

Answer 2

Я думаю, что вы дует стек. Функция сортировки реализована рекурсивно, поэтому, если вы дадите противоречивые ответы о порядке следования элементов, алгоритм может не завершиться.

Answer 3

Проблема в вашей функции сравнения:

bool compare (const vector<int>& r1, const vector<int>& r2)
{         
   for (int i = 0; i < COLS-2; i++)
     if ( r1[ i ] != r2[ i ] )
      return (r1[ i ] < r2[ i ]);
   return true; //if true is replace by r1[ COLS-1 ] < r2[ COLS-1 ] then is OK
};

Если элементы равны, выражение r1 < r2 равно false - но в случае равенства (в вашем случае, если первые 6 целых равны) вы возвращаете true.

Answer 4

Если вы хотите отсортировать в лексикографическом порядке, вы можете использовать стандартную библиотеку:

bool compare (const vector<int>& r1, const vector<int>& r2)
{  
   return std::lexicographical_compare(r1.begin(), r1.begin()+6, r2.begin(), r2.begin()+6);
}

Answer 5

Это не обязательно связано с вопросом (это не приведет к сбою), но код пропускает один столбец.Код сравнивает 6 (8-2) столбцов, а затем (если используется незакомментированный код) сравнивает последний столбец.Рядом с последним не рассматривается.Тем не менее, это может быть намерением ... если так, то комментарий, вероятно, будет хорошим, если код должен существовать какое-то время.

Answer 6

Я ожидаю, что вы работаете за пределами одного из ваших векторов, что приведет к неопределенным результатам в сборках релиза.

В Linux, запустите вашу программу, используя превосходный Valgrind .

Вы также можете создать свой код, чтобы он проверял только фактические слоты в векторах, например:

bool compare (const vector<int>& r1, const vector<int>& r2)
{  
   const int max = std::min(r1.size(),r2.size());
   for (int i = 0; i<max; i++)
     if ( r1[ i ] != r2[ i ] )
      return (r1[ i ] < r2[ i ]);
   return r1.size() < r2.size();
};

Однако, если вы ожидаете точное количество слотов, это логическая ошибка, и игнорирование функции сравнения не обязательно является хорошим решением.