c++序列式容器（二）：list
发布于2020-03-14 18:38 阅读(1311) 评论(0) 点赞(5) 收藏(0)
1. 实现原理
list由一个环状的双向链表构成，存有一个node指针，指向置于尾端的空白节点，从而满足stl“前闭后开”的规范。
内存结构如下：
方法begin返回的是(*node).next，方法end返回的即是node自身。常用方法有：
push_front, push_back 从前和后插入节点
erase 移除节点
pop_front, pop_back 移除头，尾节点
clear 通过node遍历节点并销毁
remove 遍历移除传入数值一样的所有节点
unique 将连续且数值相同的节点，移除只剩一个
splice 接合指定列表
merge 合并列表，两个list都是经过排序的递增序列
reverse 反向list，遍历节点，利用transfer将后续节点总是迁移到begin节点之前
sort 有两层while循环，外层循环主要取出元素，内层循环维护了一个list数组，数组中的每个list存放最大长度为2的(n)次幂，最后再将list数组合并。核心代码如下：
// carry 是辅助list存储
while(!empty()){
carry.splice(carry.begin(), *this, begin()); // 取出一个元素
int i=0;
// 随着循环i的递增，当counter[i]非空，会将counter[i]与carry合并，并与carry交换，即carry会保存合并后的序列，直到counter[i]为空，因为是翻倍往上堆叠，所以个数呈现2的指数次幂。
while(i<fill && !counter[i].empty()){
counter[i].merge(carry);
carry.swap(counter[i++]);
}
// 将合并后的carry序列和counter[i]交换
carry.swap(counter[i]);
if (i==fill) ++fill;
}
原文链接:https://blog.csdn.net/formst001/article/details/104825471
所属网站分类: 技术文章 > 博客
作者：恋爱后女盆友的变化
链接：https://www.pythonheidong.com/blog/article/259374/8dd431143d33ad9b121d/
来源：python黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容：(最多支持255个字符)
---无人问津也好，技不如人也罢，你都要试着安静下来，去做自己该做的事，而不是让内心的烦躁、焦虑，坏掉你本来就不多的热情和定力