list部分接口介绍

文章目录

• list部分接口介绍
• • resize
  • erase
  • operation系列接口
  • • remove
    • sort
    • • 迭代器种类
    • unique
    • merge
    • reserve
    • splice
  • 总结

resize

这个一旦小于原先的大小就会释放掉空间！

erase

这个会直接导致迭代器失效！

operation系列接口

remove

就是find + erase

如果这个值有就删除，没有就无事发生！

remove(x);

sort

为什不用库里面的sort而是要自己提供一个呢？

list的迭代器种类是一个双向的！

库里面的期望的是一个随机的

链表的排序是一个归并排序！

迭代器种类

1. 单向 ++——像是单链表只能++
2. 双向 ++/-- ——双向链表
3. 随机 ++/-- / + / - 能支持这四种操作的就是随机迭代器

库里的sort

可以从模板的名字看出其实他是希望我们给它传一个随机迭代器

库里面的排序是一个快速排序

unique

这个接口是用来去重的！

但是去重要在排序的基础上！否则会失效

为什么不内部自己排序一下呢？

因为如果这个链表开始就是有序的话，不就白费功夫了

所以就是将去重和排序分开了

merge

合并链表！将两个链表合并成为一个！

合并后x这个链表是空的！

reserve

逆置链表

算法库里面的也可以

splice

将另一个链表的节点转移到这个链表上！

1. 全部转移
2. 从i位置开始转移
3. 给一个迭代器区间进行转移

是插入到前面

总结

上面的接口其实使用的都不多！

包括sort！

sort的性能测试！

#define _CRT_SECURE_NO_WARNINGS 1 
#include
#include
#include
#include
using namespace std;#include
void test_op()
{srand(time(0));const int N = 10000000;vector v;v.reserve(N);list lt1;for (int i = 0; i < N; ++i){auto e = rand();v.push_back(e);lt1.push_back(e);}int begin1 = clock();sort(v.begin(), v.end());int begin2 = clock();int end1 = clock();lt1.sort();int end2 = clock();printf("vector sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);
}
int main()
{test_op();return 0;
}

效率特别的低下！

甚至不如将list拷进vector后然后排序最后拷贝回来！

#define _CRT_SECURE_NO_WARNINGS 1 
#include
#include
#include
#include
using namespace std;#include
void test_op()
{srand(time(0));const int N = 10000000;vector v;v.reserve(N);list lt1;list lt2;for (int i = 0; i < N; ++i){auto e = rand();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;//然后从vector拷回来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);
}
int main()
{test_op();return 0;
}

即使如此速度依旧比单纯的list的sort更快！

所以大数据量的时候不要使用list的sort！

数据量小的时候还好！一旦数据量大起来的时候就不要使用list的sort！

虽然list是归并排序但是链表在数据量大之后空间的访问效率还是很低下的

所以排序使用vector

要头插头删用链表