custom string sort comparison function weird behavior

Question

I need to sort a vector of strings, however its not a strait forward sorting. I wrote a custom sort function which works perfectly for smaller vector sizes (<100 element), however I get really weird behavior with larger sizes. Note: the values input are all numbers.

I added some debug printf statements to see what was happening internally which is where I found that empty strings and other strange strings are being passed into the function to be sorted.

My expectation is that only the values in the vector will be passed into the function. I verified that vector is filled with known values.

Sorting function:

bool sortFunc( string a, string b ){    
    printf( "a: %s,\tb: %s  \t", a.c_str(), b.c_str() );

    //sorting magic defining 'bool retVal'

    printf( "%s goes before %s\n", retVal?a.c_str():b.c_str(), retVal?b.c_str():a.c_str() );

    return retVal;
}

Main function:

vector<string> a(n);
for( int i=0; i<n; ++i ){
    cin >> a[i];
}

sort(a.begin(),a.end(),sortFunc);

Sample of weird output:

a: 2,   b: 10   2 goes before 10
a: 10,  b: 10   10 goes before 10
a: ,    b: 10    goes before 10
a: ,    b: 10    goes before 10
a: \240E,   b: 10   \240E goes before 10
a: ,    b: 10    goes before 10
a: {@,  b: 10   {@ goes before 10
a: ,    b: 10    goes before 10
a: ,    b: 10    goes before 10
a: ,    b: 10    goes before 10
a: \225E,   b: 10   10 goes before \225E
a: 2,   b: 10   2 goes before 10
a: 10,  b: \225E    10 goes before \225E
a: ,    b:       goes before 
a: ,    b:       goes before 
a: \245E,   b:       goes before \245E
a: \236E,   b: \245E    \245E goes before \236E
a: 0G\260\377, b: \236E    0G\260\377 goes before \236E
a: 0G\260\377, b: \245E    0G\260\377 goes before \245E
a: 0G\260\377, b:      0G\260\377 goes before

(A) Why are you accepting the strings by value? (B) The sort algorithm may very welly have a scratch space to move strings in and out of. Moving a string would leave it in some unknown but valid state. (C) Did it occur to you that your "magic" may not be a strict weak ordering, like the sort algorithm expects? Leaving the code with undefined behavior. — StoryTeller - Unslander Monica
– StoryTeller - Unslander Monica, Commented Dec 6, 2017 at 7:32
What if you print your vector<string> a before you sort it? Are you sure there are no "weird" values in it. — xander
– xander, Commented Dec 6, 2017 at 7:32
If you get the output "10 goes before 10" because retVal is true (it's impossible to tell from the output), you don't have a strict weak ordering and the result is undefined. — molbdnilo
– molbdnilo, Commented Dec 6, 2017 at 11:48
@xander, I do print it before as well as inspect the variable in Xcode — SmittyMcSmith
– SmittyMcSmith, Commented Dec 6, 2017 at 16:43

Pete Becker · Accepted Answer · 2017-12-06 14:52:03Z

3

When std::sort acts funny, it's almost always because of an invalid comparison function. The comparison function that you pass to std::sort must provide a strict weak ordering. The usual failure is that the comparison function is defined such that for two objects a and b, compare(a,b) returns true and compare(b,a) returns true, i.e., a comes before b and b comes before a. When that happens, the sort algorithm may well run off the end of your data and do all sorts of wild and crazy things.

The actual answer to this question lies somewhere inside this:

//sorting magic defining 'bool retVal'

answered Dec 6, 2017 at 14:52

Pete Becker

77.2k8 gold badges82 silver badges171 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

custom string sort comparison function weird behavior

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related