目录
链接
cplusplus.com/reference/list/list/?kw=list
https://cplusplus.com/reference/list/list/?kw=list
前言
list的结构其实就是一个 "带头双向循环链表"，与string和vector相比，list不支持下标+[]的访问，因为链表是由一个节点一个节点连接而成的，空间并不是连续的
1. 迭代器浅解
不同性质的迭代器所支持的功能也不同，这是因为底层结构所决定的
如果我们使用不匹配的迭代器就会出错，比如sort就只能使用随机迭代器，因为其底层函数需要进行 - 的操作，如果是其它迭代器就会报错
list<int> lt(5, 1);
//错误,sort函数的底层要求使用随机迭代器类型
sort(lt.begin(), lt.end()); 
2. 接口
2.1 构造函数
//n个val构造
list<int> lt(5, 1);
//迭代器遍历
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//范围for遍历
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;2.2 push_back
push_back只能尾插单个数据，无法直接插入(3,3)这样类型的函数
//n个val构造
list<int> lt(5, 1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
//迭代器遍历
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
list<A> lt;
A aa1(1, 1);
lt.push_back(aa1);
//匿名对象
lt.push_back(A(2,2));
//报错
//lt.push_back(3, 3);
2.3 emplace_back
也是尾插函数，但是emplace_back可以直接插入(3,3)这样的数据
void test_list2()
{
list<A> lt;
A aa1(1, 1);
lt.push_back(aa1);
lt.push_back(A(2,2));
//lt.push_back(3, 3);
lt.emplace_back(aa1);
lt.emplace_back(A(2,2));
cout << endl;
// 支持直接传构造A对象的参数emplace_back
lt.emplace_back(3, 3);
}
2.4 insert
在指定位置之前插入数据，list中insert使用的是双向迭代器，不是随机迭代器，那么就不能向以前一样使用
//不支持这样
lt.insert(it.begin()+3,30);
list<int> lt(5, 1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
lt.insert(lt.begin(), 10);//在首位前插入数据
//在第k个位置之前插入数据
auto it = lt.begin();
int k = 3;
while (k--)
{
it++;
}
lt.insert(it, 30);
//迭代器遍历
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//范围for遍历
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
2.5 erase
删除指定位置数据
list<int> lt(5, 1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
int x = 0;
cin >> x;
auto it = find(lt.begin(), lt.end(), x);
//如果find没有找到就会返回第二个参数也就是lt.end()
while (it != lt.end())
{
lt.erase(it);
}
//迭代器遍历
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//范围for遍历
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
2.6 reverse
逆置
list<int> lt(5, 1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
lt.reverse();
//迭代器遍历
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//范围for遍历
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
2.7 sort
因为算法库中的sort函数不支持链表，所以链表自实现了一个sort函数来进行排序，默认是升序
如果要降序的话可以使用仿函数来进行降序的调整：
1. lt.sort(greater<int>()) 2. lt.sort(less<int>())
list<int> lt(5, 1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
lt.sort();
//迭代器遍历
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//范围for遍历
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;2.8 merge
merge的作用是将两个有序链表进行合并，合并的前提是有序的
合并计算将second链表合并到first链表，那么second链表就会置空，其合并的原理就是取小的尾插到被合并链表
list<int> first;
first.push_back(1);
first.push_back(2);
first.push_back(3);
first.push_back(4);
list<int> second;
second.push_back(10);
second.push_back(20);
second.push_back(30);
second.push_back(40);
first.merge(second);
//范围for遍历
for (auto e : first)
{
cout << e << " ";
}
cout << endl;
//范围for遍历
for (auto e : second)
{
cout << e << " ";
}
cout << endl; 
2.9 unique
将有序的数据去掉重复的数据
list<int> lt(5, 1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
//范围for遍历
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.unique();
//范围for遍历
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;2.10 splice
剪切
将链表指定的数据剪切到被粘贴的链表中去，被剪切链表中被剪切的数据会直接删除，也可以对自身进行操作，即变化自身链表数据的顺序
void test_list6()
{
// 一个链表节点转移给另一个链表
std::list<int> mylist1, mylist2;
std::list<int>::iterator it;
// set some initial values:
for (int i = 1; i <= 4; ++i)
mylist1.push_back(i); // mylist1: 1 2 3 4
for (int i = 1; i <= 3; ++i)
mylist2.push_back(i * 10); // mylist2: 10 20 30
it = mylist1.begin();
++it; // points to 2
mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4
// mylist2 (empty)
// "it" still points to 2 (the 5th element
// 调整当前链表节点的顺序
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
lt.push_back(6);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
int x = 0;
cin >> x;
it = find(lt.begin(), lt.end(), x);
if (it != lt.end())
{
//lt.splice(lt.begin(), lt, it);
lt.splice(lt.begin(), lt, it, lt.end());
}
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
感谢观看~