2.2 顺序容器-list

list（双向链表）

1）

*  :包含头文件list

**：不支持随机存取；增删元素时间是常数，只需要修改指针

2）成员函数

*  ：vector的成员函数list基本都有

**：以下是部分独有成员函数

      sort()算法需要随机访问，故list不支持，所以引入一个成员函数sort（）

3）list示例

*

//常用成员函数示例 
#include<iostream>
#include<list>
#include<algorithm>
using namespace std;
class A{
    private:
        int n;
    public:
        A(int n_){
            n=n_;
        }
        friend bool operator<(const A & a,const A & a2);
        friend bool operator==(const A & a,const A & a2);
        friend ostream & operator<<(ostream & o, const A & a2);
};
bool operator<(const A & a,const A & a2){
    return a.n<a2.n;
}
bool operator==(const A & a,const A & a2){
    return a.n==a2.n;
}
ostream & operator<<(ostream & o,const A & a){
    o<<a.n;
    return o;
}

template<class T>
void Print(T first,T last){
    for(;first!=last;++first)
        cout<<*first<<" ";
    cout<<endl;
}

int main(){
    
    A a[5]={1,3,2,4,2};
    A b[7]={10,30,20,30,30,40,40};
    list<A>lst1(a,a+5),lst2(b,b+7);
    lst1.sort();  //sort()此处是成员函数，不是算法 
    cout<<"1)"; Print(lst1.begin(),lst1.end());
    lst1.remove(2); //删除和2相等的参数 
    cout<<"2)";Print(lst1.begin(),lst1.end());
    lst2.pop_front();  //删除第一个元素 
    cout<<"3)"; Print(lst2.begin(),lst2.end());
    lst2.unique(); //删除和前一个相等的元素
    cout<<"4)"; Print(lst2.begin(),lst2.end());
    lst2.sort();
    lst1.merge(lst2);//合并lst2到lst1,并删除lst2
    cout<<"5)"; Print(lst1.begin(),lst1.end());
    cout<<"6)";Print(lst2.begin(),lst2.end()) ;
    lst1.reverse();  //前后颠倒
    cout<<"7)"; Print(lst1.begin(),lst1.end());
    lst2.insert(lst2.begin(),a+1,a+4);
    list<A>::iterator p1,p2,p3;
    p1=find(lst1.begin(),lst1.end(),30);
    p2=find(lst2.begin(),lst2.end(),2);
    p3=find(lst2.begin(),lst2.end(),4);
    lst1.splice(p1,lst2,p2,p3);//将[p2,p3)插入p1之前，并从lst2中删除
    cout<<"8)";Print(lst1.begin(),lst1.end()); 
    cout<<"9)";Print(lst2.begin(),lst2.end()); 

    return 0;
} 

**

//list 的约瑟夫问题 
#include<iostream>
#include<list>
using namespace std;
int main(){
    list<int>monkeys;
    int n,m;
    while(true){
        cin>>n>>m;
        if(n==0&&m==0) break;
    monkeys.clear();
    for(int i=1;i<=n;++i)
        monkeys.push_back(i);
    list<int>::iterator it=monkeys.begin();
    while(monkeys.size()>1){
        for(int i=1;i<m;++i){
            ++it;
            if(it==monkeys.end())
               it=monkeys.begin();
        }
        it=monkeys.erase(it);
        if(it==monkeys.end())
           it=monkeys.begin();
    }
    cout<<*it<<endl;
}
    return 0;
}

此例用vector也可以，因为vector的erase操作牵涉元素的移动，不是常数时间完成，n很大时在速度上有明显差别。