Ошибка сегментирования где-то в sort

211
26 ноября 2017, 14:51

Добрый день!

Падает программа с ошибкой сегментирования написал 2 варианта программы, ошибку найти не могу

#include <algorithm>
#include <sstream>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using std::vector;
using std::string;

bool is_ge(string digit1, string digit2){
  std::cout << "Input compare" << digit1 << " " << digit2 << std::endl;
  std::cout << "Input compare size" << digit1.size() << " " <<   digit2.size() << std::endl;
  bool  result = true;
  for(int i = 0; i < std::min(digit1.length(), digit2.length()); ++i){
  std::cout << "Debug: " << digit1.size() << " " << digit2.size() << std::endl;
  std::cout << "Debug: " << digit1[i] << " " << digit2[i] << std::endl;
  if(digit1[i] > digit2[i]){
    std::cout << "cool" << std::endl; 
    break;
  } else if(digit1[i] < digit2[i]){
    std::cout << "bad" << std::endl; 
    result = false;
    break; 
  }
   std::cout << "Debug2: " << digit1[digit1.size() - i] << " " << digit2[digit2.size() - i] << std::endl;
  }
  std::cout << "exit of compare" << std::endl;
  return result;
}


string largest_number(vector<string> &a) {
  sort(a.begin(), a.end(), is_ge);
  std::cout << " bla" << std::endl;
  std::stringstream ret;
  for (size_t i = 0; i < a.size(); i++) {
      ret << a[i];
  }
  string result;
  ret >> result;
  std::cout << "result :" << std::endl;
  return result;
}

Причем падает где-то в сорт... Написал такую же версию без сорт - все равно падает, а где - понять не могу. В чем ошибка и как вообще отлаживать и ловить такие вещи?

Использую гцц.

int main() {
  int n;
  std::cin >> n;
  vector<string> a(n);
  for (size_t i = 0; i < a.size(); i++) {
      std::cin >> a[i];
  }
  std::cout << largest_number(a);
}

Второй код, где все падает:

#include <algorithm>
#include <sstream>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdlib>

using std::vector;
using std::string;

bool is_ge(string digit1, string digit2){
  std::cout << "Input compare" << digit1 << " " << digit2 << std::endl;
  std::cout << "Input compare size" << digit1.size() << " " <<     digit2.size() << std::endl;
  bool  result = true;
  for(int i = 0; i < std::min(digit1.length(), digit2.length()); ++i){
    std::cout << "Debug: " << digit1.size() << " " << digit2.size() << std::endl;
    std::cout << "Debug: " << digit1[i] << " " << digit2[i] << std::endl;
    if(digit1[i] > digit2[i]){
      std::cout << "cool" << std::endl; 
      break;
    } else if(digit1[i] < digit2[i]){
      std::cout << "bad" << std::endl; 
      result = false;
      break; 
    }
    std::cout << "Debug2: " << digit1[digit1.size() - i] << " " << digit2[digit2.size() - i] << std::endl;
    }
    std::cout << "exit of compare" << std::endl;
    return result;
 }


string largest_number(vector<string> &a) {
  sort(a.begin(), a.end(), is_ge);
  std::cout << " bla" << std::endl;
  std::stringstream ret;
  for (size_t i = 0; i < a.size(); i++) {
    ret << a[i];
  }
  string result;
  ret >> result;
  std::cout << "result :" << std::endl;
  return result;
 }


