Operations
remove
remove 相当于 find + erase，如果想要删除的元素不错在，也不会报错。
void TestList6() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(3); lt.push_back(4); lt.remove(3); for (auto e : lt) { cout << e << " "; } cout << endl; }
sort
void TestList7() { list<int> lt; lt.push_back(10); lt.push_back(2); lt.push_back(5); lt.push_back(3); lt.push_back(4); lt.push_back(4); lt.push_back(6); lt.push_back(4); lt.push_back(0); lt.sort(); for (auto e : lt) { cout << e << " "; } cout << endl; }
算法库不是用排序函数吗，为什么 list 还要自己实现一个 sort 函数呢？这就要知道迭代器的分类了。
迭代器的分类 1.单向 只能++ 2.双向 可以++和-- 3.随机 可以++ -- + -
算法库中的 sort 函数是快速排序，需要支持随机访问和指针相减，否则三数取中无法支持。而 list 中的节点地址是随机的，无法通过指针相减来得到元素的个数。所以，需要为 list 单独设计一个 sort 函数。注：list 的 sort 函数是用归并排序实现的。
排序性能的比较
vecor 和 list 的比较
// N个数据需要排序，vector+ 算法sort list+ sort void Test() { srand(time(0)); const int N = 100000; vector<int> v; v.reserve(N); list<int> lt1; list<int> lt2; for (int i = 0; i < N; ++i) { auto e = rand(); v.push_back(e); //lt1.push_back(e); lt2.push_back(e); } int begin1 = clock(); sort(v.begin(), v.end()); int end1 = clock(); int begin2 = clock(); lt2.sort(); int end2 = clock(); printf("vector sort:%d\n", end1 - begin1); printf("list sort:%d\n", end2 - begin2); }
先用 vector 排序后，再将数据拷贝回 list 中
// N个数据需要排序，vector+ 算法sort list+ sort void Test() { srand(time(0)); const int N = 1000000; vector<int> v; v.reserve(N); list<int> lt1; list<int> lt2; for (int i = 0; i < N; ++i) { auto e = rand(); //v.push_back(e); lt1.push_back(e); lt2.push_back(e); } // 拷贝到vector排序，排完以后再拷贝回来 int begin1 = clock(); for (auto e : lt1) { v.push_back(e); } sort(v.begin(), v.end()); size_t i = 0; for (auto& e : lt1) { e = v[i++]; } int end1 = clock(); int begin2 = clock(); lt2.sort(); int end2 = clock(); printf("vector sort:%d\n", end1 - begin1); printf("list sort:%d\n", end2 - begin2); }
list 的排序总体来说还是比 vector 的排序要慢得，所以个人不太推荐使用 list 的进行排序。
unique
unique 是一个去重函数，该函数需要在排完序后才能够使用。
void TestList8() { list<int> lt; lt.push_back(10); lt.push_back(2); lt.push_back(5); lt.push_back(3); lt.push_back(4); lt.push_back(4); lt.push_back(6); lt.push_back(4); lt.push_back(0); // 先排序，才能去重 lt.sort(); lt.unique(); //sort(lt.begin(), lt.end()); for (auto e : lt) { cout << e << " "; } cout << endl; }
splice
splice 可以将链表中的节点转移到另一个链表中。
void TestList9() { list<int> lt1; lt1.push_back(1); lt1.push_back(1); lt1.push_back(1); list<int> lt2; lt2.push_back(2); lt2.push_back(3); lt2.push_back(4); lt2.push_back(5); lt1.splice(lt1.end(), lt2); for (auto e : lt1) { cout << e << " "; } cout << endl; cout << lt1.size() << endl; cout << lt2.size() << endl; }
👉vector 和 list 的对比👈
vector list -------------------------------------------- 底层结构 动态顺序表，一段 带哨兵位头节点 连续的空间 的双向循环链表 -------------------------------------------- 随机访问 支持随机访问，访 不支持随机访问， 问某个元素效率O(1) 访问某个元素效率O(N) -------------------------------------------- 插入和删除 任意位置插入和删除 任意位置插入和删除 效率低，需要搬移元素， 效率高，不需搬移元 时间复杂度为O(N)， 素，时间复杂度为O(1) 插入时有可能需要增容 增容：开辟新空间，拷 贝元素，释放旧空间， 导致效率更低 -------------------------------------------- 空间利用率 底层为连续空间，不容 底层节点动态开辟， 易造成内存碎片，空间 小节点容易造成内 利用率高，缓存利用率 存碎片，空间利用率 高 低，缓存利用率低 -------------------------------------------- 迭代器失效 在插入元素时，要给所 插入元素不会导致迭 有的迭代器重新赋值， 代器失效，删除元素 因为插入元素有可能 时，只会导致当前迭 会导致重新扩容，致使 代器失效，不会影响 原来迭代器失效，删除 其他迭代器 时，当前迭代器需要重 新赋值否则也会失效 -------------------------------------------- 使用场景 需要高效存储，支持随 大量插入和删除操作， 机访问，不关心插入删 不关心随机访问 除效率
👉总结👈
本篇博客主要介绍了 list 的常用的函数接口，难度不是很大。那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️
