不要使用短路逻辑编写 stl sorter 多条件比较

最近工期紧、任务多，没有时间更新博客，就水一期吧。虽然是水，也不能太水，刚好最近工作中遇到一个 sorter 多条件排序的问题，花费了半天时间来定位解决，就说说它吧。

公司产品是一个跨端的数据传输 sdk，当下载资源时，会先从服务器拉取一批 peer，每个 peer 是包含要下载资源分片的 p2p 端，每个节点有一个序号，sdk 根据这个值从小到大排序后依次选取 peer 进行连接，序号是由服务器决定的，主要根据地域、连通率、带宽等决定的，可以简化为下面的 demo：

#include <stdio.h>
#include <vector>
#include <string>
#include <algorithm>

struct PeerInfo
{
    std::string peerid;
    std::string ip;
    short port;
    int begin;
    int end;
    int seq;

    void print(void);
};

void PeerInfo::print(void)
{
    printf ("peer %s: %d, %s:%d, %d-%d\n",
            peerid.c_str(), seq,
            ip.c_str(), port, begin, end);
}

struct PeerInfoSorter
{
    bool operator() (PeerInfo const& lhs, PeerInfo const& rhs) {
        return lhs.seq < rhs.seq;
    }
};

int main (void)
{
    std::vector<peerinfo> vpi;
    // init this vector by server response
    // ...

    std::sort (vpi.begin(), vpi.end(), PeerInfoSorter());
    for (auto it = vpi.begin(); it != vpi.end(); ++ it)
    {
        it->print();
    }
}</peerinfo></algorithm></string></vector></stdio.h>

在下载过程中会向服务器请求多次，每批返回的 peer 都放在一个容器中排序，但是序号是基于批的，多个批次之间的 peer 如果仅按照 seq 排序的话，就会将前面批次旧的 peer 排在前面，从而导致一些新 peer 没有机会被用到，发生饥饿现象。

问题的产生

了解到这个情况后，采取了按批和序号同时排序的方案，即为 peer 增加一个 batch 字段用于记录批号，在排序时只有 batch 相同时才去比较 seq，代码类似下面这样：

struct PeerInfo
{
    std::string peerid;
    std::string ip;
    short port;
    int begin;
    int end;
    int seq;
    int batch;

    void print(void);
};

void PeerInfo::print(void)
{
    printf ("peer %s: %d-%d, %s:%d, %d-%d\n",
            peerid.c_str(), batch, seq,
            ip.c_str(), port, begin, end);
}

struct PeerInfoSorter
{
    bool operator() (PeerInfo const& lhs, PeerInfo const& rhs) {
        return lhs.batch < rhs.batch || lhs.seq < rhs.seq;
    }
};

当时的想法比较直接，先比较 batch，如果 batch 已经小了就直接短路返回结果；再比较 seq。看着逻辑没什么问题，但是运行起来后发现还是有旧批次的 peer 排在前面，以上面那个 demo 为例，制造一些测试数据：

    // ...

    vpi.push_back ({"1a2b", "10.0.1.29", 8001, 0, 16384, 1, 1});
    vpi.push_back ({"3c4d", "10.0.1.30", 8002, 16384, 32768, 2, 1});
    vpi.push_back ({"5e6f", "10.0.1.31", 8003, 8192, 24576, 1, 2});
    vpi.push_back ({"7a8b", "10.0.5.22", 8081, 32768, 49152, 2, 2});
    vpi.push_back ({"9c0d", "10.0.5.23", 8082, 49152, 65536, 1, 3});
    vpi.push_back ({"afec", "10.0.5.24", 8083, 0, 65536, 2, 3});

其中最后两个字段分别是 seq 与 batch 的初始值。执行后输出如下：

$ ./peer
peer 1a2b: 1-1, 10.0.1.29:8001, 0-16384
peer 5e6f: 2-1, 10.0.1.31:8003, 8192-24576
peer 9c0d: 3-1, 10.0.5.23:8082, 49152-65536
peer 3c4d: 1-2, 10.0.1.30:8002, 16384-32768
peer 7a8b: 2-2, 10.0.5.22:8081, 32768-49152
peer afec: 3-2, 10.0.5.24:8083, 0-65536

peer 1-2 排在 2-1 后面明显不是我们想要的，那是哪里出了问题呢？

问题的解决

看起来是 sorter 写的有问题，重新考察一下它的逻辑：

• lhs.batch < rhs.batch 时，直接返回 true 并短路后面的条件，这是正确的
• lhs.batch = rhs.batch 时，结果退化为 seq 之间的比较，也是正确的
• lhs.batch > rhs.batch 时，结果退化为 seq 之间的比较，问题出在这里，此时应当直接返回 false

因此 sorter 正确的写法应该是这样：

struct PeerInfoSorter
{
    bool operator() (PeerInfo const& lhs, PeerInfo const& rhs) {
        if (lhs.batch != rhs.batch)
           return lhs.batch < rhs.batch;

        return lhs.seq < rhs.seq;
    }
};

前面的条件只要不相等就直接短路了，更正后输出正常了：

