C++系列-STL容器之list

STL容器之list

list容器的基本结构
list容器的特点
- list容器的优点
- list容器的缺点
list容器的构造函数
list容器的常用接口
- list赋值操作
- list大小及空否
- list访问
- list迭代器相关
- list增删查改
- - push and pop
  - insert
  - 其它

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

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

list容器的基本结构

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

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

list容器的特点

list容器的优点

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

list容器的缺点

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

list容器的构造函数

构造函数	说明
list (n, elem)	创建的对象中含有n个elem
list{}	创建的对象中的内容是花括号中的元素
list ()	默认构造，空list
list (const list& x)	拷贝构造
list (InputIterator first, InputIterator last)	用迭代区间 [first, last) 区间中的元素构造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赋值操作

形式	说明
=重载	lst2=lst1
assign({})	用初始化列表中的元素替换容器中原有的内容
assign(n elem)	用n个elem替换容器中原有的内容
assign(iterator first, iterator last)	用[first, last)前闭后开区间的元素替换容器中原有的内容

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>，但是这并不意味着vector已经被实例化了，也就是说当编译器解析
// func时，尚未清楚list到底是什么东西，那么当然也就无法确认list<T>::const_iterator是什么东西了。它可能是
// 一个类型，也可能是static成员。这就会导致歧义出现，编译器无法判断，因此解决方法就是，在嵌套从属类型前面
// 加上typename，告诉编译器这就是一个类型，于是编译器就不会爆出语法错误了。void test01()
{list<int> lst1(5, 10);			// list (n, elem)， 创建的对象中含有n个elem cout << "---------- lst1 ----------" << lst1.size() << endl;print_list<int>(lst1);list<int> lst2 = lst1;			// =重载cout << "---------- lst2 ----------" << lst2.size() << endl;print_list(lst2);				// 函数模板自动类型推导list<int> lst3;lst3.assign(5, 666);			// assign(n, elem)cout << "---------- lst3 ----------" << lst3.size() << endl;print_list(lst3);list<char> lst4;				// assign{初始化列表}lst4.assign({'a', 'b', 'c'});cout << "---------- lst4 ----------" << lst4.size() << endl;print_list<char>(lst4);vector<int> vct1{100, 200, 300, 400};list<int> lst5;					lst5.assign(vct1.begin(), vct1.begin()+2);	// assign(iterator first, iterator last)cout << "---------- lst5 ----------" << lst5.size() << endl;print_list(lst5);				// 函数模板自动类型推导
}
int main()
{test01();system("pause");return 0;
}result:
---------- lst1 ----------5
10 10 10 10 10
---------- lst2 ----------5
10 10 10 10 10
---------- lst3 ----------5
666 666 666 666 666
---------- lst4 ----------3
a b c
---------- lst5 ----------2
100 200

list大小及空否

接口函数	说明
empty()	检测list是否为空，是返回true，否则返回false
size()	返回list中有效节点的个数
resize(num)	重新指定容器的长度为num，若容器变长，则以默认值填充新位置，若容器变短，则末尾超出原容器长度的元素被删除
resize(num，elem)	重新指定容器的长度为num，若容器变长，则以elem填充新位置，若容器变短，则末尾超出原容器长度的元素被删除

list访问

接口函数	说明
front()	返回list的第一个节点中值的引用
back()	返回list的最后一个节点中值的引用

list迭代器相关

接口函数	说明
begin()	返回指向列表第一个元素的迭代器
end()	返回指向列表尾端元素的下一个的迭代器
rbegin()	返回指向从反向数的第一个元素的迭代器
rend()	返回指向从反向数的尾端元素的下一个的迭代器

code:
#include <iostream>
#include <list>
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++)	// 在模板嵌套中，这里要加上typename 表明T是一个模板参数{cout << *it << " ";}cout << endl;
}void test01()
{list<int> lst1;			if (lst1.empty())			// 判断是否为空{cout << "lst1 is empty!" << endl;}cout << "---------- lst1, lst1.size() ----------" << lst1.size() << endl;	// 有效节点个数lst1.assign({ 1,2,3,4 });								// assign初始化赋值cout << "lst1.assign({ 1,2,3,4 })" << endl;print_list<int>(lst1);cout << "lst1.front(): " << lst1.front() << endl;		// front() 头元素cout << "lst1.back(): " << lst1.back() << endl;			// back() 尾元素cout << "* lst1.begin(): " << *lst1.begin() << endl;	// lst1.begin()迭代器指向第一个元素cout << "* (--lst1.end()): " << *(--lst1.end()) << endl;// lst1.end()迭代器指向末尾元素的下一个,--lst1.end()指向末尾元素cout << "* lst1.rbegin(): " << *lst1.rbegin() << endl;cout << "*(--lst1.rend()): " << *(--lst1.rend()) << endl;// resize(num), 添加默认元素lst1.resize(8);cout << "---------- lst1.resize(8), lst1.size()  ----------" << lst1.size() << endl;print_list<int>(lst1);//resize(num，elem), 添加elem元素lst1.resize(10, 666);cout << "---------- lst1.resize(10, 666)), lst1.size()  ----------" << lst1.size() << endl;print_list<int>(lst1);//resize(num，elem), 添加elem元素lst1.resize(3);cout << "---------- lst1.resize(3), lst1.size()  ----------" << lst1.size() << endl;print_list<int>(lst1);
}
int main()
{test01();system("pause");return 0;
}result:
lst1 is empty!
---------- lst1, lst1.size() ----------0
lst1.assign({ 1,2,3,4 })
1 2 3 4
lst1.front(): 1
lst1.back(): 4
* lst1.begin(): 1
* (--lst1.end()): 4
* lst1.rbegin(): 4
*(--lst1.rend()): 1
---------- lst1.resize(8), lst1.size()  ----------8
1 2 3 4 0 0 0 0
---------- lst1.resize(10, 666)), lst1.size()  ----------10
1 2 3 4 0 0 0 0 666 666
---------- lst1.resize(3), lst1.size()  ----------3
1 2 3

