Learning a Prat of C++(for ACM/ICPC) (extended 1) 那些年踩过的坑

这里整理一下一些经典的、能让你调试老半天的大坑。
（在前面出现过的，就不重复提了。）

1、

int i=0;
int f(){
    i*=2;
    return i;
}
int g(){
    i+=1;
    return i;
}
int main(){
    printf("%d\n",g()+f());
}

你们觉得结果是多少？
事实上，这个结果是不确定的！根据编译器的不同，可能会先执行g()再执行f()，也可能会先执行f()再执行g()。
也可以参见：https://www.zhihu.com/question/34787444/answer/60930197
或者买本《C++程序设计陷阱》，陷阱14就包含这个问题。

2、
51nod上的题：
https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1376
有人写了代码，思路很正确，可是跑起来就是不对头。
（提示：注意第76行）

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#include<vector>
#include<algorithm>
#define MAXN 50003
using namespace std;
const int P=15954746;
const int A=16233459;
const int BG=1000000007;
const int INF =0x3f3f3f3f;
int dp[MAXN];
int data[MAXN];
int f[MAXN];
int H[MAXN];
int U=A;
int Frand()
{
    srand((U+A)%P);
    U=rand()%P;
    return U;
}
struct point
{
    int key;
    int c[3];
    int H;
    int h;
    int pri;
    point ()
    {
        pri=Frand();
        c[1]=c[0]=0;
        key=h=H=0;
    }
    point(int key,int pri,int h,int H):key(key),pri(pri),h(h),H(H)
    {
        c[1]=c[0]=0;
    }
};
struct Treap
{
    vector<point>D;
    int root;
    Treap ()
    {
        root=0;
        D.push_back(point(0,INF,0,0));
    }
    void updata(int x)
    {
        D[x].H=( ( D[D[x].c[0]].H + D[D[x].c[1]].H ) % BG+ D[x].h ) % BG ;
    }
    int  rotate(int x,int t)
    {
        int y=D[x].c[t];
        D[x].c[t]=D[y].c[1-t];
        D[y].c[1-t]=x;
        updata(x);
        return y;
    }
    int _insert(int x,int k,int h)
    {
        if(x)
        {
            if(D[x].key==k)
            {
                D[x].h=(D[x].h+h)%BG;
            }
            else
            {
                int t=D[x].key<k;
                //int res=_insert(D[x].c[t],k,h);
                //D[x].c[t]=res;
                D[x].c[t]=_insert(D[x].c[t],k,h);
                //printf("-%d(%d %d) ",D[x].c[t],D.capacity(),D.size());
                if(D[D[x].c[t]].pri<D[x].pri)       x=rotate(x,t);
            }
        }
        else
        {
            x=D.size(); 
            //printf("%d(%d %d)",x,D.capacity(),D.size());
            D.push_back(point(k,Frand(),h,h));
        }
        updata(x);
        return x;
    }
    int _Query(int x,int k)
    {
        if(x==0) return 0;
        if(D[x].key==k)return D[D[x].c[0]].H;
        if(D[x].key<k) return ( ( D[D[x].c[0]].H + D[x].h ) % BG+ _Query ( D[x].c[1] , k )  )% BG;
        return _Query ( D[x].c[0] , k);
    }
    void insert(int k,int h)
    {
        root=_insert(root,k,h);
    }
    int Query(int k)
    {
        return _Query(root,k);
    }
}T[MAXN];
int main ()
{
    memset(dp,0x3f,sizeof(dp));
    srand((time(NULL)+A)%P);
    U=rand()%P;
    int N,len=1;
    scanf("%d",&N);
    for(int i=0;i<N;i++)
    {
        scanf("%d",data+i);
        f[i]=lower_bound(dp+1,dp+N+1,data[i])-dp;
        dp[f[i]]=data[i];
        len=max(len,f[i]);
    }
    int sum=0;
    T[0].insert(-INF,1);
    for(int i=0;i<N;i++)
    {
        H[i]=T[f[i]-1].Query(data[i]);
        if(f[i]==len) sum=(sum+H[i])%BG;
        else T[f[i]].insert(data[i],H[i]);
    }
    printf("%d\n",sum);
    return 0;
}

样例数据：

5
1 3 2 0 4
应该输出
2

然后发现Treap的插入操作好像并没有正确执行。
然后发现第76行改成第74、75行就行了。
为什么？

这是前面例子的一个更隐蔽的版本。
vector的下标运算符也算是函数调用。
对于D[x].c[t]=_insert(D[x].c[t],k,h);，编译器发现有：赋值运算符前面的D[x].c[t]、_insert中的D[x].c[t]、_insert()函数自己要结算。
显然_insert要在_insert中的D[x].c[t]算出来之后再执行，那么，2个D[x].c[t]，他们要按照什么顺序结算呢？
答：因为不存在相互依赖的关系，什么顺序都行。
C++里，这种子表达式的求值顺序，是不确定的。

于是有的编译器先算好了赋值运算符前面的D[x].c[t]（的地址）。
然后灾难在后面的递归调用中的push_back()。
push_back()修改了vector。而vector增加东西，如果发现剩余空间不够，在内部，会new一块新数组，老的数组就不要了。
这时候，先计算的 赋值运算符前面的D[x].c[t]（的地址）其实已经是废弃的地方了，函数返回了，再往里面写入，就显得没有效果了。

——所以，不要偷懒，多写几句，省下你自己不知道多少debug时间。