顺序性容器之列表list

一、list简介

列表list容器本质就是前面介绍过的双向链表。list是一个线性链表结构，它的数据由若干个节点构成，每一个节点都包括一个信息块（即实际存储的数据）、一个前驱指针和一个后继指针。它无需分配指定的内存大小且可以任意伸缩，这是因为它存储在非连续的内存空间中，并且由指针将有序的元素链接起来。

由于其结构的原因，与vector不同，list不支持随机存取，检索时要从头一个一个的顺序查找，这样目标元素越靠后，它的检索时间就越长。检索时间与目标元素的位置成正比。

虽然list检索的速度不够快，但是它可以迅速地在任何节点进行插入和删除操作。因为list的每个节点保存着它在链表中的位置（有指向前一个元素的前驱指针和指向后一个元素的后继指针），插入或删除一个元素仅对最多三个元素有所影响，不像vector会对操作点之后的所有元素的存储地址都有影响（整体后移或者前移），这方面的效率是vector不能比的。

list 的特点：

1. 不使用连续的内存空间，这样可以随意地进行动态插入删除操作；
2. 可以在内部任何位置快速地插入或删除，当然也可以在两端进行插入和删除；
3. 不支持随机访问，即不支持[ ]操作符和at()；
4. 相对于verctor占用更多的内存。

使用list容器，不需要关注“双向链表”的实现细节，直接使用其提供的成员函数进行相应的操作即可。例如我们使用list的erase()删除某个元素后，list内部会自动维持删除元素后的双链表中的前驱后继指针。

二、list的基本使用

list的使用和vector类似，只是双向链表决定了某些操作上的局限性，相比较vector也多出了一些成员函数。

1.引入list头文件

要使用list，首先要引入list头文件：#include<list>。

2.申明list变量

因为list是模板类，所以申明list变量时需要指明元素的数据类型。例如：

list<int> li1;
list<double> li2;
list<Circle> li3;
list<int> li4(20);		 //li4有20个int元素，每个元素值均为0
list<int> li5(1000,-1);	//li5有1000个int元素，每个元素值均为-1

3.插入、删除元素

相比较vector，list提供了在链尾追加元素的push_back()、删除链尾元素的pop_back()，还提供了在链首前插入元素的push_front()、删除链首元素的pop_front()这些成员函数。也提供了更普遍的插入元素的insert()，删除元素的erase()这些成员函数。因为list是双向链表，所以添加元素、删除元素的效率很高。调用size()可以返回list中元素的数量。

#include<iostream>
#include<list>
using namespace std;
int main()
{
    list<int> li;
    for(int i=1;i<=5;i++) li.push_back(i);
    cout<<li.size()<<endl;
    
    for(int i=1;i<=2;i++) li.pop_back();
    cout<<li.size()<<endl;
    
    for(int i=1;i<=5;i++) li.push_front(i);
    cout<<li.size()<<endl;
    
    for(int i=1;i<=2;i++) li.pop_front();
    cout<<li.size()<<endl;
    
    li.clear();
    cout<<li.size()<<endl;
    if(li.empty()) cout<<"None."<<endl;
    return 0;
}

4.遍历list

和vector类似，可以借助迭代器遍历list，begin()返回指向链首元素的迭代器，end()返回指向链尾元素的下一个位置的迭代器；对应的还有返回反向迭代器的rbegin()和rend()：

#include<iostream>
#include<list>
using namespace std; 
void print(list<int> &li){
	list<int>::iterator it = li.begin();
	for(;it!=li.end();it++) cout<<*it<<" ";
	cout<<endl;
} 
int main()
{
	list<int> li;
	for(int i=1;i<=10;i++) li.push_back(i);
	
	//正向遍历list 
	list<int>::iterator it = li.begin();
	for(;it!=li.end();it++) cout<<*it<<" ";
	cout<<endl;
	
	//反向遍历list 
	list<int>::reverse_iterator rit = li.rbegin();
	for(;rit!=li.rend();rit++) cout<<*rit<<" ";
	cout<<endl;
	
	print(li); 
	return 0;
}

注意，list的迭代器支持++和--运算，其他加减运算会出现编译错误。

#include<iostream>
#include<list>
using namespace std; 
int main()
{
	list<int> li;
	for(int i=1;i<=10;i++) li.push_back(i);
	auto it = li.begin();
	cout<<*it<<endl;
	it++;
	cout<<*it<<endl;
	it--;
	cout<<*it<<endl;
	
	//下面三条语句中对迭代器的运算均会出现编译错误 
	cout<<*(it+1)<<endl;
	it = it+1;
	it += 1;
	 
	return 0;
}

此外，还可以借助C++语言for循环的高级用法遍历list：

#include<iostream>
#include<list>
using namespace std;
int main()
{
    list<int> li{1,2,3,4,5,6,7,8,9,10};
	for(int n:li){
		cout<<n<<endl;
	}
    return 0;
}

#include<iostream>
#include<list>
using namespace std;
int main()
{
    list<int> li{1,2,3,4,5,6,7,8,9,10};
    for(int &n:li){  //引用方式遍历
		n = n*n;  //修改n值，li元素值也会改变
	}
	for(int n:li){
		cout<<n<<endl;
	}
    return 0;
}

5.访问list元素

因为list不支持随机访问，所以需要借助迭代器和循环结构来访问list的元素。特殊地，list的front()返回第一个元素，back()返回最后一个元素。