list增删查改

push and pop

接口函数	说明
push_front(const T &val)	在list首元素前插入值为val的元素
pop_front()	删除list中第一个元素
push_back(const T &val)	在list尾部插入值为val的元素
pop_back()	删除list中最后一个元素

insert

接口函数	说明
insert(iterator pos, const T &val)	在list position 位置前插入值为val的元素
insert(iterator pos, num, const T &val)	在list position 位置前插入值为num个值为val的元素
insert(iterator pos, begin, end)	在list position 位置前插入值为num个值为val的元素

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;
}void test01()
{// push pop举例list<string> lst1;lst1.push_back("push_back");cout << "---------- push_back ---------- " << lst1.size() << endl;print_list(lst1);lst1.push_front("push_front");cout << "---------- push_front ---------- " << lst1.size() << endl;print_list(lst1);lst1.pop_back();cout << "---------- pop_back ---------- " << lst1.size() << endl;print_list(lst1);lst1.pop_front();cout << "---------- pop_front, lst1.size() ---------- " << lst1.size() << endl;print_list(lst1);// insert举例list<int> lst2{1, 2, 3, 4, 5, 6};lst2.insert(++lst2.begin(), 222);		// insert(iterator pos, const T &val)cout << "---------- lst2.insert(++lst2.begin(), 222), lst2.size() ---------- " << lst2.size() << endl;print_list(lst2);lst2.insert(--lst2.end(), 3, 666);		// insert(iterator pos, num, const T &val)cout << "---------- lst2.insert(--lst2.end(), 3, 666), lst2.size() ---------- " << lst2.size() << endl;print_list(lst2);vector<int> vec1{11, 22, 33, 44};lst2.insert(lst2.end(), vec1.begin(), vec1.begin() + 3);		// insert(iterator pos, begin, end)cout << "---------- lst2.insert(lst2.end(), vec1.begin(), vec1.begin()+3), lst2.size() ---------- " << lst2.size() << endl;print_list(lst2);// erase举例lst2.erase(++lst2.begin());		// erase(iterator pos)cout << "---------- lst2.erase(++lst2.begin()), lst2.size() ---------- " << lst2.size() << endl;print_list(lst2);
}
int main()
{test01();system("pause");return 0;
}result:
---------- push_back ---------- 1
push_back
---------- push_front ---------- 2
push_front push_back
---------- pop_back ---------- 1
push_front
---------- pop_front, lst1.size() ---------- 0---------- lst2.insert(++lst2.begin(), 222), lst2.size() ---------- 7
1 222 2 3 4 5 6
---------- lst2.insert(--lst2.end(), 3, 666), lst2.size() ---------- 10
1 222 2 3 4 5 666 666 666 6
---------- lst2.insert(lst2.end(), vec1.begin(), vec1.begin()+3), lst2.size() ---------- 13
1 222 2 3 4 5 666 666 666 6 11 22 33
---------- lst2.erase(++lst2.begin()), lst2.size() ---------- 12
1 2 3 4 5 666 666 666 6 11 22 33

其它

接口函数	说明
erase(iterator pos)	删除list position位置的元素
lst1.swap(lst2)	交换两个list中的元素
clear()	清空list中的有效元素
remove(const T &val)	删除列表中所有指为val的元素
reverse()	反转列表
sort()	对列表排序

code:
#include <iostream>
#include <list>
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;
}void test01()
{list<int> lst1{1,2,3,4,5,6};list<int> lst2{99, 88, 77, 66};// swap 举例cout << "---------- before swap,lst1, lst2 ---------- " << endl;print_list(lst1);print_list(lst2);cout << "---------- after swap,lst1, lst2 ---------- " << endl;lst1.swap(lst2);print_list(lst1);print_list(lst2);// remove举例cout << "---------- lst2.insert(--(--lst2.end()), 3, 666) ---------- " << endl;lst2.insert(--(--lst2.end()), 3, 666);print_list(lst2);lst2.remove(666);cout << "---------- lst2.remove(666), lst2.size() ---------- " << lst2.size() << endl;print_list(lst2);// reverse举例lst2.reverse();cout << "---------- lst2.reverse() ---------- " << endl;print_list(lst2);// clear举例lst2.clear();cout << "---------- lst2.clear(), lst2.size() ---------- " << lst2.size() << endl;print_list(lst2);// sort举例list<int> lst4{23, 1, 56, 78, 44, 35, 99, 76};cout << "---------- before sort, lst4 ---------- " << endl;print_list(lst4);cout << "---------- after sort, lst4 ---------- " << endl;lst4.sort();print_list(lst4);
}
int main()
{test01();system("pause");return 0;
}result:
---------- push_back ---------- 1
push_back
---------- push_front ---------- 2
push_front push_back
---------- pop_back ---------- 1
push_front
---------- pop_front, lst1.size() ---------- 0---------- lst2.insert(++lst2.begin(), 222), lst2.size() ---------- 7
1 222 2 3 4 5 6
---------- lst2.insert(--lst2.end(), 3, 666), lst2.size() ---------- 10
1 222 2 3 4 5 666 666 666 6
---------- lst2.insert(lst2.end(), vec1.begin(), vec1.begin()+3), lst2.size() ---------- 13
1 222 2 3 4 5 666 666 666 6 11 22 33
---------- lst2.erase(++lst2.begin()), lst2.size() ---------- 12
1 2 3 4 5 666 666 666 6 11 22 33