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

deque源码1(deque概述、deque中的控制器)

deque源码2(deque迭代器、deque的数据结构)

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

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

 

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;
}