#include<iostream>
#include<list>
using namespace std;
int main()
{
    list<int> li;
    for(int i=1;i<=5;i++) li.push_back(i);    
    cout<<li.front()<<" "<<li.back()<<endl;

    li.front() = 0;         //li.front()还可以赋值
    li.back() = -1;         //li.back()还可以赋值
    cout<<li.front()<<" "<<li.back()<<endl;
    
    //通过迭代器和循环结构获取list的第n个元素（从0开始编号）
    int n = 3; 
    auto it = li.begin();
    for(int i=1;it!=li.end() && i<=n;i++,it++);  //for循环体为空语句
    if(it != li.end()){
        cout<<*it<<endl;
        *it = 123;          //修改list元素的值
        cout<<*it<<endl;
    }
    return 0;
}

6.insert、erase、remove

list提供了insert()用于在指定位置（迭代器）前插入元素，erase()用于删除指定位置（迭代器）的元素，remove()用于移除与参数值相等的所有元素。

#include<iostream>
#include<list>
using namespace std; 
void print(list<int> &li){
	for(auto it=li.begin();it!=li.end();it++) cout<<*it<<" ";
	cout<<endl;
}

//返回指向list第n个元素的迭代器（从0开始编号） 
list<int>::iterator go(list<int> &li,int n){
	auto it = li.begin();
	for(int i=1;it!=li.end() && i<=n;i++,it++);
	return it;
}
int main()
{
	list<int> li;
	for(int i=1;i<=10;i++) li.push_back(i);
	print(li);
	
	//指定迭代器前插入一个元素 
	auto it2 = go(li,3);
	li.insert(it2,-1);
	print(li);
	
	//指定迭代器前插入多个相同元素 
	li.insert(li.begin(),5,-1);
	print(li);
	
	//删除指定迭代器处的元素
	auto it1 = go(li,0);
	li.erase(it1);
	print(li);
	
	//删除区间元素（左闭右开） 
	li.erase(go(li,1),go(li,4));
	print(li);
	
	//移除与参数值相等的所有元素 
	li.remove(-1);
	print(li); 
	 
	return 0;
}

7.其它成员函数

1. resize()改变list元素的数量，可以产生截断或者扩充的效果；
2. swap()与另外一个list交换所有元素；
3. reverse()反转list的所有元素（按逆序重新组织list的所有元素）；
4. sort()对list元素重新排序，使用方法和sort函数相同；
5. remove_if()移除所有符合条件的元素；
6. 一个有序的list调用unique()可以删除list中重复的元素，多次重复的元素只保留第一次出现的。

7.1.reverse()逆序、sort()排序

#include<iostream>
#include<list>
using namespace std; 
void print(list<int> &li){
    for(auto it=li.begin();it!=li.end();it++) cout<<*it<<" ";
    cout<<endl;
}
bool cmp(int x,int y){
    return x%2<y%2;
}
int main()
{
    list<int> li;
    for(int i=1;i<=10;i++) li.push_back(i);
    print(li);
    
    li.reverse();
    print(li);
    
    li.sort();
    print(li);

    li.sort(cmp);
    print(li);
    
    li.sort(greater<int>());
    print(li);
    return 0;
}

7.2.remove_if()移除符合条件的元素

#include<iostream>
#include<list>
using namespace std; 
void print(list<int> &li){
    for(auto it=li.begin();it!=li.end();it++) cout<<*it<<" ";
    cout<<endl;
}

bool judge(int x){
	return x%2==0;
}
int main()
{
    list<int> li;
    for(int i=1;i<=10;i++) li.push_back(i);
    print(li);
    
    //根据judge函数判断每个元素
	//移除符合条件的所有元素（元素为参数调用judge函数返回值为true） 
    li.remove_if(judge);
	print(li);
     
    return 0;
}

7.3.有序list调用unique()清除list中的重复元素

#include<iostream>
#include<list>
using namespace std;

//遍历容器的模板函数 
template<typename Iter>
void list_elements(Iter begin, Iter end){
    while(begin!=end){
    	cout<<*begin<<" ";
    	begin++;
	}
    cout<<endl;    
}

bool judge(double x,double y){
    return (int)x == (int)y;
}
int main()
{
    list<int> li;
    for(int i=1;i<=10;i++) li.push_back(i%2);
    list_elements(li.begin(),li.end());
    
    li.sort();        //排序 
    li.unique();      //清除一个有序list中重复的元素 
    list_elements(li.begin(),li.end());
    
    
    double da[] = {12,12.2,12.4,13.1,13.5,14.7,15.5};
    list<double> dli;
    for(int i=0;i<7;i++) dli.push_back(da[i]);
    list_elements(dli.begin(),dli.end());
    
    //根据条件清除有序list中“重复”的元素
    //以两个元素为参数执行judge函数返回值为true就认为两个元素相同 
    dli.unique(judge);
    list_elements(dli.begin(),dli.end());
    return 0;
}

三、经典例题：约瑟夫问题

约瑟夫问题详见前面教程的介绍：数组例题——约瑟夫问题

#include<iostream>
#include<list>
using namespace std;
int main()
{
	int n,m;
	cin>>n>>m; 
    list<int> li;
    for(int i=1;i<=n;i++) li.push_back(i);
    
    //list中第0个元素“数”1 
    auto it = li.begin();
    int tot = 1;
    //list中还有元素，那么继续 
    while(!(li.empty())){
    	if(tot==m){		//数到m 
    		cout<<*it<<" ";
    		//删除这个元素，下一个元素“数”1 
    		it = li.erase(it);
    		tot = 1;
		}else{
			//数数 
			it++;
			tot++;	
		}
		//考察到最后一个元素的下一个元素，回到第一个元素	
    	if(it==li.end()) it = li.begin();
	}
    return 0;
}