deque源码4(deque元素操作:pop_back、pop_front、clear、erase、insert）

deque源码3(deque的构造与内存、ctor、push_back、push_front)

pop_back()函数如下：

void pop_back(){
    if(finish.cur!=finish.first){
        //最后缓冲区至少有一个元素
        --finish.cur; //调整指针，相当于排除了最后元素
        destory(finish.cur); //将最后元素构析
    }
    else
        //最后缓冲区没有任何元素
        pop_back_aux(); //这里将进行缓冲区的释放工作
}

//只有当finish.cur==finish.first时才会被调用
template <class T,class Alloc,size_t BufSize>
void deque<T,Alloc,BufSize>::pop_back_aux(){
    deallocate_node(finish.first); //释放最后一个缓冲区
    finish.set_node(finish.node-1); //调整finish的状态，使指向上一个缓冲区的最后一个元素
    finish.cur=finish.last-1;
    destory(finish.cur); //将该元素析构
}

pop_front()函数如下：

void pop_front(){
    if(start.cur!=start.last-1){
        //第一缓冲区至少有一个元素
        destory(start.cur); //将第一元素析构
        ++start.cur; //调整指针，相当于排除了第一元素
    }
    else
        //第一个缓冲区仅有一个元素
        pop_front_aux(); //这里将进行缓冲区释放工作
}

//只有当start.cur==start.last-1时才会被调用
template <class T,class Alloc,size_t BufSize>
void deque<T,Alloc,BufSize>::pop_front_aux(){
    destory(start.cur); //将第一缓冲区的第一个元素析构
    deallocate_node(start.first); //释放第一缓冲区
    start.set_node(start.node+1); //调整start的状态，使指向下一个缓冲区的第一个元素
    start.cur=start.first;
}

clear()用来清除整个deque，需要注意的是deque的最初状态没有任何一个元素，保有一个缓冲区，因此，clear()完成之后回复初始状态，也一样要保留一个缓冲区。

clear()函数如下：

template <class T,class Alloc,size_t BufSize>
void deque<T,Alloc,BufSize>::clear(){
    //以下针对头尾以外的每一个缓冲区
    for(map_pointer node=start.node+1;node<finish.node;++node){
        //将缓冲区内的所有元素析构
        destory(*node,*node+buff_size());
        //释放缓冲区内存
        data_allocator::deallocate(*node,buff_size());
    }
    if(start.node!=finish.node){ //至少有头尾两个缓冲区
        destory(start.cur,start.last); //将头缓冲区的目前所有元素析构
        destory(finish.first,finish.cur); //将尾缓冲区的目前所有元素析构
        //以下释放尾缓冲区，注意，头缓冲区保留
        data_allocator::deallocate(finish.first,buffer_size());
    }
    else //只有一个缓冲区
        destory(start.cur,finish.cur); //将此唯一缓冲区内所有元素析构，并保留缓冲区
    finish=start; //调整状态
}

erase()函数清除某一个元素：

//清除pos所指向的元素，pos为清除点
iterator erase(iterator pos){
    iterator next=pos;
    ++next;
    difference_type index=pos-start; //清除点之前的元素个数
    if(index<(size()>>1)){ //如果清除点之前的元素比较少
        copy_backward(start,pos,next); //就移动清除点之前的元素
        pop_front(); //移动完毕，清除最前一个元素
    }
    else{ //清除点之后的元素比较少
        copy(next,finish,pos); //就移动清除点之后的元素
        pop_back(); //移动完毕，清除最后一个元素
    }
    return start+index;
}

erase()函数用来清除(first，last)区间内所有元素：

template <class T,class Alloc,size_t BufSize>
deque<T,Alloc,BufSize>::iterator
void deque<T,Alloc,BufSize>::erase(iterator first,iterator last){
    if(first==start&&last==finish){ //如果清除区间就是整个deque
        clear(); //直接调用clear()函数
        return finish;
    }
    else{
        difference_type n=last-first; //清除区间的长度
        difference_type elems_before=first-start; //清除区间前方的元素个数
        if(elems_before<(size()-n)/2){ //如果前方的元素比较少
            copy_backward(start,first,last); //向后移动前方元素(覆盖清除区间)
            iterator new_start=start+n; //标记deque的新起点
            destory(start,new_start); //移动完毕，将冗余的元素析构
            //以下将冗余的缓冲区释放
            for(map_pointer cur=start.node;cur<new_start.node;++cur)
                data_allocator::deallocate(*cur,buffer_size());
            start=new_start; //设定deque的新起点
        }
        else{ //如果清除区间后方的元素比较少
            copy(last,finish,first); //向前移动后方元素(覆盖清除区间)
            iterator new_finish=finish-n; //标记deque的新尾点
            destory(new_finish,finish); //移动完毕，将冗余的元素析构
            //以下将冗余的缓冲区释放
            for(map_pointer cur=new_finish.node+1;cur<=finish.node;++cur)
                data_allocator::deallocate(*cur,buffer_size());
            finish=new_finish; //设定deque的新尾点
        }
        return start+elems_before;
    }
}

deque提供了多个insert功能，这里描述最基础的insert方法，允许在某个点之前插入一个元素，并设定其值。

insert()函数如下：

//在position处插入一个元素，其值为x
iterator insert(iterator position,const value_type& x){
    if(position.cur==start.cur){ //如果插入点是deque最前端
        push_front(x); //调用push_front函数
        return start;
    }
    else if(position.cur==finish.cur){ //如果插入点是deque最尾端
        push_back(x); //调用push_back函数
        iterator temp=finish;
        --temp;
        return temp;
    }
    else{
        return insert_aux(position,x); //调用insert_aux函数
    }
}

template <class T,class Alloc,size_t BufSize>
deque<T,Alloc,BufSize>::iterator
void deque<T,Alloc,BufSize>::insert_aux(interator pos,const value_type& x){
    difference_type index=pos-start; //插入点之前的元素个数
    value_type x_copy=x;
    if(index<size()/2){ //如果插入点之前的元素个数比较少
        push_front(front()); //在最前端口加入与第一元素同值的元素
        iterator front1=start; //以下标示记号，然后进行元素移动
        ++front1;
        iterator front2=front1;
        ++front2;
        pos=start+index;
        iterator pos1=pos;
        ++pos1;
        copy(front2,pos1,front1); //元素移动
    }
    else{ //插入点之后的元素个数比较少
        push_back(back()); //在最尾端加入与最后元素同值的元素
        iterator back1=finish; //以下标示记号，然后进行元素移动
        --back1;
        iterator back2=back1;
        --back2;
        pso=start+index;
        copy_backward(pos,back2,back1); //元素移动
    }
    *pos=x_copy; //在插入点上设定新值
    return pos;
}

deque源码4(deque元素操作:pop_back、pop_front、clear、erase、insert）

相关推荐