I want to sort a vector of strings representing very large (10**6 digits) in ascending order in C++. I am trying to use a custom comparitor, but the sort is failing when comparing numbers of the same number of digits, eg. failing to re-arrange 82 and 44.
Here is a small example:
#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;
}
This outputs:
2
82
44
131
where the numbers with different digits are fine, but those with two digits are not sorted. What is the issue, please?
You aren't returning true when you see a larger digit in right, so the later smaller digit is compared and false is returned. N.b. you are not meeting the requirements for std::sort, as returning true when things compare equal is invalid, you need a strict less than.
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;
}
However there is a much easier way of doing this comparison, which is to construct a std::tuple of each thing you want to compare, in the order of priority
bool comp(const string &left, const string &right)
{
return std::forward_as_tuple(left.size(), left) < std::forward_as_tuple(right.size(), right);
}