c++ - 重用字符串比较结果以加快 std::sort

Question

我想使用 strcmp 对唯一字符串的 vector 进行排序。

std::sort 需要一个判断一个字符串是否小于另一个的谓词，但是 strcmp 实际上已经返回了字符串的关系，这实际上是明智的利用这些信息而不是丢失它。

这很有用，因为它还需要确定字符串是否相等 - 在这种情况下，将使用相同的字符串再次调用谓词，但参数顺序相反。

这是简单的排序方式:

vector<const char*> cache;
sort(cache.begin(), cache.end(), [](const char* left, const char* right)
{
    return strcmp(left, right) < 0;
});

我正在试验以下想法，我将比较结果存储在其中，如果再次比较相同的字符串，则重新使用它。

vector<const char*> cache;
sort(cache.begin(), cache.end(), [notLess = false, r = (const char*)nullptr](const char* left, const char* right) mutable
{
    // possibly reuse previous comparison of same strings passed in inverse order
    if (notLess &&
        r == left)
    {
        notLess = false;
        // always less since vector contains unique strings
        return true;
    }

    if (notLess = strcmp(left, right) >= 0)
        r = right;
    return !notLess;
});

为了限制存储的信息和额外引入比较的次数，我想到了只存储right的字符串，它正在变成左边的进行逆比较。

现在，我真正的问题是只检查之前的 right 字符串是否足够，还是我还需要存储和检查之前的 left 字符串？

Answer 1

首先，您的假设是错误的。 std::sort 不会使用相同的参数调用比较两次。因此，整个想法是有缺陷的。

其次(更重要的是)您的想法有缺陷，因为谓词不应该保持状态。 std::sort 可以复制那些谓词并重复使用拷贝(事实上，我前段时间检查时，gcc 版本肯定复制了谓词)因此会破坏整个比较。