似乎按理讲无旋会比旋转慢...

但我最近把以前的无旋Treap板子里面插入改成旋转的

然后慢了大概30%，，，

所以有巨佬能看看我的实现有什么问题吗...

下面是我两个版本的insert函数，，，（不要在意我奇怪的template

分裂合并、旋转如果有需要再放

//旋转
template<typename _Tp,typename _Cmp,typename _Alloc>
std::pair<bool,typename treap<_Tp,_Cmp,_Alloc>::iterator>
treap<_Tp,_Cmp,_Alloc>::insert(const _Tp& Value)
{
    Node *ptr=root,*last_ptr=end_node;
	bool is_lc=1;
	while(ptr!=NULL)
	{
		last_ptr=ptr;
		if(_Cmp::operator()(Value,ptr->value))ptr=ptr->lc,is_lc=1;
		else if(_Cmp::operator()(ptr->value,Value))ptr=ptr->rc,is_lc=0;
		else return std::make_pair(false,iterator(end_node));
	}
    //下面两行是分配节点不用管
    Node *new_ptr=_node_alloc_traits_type::allocate(_node_allocator,1);
    _node_alloc_traits_type::construct(_node_allocator,new_ptr,Value);
	if(is_lc)last_ptr->lc=new_ptr;
	else last_ptr->rc=new_ptr;
	new_ptr->ftr=last_ptr;
	ptr=new_ptr;
	end_node->maintain();
	while(ptr->ftr!=end_node)
	{
		++ptr->ftr->s;
		ptr=ptr->ftr;
	}
	while(new_ptr->ftr!=end_node&&new_ptr->pri<new_ptr->ftr->pri)
	{
		++new_ptr->ftr->s;
		new_ptr->rotate();
	}
    return std::make_pair(true,iterator(new_ptr));
}

//无旋
template<typename _Tp,typename _Cmp,typename _Alloc>
std::pair<bool,typename treap<_Tp,_Cmp,_Alloc>::iterator>
treap<_Tp,_Cmp,_Alloc>::insert(const _Tp& Value)
{
    Node *ptr1,*ptr2,*ptr3;
    split_val(root,Value,ptr1,ptr2);
    split_val_equal(ptr2,Value,ptr2,ptr3);
    if(ptr2!=NULL)
    {
        root=merge(merge(ptr1,ptr2),ptr3);
        return std::make_pair(false,iterator(end_node));
    }
    Node *new_ptr=_node_alloc_traits_type::allocate(_node_allocator,1);
    _node_alloc_traits_type::construct(_node_allocator,new_ptr,Value);
    root=merge(merge(ptr1,new_ptr),ptr3);
    return std::make_pair(true,iterator(new_ptr));
}