Пользовательский компаратор для целых чисел в векторе строки
Я хочу отсортировать вектор строк, представляющих очень большие значения (10**6 цифр) в порядке возрастания в C++. Я пытаюсь использовать собственный компаратор, но сортировка не удается при сравнении чисел с одинаковым количеством цифр, например. не удалось переставить 82 и 44.
Вот небольшой пример:
#include <bits/stdc++.h>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
string ltrim(const string &);
string rtrim(const string &);
bool comp(const string &left, const string &right)
{
if (left.size() < right.size())
{
return true;
}
if (left.size() > right.size())
{
return false;
}
for (unsigned long int i = 0; i < left.size(); i++)
{
if (left[i] > (right[i]))
{
// left is bigger
return false;
}
}
// left is smaller or equal
return true;
}
int main(void)
{
vector<string> str_nums = {"82", "44", "131", "2"};
sort(str_nums.begin(), str_nums.end(), comp);
for (string e : str_nums)
{
cout << e << endl;
}
return 0;
}
Это выводит:
2
82
44
131
где числа с разными цифрами подходят, но числа с двумя цифрами не сортируются. В чем проблема, пожалуйста?
Использование правильной проекции гарантирует правильность: return std::tuple{lhs.size(), lhs} < std::tuple(rhs.size(), rhs);
Примечания: (1) Почему мне не следует #include <bits/stdc++.h>? (2) В чем проблема с «использованием пространства имен std;»?.
Ваша функция не сравнивает числа, она сравнивает отдельные символы. Это почти эквивалентно left <= right.
В вашем цикле, когда left[i] < right[i], вы просто пропускаете эту цифру...
Если ваши числа могут иметь ведущие 0, сравнение размеров не будет надежным.
Кажется, вы просто хотите std::stoi(left) <= std::stoi(right).
@Someprogrammerdude: < нет <= ;-)
В чем проблема, пожалуйста? -- Что такое отладчик? . Умение отлаживать собственный код является неотъемлемой частью обучения написанию программ. Начните учиться использовать отладчик этой программы, которая содержит только те данные, которые, по вашему мнению, работают неправильно.
@Someprogrammerdude это 10^6 цифр, а не просто 10^6; так что это слишком долго, даже если long long unsigned stoi также выдаст ошибку, поскольку число слишком велико
@YWH Тогда тебе нужно придумать другой способ сравнения чисел. Или используйте существующую библиотеку bignum. Также обратите внимание, что показанная вами функция неоднозначна. Для размера он выполняет как «меньше», так и «меньше или равно», а для символов (не чисел) — «меньше или равно». Это нарушает строгое требование слабого порядка для функций сравнения.
Типичные операторы сравнения возвращают информацию о трех состояниях <, =, >
Сначала преобразуйте строку в число, а затем сравните их (если ваши числа находятся в диапазоне 1–10^6)! Когда вы сравниваете строковый символ, сравниваются не числа, а числа ASCII. также, если вам нужно сравнить числа ascii, вы можете выполнить преобразование для этого одного символа.
Если ваше задание или упражнение заключается в реализации собственных функций bignum, возможно, вам действительно захочется освежить в памяти математику в начальной и средней школе. Например, как вы выполняли обычную арифметику (сложение, деление и т. д.), используя карандаш и бумагу. Многое из этого можно более или менее точно так же перевести в компьютерную программу. Для сравнения сделайте вычитание: Результат отрицательный? Положительный? Нуль? Это скажет вам, является ли первое значение меньше, больше или равно второму значению. Так что за меньший заказ это return subtract(left, right) < 0.
Комментарии Jarod42 и некоторых чуваков-программистов по поводу строгого слабого порядка дали ответ, спасибо! Проблема заключалась в том, что цифра игнорировалась, когда она была меньше.
Ответы 3
Это код:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // std::sort
bool compare_numstrings(std::string &left, std::string &right) {
left = left.substr(left.find_first_not_of('0'));
right = right.substr(right.find_first_not_of('0'));
if (left.size() < right.size()) {
return true;}
else if (left.size() > right.size()) {
return false;}
else {
for (long int i = 0; i < left.size(); i++) {
if (left[i] < right[i]) {
return true;}
else if (left[i] > right[i]) {
return false;}}
return true;} // return true when numbers are equal.
};
int main() {
std::vector<std::string> v_numstrings = {"08221014", "00000013141234", "00013141235", "013141236", "008221014", "01048576", "001048575", "004414201", "04414202"};
std::sort(v_numstrings.begin(), v_numstrings.end(), compare_numstrings);
for (std::string numstring: v_numstrings) {
std::cout << numstring << "\n";}
return 0;
}
«Без использования какой-либо странной библиотеки»? std::sort находится в той же библиотеке, что и std::vector и std::string, то есть в стандартной библиотеке.
Почему вы считаете, что пузырьковой сортировки «более чем достаточно»? И почему ваш ответ в основном сосредоточен на замене той части, которая уже сработала (std::sort), а не только той части, которая не сработала (предикат)?
Стандартная библиотека НЕ странная, на самом деле НАСТОЯТЕЛЬНО рекомендуется использовать ее, когда есть возможность. Написание собственного метода сортировки, когда std::sort может выполнять только эту работу, потребует написания и тестирования большего количества кода.
Без использования какой-либо странной библиотеки, это правильный путь. Честно говоря, этот код не пройдет проверку кода почти в каждом магазине C++ — программист, работающий над вашим кодом, скорее всего, просто выбросит его и заставит std::sort работать с ним. правильный предикат. std::sort всегда работает, если задана правильная функция предиката.
Токсичные люди прибыли в рекордно короткие сроки, братан.
Нет, мы предупреждаем других читателей, что ваш код — это не то, что написали бы опытные разработчики. Это не токсично, это похоже на то, как учителя пытаются вас чему-то научить :) Обратите внимание: вы передаете свои данные по значению в функцию сортировки, это приводит к ненужному копированию (что является проблемой для больших строк).
Ребята, код работает как задумано, я только что добавил код для удаления возможных нулей в начале. Если вы хотите использовать сортировку, это нормально, мне это просто не нравится. важно то, что код дает точные результаты, и это действительно так.
Я ценю усилия, которые вы приложили к этому. Однако, по нашему мнению, это не тот тип кодирования, который другие люди должны копировать или использовать в качестве образца.
Это эквивалентно тому, что я захожу в раздел Python и отвечаю на вопрос, написав цикл вместо использования понимания списка или множества, и, кроме того, называю последнее «странным». Программисты Python сказали бы что-нибудь, если бы я дал в качестве ответа цикл for, точно так же, как программисты C++ говорят вам что-то о том, что вы должны написать свой собственный вид, когда std::sort существует. Это не токсично.
Угадай, что. Я нуб. Для меня сортировка странная, я не умею ею пользоваться и мне не нужно ею пользоваться. Моя цель — заставить эту штуку работать точно, и она работает. Я знаю кое-что о Python. Понимание списков является альтернативой циклам for, у которого есть свои плюсы и минусы, и использование цикла for вместо понимания списка неплохо, если код работает так, как задумано, поэтому никто не должен даже жаловаться на это. Разве этот сайт не о том, как добиться цели? Он не просил необычного или профессионального решения. ему нужно только решение, и я его предлагаю
Раздел комментариев предназначен для комментариев, и другие прокомментировали. Если вы публикуете ответ, разумно принять комментарии о том, как можно улучшить ответ или почему был использован использованный подход — это не токсично. Кроме того, когда вы публикуете ответ, он предназначен не только для исходного автора, но и для других, кто может выполнять поиск и встретить тот же вопрос StackOverflow.
Блин, я только что научился пользоваться сортировкой, и наконец-то сделал это с помощью сортировки.
Вам нужно удалить все ведущие нули. Кроме того, вы не сравниваете строки, а сравниваете «большие числа», поэтому почти всегда имеет смысл написать класс, который поможет вам поддерживать некоторые инварианты (например, отсутствие ведущих 0 и only digits).
Объединив это с оператором космического корабля С++ 20, который может сравнивать меньшее/равное/большее, вы можете сделать это следующим образом:
Живая демонстрация: https://onlinegdb.com/zLYAt2MTa
И если порядок сортировки доступен, вы можете использовать std::sort
#include <string>
#include <stdexcept>
#include <iostream>
#include <cassert>
#include <algorithm>
#include <vector>
class big_number_t
{
public:
explicit big_number_t(const std::string_view sv)
{
if (sv.size() == 0ul) throw std::invalid_argument{ "input must contain at least one digit" };
requires_all_digits(sv);
// strip leading zeros
auto pos = sv.find_first_not_of('0');
if ( pos == std::string_view::npos )
{
m_value = "0";
}
else
{
m_value = sv.substr(pos);
}
}
// Use C++20 spaceship operator if you can
// https://en.cppreference.com/w/cpp/language/default_comparisons
auto operator<=>(const big_number_t& rhs) const
{
auto result = m_value.size() <=> rhs.m_value.size();
if (result == std::strong_ordering::equal)
{
for (std::size_t pos{ 0ul }; pos < m_value.size(); ++pos)
{
result = m_value[pos] <=> rhs.m_value[pos];
if (result != std::strong_ordering::equal) break;
}
}
return result;
}
bool operator==(const big_number_t& rhs) const
{
return m_value == rhs.m_value;
}
const std::string& str() const noexcept
{
return m_value;
}
private:
constexpr void requires_all_digits(const std::string_view sv)
{
for (const auto c : sv)
{
if ((c < '0') || (c > '9'))
{
throw std::invalid_argument{ "non digit character found" };
}
}
}
std::string m_value;
};
int main()
{
big_number_t zero1{ "0" };
big_number_t zero2{ "000" };
assert(zero1 == zero2);
big_number_t v1{ "12341349801439486140986" };
big_number_t v2{ "0000056732859713359871" };
big_number_t v3{ "92801439486140986" };
big_number_t v4{ "56732859713359871" };
big_number_t v5{ "92801439486140986" };
big_number_t v6{ "92801439486140985" };
big_number_t v7{ "92801439486140985" };
big_number_t v8{ "92801439486140985" };
assert(v1 > v2);
assert(v3 > v4);
assert(v5 > v6);
assert(v7 == v8);
std::vector<big_number_t> numbers{
big_number_t{ "12341349801439486140986" },
big_number_t{ "0000056732859713359871" },
big_number_t{ "92801439486140986" },
big_number_t{ "56732859713359871" },
big_number_t{ "92801439486140986" },
big_number_t{ "92801439486140985" }
};
std::sort(numbers.begin(), numbers.end());
for (const auto& number : numbers)
{
std::cout << number.str() << "\n";
}
}
@Jarod42 Спасибо, ты прав (я просто поторопился)
Код исправлен для ввода всех нулей.
Вы не возвращаете true, когда видите большую цифру в right, поэтому сравнивается более поздняя меньшая цифра и возвращается false. Н.б. вы не соответствуете требованиям для std::sort, так как возврат true при сравнении объектов недействителен, вам нужно строго меньше.
bool comp(const string &left, const string &right)
{
if (left.size() < right.size())
{
return true;
}
if (left.size() > right.size())
{
return false;
}
for (unsigned long int i = 0; i < left.size(); i++)
{
if (left[i] > (right[i]))
{
// left is bigger
return false;
}
if (left[i] < right[i])
{
// right is bigger
return true;
}
}
// left is equal
return false;
}
Однако есть гораздо более простой способ выполнить это сравнение: составить std::tuple каждого объекта, который вы хотите сравнить, в порядке приоритета.
bool comp(const string &left, const string &right)
{
return std::forward_as_tuple(left.size(), left) < std::forward_as_tuple(right.size(), right);
}
Используйте отладчик, чтобы понять, почему он решил, что 82 < 44.