php网站开发预算文档,开个做网站要多少钱,php下载站源码,色无极网站正在建设中在了解了vector之后#xff0c;我们只需要简单学习List与vector不一样的接口即可 1.list的基本接口
1.1 iterator
list中#xff0c;与vector最大的区别就是迭代器由随机迭代器变成双向迭代器 string和vector中的迭代器都是随机迭代器#xff0c;支持-等#xff0c;而LIS… 在了解了vector之后我们只需要简单学习List与vector不一样的接口即可 1.list的基本接口
1.1 iterator
list中与vector最大的区别就是迭代器由随机迭代器变成双向迭代器 string和vector中的迭代器都是随机迭代器支持-等而LIST的双向迭代器不支持双目运算 -, 只支持弹幕运算 -- vector中对于迭代器的解释
list中对于迭代器的解释双向带头链表(bidirectional iterator) 双向迭代器不支持 -的原因 效率低毕竟链表无法随机访问 自然也无法方括号访问 1.2 sort 由于排序算法的底层是快排而快排不支持随机迭代器“RandomAccessIterator” 并且双向迭代器不支持迭代器相减快排中有一些三数取中的操作无法进行所以不能使用std中的sort否则在运行时会有运行错误 因此链表中有自己的sort底层是归并排序 升序 降序正如演示中的代码链表的构造函数用法与vector一致 1.3两个建议先排序再使用的函数
li.unique();
li.merge(li1);
unique即去重将重复的元素去掉。 先排序再去重否则去不干净 不排序就去重在相同元素未连续的情况下是无法起到效果的 先降序 merge,即合并 因为其原理是用双指针取小的尾差所以先排序再合并就能将两个元素中一样的元素有序合并到一起
2.list中排序的效率问题
C语言数据结构基础——排序-CSDN博客
链表的排序复杂度和vector的排序复杂度都是O(nlogn)
但是vector的效率几乎稳定在list自带sort的2~5倍左右
测试代码
void effciency_test() {srand(time(0));//初始化时间种子避免伪随机数int N 100000000;vectorint v;for (int i 0; i N; i) {v.push_back(i rand());}listint li;for (int i 0; i N; i) {li.push_back(rand() i);}size_t begin1 clock();sort(v.begin(), v.end());size_t end1 clock();size_t begin2 clock();li.sort();size_t end2 clock();cout time of vector : end1 - begin1 endl;cout time of list : end2 - begin2 endl;
}
debug版本下两倍左右 realease版本下五倍左右 建议的方法是先将链表的内容拷贝到一个vector然后再对vector进行sort 我们拷贝之后再进行测试 只有少量数据时不太在乎效率的时候使用list自带的sort 3.结合splice剪切函数 中间的list x表示会有元素被转出的链表
注意不是复制就是把节点转移进去。
观察官网中的例子 这样操作之后链表1就是1 10 20 30 2 3 4 链表2就是empty 由于其不存在复制的问题我们还可以通过splice函数的功能将其自己的元素调换位置 测试函数
void test_of_splice() {listint li1{ 1,2,3,4,5 };listint li2{ 1,2,3,4,5 };listint li3{ 1,2,3,4,5 };listint li{ 2,5,99,89,68 };li1.splice(li1.begin(), li);//entire list//li2.splice(li2.begin(), li, --li.end());//single element//li3.splice(li3.begin(), li, li.begin(), find(li.begin(), li.end(), 89));//element rangefor (auto e : li1) {cout e ;}cout endl;for (auto e : li) {cout e ;}cout endl;for (auto e : li) {cout e ;}cout endl;}
由于splice会让被移动的元素离开原链表所以建议一次一次的测试。
