- 浏览: 229721 次
- 性别:
- 来自: 昆明
文章分类
最新评论
-
beiyangshuishi:
确实挺幽默的,太能恶搞了。不过这也让我想起日本的一则广告宣纸的 ...
一对活宝—— MySQL & PostgreSQL -
ShiningRay:
稍微看了vcf的api,比wxwidgets要干净得多
VCF 库的搞笑提示 -
Colorful:
Wow, this is amazing.
D语言 struct constrcutor 的 bug -
oldrev:
楼下,当时的 TRAC 确实说是要 py 2.4 的
出色的开源项目管理软件——Redmine -
jusdao:
...Trac可以用python2.5啊,没有说必须用2.4的 ...
出色的开源项目管理软件——Redmine
参考 STL 实现的 Quick & Dirty 双向链表模板类,勉强看的过去。参考了 boost 的新概念迭代器,遵循D的命名风格,只实现了几个简单的成员函数。
迭代器使用 i.current属性或i()读取当前指向的元素,使用 i = x; 设置当前指向的元素
update:
添加了 ReverseIterator, rbegin, rend, insert, erase, popBack, popFront
D 的函数模板特化还是有问题(或者我不知道?)
Traversal 和 ValueAccess 是给算法重载用的
迭代器使用 i.current属性或i()读取当前指向的元素,使用 i = x; 设置当前指向的元素
update:
添加了 ReverseIterator, rbegin, rend, insert, erase, popBack, popFront
D 的函数模板特化还是有问题(或者我不知道?)
D 代码
- // The STL-Like Template Class of Linked List
- // Author: Oldrev ( oldrev at gmail dot com)
- // License: BSD
- import std.stdio;
- // 越靠后的功能越多,后面的肯定包括前面的功能
- enum Traversal
- {
- // 支持的操作 ++i i++ *i++
- Incrementable,
- // ++i, a==b, a!=b
- SinglePass, //单遍,中途不能停
- // X u, ++i
- ForwardTraversal, //单向
- // --r, r--
- Bidirectional, //双向
- // r += n, a+n,n+a r-=n, a-n, b-a; a[n], a[n]=v, a
- RandomAccess //几乎就是数组
- }
- enum ValueAccess
- {
- Readable, // value = *a
- Writable, // *a = value
- Swappable, // swap(a, b)
- Lvalue
- // 返回引用? D没有显式引用,那就不支持吧
- }
- private void swap_(T)(inout T x, inout T y)
- {
- T t = x;
- x = y;
- y = t;
- }
- // 约定每个迭代器实现里需要有:
- // 一个 Traversal 型常量 TraversalCatalog 指示迭代器遍历方式类型
- // 一个 ValueAccess 型常量 ValueAccessCatalog 指示迭代器值访问类型
- // 这样算法可以通过 D 的 int 模板参数重载算法实现函数
- class List(EleType)
- {
- public alias EleType ValueType;
- public alias ValueType* PtrType;
- public alias List!(ValueType) SelfType;
- private struct Node
- {
- ValueType data;
- Node* prev;
- Node* next;
- static void join(Node* first, Node* second)
- {
- assert(first !is null);
- assert(second !is null);
- first.next = second;
- second.prev = first;
- }
- }
- // List 类的迭代器基模板
- private template IteratorBase(IterType)
- {
- public const Traversal TraversalCatalog = Traversal.Bidirectional;
- public const ValueAccess ValueAccessCatalog = ValueAccess.Swappable;
- private Node* m_node = null;
- private Node* node()
- {
- return m_node;
- }
- static IterType opCall(IterType i)
- {
- IterType ret;
- ret.m_node = i.m_node;
- return ret;
- }
- private static IterType opCall(Node* p)
- {
- IterType i;
- i.m_node = p;
- return i;
- }
- public ValueType opCall()
- {
- assert(m_node !is null);
- return m_node.data;
- }
- public PtrType ptr()
- {
- assert(m_node !is null);
- return &(m_node.data);
- }
- // 没办法,D 不能重载 *ptr
- public ValueType current()
- {
- assert(m_node !is null);
- return m_node.data;
- }
- public void current(ValueType v)
- {
- assert(m_node !is null);
- m_node.data = v;
- }
- void swap(inout IterType rhs)
- {
- IterType t = rhs;
- rhs = *this;
- *this = t;
- }
- IterType opPostInc() //i++
- {
- IterType i = *this;
- next();
- return i;
- }
- IterType opPostDec() // i--
- {
- IterType i = *this;
- back();
- return i;
- }
- bool opEquals(IterType rhs) // a == b
- {
- return rhs.m_node == this.m_node;
- }
- //D 不支持将=重载为两个同类型或可以隐式转换的类型之间的赋值
- ValueType opAssign(ValueType rhs) // *a = value
- {
- m_node.data = rhs;
- return m_node.data;
- }
- IterType opAddAssign(int n)
- {
- assert(n == 1);
- next();
- return *this;
- }
- IterType opSubAssign(int n)
- {
- assert(n == 1);
- back();
- return *this;
- }
- }
- public struct Iterator
- {
- mixin IteratorBase!(Iterator);
- public void next()
- {
- m_node = m_node.next;
- }
- public void back()
- {
- m_node = m_node.prev;
- }
- }
- public struct ReverseIterator
- {
- mixin IteratorBase!(ReverseIterator);
- public void next()
- {
- m_node = m_node.prev;
- }
- public void back()
- {
- m_node = m_node.next;
- }
- }
- //data members:
- private Node* m_head = null;
- private Node* m_tail = null;
- private uint m_length = 0;
- public this()
- {
- }
- public ~this()
- {
- clear();
- }
- public void clear()
- {
- if(empty)return;
- Iterator i = begin;
- while((i = erase(i)) != end){}
- m_head = null;
- m_tail = null;
- }
- public ValueType front()
- {
- assert(m_head !is null);
- return m_head.data;
- }
- public ValueType back()
- {
- assert(m_tail !is null);
- return m_tail.data;
- }
- public Iterator begin()
- {
- assert(!empty);
- return Iterator(m_head);
- }
- public Iterator end()
- {
- return Iterator(null);
- }
- public ReverseIterator rbegin()
- {
- return ReverseIterator(m_tail);
- }
- public ReverseIterator rend()
- {
- return ReverseIterator(null);
- }
- public bool empty()
- {
- return m_head == null;
- }
- public uint length()
- {
- return m_length;
- }
- public void pushFront(ValueType val)
- {
- Node* np = new Node;
- np.prev = null;
- np.data = val;
- if(m_head !is null)
- {
- m_head.prev = np;
- np.next = m_head;
- m_head = np;
- }
- else
- {
- np.next = null;
- m_head = np;
- m_tail = np;
- }
- m_length++;
- }
- public void pushBack(ValueType val)
- {
- Node* np = new Node;
- np.next = null;
- np.data = val;
- if(m_tail !is null)
- {
- m_tail.next = np;
- np.prev = m_tail;
- m_tail = np;
- }
- else
- {
- np.prev = null;
- m_head = np;
- m_tail = np;
- }
- m_length++;
- }
- // 删除第一个元素
- public void popFront()
- {
- assert(!empty);
- erase(Iterator(m_head));
- }
- public void popBack()
- {
- assert(!empty);
- erase(Iterator(m_tail));
- }
- //迭代器指向被删除的元素之后的下一个元素或 end,
- //注意删除之后 where 迭代器就无效鸟
- public Iterator erase(Iterator where)
- {
- assert(!empty);
- Node* i = where.m_node.next;
- Node* n = where.m_node;
- if(n.prev !is null) n.prev.next = n.next;
- if(n.next !is null) n.next.prev = n.prev;
- delete n;
- m_length--;
- return Iterator(i);
- }
- public Iterator erase(Iterator first, Iterator last)
- {
- assert(!empty);
- Iterator i = first;
- while(i != last) i = erase(i);
- return i;
- }
- //在给定的有效迭代器前面插入,返回新元素位置
- public Iterator insert(Iterator where, ValueType val)
- {
- assert(where.m_node !is null);
- Node* newNode = new Node;
- Node* oldPrev = where.m_node.prev;
- newNode.data = val;
- Node.join(newNode, where.m_node);
- if(oldPrev !is null)Node.join(oldPrev, newNode);
- return Iterator(newNode);
- }
- //在 where 前面连续插入 count 个相同的元素
- public void insert(Iterator where, uint count, ValueType val)
- {
- Iterator iter = where;
- for(uint i = 1; i < count; ++i)
- iter = insert(iter, val);
- return iter;
- }
- // 不能重载提领操作符就不能很好地使用,比如:
- // const int array[] = [1, 2, 3, 4];
- // auto list = List!(int);
- // list.pushBack(0);
- // list.insert(list.begin, array.ptr, array.ptr + array.length);
- // 看来只有专门为数组重载了
- // 在 where 前面插入一段元素,要求 InputIterator 定义了 ++i, i.current
- public void insertElements ( InputIterator ) // D 的函数模板还是有问题,为什么不能叫 insert
- (Iterator where, InputIterator first, InputIterator last)
- {
- InputIterator i = first;
- Iterator pos = where;
- while(i != last)
- {
- pos = insertBack(pos, i());
- ++i;
- }
- }
- // 在 where 后面插入,并返回新位置
- private Iterator insertBack(Iterator where, ValueType val)
- {
- Node* oldNext = where.m_node.next;
- Node* newNode = new Node;
- newNode.data = val;
- Node.join(where.m_node, newNode);
- if(oldNext !is null) Node.join(newNode, oldNext);
- return Iterator(newNode);
- }
- public void opCatAssign(SelfType rhs)
- {
- for(Iterator i = rhs.begin; i != rhs.end; ++i)
- {
- pushBack(i.current);
- }
- }
- public void swap(inout SelfType rhs)
- {
- assert(rhs !is null);
- swap_(rhs.m_tail, m_tail);
- swap_(rhs.m_head, m_head);
- swap_(rhs.m_length, m_length);
- }
- }
- // 最简单的 STL 算法, find
- // D不支持提领,我们只能约定 opCall 读取值,opAssign 设置值
- private IterType find(IterType, ValueType)(IterType first, IterType last, ValueType val)
- {
- IterType i = first;
- while(i != last && i() != val) ++i;
- return i;
- }
- void main()
- {
- alias List!(int) MyList;
- auto l = new MyList;
- l.pushBack(1);
- l.pushBack(2);
- l.pushBack(3);
- l.pushBack(4);
- l.pushBack(5);
- for(MyList.Iterator i = l.begin; i != l.end; i++)
- {
- writefln(i());
- }
- writefln("\nreversed:");
- MyList.Iterator i = l.begin;
- i++;
- i++;
- l.insert(i, 12);
- l.erase(i);
- for(MyList.ReverseIterator ri = l.rbegin; ri != l.rend; ri++)
- {
- writefln(ri());
- }
- }
评论
3 楼
oldrev
2007-04-09
由于GC的使用,链表也完全可以实现copy on write,因此我准备仔细设计之后为它添加一个存储 Policy,让用户可以在编译时决定时候启用 copy on write 特性。
2 楼
oldrev
2007-04-07
引用
好!
不过Traversal和 ValueAccess 好像没用进去亚。
我把boost里面迭代器部分的PDF全下载了,还真不少,看完再说
不过Traversal和 ValueAccess 好像没用进去亚。
我把boost里面迭代器部分的PDF全下载了,还真不少,看完再说
Traversal 和 ValueAccess 是给算法重载用的
1 楼
qiezi
2007-04-07
好!
不过Traversal和 ValueAccess 好像没用进去亚。
我把boost里面迭代器部分的PDF全下载了,还真不少,看完再说
不过Traversal和 ValueAccess 好像没用进去亚。
我把boost里面迭代器部分的PDF全下载了,还真不少,看完再说
发表评论
-
Tango 0.99.7 Dominik 今天放出
2008-07-25 12:16 1370详细的发布公告: http://www.dsource.org ... -
D新闻组里的天才代码
2008-03-30 21:26 3260超猛的代码,刚才逛新闻组刚看到的,随便记录一下。 出自: ... -
Ubuntu & D
2008-03-23 12:33 2377前几天 Ubuntu Linux 8.04 (Hardy) 刚 ... -
Dotmars.test 单元测试框架简介
2007-11-19 22:43 94D语言内置的 unittest关键字+assert 组成的单元 ... -
mixin 模拟多继承
2007-11-10 17:40 3649D1.0 代码 /** TupleMixin ... -
简单的 C to D 转换 Ruby 脚本
2007-10-24 22:06 4586今天晚上费了点脑筋写了一个简单的 C2D 转换脚本,大致实现了 ... -
D1.0代码模拟 __traits(hasMember, ...)
2007-10-08 23:12 5100通过1.0的代码完全模拟了 D 2.0 __traits(ha ... -
更好的C++——给C++使用者的D语言简介
2007-09-14 01:30 12209作为 C++ 狂热的粉丝, ... -
让D代码自己编译自己
2007-09-12 22:55 4747刚在 D语言的新闻组里看到了D模板&元编程顶尖高人 ... -
Dotmars 实例之:容器、迭代器与算法框架
2007-08-03 23:49 5669Dotmars 实例之:容器、迭代器与算法框架 这几天 Mr. ... -
基于 D 2.0 编译时反射的单元测试框架
2007-07-27 21:25 2789一个模仿 Ruby Test::Unit 的 Quick &a ... -
D 2.0 Const/Final/Invariant 概念简介
2007-07-24 22:55 5418D 2.0 Const/Final/Invariant 概 ... -
DotMars 版 Hello World
2007-06-05 02:17 8180DotMars 已经具有初步的样子了,特别发帖庆祝。 Dot ... -
关联数组字面值+函数字面值=支持任意类型的 switch
2007-05-19 23:29 4504刚才写字符串格式化的由于要处理所有内置类型,而且只有 Type ... -
.Net/Java 风格格式化字符串
2007-05-18 22:51 3579基础类库的东西看起来容易做起来难,今天花时间实现了一点点 . ... -
修改版 juno.com.base
2007-04-20 00:28 4272dsource 上的 juno 是一个很不错的 Windows ... -
C#-like 的 DLL 封装
2007-04-16 23:19 4364一个类似 C# 的 DllImport 实现,用于“半”动态加 ... -
简单的D语言 VIM 缩写插件
2007-04-13 15:45 3438昨晚我写了一个非常简单的 VIM 的D语言缩写插件,希望能让用 ... -
用Rant自动化D语言程序构建
2007-03-31 13:54 3181上回说到 Rank 这个 Ruby 世界最广泛使用的构建工具在 ... -
D语言通用 Rakefile
2007-03-31 00:21 2901在一个日文网站上发现的通用 Rakefile for GDCr ...
相关推荐
数据结构——双向链表模板类的实现 //数据结构——双向链表模板类的实现2007年06月16日 星期六 10:14 ////////////////////////////////////////////////////////////////////// // 模块名: 双向链表模板类 // 代码...
用模板类实现了一个简单的双向链表domo。
一种支持类模版和函数模版的C++双向链表,实现了各种排序算法(排序原则可定制),包含学生信息的使用示例(VC 6.0、VS2008).
两个VC 链表模板类,一个是单向链表,一个是多向链表,用法在main()函数中都有说明,对初学者应该有帮助,说明了原理,还有代码示例,不失为一套不错的学习资料。
双向链表模板(纯C++语言),不能百分百正确,但一般情况可以用
网上搜集的七种双向链表模板c++实现,耗掉不少分,集中一下,希望会赚一些,也会省掉你不少分:)
此代码是我收集的用C++实现双向链表模板类。
双向链表List模板类(模拟STL容器中的list),提供插入删除,清空,获取链表长度,判断链表是否为空等操作,内置了迭代器类型
C++ 双向链表(用模板实现) 大家可以看看,参考一下。
该示例使用VS2013编写,其中DoubleDIRList为数据元素类,DoubleDIRListContainer为自己手写实现的双向链表类,DequeForListContainer为使用Deque实现的双向链表类
数据结构 双向链表的实现
C++ 双向链表(不用模板实现)。 大家可以看看,参考下。
JAVA 循环链表, 模板类. 后续将提交JavaScript版本, C语言版本及C++版本
这里采用模板机制实现双向链表。 由于做的项目需要对结点进行频繁的增删,这里把结点地址公布出来以提高删除结点的速度(删除时,不需要进行链表的搜索操作) 重载了ostream& operator运算符,方便使用cout写调试...
c++双向循环链表类模板[归纳].pdf
用模板实现链表的建立删除等操作,可以根据具体情况稍作修改即可实现链表操作,或直接使用,我在链表的学习和类模板的学习和以后的编程时这种链表构造思想觉得挺好的,有点面向对象的意思……粗浅的理解呵呵!
1、讲解和演示打印和排序模板函数的开发过程; 2、讲解和演示CList双向链表的模板类的开发过程; 3、初步讲解CArray模板类的原理和使用方法;
C++源码 数据结构 模板类 顺序表 单链表 双向链表 循环链表 顺序队列 链式队列 优先级队列 二叉树
采用c++类封装约瑟夫问题,实现过程中使用了c++中的双向链表模板list