int main() {
  int n;
  std::cin >> n;
  vector<string> a(n);
  for (size_t i = 0; i < a.size(); i++) {
    a[i] = std::to_string(rand() % 10 + 1);
  }
  for (size_t i = 0; i < a.size(); i++) {
    std::cout << a[i] << "  ";
  }
  std::cout << std::endl;
  std::cout << largest_number(a);
}`

падает на размере 100 точно. Второй код - это вводишь размер и все, в отличии от первого

С сортом понятно, а почему падает без сорта следующий код?:

string largest_number(vector<string> &a) {
  string str;
  int j;
  std::stringstream ret;
  while(a.size() > 0){
    str = a[0];
  for(j = 0; j < a.size(); ++j){
     if(is_less(str, a[j])){
     std::cout << "1" << std::endl;
     str = a[j];
     } 
   }
   ret << a[j];
   std::cout << "Test1" << std::endl;
   std::cout << "Test3 " << std::endl;
   a.erase(a.begin() + j);
   std::cout << "Test2" << std::endl;
  }
  std::cout << " bla" << std::endl;
  string result;
  ret >> result;
  std::cout << "result :" << std::endl;
  return result;
}

при компараторе таком:

bool is_less(string digit1, string digit2){
 std::cout << "Input compare" << digit1 << " " << digit2 << std::endl;
 std::cout << "Input compare size" << digit1.size() << " " << digit2.size() << std::endl;
 bool  result = true;
 for(int i = 0; i < std::min(digit1.length(), digit2.length()); ++i){
    std::cout << "Debug: " << digit1.size() << " " << digit2.size() << std::endl;
    std::cout << "Debug: " << digit1[i] << " " << digit2[i] << std::endl;
    if(digit1[i] < digit2[i]){
      std::cout << "cool" << std::endl; 
      return false;
    } else if(digit1[i] > digit2[i]){
      std::cout << "bad" << std::endl; 
      return true;
      break; 
    }
    std::cout << "Debug2: " << digit1[digit1.size() - i] << " " << digit2[digit2.size() - i] << std::endl;
  }
  std::cout << "exit of compare" << std::endl;
  return false;
 }

Идея такая - я нахожу максимальный элемент в векторе, кидаю его в стрингстрим, а из вектора удаляю. И так до нулевого размера вектора.

Answer 1

Возможно, ваша сортировка падает потому, что функция сравнения не является полностью упорядочивающей функцией. Ваша функция не принимает во внимание «хвост» более длинной строки.

Кроме того, ваша функция (пытается) делать нестрогое сравнение, а нужно строгое.

Например, если сравнивать "" и "a", она выдаёт true, но если сравнивать их в обратном порядке ("a" и ""), она тоже выдаёт true. Это ошибка.

Ну и сравнение строки с самой собой тоже выдаёт true, и это тоже ошибка.

Исправьте эти ошибки, должно заработать.

Например, можно написать такой алгоритм (лексикографическое сравнение):

  1. Для индексов от 0 до минимума из длин, если a[i] < b[i] вернуть true, а если a[i] > b[i] вернуть false.
  2. Если длина a меньше длины b, вернуть true, если длина a больше длины b, вернуть false.
  3. В противном случае строки равны, вернуть false.

(Кстати, сравнение строк через < должно давать тот же результат.)

Документация: (http://eel.is/c++draft/alg.sorting#3 и дальше):

[3] ... comp shall induce a strict weak ordering on the values.

[4] The term strict refers to the requirement of an irreflexive relation (!comp(x, x) for all x)

На пальцах, почему std::sort падает? Когда он ищет по массиву элементы меньше некоторого элемента, то этот самый элемент попадает в список элементов, которые меньше себя. Например, если мы используем quicksort в реализации отсюда, то в цикле разбиения есть такая часть:

while (A[i] < pivot)
    i++;

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

READ ALSO
как вывести нормальную строку?

как вывести нормальную строку?

Всем приветСтолкнулся с проблемой

224
Как вытащить из ListView, item DynamicAppearance текст

Как вытащить из ListView, item DynamicAppearance текст

Друзья, закинул на форму 2 ListView'аУ одного тип item'а простой, а другого тип item'а DynamicAppearance и добавил несколько TTextObjectAppearance со своими названиями

233
Выборка одного поля из БД

Выборка одного поля из БД

Как выбрать из базы только одно значение? Выборка происходит вот так

192
Парсинг XML &gt; 3 GB

Парсинг XML > 3 GB

Всем привет, необходимо поменять некоторые параметры в XML файле, со сложной структуройРанее данную задачу решал через DocumentFactoryBuilder, как оказалось...

185