Program terminated with signal SIGABRT, Aborted. terminate called after throwing an instance of 'std::out_of_range'

Question

The question is : Consider an array of numeric strings where each string is a positive number with anywhere from 1 to 10^6 digits. Sort the array's elements in non-decreasing, or ascending order of their integer values and return the sorted array.

vector<string> bigSorting(vector<string> unsorted) {
    for(int i=0 ; i<unsorted.size() ; i++){
        for(int j=0 ; j<unsorted.size()-1; j++){
            long int a = stol(unsorted[j]);
            long int b = stol(unsorted[j+1]);
            if(a > b){
                string x = unsorted[j];
                unsorted[j] = unsorted[j+1];
                unsorted[j+1] = x;
            }
        }
    }
    return unsorted;
}

I made the above function for the question and it gave an error :

terminate called after throwing an instance of 'std::out_of_range'
  what():  stol
Reading symbols from Solution...done.
[New LWP 450]
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
Core was generated by `./Solution'.
Program terminated with signal SIGABRT, Aborted.
#0  __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:50
To enable execution of this file add
    add-auto-load-safe-path /usr/local/lib64/libstdc++.so.6.0.25-gdb.py
line to your configuration file "//.gdbinit".
To completely disable this security protection add
    set auto-load safe-path /
line to your configuration file "//.gdbinit".
For more information about this security protection see the
"Auto-loading safe path" section in the GDB manual.  E.g., run from the shell:
    info "(gdb)Auto-loading safe path"

What is the meaning of this error code and how do I fix it?

1 to 10^6 digits, stol throws std::out_of_range. How many digits does `long` support? 20-ish on 64-bit. You cannot use stol for this. — , Jan 07 '21 at 15:57
Moreover, your sorting with complexity O(n^2) will likely fail for large problem sizes (=n) — Walter, Jan 07 '21 at 16:03
You can simply use `unsorted[i] < unsorted[j]`, which uses lexicographical comparison, provided, your strings are consistent (i.e. no intermixing 0042 and 42 for the same number) — Walter, Jan 07 '21 at 16:08
To clarify: 10 to the 6th is 1,000,000, which, at 7 digits, will fit in a `long`, but the input is up to 1,000,000 **digits** in length, not up to the number 1,000,000. — user4581301, Jan 07 '21 at 16:11
Pure string comparison will do 1234 < 234 < 88 < 9 which may not be what you want. The task appears to ask you to implement numeric-like comparison on strings. — , Jan 07 '21 at 16:11
Why not simply use `std::sort` with the appropriate lambda function? That bubble sort you wrote should have been the last resort, and would probably fail anyway due to timeout issues with a large size. — PaulMcKenzie, Jan 07 '21 at 16:19
@PaulMcKenzie That was my first approach but I couldn't think of an appropriate lambda function. — Samit Kapoor, Jan 07 '21 at 16:24
@SamitKapoor `return stol(string1) < stol(string2);`. And if you had no idea of `std::sort`, [this link shows various sorting algorithm implementation, written in modern C++](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c). If this question is from one of those online competition websites, don't go armed with a naive bubble-sort if you are asked to sort the data. — PaulMcKenzie, Jan 07 '21 at 16:25
@PaulMcKenzie we do know the input has numbers up to 1 million digits in length, so any lambda involving stol is doomed to fail — , Jan 07 '21 at 16:41
@SamitKapoor you have two strings with numbers in them, how would you compare them? If their length differs, decide immediately based on that, otherwise go digit by digit until you find a difference. — , Jan 07 '21 at 16:44
Yes, I see that the lambda needs to consist of two steps -- string size, and then digit comparison. — PaulMcKenzie, Jan 07 '21 at 16:47

score 0 · Accepted Answer · answered Jan 07 '21 at 18:38

As pointed out in the comments, your error originates form your attempt to read a number with many digits (up to a million) into a 64bit number, which can hold all numbers up to 1<<64=18446744073709551616, i.e. no numbers with more than 20 digits.

Hence you must find another way to compare those strings. The question is not very clear about leading zeros, but let us assume that the numbers are represented without leading zeros. Then the std::strings, representing the numbers, can be compared by their size() and, if that is equal, lexicographically, which is implemented by operator< between std::strings, i.e.

std::vector<std::string> bigSorting(std::vector<std::string> unsorted)
{
    std::sort(unsorted.begin(), unsorted.end(), 
        [](std::string const&x, std::string const&y) {
            return x.size()==y.size()? x<y : x.size() < y.size();
        });
    return unsorted;
}

If there are leading zeros, you must adapt your method accordingly.

Program terminated with signal SIGABRT, Aborted. terminate called after throwing an instance of 'std::out_of_range'

1 Answers1