Sorting c++ vector

Question

I want to sort a string vector for an exercise. These string has only digits from 0 to 9 like [ 10 2 1 9 91 ] and I want to sort as [ 9 91 2 1 10 ] to reach the largest number ( 9912110 ). I did the following code using the sort function

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

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

bool compare(string i1, string i2) 
{ 
     int a, b;
     int i = 0;
     int min_len = (i1.length() > i2.length()) ? i2.length(): i1.length();
     while(i < min_len) {
          a = (int) (i1.at(i) - '0');
          b = (int) (i2.at(i) - '0');
          if (a != b)
             break;
          i++;
     }
     if (a > b)
        return true; 
     if (a < b)
        return false; 

     if (i1.length() > i2.length())
        return false;

     return true;
} 

int main() {
    int n;
    std::cin >> n;
    vector<string> a(n);
    for (size_t i = 0; i < a.size(); i++) {
        std::cin >> a[i];
    }
    sort(a.begin(), a.end(), compare);
 }

The problem is that when I execute with arguments:

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

gives me the following error:

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

But if I execute with 99 and I delete the last number it works fine. Also gives the same error if I try with more than 100 (like 101 or 102 ...). I suppose that the error is in the compare function.

Edited :

 bool compare(const std::string& i1, const std::string& i2) 
 { 
      int i = 0;
      int min_len = (i1.length() > i2.length()) ? i2.length(): i1.length();
      while (i < min_len) {
            int a = (int) (i1.at(i) - '0');
            int b = (int) (i2.at(i) - '0');
            if (a > b)
               return true; 
            if (a < b)
               return false; 
            i++;
      }

      return (i1.length() < i2.length());
 }

Tip: Get in the habit of declaring string arguments as `const std::string&` and not `string`. Use `const`, use references, and [don't put `using namespace std`](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). — tadman, Jan 09 '19 at 16:23
I think just sorting them lexicographically in descending order should be enough — Slava, Jan 09 '19 at 16:24
`a` and `b` are potentially uninitialized when you use them for comparison. Also, please get rid of the input statements and instead, hard-code the data into the program. There is no need to burden us (and yourself) in repeatedly entering the data over and over again when testing. — PaulMcKenzie, Jan 09 '19 at 16:24
If two strings are equal your comparison function returns true, if should return false in this case. `compare` should implement a 'less than' operation and given equal arguments should always return false. — john, Jan 09 '19 at 16:25
Your compare is nothing but a greater operation, can can be shortened to `return a > b`. — SergeyA, Jan 09 '19 at 16:29
@SergeyA I don't want [10 9 1] I want [9 1 10] because 9110 is grater than 1091 — gagiuntoli, Jan 09 '19 at 16:33
@Slava Sorry, `using std::string` but it's the same problem. — tadman, Jan 09 '19 at 16:39
@GG1991 [For the sake of anyone testing your code, a non-input routine version](http://coliru.stacked-crooked.com/a/061b9d01e927a089). — PaulMcKenzie, Jan 09 '19 at 16:39
You don't need to subtract '0' to get a and b - the result of comparison remains the same, no matter if you add some offset to both - as long as offset is the same in both cases, of course... — Aconcagua, Jan 09 '19 at 16:39
@GG1991 that would work as you expect, since arguments are string. — SergeyA, Jan 09 '19 at 16:39
@GG1991 FYI, your code produces an `assert` error on Visual Studio due to an invalid comparison operator. VS checks for mistakes such as the one you're making in `compare`. — PaulMcKenzie, Jan 09 '19 at 16:42
@SergeyA Well it wouldn't, because "1" < "10", so you get 9101. — jrok, Jan 09 '19 at 16:43
@tadman no it is not the same, bringing whole namespace is a disaster, bringing only some names from it should be fine if you know what you are doing. — Slava, Jan 09 '19 at 19:00
@Slava I've seen a ton of C++ questions here and this is the first time I've seen someone literally `using std::string`. In this rare case my boilerplate advisory doesn't necessarily apply, you're right there. — tadman, Jan 09 '19 at 19:02

score 7 · Accepted Answer · answered Jan 09 '19 at 16:30

7

The comparison function for std::sort should always return false given equal arguments. But your function returns true. Try the following modification

bool compare(string i1, string i2) 
{ 
     ...

     if (a > b)
        return true; 
     if (a < b)
        return false; 

     return i1.length() < i2.length();
}

I'm guessing that what is happening is that on your platform std::sort chosens a different algorithm when the size of the sequence to sort is >= 100. And for this different algorithm it is crucial that the requirements of the comparison function are met.

answered Jan 09 '19 at 16:30

john

85,011
4
57
81

You need to be more specific than that. You should speak in terms of requirements to compare function. – SergeyA Jan 09 '19 at 16:32
Good catch with the comparator, and I wonder why someone downvoted you. – jrok Jan 09 '19 at 16:33
@SergeyA I mentioned the requirement that is crucial, that for equal arguments the return should be false. Strict weak ordering is not something I readily understand. – john Jan 09 '19 at 16:34
Thank you John you are right. This program is working properly now and I agree on your intuition that `sort` function changes the algorithm for `n>=100`. – gagiuntoli Jan 09 '19 at 16:37
@john it is called strict total ordering, and you can read about it here: https://en.cppreference.com/w/cpp/named_req/Compare – SergeyA Jan 09 '19 at 16:38
@SergeyA the link you posted calls it strict weak ordering. My confusion about it is in thinking of a realistic example where it is different from a total ordering – john Jan 09 '19 at 16:45
`Note: comp induces a strict total ordering on the equivalence classes determined by equiv` – SergeyA Jan 09 '19 at 16:48
@SergeyA So a strict weak ordering is simply an ordering where some elements are allowed to be equal, but unequal elements have a strict total ordering? That's so easy, I feel a bit stupid for not having realised it before. I assumed it was something more complex than that. Never been explained to me in simple language I guess. – john Jan 09 '19 at 16:53

score 2 · Answer 2 · answered Jan 09 '19 at 17:20

While the answer to the actual question is already given, your comparison algorithm is not suitable to get the desired result!

Consider the following examples:

Case 1: [99, 991] – you need to sort the shorter string first to get 99991 instead of 99199.

Case 2: [91, 919] – you need to sort the longer first to get 91991 instead of 91919.

While lexicographical comparison (which is what you implemented) is fine to sort strings on their common length, the criterion 'length', if strings compare equal on their common length, cannot be used to decide which string is to be sorted first!

You could, though, do the following:

std::sort
(
    a.begin(), a.end(),
    [](std::string x, std::string y)
    {
        std::string xy = x + y;
        std::string yx = y + x;
        return xy > yx;
    }
);

i. e. sort the one string first that results, if concatenated with the other one, in the larger value.

Hi, @Aconcagua this is the right solution for the problem. I would put this the right solution but the original question was about the error of the sort function. In fact the solution that I wrote was bad and this one that you put is right. Thank you ! — gagiuntoli, Jan 09 '19 at 20:46

Sorting c++ vector

2 Answers2