双向链表模板类

参考 STL 实现的 Quick & Dirty 双向链表模板类，勉强看的过去。参考了 boost 的新概念迭代器，遵循D的命名风格，只实现了几个简单的成员函数。
迭代器使用 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 是给算法重载用的

1 楼 qiezi 2007-04-07  

好！

不过Traversal和  ValueAccess  好像没用进去亚。

我把boost里面迭代器部分的PDF全下载了，还真不少，看完再说