c++ - 自定义字符串排序比较函数奇怪的行为

Question

我需要对一个字符串 vector 进行排序，但这不是一个严格的前向排序。我写了一个自定义排序函数，它非常适合较小的 vector 大小(<100 个元素)，但是我在较大的 vector 中得到了非常奇怪的行为。注意:输入的值均为数字。

我添加了一些调试 printf 语句以查看内部发生了什么，我发现空字符串和其他奇怪的字符串被传递到要排序的函数中。

我的期望是只有 vector 中的值会被传递到函数中。我验证了 vector 中填充了已知值。

排序函数:

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;
}

主要功能:

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

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

奇怪的输出示例:

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 

Answer 1

当 std::sort 表现得很滑稽时，几乎总是因为比较函数无效。您传递给 std::sort 的比较函数必须提供严格的弱排序。通常的失败是比较函数的定义使得对于两个对象 a 和 b，compare(a,b) 返回 true and compare(b,a) 返回 true，即 a 在 b 和 b 之前> 出现在 a 之前。发生这种情况时，排序算法可能会耗尽数据的末尾并做出各种疯狂的事情。

这个问题的实际答案就在下面的某处:

//sorting magic defining 'bool retVal'