C++系列-STL容器之list

寄扬州韩绰判官
杜牧〔唐代〕

青山隐隐水迢迢，秋尽江南草未凋。
二十四桥明月夜，玉人何处教吹箫？

list容器的基本结构

list容器的内部结构是双向循环链表，主要由一系列的节点组成，每个节点包含3个部分

• 数据域：存储实际的元素值。
• 前向指针：指向链表中的前一个节点。
• 后向指针：指向链表中的后一个节点。
• 整个list通过这些节点的指针指向互相连接，形成一个有序的序列。头节点不放实际数据，只放下一个节点的指针。
• 每个节点中的previous指针指向前一个节点，next指针指向后一个节点。最后一个节点的next指向头节点，头节点的previous指针最后一个节点。
  

list容器的特点

list容器的优点

• 采用动态存储分配，内存分配更灵活，不会造成内存的浪费和溢出。
• 执行插入和删除不需要移动大量的元素，只需要修改节点中的指针，在频繁插入和删除的情况下，高效。
• 提供反向迭代器，可以方便地从后向前遍历list。
• 插入操作不会造成原有的list迭代器失效，只是修改了节点中的指针指向关系。
• 删除操作中指向被删除节点的迭代器会失效，其余的迭代器并不失效。

list容器的缺点

• 空间(指针域占用空间)和时间(遍历)额外耗费较大，不如vector。
• 不能支持迭代器任意位置，迭代器计算只支持++或者–。

list容器的构造函数

code:
#include <iostream>
#include <list>
#include <vector>
using namespace std;

template<typename T>
void print_list(const list<T>& lst)
{
   
	for (list<int>::const_iterator it = lst.begin(); it != lst.end(); it++)  // 不能<哪个迭代器
	{
   
		cout << *it << " ";	
	}
	cout << endl;
}

void test01()
{
   
	list<int> lst1(5, 10);		// list (n, elem), 创建的对象中含有n个elem 
	cout << "---------- lst1 ----------" << lst1.size() << endl;
	cout << "lst1.size(): " << lst1.size() << endl;
	print_list(lst1);

	list<int> lst2{
   1, 2, 3};	// list{}, 利用{}创建对象
	cout << "---------- lst2 ----------" << lst1.size() << endl;
	print_list(lst2);

	list<int> lst3(lst2);		// 拷贝构造
	cout << "---------- lst3 ----------" << lst1.size() << endl;
	print_list(lst3);

	list<int> lst4;				// 默认构造
	lst4.push_back(666);
	lst4.push_back(888);
	lst4.push_front(1);
	cout << "---------- lst4 ----------" << lst4.size() << endl;
	print_list(lst4);

	vector<int> v1{
    11, 22, 33, 44, 55 };
	list<int> lst5(v1.begin(), v1.begin() + 3);	// 迭代区间构造
	cout << "---------- lst5 ----------" << lst5.size() << endl;
	print_list(lst5);
}
int main()
{
   
	test01();
	system("pause");
	return 0;
}

result:
---------- lst1 ----------5
lst1.size(): 5
10 10 10 10 10
---------- lst2 ----------5
1 2 3
---------- lst3 ----------5
1 2 3
---------- lst4 ----------3
1 666 888
---------- lst5 ----------3
11 22 33

list容器的常用接口

list赋值操作

code:
#include <iostream>
#include <list>
#include <vector>
using namespace std;

template<typename T>
void print_list(const list<T>& lst)
{
   
	for (typename list<T>::const_iterator it = lst.begin(); it != lst.end(); it++)
	{
   
		cout << *it << " ";	// 返回第一个元素
	}
	cout << endl;
}
// 在这里存在模板的嵌套，list<T>::const_iterator这个类型就是list模板中的类型，而且嵌套在了模板函数func当中，
// 当实例化func时，vector<T>变成了vector<int>，