Добрый день!
Падает программа с ошибкой сегментирования написал 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
, и значит, может бежать до выхода за границу массива.
Кофе для программистов: как напиток влияет на продуктивность кодеров?
Рекламные вывески: как привлечь внимание и увеличить продажи
Стратегії та тренди в SMM - Технології, що формують майбутнє сьогодні
Выделенный сервер, что это, для чего нужен и какие характеристики важны?
Современные решения для бизнеса: как облачные и виртуальные технологии меняют рынок
Друзья, закинул на форму 2 ListView'аУ одного тип item'а простой, а другого тип item'а DynamicAppearance и добавил несколько TTextObjectAppearance со своими названиями
Всем привет, необходимо поменять некоторые параметры в XML файле, со сложной структуройРанее данную задачу решал через DocumentFactoryBuilder, как оказалось...