大话STL第四期——list双向链表

  书接上期，这一期我们聊聊最后一种顺序容器 list，在实际操作中链表list的使用也尤为频繁

文章目录

什么是list？

list的API使用 

list的构造：

 list赋值和交换：

list的大小操作：

list的插入和删除操作：

list的数据存取操作：

list的反转和排序：

什么是list？

list底层是一个双向链表，是环状的，所以是双向循环链表，因此不支持随机访问，但是由于它链表的特殊结构即它可以在序列已知的任何位置快速插入或删除元素（时间复杂度为O(1)）。并且在 list 容器中移动元素，也比其它容器的效率高。

由于链表存储方式不是连续的内存空间，故迭代器进行+i，-i操作时不一定能找到下一个结点，可能会发生内存越界的问题。因此链表list中的迭代器只支持++和--方式访问内存，属于双向迭代器

注意：使用 list 容器的缺点是，它不能像 array 和 vector 那样，通过位置直接访问元素。举个例子，如果要访问 list 容器中的第 6 个元素，它不支持容器对象名[6]这种语法格式，正确的做法是从容器中第一个元素或最后一个元素开始遍历容器，直到找到该位置。

因此在实际场景中，如果需要对序列进行大量添加或删除元素的操作，而直接访问元素的需求却很少，这种情况建议使用 list 容器存储序列。

list的API使用 

下面我从list的创建和常用的函数使用分模块进行举例演示，初学者可以边看边敲加深印象。

list的构造：

list lst;//list采用模板类实现，对象的默认构造
list(beg,end);//构造函数将[beg,end]区间中的元素拷贝给自身
list(n,elem);//拷贝函数将n个elem拷贝给本身
list(const list &lst);//拷贝构造函数

template<typename T>
void Show(list& lst)
{
	for (list::const_iterator it = lst.begin(); it != lst.end(); ++it)
	{
		cout << *it << " ";
	}
	cout << endl;
}
int main()
{
	list<int> lst;//创建list容器 默认构造
	
	lst.push_back(1);//添加数据
	lst.push_back(2);
	lst.push_back(3);
	Show(lst);
 
	list lst1{ "猴子","八戒" };//初始化列表
    							  //vector deque list map set都可以用初始化列表初始化
	Show(lst1);
 
	//区间方式构造
	list<int>lst2(lst.begin(), lst.end());
	Show(lst2);
 
	//拷贝构造
	list<int>lst3(lst2);
	Show(lst3);
 
	//n个elem
	list<int>lst5(5, 20);
	Show(lst5);
 
}

 list赋值和交换：

assign(beg,end);//将[beg,end]区间中的数据拷贝赋值给本身
assign(n,elem);//将n个elem拷贝赋值给本身
list& operator=(const list& lst);//重载=号
swap(lst);//交换与lst的数据

template<typename T>
void Show(list& lst)
{
	for (list::const_iterator it = lst.begin(); it != lst.end(); ++it)
	{
		cout << *it << " ";
	}
	cout << endl;
}
int main()
{
	list<int> lst;//创建list容器 默认构造
	lst.assign(5, 10);//赋值5个10
	Show(lst);
 
	list<int> lst1;//区间
	lst1.assign(lst.begin(), lst.end());
	Show(lst1);
 
	list<int> lst2 = lst1;//赋值
	Show(lst2);
 
	list<int> lst3{ 5,4,3,2,1 };//初始化列表初始化
	lst2.swap(lst3);//交换二者数据
	Show(lst2);
	Show(lst3);
 
	return 0;
}

list的大小操作：

size();//返回容器中的元素个数
empty();//判断容器是否为空
resize(num);//更改大小，重新指定容器的长度为num，若容器变长，则以默认值填充新位置
	//如果容器变短，则末尾超出容器长度的元素被删除
resize(num,elem);//更改大小，重新指定容器的长度为num，若容器变长，则以elem填充新位置
	//如果容器变短，则末尾超出容器长度的元素被删除

template<typename T>
void Show(list& lst)
{
	for (list::const_iterator it = lst.begin(); it != lst.end(); ++it)
	{
		cout << *it << " ";
	}
	cout << endl;
}
int main()
{
	list<int> lst;//创建list容器 默认构造
	lst.push_back(1);
	lst.push_back(2);
	lst.push_back(3);
	lst.push_back(4);
	Show(lst);
	if (lst.empty())
	{
		cout << "为空" << endl;
	}
	else
		cout << "不空" << endl;
	//重新指定大小
	lst.resize(5);
	Show(lst);
	
	lst.resize(10, 5);
	Show(lst);
	return 0;
 
}

list的插入和删除操作：

