Dotmars 实例之：容器、迭代器与算法框架

这几天 Mr. Bright 老是不放新版本，圈子里太冷清了，我来发篇程序凑个数。

这是一个类似 C++ STL 的容器、迭代器和算法框架，迭代器的设计参考了 C++ boost 库中的"new-style" 迭代器，把迭代器的遍历和读写操作分开，内置数组处理参考了 qiezi 的文章： 仿STL的vector，写了一组array操作方法。容器方法的命令没有遵循 STL 的风格，而是采用 .Net 范型容器的名称。

借助于 D 威力强大的模板和模板混入，代码虽然大量用到了模板，但是十分地简短易读。

目前仅仅实现的部分包括：

• 双向列表容器
• find & copy 算法（没有模板特化的优化）
• 内置一维数组的迭代器
• 一个AOP模式的容器操作符重载

废话少说，看看范例程序展现的威力：

D 代码

module samples.base.collections;

import dotmars.base.iterator;
import dotmars.base.collection.list;
import dotmars.base.collection.array;
import dotmars.base.algorithms;
import dotmars.io.console;

void main()
{
    alias List!(int) MyList;

    auto list = new MyList;

    list ~= 1; // this is equal to list.addList(1);
    list ~= 2;
    list ~= 3;
    list ~= 4;
    list ~= 5;
    list ~= 6;
    list.addFirst(7);

    //现在序列为： 7,1,2,3,4,5,6

    MyList.Iterator it = list.begin();
    ++it;
    ++it;

    //删除2, it 指向3
    it = list.remove(it);

    //现在序列为： 7,2,3,4,5,6

    list.addBefore(it, 2); //在3之前插入2，it 指向 3


    int[] array;
    array.addLast(8);  //内置数组也能享受到同样的 addLast 成员函数
    array.addLast(9);

    // 内置数组也可以用迭代器访问
    list.addRangeBefore(it, array.begin(), array.end()); //在3之前插入array的内容，即 8,9

    //使用 foreach 语句遍历 list
    foreach(int i; list)
        Console.print("{0}, ", i);

    Console.newLine();

    //与 STL 类似，通过内部的迭代器反向遍历 list
    for(MyList.ReverseIterator ri = list.rbegin(); ri != list.rend(); ++ri)
        Console.print("{0}, ", ri.current);

    Console.newLine();

    //调用通用算法
    MyList.Iterator pos = find(list.begin(), list.end(), 5);

    if(pos != list.end())
        Console.printLine("Pattern found: {0}", pos.current);

    list.clear();
}

运行结果：

7, 1, 2, 9, 8, 3, 4, 5, 6,
6, 5, 4, 3, 8, 9, 2, 1, 7,
Pattern found: 5

最新版程序可在 dotmars.googlecode.com/svn/trunk/samples/base/collections.d 处下载。

编译与执行参考这里：http://oldrev.iteye.com/blog/86634

评论

9 楼 oldrev 2007-08-07  

那个单元测试框架已经移植到了1.0，不过用起来没2.0那么方便

8 楼 Colorful 2007-08-07  

在我看来,大概有1/3左右的.NET Framework API无法实现,或者很难实现.

.NET解决了Windows DNA体系的所有重大问题.比如Dll hell,分布式计算等.

D仍然是基于Windows DNA体系的.比如要实现Application Domain,基于VM的GC和Native的GC等,都有相当多的问题.

还是以.NET的设计原则,考虑D语言的特性来实现核心库比较现实.

7 楼 oldrev 2007-08-07  

引用

其实我是这样想的，既然Dotmars是D的C#语法化为什么不多借鉴一些C＃的优点呢？比如Delegate在C#中就是一个对象，一个特殊的对象

Dotmars 只是一个类库而已，并没有涉及到语法。D也不可能完全学C#，比如 D 的编译时特性包括模板、CTFE、静态反射等都是C#没有滴，为了效率和方便性不可能放弃使用这些特性而完全 clone .net fx。
我想大概原则就是适合OO的地方就OO，适合范型的地方就范型。

6 楼 niijyeni 2007-08-07  

引用

to 楼上：

链表是不能直接访问元素的，必须通过迭代器遍历

MyList.Iterator pos = find(list.begin(), list.end(), 5);
list.remove(pos); //注意当容器变化后迭代器 pos 就无效了

对于链表来说，这种操作是很低效的，需要快速的查找和删除可以使用散列表或红黑树实现的 set

其实我是这样想的，既然Dotmars是D的C#语法化为什么不多借鉴一些C＃的优点呢？比如Delegate在C#中就是一个对象，一个特殊的对象

5 楼 oldrev 2007-08-04  

本来就在SVN里

4 楼 xgene 2007-08-04  

你的这些例子为什么不妨在svn中呢，这样方便取出！！！

3 楼 oldrev 2007-08-04  

to 楼上：

链表是不能直接访问元素的，必须通过迭代器遍历

MyList.Iterator pos = find(list.begin(), list.end(), 5); 
list.remove(pos); //注意当容器变化后迭代器 pos 就无效了

对于链表来说，这种操作是很低效的，需要快速的查找和删除可以使用散列表或红黑树实现的 set

2 楼 niijyeni 2007-08-04  

引用

#     list ~= 1; // this is equal to list.addList(1); 

如果我想从这个链表中删除 1 怎么作呢？？
list -= 1;??

1 楼 shawind 2007-08-04  

D圈子的活力也不能总是靠DMD的新版本来支持。最近在看STL，正好借你的源码来学习了。