C++ program not working for large input (logic_error, _M_construct null not valid)

Question

I'm trying to implement the maximizing salary problem. Like if we are given two numbers 2 and 21 then the resultant number should be 221 not 212. I implemented the code and it works very well for small inputs. The code uses C++ std::sort with a simple comparator function. For big inputs like for 100 it fails and gives following error.

stderr:
terminate called after throwing an instance of 'std::logic_error'
  what():  basic_string::_M_construct null not valid

Here's my code:

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

using std::vector;
using std::string;
using std::max;


bool comp(const string &a, const string &b) {
  string combo1 = a+b;
  string combo2 = b+a;
  return combo1>=combo2;
}

string largest_number(vector<string> a) {
  std::sort(a.begin(), a.end(), comp);
  string result = "";
  for (int i=0; i< a.size(); i++) {
    result = result + a[i];
  }
  return result;
}

int main() {
  int n;
  std::cin >> n;
  vector<string> a(n);
  for (size_t i = 0; i < a.size(); i++) {
    std::cin >> a[i];
  }
  std::cout << largest_number(a);
}

For the following inputs it gives error.

100

2 8 2 3 6 4 1 1 10 6 3 3 6 1 3 8 4 6 1 10 8 4 10 4 1 3 2 3 2 6 1 5 2 9 8 5 10 8 7 9 6 4 2 6 3 8 8 9 8 2 9 10 3 10 7 5 7 1 7 5 1 4 7 6 1 10 5 4 8 4 2 7 8 1 1 7 4 1 1 9 8 6 5 9 9 3 7 6 3 10 8 10 7 2 5 1 1 9 9 5

How do I solve this issue? I read some probable solutions and it was something about NULL pointers which I couldn't understand.

Your comparator function is wrong, see the [requirements](https://en.cppreference.com/w/cpp/named_req/Compare). For instance, `comp("a","a")` is `true`, which does not define _strict weak ordering_. — Daniel Langr, Jan 03 '21 at 12:12
Yes! right! This is something which I did wrong. Didn't knew. These online tutorials don't teach about all this, they give only syntax and example. To have complete insight one should always read the documentation. You please post your answer I'll give it a green tick. — raviujjwal, Jan 03 '21 at 12:23

score 3 · Accepted Answer · answered Jan 03 '21 at 12:41

Your comparator function does not meet the requirements. Namely, it does not define strict weak ordering. See the documentation for more details.

For example, comp(s,s) must be false, while in your code, calling comp with the same argument always yields true. Basically, you may not use >= or <= when defining a comparator.

Relatdet question: Why will std::sort crash if the comparison function is not as operator <?

C++ program not working for large input (logic_error, _M_construct null not valid)

1 Answers1