insert(const iterator pos, int count, ele);//迭代器指向pos位置插入count个元素ele
insert(const iterator pos, ele);//迭代器指向pos位置插入元素ele的拷贝
insert(const iterator pos, beg,end);//迭代器指向pos位置插入[beg,end]区间的数据
push_back(elem);//尾部插入元素elem
pop_back();//删除最后一个元素
push_front(elem);//在容器开头插入一个元素
pop_front();//删除第一个元素
erase(const iterator start, const iterator end);//删除迭代器start到end间的元素
erase(const iterator pos);//删除迭代器指向的元素
clear();//删除容器中所有元素
remove(elem);//删除容器中所有elem值匹配的元素

template<typename T>
void Show(list& lst)
{
	for (list::const_iterator it = lst.begin(); it != lst.end(); ++it)
	{
		cout << *it << " ";
	}
	cout << endl;
}
int main()
{
	list<int> lst;//创建list容器 默认构造
	//尾插
	lst.push_back(1);
	lst.push_back(2);
	lst.push_back(3);
	//头插
	lst.push_front(1);
	lst.push_front(2);
	lst.push_front(3);
	Show(lst);
	//尾删
	lst.pop_back();
	//头删
	lst.pop_front();
	Show(lst);
	//插入
	lst.insert(lst.begin(), 2, 100);
	Show(lst);
 
	//lst.insert(lst.begin()+2, 2, 100);错误，list迭代器只支持++ --操作
	//不支持+ 或- ，因为链表不能随机访问操作
	//想在链表中加插入，如下操作
	list<int>::iterator it = lst.begin();
	lst.insert(++(++it), 2, 50);
	Show(lst);
	//移除50
	lst.remove(50);
	Show(lst);
	
	//删除区间的链表
	lst.erase(lst.begin(), lst.end());
	Show(lst);
	return 0;
}

list的数据存取操作：

front();//返回容器中第一个数据元素
back();//返回容器中最后一个元素

template<typename T>
void Show(list& lst)
{
	for (list::const_iterator it = lst.begin(); it != lst.end(); ++it)
	{
		cout << *it << " ";
	}
	cout << endl;
}
int main()
{
	list<int> lst{ 1,2,3,4,5,6 };
	//返回首元素
	cout << lst.front() << endl;
 
	//返回最后一个元素
	cout << lst.back() << endl;;
 
	//不可以用[]或at方式访问lsit容器元素
	//原因list本质链表，不是用连续线性空间存储数据，迭代器也是不支持随机访问
	return 0;
}

list的反转和排序：

reverse();//反转链表
sort();//链表排序

template<typename T>
void Show(list& lst)
{
	for (list::const_iterator it = lst.begin(); it != lst.end(); ++it)
	{
		cout << *it << " ";
	}
	cout << endl;
}
bool fun(int v1, int v2)
{
	return v1 > v2;
}
int main()
{
	list<int> lst{ 1,2,3,4,5,6 };
	Show(lst);
 
	lst.reverse();//反转
	Show(lst);
 
	//所有不支持随机访问迭代器的容器，不可以用标准算法
	//不支持随机访问迭代器的容器，内部会提供对应一些算法
	list<int> lst1{ 8,1,4,3,5,6,1,0 };
	lst1.sort();//默认升序
	cout << "排序后:";
	Show(lst1);
 
	lst1.sort(fun);//降序 +自定义的排序规则
	cout << "排序后:";
	Show(lst1);
	return 0;
}

对于自定义类型的list排序示例：

class Person {
 
public:
	string M_name;
	int M_age;
	int M_height;
	Person(string name,int age,int height):M_name(name),M_age(age),M_height(height){}
	
};
template<typename T>
void Show(list& lst)
{
	for (list::iterator it = lst.begin(); it != lst.end(); ++it)
	{
		cout << "姓名: " <<(*it).M_name<<" 年龄:"<< (*it).M_age<<" 身高:" << (*it).M_height;
		cout << endl;
	}
 
}
//自定义排序规则，也可以利用仿函数 后面会讲
bool fun(Person& p1, Person& p2)
{
	//按照年龄升序
	if (p1.M_age == p2.M_age)
	{
		//年龄相同，按照身高降序
		return p1.M_height > p2.M_height;
	}
	else
	return p1.M_age < p2.M_age;
}
int main()
{
	list lst;
	Person p1("张三", 35, 175);
	Person p2("李四", 45, 185);
	Person p3("王五", 30, 180);
	Person p4("刘备", 25, 190);
	Person p5("张飞", 35, 180);
 
	lst.push_back(p1);
	lst.push_back(p2);
	lst.push_back(p3);
	lst.push_back(p4);
	lst.push_back(p5);
 
	Show(lst);
 
	cout << "-----------------------------" << endl;
	cout << "排序后:" << endl;
	lst.sort(fun);
	Show(lst);
	return 0;
 
}

感谢观看！有兴趣可以订阅浏览！STL容器接口众多还有许多算法，一定跟着敲一敲加深印象