C++ STL序列容器-------list
目录
一、list 简介
二、list函数
2.1 clear
2.2 插入删除
2.3 merge合并2个有序列表
三、list静态对象数组
四、list 与 vector结合使用
五、list使用场景
一、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 void Print(const T&con){auto it = con.begin();for (it; it != con.end(); it++){cout << *it<<\" \";}cout << endl;}int main(){listlist1;listlist2;int n = 10;for (int i = 0; i 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 void Print(const T& con){for (auto& x : con){cout << x << \" \";}}int main(){const int n = 10;listlist2[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>arr;cin >> n;//vector的数据元素是n个list对象arr.reserve(n);for (int i = 0; i > m;//每个list里面有m个数据元素arr.push_back(list());//给vector插入元素，元素类型是listfor (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、内存管理
