蒟蒻无力抗衡这般玄学操作？？？！！！

薄荷凉了夏 @ 2018-08-08 12:08:50

while (abs(q1.size()-q2.size())>1) 
    if (q1.size()>q2.size()) {
        q2.push(q1.top());
        q1.pop();
    }
    else {
        q1.push(q2.top());
        q2.pop();
    }

while(!q1.empty()&&q1.size()-q2.size()>1) {
    q2.push(q1.top());
    q1.pop();
}
while(!q2.empty()&&q2.size()-q1.size()>1) {
    q1.push(q2.top());
    q2.pop();
}

by silverxz @ 2018-08-08 13:24:16

有可能是因为以下玄学原因： 去翻一下queue的源代码，size函数的返回类型是

queue::size_type;

我们找到这个size_type的定义，如下：

typedef typename _Sequence::size_type       size_type;

而我们发现，_Sequence是模板参数，默认值如下：

typename _Sequence = deque<_Tp>

于是我们去翻deque的源代码，发现有这么一句：

typedef size_t    size_type;

现在我们知道了，size()函数的返回类型是size_t（其实很多STL的size函数返回类型都是它）。size_t是个什么东西呢？我们再翻一翻源代码就可以得到。size_t在不同的实现中可能不一样，但是无论如何实现，它都是unsigned的！！！可以理解为unsigned int，但也可能是别的，比如unsigned long int。总是，它是无符号整数！

我们再看你的代码

q1.size()-q2.size()>1

两个无符号整数相减，如果结果小于零，会发生什么？会变成一个大的无符号整数。结果很可能大于1。

如果你还不确信这一点，可以跑一下下面的代码：

int main() {
    size_t x1 = 1, x2 = 10;
    if(x1-x2 > 1) {
        std::cout << x1-x2;
    }
    return 0;
}

我的机器输出的是4294967287。

是因为无符号整数的最高位和有符号整数的符号位是同一位，所以会出现这样的现象。大概就是这么回事。

by 薄荷凉了夏 @ 2018-08-08 14:02:09

@silverxz 好像懂点了诶 那上面那个呢，就加了个abs啊~(>_<)~

by silverxz @ 2018-08-08 14:27:53

@薄荷凉了夏

其实上面那个也犯了同样的错误。但是非常巧地，上面那个即便犯错了，也不会带来问题。

我们观察一下，什么情况下上面那个代码会出错。出现我们之前所说的那个错误的条件是，当且仅当：

q1.size()==q2.size()-1

按照代码编写者的期望，这时应该跳出循环，因为相差不超过1；但是我们知道，两个无符号整数相减，如果是负数，将会变成一个特别大的正数，因此这种情况不会跳出循环，而是会执行循环。

但是非常巧地，即便执行了这个循环，两者的size之差依旧不超过1，因为while循环中的代码是把size大的元素给size小的，执行循环之后，两者的关系如下：

q1.size()==q2.size()+1

然后会跳出循环，正常执行。

这就和你的第二份代码不一样。手动模拟一下就知道了。

我猜第一份代码也没有考虑到无符号整数相减的问题，然而……这就是运气问题了╮(╯▽╰)╭。

by 薄荷凉了夏 @ 2018-08-08 14:41:07

@silverxz %%%%Orz！！真的十分感谢诶

by n0000000000o @ 2018-10-02 20:11:19

受教了，谢谢