C++. What could cause a runtime error here? Radix sort

Question

Task: To write a program that inputs key-value pairs, sorts them in ascending key by the specified sorting algorithm in linear time, and outputs the sorted sequence. Radix sort.

Key type: dates in the format DD.MM.YYYY, for example, 1.1.1, 1.9.2009, 01.09.2009, 31.12.2009.

Value type: strings of fixed length 64 characters, strings of smaller length may occur in the input data, in this case the string is padded to 64 characters with null symbols, which are not displayed.

Input format: Each non-empty line of the input file contains a key-value pair, in which the key is specified according to the task, followed by a tab character and the corresponding value.

Output format: The output consists of the same strings as the input, except for empty strings and order.

Example:
Input
1.1.1 n399tann9nnt3ttnaaan9nann93na9t3a3t9999na3aan9antt3tn93aat3naatt
01.02.2008 n399tann9nnt3ttnaaan9nann93na9t3a3t9999na3aan9antt3tn93aat3naat
1.1.1 n399tann9nnt3ttnaaan9nann93na9t3a3t9999na3aan9antt3tn93aat3naa
01.02.2008 n399tann9nnt3ttnaaan9nann93na9t3a3t9999na3aan9antt3tn93aat3na

Output
1.1.1 n399tann9nnt3ttnaaan9nann93na9t3a3t9999na3aan9antt3tn93aat3naatt
1.1.1 n399tann9nnt3ttnaaan9nann93na9t3a3t9999na3aan9antt3tn93aat3naa
01.02.2008 n399tann9nnt3ttnaaan9nann93na9t3a3t9999na3aan9antt3tn93aat3naat
01.02.2008 n399tann9nnt3ttnaaan9nann93na9t3a3t9999na3aan9antt3tn93aat3na

CODE:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

pair<int, string> ParseLine(const string& line)
{
    int day;
    int month;
    int year;
    sscanf(line.c_str(), "%d.%d.%d", &day, &month, &year);
    int key = day + month * 50 + year * 1000;
    return make_pair(key, line.c_str());
}

int GetMax(vector < pair<int,string> > v, int size)
{
    int max = v[0].first;
    for (int i = 1; i < size; i++)
        if (v[i].first > max)
            max = v[i].first;
    return max;
}

void CountSort(vector < pair<int,string> >& v, int size, int exp)
{
    pair <int, string> output[size]; // output array
    int i, count[10] = { 0 };
  
    // Store count of occurrences in count[]
    for (i = 0; i < size; i++){
        int digit = (v[i].first / exp) % 10;
        count[digit]++;
    }
    

    // Change count[i] so that count[i] now contains actual
    //  position of this digit in output[]
    for (i = 1; i < 10; i++){
        count[i] += count[i - 1];
    }

    
    // Build the output array
    for (i = size - 1; i >= 0; i--) {
        int digit = v[i].first / exp % 10;
        output[count[digit] - 1] = v[i];
        count[digit]--;
    }
  
    // Copy the output array to v[], so that v[] now
    // contains sorted numbers according to the current digit
    for (i = 0; i < size; i++){
        v[i].first = output[i].first;
        v[i].second = output[i].second;
    }

}
  

void RadixSort(vector < pair<int,string> >& v, int size)
{
    // Find the maximum number to know number of digits
    int max = GetMax(v, size);
    // Do counting sort for every digit. Note that instead
    // of passing digit number, exp is passed. exp is 10^i
    // where i is current digit number
    for (int exp = 1; max / exp > 0; exp *= 10)
        CountSort(v, size, exp);
}

void PrintVec(vector < pair<int,string> >& v){
    for (int i = 0; i < v.size(); ++i){
        cout << v[i].second << endl;    
    }
}

int main() {
    
    vector <string> lines;
    string line;
    while (getline(cin, line))
    {
        line.shrink_to_fit();
        if (!line.empty())
            lines.push_back(line);
    }
    int size = lines.size();
    vector < pair<int,string> > v;
    for (size_t i = 0; i < size; i++)
    {
        v.push_back(ParseLine(lines[i]));
    }
    RadixSort(v, size);
    PrintVec(v);
}

PROBLEM: the code passes first two tests, but causes a run-time error on the third test. What could be the reason? How can I better this code? The tests can't be accessed, so I don't know what's in the 3rd test.

There is no info what type of runtime error it is

Replace your `vector` accesses using `[ ]` with `at()`. Then see if a `std::out_of_range` exception is thrown. If so, then that means that you are going out-of-bounds. — PaulMcKenzie, Aug 04 '22 at 14:48
https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems#25385174 — Jesper Juhl, Aug 04 '22 at 14:48
`pair output[size]; // output array` -- Second, this is not valid C++. Arrays in C++ must have their size denoted by a compile-time expression, not a runtime value. You are already using `std::vector`, so why did you not use it here? `std::vector> output(size);`. Now you can use `at()` to check `output` to ensure you are not going out of bounds. This is why using websites that give out random puzzle questions to learn proper C++ is not a good way to actually learn C++. — PaulMcKenzie, Aug 04 '22 at 14:49
What runtime error did you get? Usually in a debugging environment like Visual Studio you get a very specific error like stack overflow / divide by zero / access violation ... and not just a nonspecific runtime error. — drescherjm, Aug 04 '22 at 14:56
@drescherjm There is no info what runtime error I get, unfortunately — Mahmud, Aug 04 '22 at 14:58
@drescherjm "terminate called after throwing an instance of 'std::out_of_range' what(): vector::_M_range_check: __n (which is 0) >= this->size() (which is 0)" — Mahmud, Aug 08 '22 at 12:59
Means your vector is empty but you are trying to access nonexistent elements in the vector. With an IDE like Visual Studio Community it will stop on the line causing the error and let you change your "Stack Frame" to your code to see the exact line of the error and look at your variables at that point. — drescherjm, Aug 08 '22 at 13:28
@drescherjm thank you, brother, it helped. You are a c++ monster — Mahmud, Aug 08 '22 at 14:35

score 0 · Answer 1 · answered Aug 04 '22 at 14:58

0

Change

pair<int, string> output[size];

to

vector<pair<int, string>> output(size);

and this code runs for me -- well, with the input hardcoded in. Variable length arrays are not part of standard C++. See here.

answered Aug 04 '22 at 14:58

jwezorek

8,592
1
29
46

C++. What could cause a runtime error here? Radix sort

1 Answers1