博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
STL源码解析-04序列容器-02list
阅读量:4698 次
发布时间:2019-06-09

本文共 1765 字,大约阅读时间需要 5 分钟。

************************************************
 * list的实现其数据结构是双向链表。
 * 特点:
 * 不保证存储空间的连续性
 * 迭代器必须具备前移和后移的能力,提供++(链表的next操作),--(链表的prev操作),==,!=等操作的重载
 * 插入操作和删除操作不会造成原有list迭代器失效
 * ************************************************
 
 
******************************************
 * 在SGI的STL中,list采用的循环双向链表,因此只有一个头指针p,p->next是begin,p直接就是end,满足左闭右开的原则。
 * 空链表时有一个节点,但是size()返回0.
 * push_back,push_front其实调用的是insert操作,insert(end(),t), insert(begin(),T)
 * pop_back,pop_front也是通过调用erase操作。
 * splice,将链表中制定的内容进行接和。将一个链表中的一部分移动并插入到另一个链表的制定位置,这两个链表可以是一个。
 * reverse,将链表反转,依次将后面的节点插入到跟节点之后。
 * sort,采用快速排序算法。
 * list 不能使用STL 算法 sort(),必须使用自己的 sort() member function,
 * 因为STL算法sort() 只接受RamdonAccessIterator.
 * 本函式采用 quick sort.
// template <class T, class Alloc>
// void list<T, Alloc>::sort() {
// 以下判断,如果是空白串行,或仅有一个元素,就不做任何动作。
// if (node->next == node || link_type(node->next)->next == node) return;
//
// 一些新的 lists,做为中介数据存放区
// list<T, Alloc> carry;
// list<T, Alloc> counter[64];
// int fill = 0;
// while (!empty()) {
//     carry.splice(carry.begin(), *this, begin()); //取出list中的一个数据,存入carry
//     int i = 0;
//     while(i < fill && !counter[i].empty()) {
//      counter[i].merge(carry);                   //将carry中的数据,和 counter[i]链中原有数据合并
//      carry.swap(counter[i++]);                  //交换carry 和counter[i] 数据
//     }
//     carry.swap(counter[i]);        
//     if (i == fill) ++fill;
//  }
// for (int i = 1; i < fill; ++i)                   // sort之后,善后处理,把数据统一起来
//   counter[i].merge(counter[i-1]);
//   swap(counter[fill-1]);
// }
// 看起来其实是合并排序,分配了64个list,fill表示目前用到第几个list,每一个list的容量是2^index个元素。
// 将前两个元素归并,再将后两个元素归并,归并这两个小子序列成为4个元素的有序子序列;
// 重复这一过程,得到8个元素的有序子序列,16个的,32个的。。。,直到全部处理完。
// 主要调用了swap和merge函数,而这些又依赖于内部实现的transfer函数(其时间代价为O(1))。
 * *********************************************

转载于:https://www.cnblogs.com/shaotenghan/archive/2011/12/02/2272132.html

你可能感兴趣的文章
[CCF2015.09]题解
查看>>
[NYIST15]括号匹配(二)(区间dp)
查看>>
json_value.cpp : fatal error C1083: 无法打开编译器生成的文件:No such file or directory
查看>>
洛谷 P1101 单词方阵
查看>>
Swift DispatchQueue
查看>>
C#和JAVA 访问修饰符
查看>>
小甲鱼OD学习第1讲
查看>>
HDU-1085 Holding Bin-Laden Captive-母函数
查看>>
php提示undefined index的几种解决方法
查看>>
LRJ
查看>>
Struts2环境搭建
查看>>
Linux: Check version info
查看>>
stl学习之测试stlen,cout等的运行速度
查看>>
魔戒三曲,黑暗散去;人皇加冕,光明归来
查看>>
Error和Exception
查看>>
Python和Singleton (单件)模式[转载]
查看>>
httpclient设置proxy与proxyselector
查看>>
IT常用单词
查看>>
拓扑排序
查看>>
NYOJ--32--SEARCH--组合数
查看>>