CODEWITHSUNDEEP
c++sorting
Jason Huh
Jason Huh

Reputation: 39

cpp vector sort runtime error

#include <stdio.h>
#include <algorithm>
#include <string>
#include <vector>
#include <iostream>

using namespace std;
int max(int a, int b) {
    return a < b ? b : a;
}
bool comp(const string &l, const string &r) {
    for (int i = 0; i < max(l.length(), r.length()); i++) {
        if (i >= l.length()) return false;
        if (i >= r.length()) return true;
        if (l[i] < r[i]) return l[i] < r[i];
    }
    return true;
}

int main(void) {
    int N; scanf("%d", &N);
    vector<string> v;
    for (int i = 0; i < N; i++) {
        string s; cin >> s;
        v.push_back(s);
    }
    sort(v.begin(), v.end(), comp);
    for (const string& s : v) {
        cout << s;
    }
    cout << endl;
}

In Educational Codeforces Round 9 held on yesterday, I couldn't solve the problem http://codeforces.com/contest/632/problem/C using sort with user-defined function.

I used stl vector containing string and it seems to work on some test cases, but it occurs runtime-error on following testcase.

100 abccaacaacacabbbcbbabcccccacabbaccbcacabcbbbaca bbbaccbbccbbbcacaabbcccaabcbbcbbbacaacabc cccabccaaabcaccabccbcccbbaacaaccbb cccabccaaabcaccabccbcccbbaacaaccbbcb cccabccaaabcaccabccbcccbbaacaaccbb cccabccaaabcaccabccbcccbbaacaaccbbbcca abbbcbbbbbbcccccbcbbb bbbaccbbccbbbcacaabbcccaabcbbcbbbacaacabcb abbcacbcabacccbcbabaabcaabcabacbbbbbca cccabccaaabcaccabccbcccbbaacaaccbbcaa cbcbbaccacbcababbccaacabacbcabbaccbcbcbcabbc acbbbbbbbcabbcbcaccccbcbaacccaccabcbaac bacccabacbbaaa

I can't view the full test input due to codeforces' policy. How do I defeat this situation?

Upvotes: 0

Views: 1523

Answers (2)

VolAnd
VolAnd

Reputation: 6407

Try to use standard comparison method (not your own bool comp(const string &l, const string &r)), e.g.:

#include <algorithm>
#include <string>
#include <vector>
#include <iostream>
#include <functional>

using namespace std;

int main(void) {
    int N; 
    cin >> N;
    vector<string> v;
    for (int i = 0; i < N; i++) {
        string s; 
        cin >> s;
        v.push_back(s);
    }
    std::sort (v.begin(), v.end(), std::greater<string>());
                                // or   std::less<string>()
    for (const string& s : v) {
        cout << s << endl;
    }
    cout << endl;
}

Or change your function to simple one, like:

bool comp(const string &l, const string &r) {
    return l < r;
}

Update:

But if you really want to use your own comp function, you should understand that reason why exception invalid operator < occurs because your comparison function (comp) returns true when both relevant fields are equal (this not correct behavior for "less than" required for sort).

And at the end, small tip (it is hardly a solution) - try this for your code:

bool comp(const string &l, const string &r) {
    for (int i = 0; i < max(l.length(), r.length()); i++) {
        if (i >= l.length()) return false;
        if (i >= r.length()) return true;
        if (l[i] != r[i]) return l[i] < r[i];
    }
    return true;
}

Upvotes: 1

Jim Lewis
Jim Lewis

Reputation: 45045

Your comp() predicate doesn't handle the case where l[i] > r[i]. So it returns 1 when comparing "foo" and "boo", and also returns 1 when comparing "boo" and "foo". Therefore, it fails to implement a strict weak ordering (i.e., fails to behave like <=) , and the results of passing it to std::sort() are undefined.

Upvotes: 3

Related Questions