平衡树以string作为元素为什么比以内含两个变量的结构体快很多？

Question

问题

我需要一种能支持插入一段字符串并且能查询这段字符串最后出现的排名（类似于upper_bound）（按字典序排序）
然后我选择了可持久化Treap
然后因为插入很多字符串并且字符串长度很长
所以空间开销很大
但是因为我所要插入和查询的字符串都是某一个大字符串的一个子串
所以我改进了这个算法
我使用了一个结构体

struct si{
    int l,r;
};

来表示这个字符串在大字符串中的位置
其中str是大字符串，a,b分别是需要比较的两个字符串
然后手写了一个比较器(按照字典序)来比较两个字符串的大小

bool QxHd(si a,si b){
    ii=a.l,jj=b.l;
    int lena=a.r-a.l+1,lenb=b.r-b.l+1;
    for(register int k=0;k<min(lena,lenb);++k)
        if(str[ii+k]<str[jj+k])return true;
        else if(str[ii+k]==str[jj+k])continue;
        else return false;
    return lena<=lenb;
}

这个算法的代码和用string比较的代码基本一致

但是我随后发现了一个问题
使用string实现的算法除了部分特殊数据会非常慢之外
速度一般比用结构体实现的快2-4倍
我使用的数据是
大字符串大小是50000，插入和查询的字符串大小为5000-20000左右

两段代码比较

这是使用string当平衡树元素的一段代码

class Treap{
    private:
    int com,x,y,z,a,b;
    int root;
    int ch[N][3];
    string val[N];
    int pri[N];
    int siz[N];
    int sz;
    void update(int x){
        siz[x]=1+siz[ch[x][0]]+siz[ch[x][1]];
    } 
    int new_node(string v){
        siz[++sz]=1;
        val[sz]=v;
        pri[sz]=rand(); 
        return sz;
    }
    int merge(int x,int y){
        if(!x||!y)return x+y;
        if(pri[x]<pri[y]){
            ch[x][1]=merge(ch[x][1],y); 
            update(x);
            return x;
        } 
        else{
            ch[y][0]=merge(x,ch[y][0]);
            update(y);
            return y;
        }
    }
    void split(int now,string k,int &x,int &y){
        if(!now)x=y=0;
        else{
            if(val[now]<=k)    
                x=now,split(ch[now][1],k,ch[now][1],y);
            else 
                y=now,split(ch[now][0],k,x,ch[now][0]);
            update(now);
        } 
    }
    public:
    Treap(){
        root=0;
    }
    void Insert(string a){       
        split(root,a,x,y);
        root=merge(merge(x,new_node(a)),y);
    }
    int Find(string a){
        split(root,a,x,y);
        int ans=siz[x];
        root=merge(x,y);
        return ans;
    }
};

char str[N];

struct si{
    int l,r;
};

int ii=0,jj=0;

bool QxHd(si a,si b){
    ii=a.l,jj=b.l;
    int lena=a.r-a.l+1,lenb=b.r-b.l+1;
    for(register int k=0;k<min(lena,lenb);++k)
        if(str[ii+k]<str[jj+k])return true;
        else if(str[ii+k]==str[jj+k])continue;
        else return false;
    return lena<=lenb;
}

class Treap{
    private:
    int com,x,y,z,a,b;
    int root;
    int ch[N][3];
    si val[N];
    int pri[N];
    int siz[N];
    int sz;
    void update(int x){
        siz[x]=1+siz[ch[x][0]]+siz[ch[x][1]];
    } 
    int new_node(si asd){
        siz[++sz]=1;
        val[sz]=asd;
        pri[sz]=rand(); 
        return sz;
    }
    int merge(int x,int y){
        if(!x||!y)return x+y;
        if(pri[x]<pri[y]){
            ch[x][1]=merge(ch[x][1],y); 
            update(x);
            return x;
        } 
        else{
            ch[y][0]=merge(x,ch[y][0]);
            update(y);
            return y;
        }
    }
    void split(int now,si &k,int &x,int &y){
        if(!now)x=y=0;
        else{
            if(QxHd(val[now],k))    
                x=now,split(ch[now][1],k,ch[now][1],y);
            else 
                y=now,split(ch[now][0],k,x,ch[now][0]);
            update(now);
        } 
    }
    public:
    Treap(){
        root=0;
    }
    void Insert(si &a){       
        split(root,a,x,y);
        root=merge(merge(x,new_node(a)),y);
    }
    int Find(si &a){
        split(root,a,x,y);
        int ans=siz[x];
        root=merge(x,y);
        return ans;
    }
};