Добрый день!
Падает программа с ошибкой сегментирования написал 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;
}
Идея такая - я нахожу максимальный элемент в векторе, кидаю его в стрингстрим, а из вектора удаляю. И так до нулевого размера вектора.
Возможно, ваша сортировка падает потому, что функция сравнения не является полностью упорядочивающей функцией. Ваша функция не принимает во внимание «хвост» более длинной строки.
Кроме того, ваша функция (пытается) делать нестрогое сравнение, а нужно строгое.
Например, если сравнивать "" и "a", она выдаёт true, но если сравнивать их в обратном порядке ("a" и ""), она тоже выдаёт true. Это ошибка.
Ну и сравнение строки с самой собой тоже выдаёт true, и это тоже ошибка.
Исправьте эти ошибки, должно заработать.
Например, можно написать такой алгоритм (лексикографическое сравнение):
a[i] < b[i] вернуть true, а если a[i] > b[i] вернуть false.a меньше длины b, вернуть true, если длина a больше длины b, вернуть false.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, и значит, может бежать до выхода за границу массива.
Современные инструменты для криптотрейдинга: как технологии помогают принимать решения
Апостиль в Лос-Анджелесе без лишних нервов и бумажной волокиты
Основные этапы разработки сайта для стоматологической клиники
Продвижение своими сайтами как стратегия роста и независимости