list源码4(参考STL源码--侯捷)：transfer、splice、merge、reverse、sort

transfer

list内部提供一个所谓的迁移技术：transfer，将某连续范围的元素迁移到某个指定的位置之前：

//将[first，last]内所有元素移动到position之前

void transfer(iterator position,iterator first,iterator last){

    if(position!=last){

        (*(link_type((*last.node).prev))).next=position.node; //

        (*(link_type((*first.node).prev))).next=last.node; //

        (*(link_type((*position.node).prev))).next=first.node; //

        link_type temp=link_type((*position.node).prev); //

        (*position.node).prev=(*last.node).prev; //

        (*last.node).prev=(*first.node).prev; //

        (*first.node).prev=temp; //

    }

}

transfer所接受的[first,last]区间，可以存在同一个list里面，上述transfer并非公开接口，list的公开接口是splice；splice：将某个连续范围的元素从一个list移到另一个list的某个定点，使用如下：

#include<bits/stdc++.h>

using namespace std;

int main() {

    list<int> l1={,,,,,};

    int a[]={,,,};

    list<int> l2={a,a+};

    list<int>::iterator it=find(l1.begin(),l1.end(),);

    list<int>::iterator first=l2.begin();

    list<int>::iterator last=l2.end();

    if(*it==){

//        l1.splice(it,l2);

        l1.splice(it,l2,first,last);

    }

    for(auto i:l1) cout<<i<<' ';//0 1 2 11 12 13 14 3 4 5

    cout<<endl;

    l1.reverse();

    for(auto i:l1) cout<<i<<' ';//5 4 3 14 13 12 11 2 1 0

    cout<<endl;

    l1.sort();

    for(auto i:l1) cout<<i<<' ';//0 1 2 3 4 5 11 12 13 14

    cout<<endl;

    return ;

}

splice

public:

    //将x接合于position之前

    void splice(iterator position,list& x){

        if(!x.empty()){

            transfer(position,x.begin(),x.end());

        }

    }

    //将i所指元素接合于position所指位置之前，position和i可指向同一list

    void splice(iterator position, list&, iterator i){

        iterator j=i;

        ++j;

        if(position==i||position==j) return;

        transfer(position,i,j);

    }

    //将[first，last]内的所有元素接合于position所指位置之前

    //position和[first，last]可指向同一个list

    //position不能位于[first,last]之内

    void splice(iterator position, list&, iterator first,iterator last){

        if(last!=first){

            transfer(position,first,last);

        }

    }

merge

//merge()将x合并到*this身上，两个list的内容都必须经过递增排序

template<class T,class Alloc>

void list<T,Alloc>::merge(list<T,Alloc>& x){

    iterator first1=begin();

    iterator last1=end();

    iterator first2=x.begin();

    iterator last2=x.end();

    //注意：前提是两个链表都经过递增排序

    while(first1!=last1&&first2!=last2){

        if(*first2<*first1){

            iterator next=first2;

            tranfer(first1,first2,++next);

            first2=next;

        }

        else

            ++first1;

        if(first2!=last2)

            transfer(last1,first2,last2);

    }

}

reverse

//reverse()内容逆置

template<class T,class Alloc>

void list<T,Alloc>::reverse(){

    //以下判断：如果空链表或者仅有一个元素，就不进行任何操作

    //使用size()==0||size()==1来判断，虽然也可以，但是比较慢

    if(node->next==node||link_type(node->next)->next==node)

        return;

    iterator first=begin();

    ++first;

    while(first!=end()){

        iterator old=first;

        ++first;

        transfer(begin(),old,first);

    }

}

sort

//list不能使用STL算法sort()，必须使用自己的成员函数sort（）

//本函数采用quicksort（看代码好像不是快排，而是归并）

template<class T,class Alloc>

void list<T,Alloc>::sort(){

    //以下判断：如果空链表或者仅有一个元素，就不进行任何操作

    //使用size()==0||size()==1来判断，虽然也可以，但是比较慢

    if(node->next==node||link_type(node->next)->next==node)

        return;

    //新的list作为辅助数据存放区

    list<T,Alloc> carry;

    list<T,Alloc> counter[];

    int fill=;

    while(!empty()){

        carray.splice(carry.begin(),*this,begin());

        int i=;

        while(i<fill&&!counter[i].empty()){

            counter[i].merge(carray);

            carray.swap(counter[i++]);

        }

        carray.swap(counter[i]);

        if(i==fill)

            ++fill;

    }

    for(int i=;i<fill;++i){

        counter[i].merge(counter[i-]);

    }

    swap(counter[fill-]);

}
下面来解释一下sort的实现，以21，45，1，30，52，3，58，47，22，59，0，58为例：

1、counter[0]:21 注：counter[i]存放2ⁱ⁺¹个数，当达到第2ⁱ⁺¹个数时，移动数据到counter[i+1]中

2、counter[0]:21，45　　注：counter[0]元素已满

counter0]:NULL

counter[1]:21，45

3、counter[0]:1

　  counter[1]:21，45

4、counter[0]:1，30　　注：counter[0]元素已满，利用merge合并counter[0]至counter[1]

　  counter[1]:21，45

counter[0]:NULL

counter[1]:1，30，21，45　　注：counter[1]元素已满,

counter[0]:NULL

counter[1]:NULL

counter[2]:1，30，21，45

......

最后得到：

　  counter[0]:58

counter[1]:0,59

counter[2]:NULL

　  counter[3]:1，3，21，30，47，45，52，58

再次归并得到最后结果。

参考地址：https://blog.****.net/shoulinjun/article/details/19501811

秒客网

list源码4(参考STL源码--侯捷)：transfer、splice、merge、reverse、sort

相关文章