目录
一、list 简介
1、list是序列容器，允许在序列中的任何位置执行o(1)时间的插入和删除操作，并且可以在两个方向上进行迭代
2、list的底层是带头结点的双向循环链表，每个节点通过next，prev指针连接成顺序表
3、与其他的序列式容器相比（array、vector、deque），list通常在任意位置的插入、删除元素的执行效率更高（直接插入、删除一个节点，再用指针连接，不存在数据的移动）。但list和forward_list最大的缺陷是不支持随机存取（因为他的迭代器是双向迭代器，而vector的是随机迭代器），只能直接存取首尾的元素，想要获取到其他的元素，只能通过遍历的方式
4、使用链表存储数据，并不会将它们存储到一整块连续的内存空间中。恰恰相反，各元素占用的存储空间（又称为节点）是独立的、分散的，它们之间的线性关系通过指针来维持的
5、存储密度低，list要使用一些额外空间存放next、prev，如果数据域太小，导致存储密度太低
vector、list、deque一般用于存储内置类型，不存储对象，但可存储对象的地址
6、list没有重载operator[] ，因为空间不连续，也没有at函数
7、list是双向迭代器，只能++，--，不能+=，-+，+，-
8、插入元素不会导致迭代器失效，删除元素导致当前迭代器失效
二、list函数
2.1 clear
vector.clear() ：仅删除数据元素，堆区申请的空间仍在
deque.clear() ：删除数据元素，map指针和块也会被清除
list.clear() ：删除数据元素，且每个节点也会被清除
2.2 插入删除
与vector、deque函数类似
list头插，尾插，中间插的时间复杂度都是o(1)
2.3 merge合并2个有序列表
sort：对list元素进行排序（默认升序）
unique：消去合并后的
reverse()：反转元素顺序 如：15，68，10，8 反转后：8，10，68，15
template < class T> void Print(const T&con) { auto it = con.begin(); for (it; it != con.end(); it++) { cout << *it<<" "; } cout << endl; } int main() { list<int>list1; list<int>list2; int n = 10; for (int i = 0; i < n; i++) { int val = rand() % 100; list1.push_back(val); val = rand() % 100; list2.push_back(val); } Print(list1); Print(list2); list1.sort();//默认从小到大排序 list2.sort(); Print(list1); Print(list2); //list1.sort([](const auto& a, const auto& b)->bool{return a > b; });//利用lambda表达式进行降序排序 auto根据实参推演出形参类型 Print(list1); list1.merge(list2);//合并2个有序list，必须同是升序或同是降序 Print(list1); Print(list2);//合并后list2为空 list1.unique();//消去合并list的相同元素 Print(list1); }
三、list静态对象数组
template <class T>
void Print(const T& con)
{
for (auto& x : con)
{
cout << x << " ";
}
}
int main()
{
const int n = 10;
list<int>list2[10];//list2是有10个元素的数组，每个数组里面放的是list对象
for (int i = 0; i < n; i++)
{
list2[i].push_back(rand() % 100);
}
for (int i = 0; i < n; i++)
{
Print(list2[i]);
}
}
四、list 与 vector结合使用
int main()
{
int n, m;
vector<list<int>>arr;
cin >> n;//vector的数据元素是n个list对象
arr.reserve(n);
for (int i = 0; i < n; i++)
{
cin >> m;//每个list里面有m个数据元素
arr.push_back(list<int>());//给vector插入元素，元素类型是list
for (int j = 0; j < m; ++j)
{
arr[i].push_back(rand() % 100);//给存放的list插入数据
}
}
for (int i = 0; i < n; i++)
{
Print(arr[i]);
}
}五、list使用场景
1、频繁的插入和删除操作
2、双向迭代
3、保持元素顺序
4、动态数据结果
5、内存管理