list容器的使用
list的很多接口的功能及使用上都和string及vector那里类似 在熟悉了string和vector之后 list的使用上也很好理解 但是因为list物理空间上不连续 和之前的string及vector不一样 所以在list中也有些东西需要我们注意
如下 这里尾插四个int类型的值之后 可以用迭代器和范围for的方式打印 但是在list中没有重载[] 所以这里不能用类似数组的方式访问打印了
之前的string及vector他们物理空间上是连续的 所以重载[]访问里面某个元素时候可以找到 时间复杂度为O(1)
但是list存放的数据在物理结构上不是连续的 要用[]的方式访问某一个元素的时候很麻烦 所以在list中没有重载[] 其实理论上可以实现这样的接口 但是时间复杂度高为O(N)在list中就没有实现这样的接口
因为list物理空间上不连续的原因 除了没有实现[]接口之外 在需要传迭代器的地方还不能直接传迭代器+常数的方式 如下面第二行erase和第四行insert的使用上报错了
之前因为string和vector物理空间上就是连续的 所以迭代器可以直接用加常数的方式到下一个位置来访问下一个元素 但是list物理空间上不是连续的 迭代器加常数就不知道到哪里了
之前迭代器根据功能划分 可以分为
iterator reverse_iterator const_iterator const_reverse_iterator这四种
其实根据性质还可以分为 单向迭代器 双向迭代器 随机迭代器 这三种
之前学过的string和vector就是随机迭代器 这里的list就是双向迭代器
随机迭代器支持++ -- + -这样的运算 双向迭代器支持++ --的运算 而对于单向的就只支持++ 另外三个都不支持
这里的性质其实是根据他们的底层结构划分 如vector和string实际的结构就是顺序表物理空间上是连续的 根据底层结构又可以决定他们支持哪些算法
如algorithm算法库中的sort 其支持随机迭代器 可以把string和vector类型的对象进行排序 但是双向迭代器类型的list就不能使用 其实就是sort的实现用到的是快排的方式 而快排中的三数取中等逻辑只支持物理空间上连续的结构
如下图使用时候 list类型的ll不支持 vector和string可以使用sort排序 (这里的string是根据ASCII来排序的)
algorithm算法库中的reverse 就支持Bidirectional Iterator 也就是双向迭代器 list就可以使用
但其实也支持随机迭代器 因为其实单向迭代器 双向迭代器 随机迭代器之前是有包含关系的
单向迭代器可以看做一种特殊的双向迭代器 双向迭代器也可以看做一种特殊的随机迭代器
也可以根据算法里面用到的逻辑来理解 如下这里的reverse实现中用到了++ -- 对于随机迭代器和双向迭代器都支持 但是单向迭代器只支持++ 所以reverse不支持单向迭代器
其实单向迭代器 双向迭代器 随机迭代器这三种迭代器之间的这种包含关系是和之后的继承有关 这里先以包含的方式理解
其实除了这三种迭代器之外还有 Input和Ouput这两种 而这两种迭代器又可以看作是特殊的单向迭代器 但这两种基本没什么用处
如同样在算法库中的find支持Input类型的迭代器 根据上面他们的包含关系 那么find自然也支持单向迭代器 双向迭代器和随机迭代器
如下图 同样可以用算法实现的过程来理解 这里的实现只用到了++ 那么三种迭代器自然都支持
emplace_back
要理解emplace_back还需要很多没有学过的知识 这里就只是简单的使用一下
使用上和push_back没什么区别
但是如果尾插自定义类型对象的时候 两者都可以使用创建自定义类型对象插入该对象的方式 或者匿名对象的方式 但是我们想直接传3,3来构造AA类型并尾插这样的功能时 push_back因为只能传一个参数不能这样子 但是emplace_back可以这样使用
而且emplace_back额外支持的另一种方式直接进行了构造 而对于前两种都是先调用了一次构造又调用了一次拷贝构造
由于链表物理空间上不连续的结构 erase和insert在插入时候不可以用迭代器+常数的方式
如下 一个list类型的对象ll 尾插了六个数 我们想删掉下标为3位置的数据 不可以在erase里面直接写ii+
3的方式 可以先将ii++三次之后再传过去 这里的++因为重载过了可以实现找到下一个位置的功能
结合find使用就可以选择要删除的元素
之前说算法库中的sort不支持双向迭代器的list 但是在list类里面实现了排序的sort 如下可以进行排序
但是这样只能正序排序 怎样进行逆序排序呢
实现逆序排序可以用到仿函数的方式 下面的less和greater 现在先了解一下知道如何使用 在后面的内容再详细学习 有了less和greater模版类型的对象之后 sort里面传的是less的对象就是正序 greater的就是逆序
只需要传这两种类型的对象 那其实可以不用创建对象再传对象的方式 也可以直接用匿名对象的方式
merge
merge会把里面的list对象l2的内容剪切到lt中并排序好(其实里面的过程是先将两个list类型的对象分别排序好 然后按照类似于归并排序那里的方式每次从两个中找小的放到一个新的对象中 结束之后再把内容拷到lt中) merge之后 l2对象会清空
unique
unique用于对list的去重 把里面重复的内容给清掉只剩一个 但是需要list是已经排序好的 如果没有排序好就不能实现功能 如下图 (其实就是用到双指针的方法进行去重)
splice
对于第一行的 将一个链表完整的转移到另一个链表的某个位置
第二行的 把一个链表某一位置的值转移到另一个链表的某一个位置
第三行的功能是将某一个链表的迭代器区间内的值移动到另一个链表的某一个位置
splice除了对其他的链表使用外 还可以对自己使用 如下图 c为链表lt中值为3的位置 将lt从该位置到最后一个位置的值全部转移到刚开始的位置
list的sort排序速度问题
1.
如下图 vector和list类型的对象里面有一百万个相同的随机数 对里面的数分别进行排序 分别计算两者排序所花费的时间
事实上排序时间上vector要明显的高于list 但是在Debug下vector可能还比list慢 因为vector的排序用到了快排里面可能有很深的递归 在Debug下没有优化的情况就可能造成这样的结果 而在Release下vector就明显快于list了
2.
在vector实现那里提到过 vector的构造函数用迭代器方式实现构造的话 就可以用list的迭代器来构造一个vector类型的对象 在vector里面排序好之后再拷回list对象中 这可以用于排序list类型的对象
如下图创建两个一百万个相同数据的lt1和lt2 对lt1就用list里面的sort排序 对lt2先用lt2的迭代器来构造一个vector类型的对象 然后用算法库中的sort对vector对象进行排序 之后再拷贝回去 根据结果可以看到 lt1明显快于lt2 侧面也反映出拷贝其实也是很快的
所以 如果list类型对象里面数据少的时候可以直接用list里面的sort排序
但是当如果数据多的情况 建议先把list里面的内容拷贝到vector类型的对象里面 然后再用算法库里面的sort排序 之后再拷贝回去给list类型的对象