Custom string sort gives segmentation fault

Question

I am solving a problem in which you are given a bunch of numbers in string format and you have to concatenate them in such a way that the result is the maximum number possible. E.g:

Input: 6 61 68

Output: 68661

So I am using a custom sorter with std::sort to sort the strings and I am getting weird, random segmentation faults when accessing string using .at()

I am using this command to run the code

g++ -Wextra -Wall -pipe -O2 -std=c++14 largest_number_problem.cpp -lm && ./a.out

output of g++ --version

g++ (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0

The output is:

terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string::at: __n (which is 0) >= this->size() (which is 0)
Aborted (core dumped)

Note: There is no string whose length is zero in the array. Take a look at the code.

Sometimes I get: can't access memory at location 0x0.

My Code:

#include "bits/stdc++.h"
using namespace std;

bool sortNos(const string &s1, const string &s2)
{
    int i1 = 0, i2 = 0;
    int n1 = s1.size(), n2 = s2.size();
    bool result = 0;
    
    while (i1 < n1 && i2 < n2)
    {
        if (s1.at(i1) != s2.at(i2))
        {
            result = s1.at(i1) > s2.at(i2);
            return result;
        }
        i1++;
        i2++;
    }
    if (i1 == n1 && i2 == n2)
    {
        // strings are equal
        return 1;
    }
    if (i1 == n1)
    {
        result = s1.at(0) > s2.at(i2);
    }
    else if (i2 == n2)
    {
        result = s2.at(0) < s1.at(i1);
    }
    return result;
}
string largest_number(vector<string> &a)
{
    sort(a.begin(), a.end(), &sortNos);
    std::stringstream ret;
    for (size_t i = 0; i < a.size(); i++)
    {
        ret << a[i];
    }
    string result;
    ret >> result;
    return result;
}
void test()
{
    vector<string> a;
    a.push_back("2");
    a.push_back("8");
    a.push_back("2");
    a.push_back("3");
    a.push_back("6");
    a.push_back("4");
    a.push_back("1");
    a.push_back("1");
    a.push_back("10");
    a.push_back("6");
    a.push_back("3");
    a.push_back("3");
    a.push_back("6");
    a.push_back("1");
    a.push_back("3");
    a.push_back("8");
    a.push_back("4");
    a.push_back("6");
    a.push_back("1");
    a.push_back("10");
    a.push_back("8");
    a.push_back("4");
    a.push_back("10");
    a.push_back("4");
    a.push_back("1");
    a.push_back("3");
    a.push_back("2");
    a.push_back("3");
    a.push_back("2");
    a.push_back("6");
    a.push_back("1");
    a.push_back("5");
    a.push_back("2");
    a.push_back("9");
    a.push_back("8");
    a.push_back("5");
    a.push_back("10");
    a.push_back("8");
    a.push_back("7");
    a.push_back("9");
    a.push_back("6");
    a.push_back("4");
    a.push_back("2");
    a.push_back("6");
    a.push_back("3");
    a.push_back("8");
    a.push_back("8");
    a.push_back("9");
    a.push_back("8");
    a.push_back("2");
    a.push_back("9");
    a.push_back("10");
    a.push_back("3");
    a.push_back("10");
    a.push_back("7");
    a.push_back("5");
    a.push_back("7");
    a.push_back("1");
    a.push_back("7");
    a.push_back("5");
    a.push_back("1");
    a.push_back("4");
    a.push_back("7");
    a.push_back("6");
    a.push_back("1");
    a.push_back("10");
    a.push_back("5");
    a.push_back("4");
    a.push_back("8");
    a.push_back("4");
    a.push_back("2");
    a.push_back("7");
    a.push_back("8");
    a.push_back("1");
    a.push_back("1");
    a.push_back("7");
    a.push_back("4");
    a.push_back("1");
    a.push_back("1");
    a.push_back("9");
    a.push_back("8");
    a.push_back("6");
    a.push_back("5");
    a.push_back("9");
    a.push_back("9");
    a.push_back("3");
    a.push_back("7");
    a.push_back("6");
    a.push_back("3");
    a.push_back("10");
    a.push_back("8");
    a.push_back("10");
    a.push_back("7");
    a.push_back("2");
    a.push_back("5");
    a.push_back("1");
    a.push_back("1");
    a.push_back("9");
    a.push_back("9");
    a.push_back("5");
    largest_number(a);
}
int main()
{
    test();
    return 0;
}

Pro tip: [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — πάντα ῥεῖ, Sep 25 '20 at 09:36
`std::sort` wants a [strict weak ordering](https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings). In particular, two elements can't be both be ordered before the other. — molbdnilo, Sep 25 '20 at 09:36
The best way to ensure that your program works with arbitrary inputs is to use small and systematic test cases, not huge random ones. — molbdnilo, Sep 25 '20 at 09:40
use `vector a = { "2", "8", ...};` to cut your number of lines by half — 463035818_is_not_an_ai, Sep 25 '20 at 09:46
read [Why should I not `#include `?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) and [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). The first line makes your code non-standard non-portable for no good reason. You prevent others to compile your code, thats the main effect. Why do you do that? — 463035818_is_not_an_ai, Sep 25 '20 at 09:51
@idclev463035818 thank you for your suggestions. Since this is in the realm of competitive programming, it is preferred to do it that way in order to save time. — Murtaza Raja, Sep 25 '20 at 11:39
you are not saving any time by this two lines, though in the realm of competitive programming such myths are rather common — 463035818_is_not_an_ai, Sep 25 '20 at 11:44

score 2 · Accepted Answer · answered Sep 25 '20 at 09:54

As far as I can see the main problem is this piece of code:

if (i1 == n1 && i2 == n2)
{
    // strings are equal
    return 1;
}

which should be

if (i1 == n1 && i2 == n2)
{
    // strings are equal
    return false;
}

The first version implies that two identical strings should be sorted before each other, i.e. you couldn't decide which comes first. You violated the requirements for the comparator and experience undefined behaviour. One specific requirement is that for any a and b when sortNos(a, b) == true then sortNos(b, a) must be false. But this doesn't hold if a == b.

It should worik when you return 0 (or better false) instead of 1.

as @molbdnilo pointed out, I tried to fix the code the same way as you've mentioned. — Murtaza Raja, Sep 25 '20 at 11:37

Custom string sort gives segmentation fault

1 Answers1