$ ./peer
peer 1a2b: 1-1, 10.0.1.29:8001, 0-16384
peer 3c4d: 1-2, 10.0.1.30:8002, 16384-32768
peer 5e6f: 2-1, 10.0.1.31:8003, 8192-24576
peer 7a8b: 2-2, 10.0.5.22:8081, 32768-49152
peer 9c0d: 3-1, 10.0.5.23:8082, 49152-65536
peer afec: 3-2, 10.0.5.24:8083, 0-65536

现在回过头来看前面错误的代码，看上去它至少保证了 batch 的顺序，那么这是真的吗？稍微调整一下容器数据的初始顺序：

    vpi.push_back ({"9c0d", "10.0.5.23", 8082, 49152, 65536, 1, 3});
    vpi.push_back ({"afec", "10.0.5.24", 8083, 0, 65536, 2, 3});
    vpi.push_back ({"1a2b", "10.0.1.29", 8001, 0, 16384, 1, 1});
    vpi.push_back ({"3c4d", "10.0.1.30", 8002, 16384, 32768, 2, 1});
    vpi.push_back ({"5e6f", "10.0.1.31", 8003, 8192, 24576, 1, 2});
    vpi.push_back ({"7a8b", "10.0.5.22", 8081, 32768, 49152, 2, 2});

得到的输出打破了这一”幻觉”：

$ ./peer
peer 1a2b: 1-1, 10.0.1.29:8001, 0-16384
peer 5e6f: 2-1, 10.0.1.31:8003, 8192-24576
peer 3c4d: 1-2, 10.0.1.30:8002, 16384-32768
peer 7a8b: 2-2, 10.0.5.22:8081, 32768-49152
peer 9c0d: 3-1, 10.0.5.23:8082, 49152-65536
peer afec: 3-2, 10.0.5.24:8083, 0-65536

很显然 1-2 排在了 2-1 之后。再分析之前的逻辑，当 lhs.batch > rhs.batch 时，结果是由 seq 决定的，所以完全可能出现上面的场景。而到底对哪些元素进行对比完全是由输入序列和对比算法决定的，怎么构造反例还真不好设计，只有当数据量大时才会表现的比较明显。

再回头来看逻辑短路操作，如果写成下面形式：

struct PeerInfoSorter
{
    bool operator() (PeerInfo const& lhs, PeerInfo const& rhs) {
        return lhs.batch < rhs.batch || lhs.seq < rhs.seq;
    }
};

则当 lhs.batch > rhs.batch 时不会短路，从而引发错误。如果写成下面的形式：

struct PeerInfoSorter
{
    bool operator() (PeerInfo const& lhs, PeerInfo const& rhs) {
        return lhs.batch < rhs.batch && lhs.seq < rhs.seq;
    }
};

则当 lhs.batch < rhs.batch 时不会短路，也引发错误。

总结一下就是，我们需要返回 batch 或 seq 的 operator < 结果来作为比较结果，但是这个条件对于 || 和 && 在一半的情况下是不会短路的，具体而言就是：

• 使用 || 逻辑短路时，lhs.batch < rhs.batch 得到满足，lhs.batch > rhs.batch 没有得到满足
• 使用 && 逻辑短路时， lhs.batch > rhs.batch 得到满足，lhs.batch < rhs.batch 没有得到满足

那它们能得到全部满足吗？当短路发生时，lhs.batch < rhs.batch 这一条件有 true 和 false 两种情况需要返回，而短路逻辑 || 和 && 只能允许其中一种通过，所以答案是不能。除非可以预判只有其中一种条件发生 (只返回 true 或 false)，然后有针对性的写 || 或 && 语句，不过那样的话这个字段也就没有参与比较的意义了。

最终结论就是，不要使用短路逻辑处理 sorter 多条件之间的判断。

回到前面项目中，再给它加一点需求：服务器返回不同批次的 peer 可能重复，通过 peerid 可以去重，但当新 batch 中的 peer 在之前出现并连接过时，我们希望它的优先级变低，以保证未连接过的 peer 不发生饥饿现象。对于这样的需求，怎么改呢？想必大家心中已经有了答案，现在和正确答案对比一下吧：

struct PeerInfoSorter
{
    bool operator() (PeerInfo const& lhs, PeerInfo const& rhs) {
        if (lhs.connect_cnt != rhs.connect_cnt)
            return lhs.connect_cnt < rhs.connect_cnt;

        if (lhs.batch != rhs.batch)
           return lhs.batch < rhs.batch;

        return lhs.seq < rhs.seq;
    }
};

其中 connect_cnt 新字段表示连接的次数，每连接一次增加一个计数，将这个条件放在最前面以便保证连接次数最少的 peer 排在最前面，只有当连接次数相同时 (新 peer 的 connect_cnt == 0)，才对比 batch 与 seq。

举这个例子的目的是为了说明，sorter 多条件对比时，只要按重要性一个个排就可以了，你学会了吗？

Original: https://www.cnblogs.com/goodcitizen/p/pitfall_in_stl_sorter_on_multiple_conditions.html
Author: goodcitizen
Title: 不要使用短路逻辑编写 stl sorter 多条件比较