随笔-90  评论-947  文章-0  trackbacks-0
开始把库搞起来了

打算先把基础的东西组织起来，作为一个“大库”（见上一篇《小库还是大库？》）。然后填加各个实用功能，作为一个个小库或者大库，过段时间再想办法组织整理了。

首先是类型系统，我想来想去，觉得还是必须整理一下，尤其是 unsigned XXX 写起来太难看了，可是这又带来了问题——WinDef.h 把好听的名字都占去了。然后，我只能在自己的命名空间下这样来一番了：

xlDef.h
#ifndef __XLDEF_H_44FDC6C3_12F1_4BF3_8F9F_1ABED755E8ED_INCLUDED__
#define __XLDEF_H_44FDC6C3_12F1_4BF3_8F9F_1ABED755E8ED_INCLUDED__


namespace xl
{
    typedef char CHAR;
    typedef unsigned char UCHAR;
    typedef short SHORT;
    typedef unsigned short USHORT;
    typedef int INT;
    typedef unsigned int UINT;
    typedef long LONG;
    typedef unsigned long ULONG;
    typedef long long LONGLONG;
    typedef unsigned long long ULONGLONG;

    typedef void VOID;
    typedef bool BOOLEAN;
    typedef INT BOOL;

    typedef UCHAR BYTE;
    typedef USHORT WORD;
    typedef ULONG DWORD;
    typedef ULONGLONG QWORD;

    const BOOL TRUE = 1;
    const BOOL FALSE = 0;
    const VOID *NULL = 0;

    typedef struct interface;

} // namespace xl


#endif // #ifndef __XLDEF_H_44FDC6C3_12F1_4BF3_8F9F_1ABED755E8ED_INCLUDED__

但是，问题是，当 using namespace xl 并 #include <Windows.h> 以后，随手写一个“DWORD”，就会有歧义了。如果用的时候要写成 xl::DWORD，那还不如现在就命名成 XL_DWORD 好了……这点仍然在纠结中……路过朋友请给点意见：）

接下来是最基础一层的组成。我想先把 Array、List、BinaryTree 给实现一下。然后第二层中利用 Array 实现 String，利用 List 搞个 Queue、Stack 什么的，利用 BinaryTree 搞个 Map、Set 之类的。只是数据结构中的“图”，不知道怎么搞比较方便，如果可能，也可以在第一层实现掉。

不得不考虑的是 iterator 的问题。由于 STL 的 iterator 深入人心，我很想也搞个类似的支持。但是，STL 的 iterator 是可以跨容器的，也就是，可以在 list 的 insert 里填入 vector 的 iterator 作为参数。我不太了解 STL 的具体做法，但是粗看似乎是用模板实现的。可是这样的话，就有一个很大的问题，这个模板参数将是没有任何约束的，在明明需要 iterator 的参数的位置，我可以随意填一个别的东西，直到有调用 iterator 的什么方法，编译器才给出错误。这样，实际上在接口中没法为使用者提供足够的信息（或者说，提供语法上的约束）让他明白这个参数应该是什么。比较好的做法可能是 .Net 的那一套，定义接口 IEnumerator、IEnumerable 等等，然后各个类都去实现这个接口，迭代器也可以只针对接口编写。但是由于 C++ 中的多态必须用指针表示，那么在参数、返回值（特别是返回值）中，指针的 delete 又给使用带来了麻烦。于是，似乎需要先有一个完善的智能指针作为基础才可以。而智能指针，如果要线程安全，又必须有平台支持，所以似乎智能指针没法放在这么基础的位置。…………

绕了好久，也想了好久，始终还是找不到好的办法。所以，我暂时觉得还是放弃跨容器的 iterator 了，其实说到底，这只是勉强制造的、看似来很精巧、其实不那么完美的东西而已。

Array、List、Tree 暂时设计如下：

xlArray.h
#ifndef __XLARRAY_H_3B18D7E2_B52A_4D57_BE4B_657F9D17320D_INCLUDED__
#define __XLARRAY_H_3B18D7E2_B52A_4D57_BE4B_657F9D17320D_INCLUDED__


#include "xlDef.h"

namespace xl
{

    template <typename T>
    class Array
    {
    public:
        Array();
        Array(const Array<T> &that);
        ~Array();

    public:
        class Iterator
        {
        public:
            Iterator();
            Iterator(const Array<T> *array);
            Iterator(Iterator &that);

        private:
            array<T> *array;
            UINT current;
            BOOLEAN bof;
            BOOLEAN eof;

        public:
            T &operator * ();
            T *operator -> ();

        public:
            Iterator &operator = (Iterator &that);
            BOOLEAN operator == (Iterator &that);
            BOOLEAN operator != (Iterator &that);

        public:
            Iterator operator ++ ();
            Iterator operator ++ (int);
            Iterator operator -- ();
            Iterator operator -- (int);
        };

    public:
        Iterator Bof();
        Iterator Begin();
        Iterator End();
        Iterator Eof();

    public:
        Array<T> &operator=(const Array<T> &that);
        BOOLEAN operator==(const Array<T> &that) const;
        BOOLEAN operator!=(const Array<T> &that) const;

    public:
        T &operator[](UINT index);
        const T &operator[](UINT index) const;

    public:
        BOOLEAN Empty();
        UINT Count();

    public:
        VOID PushFront(const T &tValue);
        VOID PushBack(const T &tValue);
        VOID PopFront();
        VOID PopBack();
        VOID Insert(const Iterator &beforeWhich, const T &value);
        VOID Insert(const Iterator &beforeWhich, const Iterator &firstToInsert, const Iterator &NextOfLastToInsert);
        Iterator Delete(const Iterator &which);
        Iterator Delete(const Iterator &firstToDelete, const Iterator &nextOfLastToDelete);
        VOID SetValue(const Iterator &which, const T &value);
        VOID SetValue(const Iterator &firstToDelete, const Iterator &nextOfLastToDelete, const T &value);

    private:
        T *m_pData;
    };

} // namespace xl

#endif // #ifndef __XLARRAY_H_3B18D7E2_B52A_4D57_BE4B_657F9D17320D_INCLUDED__

 

xlList.h
#ifndef __XLLIST_H_2BEF1B3C_A056_4EC7_B5E3_9898E7945B54_INCLUDED__
#define __XLLIST_H_2BEF1B3C_A056_4EC7_B5E3_9898E7945B54_INCLUDED__


#include "xlDef.h"

namespace xl
{
    template <typename T>
    class List
    {
    public:
        List();
        List(const List<T> &that);
        ~List();

    private:
        struct Node
        {
            T value;
            Node *prev;
            Node *next;
        };

    public:
        class Iterator
        {
        public:
            Iterator();
            Iterator(const List<T> *list);
            Iterator(Iterator &that);

        private:
            List<T> *list;
            Node *current;
            BOOLEAN bof;
            BOOLEAN eof;

        public:
            T &operator * ();
            T *operator -> ();

        public:
            Iterator &operator = (Iterator &that);
            BOOLEAN operator == (Iterator &that);
            BOOLEAN operator != (Iterator &that);

        public:
            Iterator operator ++ ();
            Iterator operator ++ (int);
            Iterator operator -- ();
            Iterator operator -- (int);
        };

    public:
        Iterator Bof();
        Iterator Begin();
        Iterator End();
        Iterator Eof();

    public:
        List<T> &operator=(const List<T> &that);
        BOOLEAN operator==(const List<T> &that) const;
        BOOLEAN operator!=(const List<T> &that) const;

    public:
        BOOLEAN Empty();
        UINT Count();

    public:
        VOID PushFront(const T &tValue);
        VOID PushBack(const T &tValue);
        VOID PopFront();
        VOID PopBack();
        VOID Insert(const Iterator &beforeWhich, const T &value);
        VOID Insert(const Iterator &beforeWhich,
const Iterator &firstToInsert, const Iterator &NextOfLastToInsert);
        Iterator Delete(const Iterator &which);
        Iterator Delete(const Iterator &firstToDelete,
const Iterator &nextOfLastToDelete);

    public:
        Node *head;
        Node *tail;
    };

} // namespace xl

#endif // #ifndef __XLLIST_H_2BEF1B3C_A056_4EC7_B5E3_9898E7945B54_INCLUDED__

 

xlTree.h
#ifndef __XLTREE_H_6BB48AA6_133A_4E9F_944E_504B887B6980_INCLUDED__
#define __XLTREE_H_6BB48AA6_133A_4E9F_944E_504B887B6980_INCLUDED__


#include "xlDef.h"

namespace xl
{
    template <typename T>
    class Tree
    {
    public:
        Tree();
        Tree(const Tree<T> &that);
        ~Tree();

    private:
        struct Node
        {
            T value;
            Node *parent;
            Node *left;
            Node *right;
        };

    private:
        class Iterator
        {
        public:
            Iterator();
            Iterator(const Tree<T> *tree);
            Iterator(Iterator &that);

        private:
            Tree<T> *tree;
            Node *current;
            BOOLEAN bof;
            BOOLEAN eof;

        public:
            T &operator * ();
            T *operator -> ();

        public:
            Iterator &operator = (Iterator &that);
            BOOLEAN operator == (Iterator &that);
            BOOLEAN operator != (Iterator &that);

        public:
            Iterator Parent();
            Iterator Left();
            Iterator Right();
        };

        class PreorderIterator : public Iterator
        {
        public:
            Iterator operator ++ ();
            Iterator operator ++ (int);
            Iterator operator -- ();
            Iterator operator -- (int);
        };

        class InorderIterator : public Iterator
        {
        public:
            Iterator operator ++ ();
            Iterator operator ++ (int);
            Iterator operator -- ();
            Iterator operator -- (int);
        };

        class PostorderIterator : public Iterator
        {
        public:
            Iterator operator ++ ();
            Iterator operator ++ (int);
            Iterator operator -- ();
            Iterator operator -- (int);
        };

    public:
        Iterator Bof();
        Iterator Begin();
        Iterator Eof();

    public:
        Tree<T> &operator=(const Tree<T> &that);
        BOOLEAN operator==(const Tree<T> &that) const;
        BOOLEAN operator!=(const Tree<T> &that) const;

    public:
        BOOLEAN Empty();
        UINT Count();

    public:
        VOID InsertLeft(const Iterator &beforeWhich, const T &value);
        VOID InsertRight(const Iterator &beforeWhich, const T &value );
        Iterator Delete(const Iterator &which);

    public:
        Node *head;
    };

} // namespace xl

#endif // #ifndef __XLTREE_H_6BB48AA6_133A_4E9F_944E_504B887B6980_INCLUDED__

（Tree 的接口还没完全考虑好，也不知道有没有必要把 Node 独立出来。）

这样是否大概足够了？敬请大家指教~

（再次重申一下，请不要来留个言说“干吗要重新发明轮子？”、“XXX 不是很好用吗？”之类的，谢谢！欢迎志同道合的朋友探讨，如能为我解惑，那么非常感谢。）

posted on 2009-09-26 17:43 溪流 阅读(654) 评论(18)  编辑 收藏 引用 所属分类: C++

评论:
# re: 开始把库搞起来了 2009-09-27 12:46 | 陈梓瀚(vczh)
碰巧我也再造轮子。我吸取了stl和.net的经验做了一套collection出来，linq也实现了，string也实现了。现在正在做stream，还有无缝支持自定义的用户类型。这就有4套子系统了，其中自反连接和两两互转一共需要15个运算器（包括regex啦，linq啦，自定义语法分析器什么的）。

因为我是做编译器的所以对复杂数据结构的灵活运算要求非常高，但是效率并没有太苛求。完了我们可以交流一下。  回复  更多评论
  
# re: 开始把库搞起来了 2009-09-27 12:55 | 陈梓瀚(vczh)
然后我跟你说说VL++2.0的一些故事……现在已经推翻掉写3.0了，其中的一些决定就是
1：不再typedef基础类型
2：不再加前缀
3：大规模利用模板
4：加强各个模块之间的关系，互操作性要变得很强

你可以考虑不走我的老路……  回复  更多评论
  
# re: 开始把库搞起来了 2009-09-27 12:58 | 陈梓瀚(vczh)
于是最后提示一点，根据我前面几年造轮子的实践，独立二叉树的接口一点意义都没有……  回复  更多评论
  
# re: 开始把库搞起来了 2009-09-27 15:49 | 溪流
@陈梓瀚(vczh)

陈老师你好，我一年多前实习的时候因为公司不允许使用STL、MFC等等所有流行的库，叫我们“用到的数据结构自己写”。当时只写了个 Vector、String，足以应付任务了。不过我就是从那时开始明白写库的意义，以及感受到用自己的库的那种爽快的感觉的。

很佩服你的技术，粗看过你的代码，我知道你把基础数据结构全部实现了一遍，甚至regex，以及在代码里写 EBNF，等等。（我第一篇日志的开头语不知道您看过了没，呵呵）

我也想不走老路，不过有些东西可能不走一遍不会明白，所以我想可能先自然一点，到第二遍、第三遍再来总结以及回避已知问题。关于你说的4点，我比较想了解原因以及大概做法，可否稍微解释下？特别是1和2，这个是现在就摆在我面前的。然后是3、4，我可以听一听，虽然可能不是马上体会得到。  回复  更多评论
  
# re: 开始把库搞起来了 2009-09-27 15:51 | 溪流
@陈梓瀚(vczh)

你的意思是说 Tree::Node 没必要暴露出来吗？再问一下问一下，你觉得基础库里有必要存在二叉树这种结构吗？还有没有必要以及可能包含图的结构呢？  回复  更多评论
  
# re: 开始把库搞起来了 2009-09-27 18:00 | OwnWaterloo
@溪流
1. 如非必要，不typedef基础类型

为什么要typedef？
typedef是为了提供语意。

DWORD, WORD, BYTE的语意是固定长度整数。
stdint.h, cstdint, sys/stdin.h, windows.h 中已经有这样的功能， 就尽可能去复用。
自己省事 —— 你有精力去为不同平台定义出对应的DWORD, WORD, BYTE吗？
既然上面的几个文件中已经给出了这种功能， 并且在各个平台下都测试过， 为什么不直接使用呢？

别人也省事。
需要明白一点：用户与其依赖的库通常不是线性结构，而是树形结构。
A库为了可移植性的去typedef DWORD, WORD, BYTE,
B库也为了可移植性去typedef DWORD, WORD, BYTE,
一个客户C， 同时需要A、B， 他该用哪个库的DWORD？
这种作法是徒增不必要的概念。


对自己库独有， 并有可能改变的概念， 才可以考虑使用typedef 来建立一个语意。
比如time.h中的time_t, clock_t， 代表了两个独立的概念。
  回复  更多评论
  
# re: 开始把库搞起来了 2009-09-27 18:10 | OwnWaterloo
@溪流
2：不再加前缀

其实vczh同学放出来的代码中的VL_前缀……
我觉得看上去是很伤眼的……
当然， 这是口味问题。


关于这个问题：
"但是，问题是，当 using namespace xl 并 #include <Windows.h> 以后，随手写一个“DWORD”，就会有歧义了。如果用的时候要写成 xl::DWORD，那还不如现在就命名成 XL_DWORD 好了"

首先， 不必定义xl::DWORD。
对于其他情况， 名字空间相对于前缀是有一些优势的。
1. 如果存在歧义， 无论是名字空间，还是前缀， 都必须使用全称。
2. 不存在歧义的时候， 名字空间可以打开， 可以别名。 而前缀必须时刻都带着， 永远逃不掉。
3. 如果不小心， 两个使用前缀的库都出现了相同名字， 前缀技术就很麻烦。
A库是个做网络的， 有一个 net_f,
B库也是个做网络的， 依然一个 net_f,
要同时使用两个库， 就需要自己去写转发函数。

而名字空间， 可以一开始就很长。
namespace net_byA { void f() }
namespace net_byB { void f() }


只使用A（或B）的用户，就可以使用别名：
namepsace net = net_byA(B);
net::f;

如果同时使用A、B的用户， 只好：
net_byA::f;
net_byB::f;

也比自己写转发函数要强。

总之， 名字空间是一种更灵活的方式。

如果决定使用C++编写库， 而且不考虑过分古董的编译器， 就应该选用名字空间。  回复  更多评论
  
# re: 开始把库搞起来了 2009-09-27 18:26 | OwnWaterloo
@溪流

各种现有的流行的库中， 实现了侵入式容器的比较少。
大都是非侵入式容器。

侵入式容器我只在如下一些库中见到过：
linux/list.h, linux/rbtree.h
sourceforge有个叫libaasdl的项目，有一个GDST(generic data-structure template)子库中的一些是侵入式的（还有一些我没看完）

SGI-STL中4种关联容器底层使用的是同一种容器，_Rb_tree。
它是非侵入式的。
但是构建它的_Rb_tree_base、_Rb_tree_base_iterator都是非侵入式的。
SGI-STL没有构建出一个侵入式的RbTree层， 而是直接使用侵入式的_Rb_tree_base,和_Rb_tree_base_iterator构建出了非侵入式的_Rb_tree。
稍微有点可惜。
不过即使有一个侵入式的RbTree, SGI-STL也是不会将其公开出来的。


如果想练手， 可以考虑构建一套侵入式的容器， 比仅仅重复STL中的东西来得有意义。

还有， STL中没有树式的堆。
heap相关的那几个函数都是对random_access的线性表使用的。
也可以考虑在这里做做文章。  回复  更多评论
  
# re: 开始把库搞起来了 2009-09-27 18:51 | OwnWaterloo
const VOID *NULL = 0;
在C++中， 这样定义NULL是行不通的。
 
普遍的做法是直接使用0，或者stddef.h, cstddef 中的NULL宏：
#ifdef __cplusplus
#define NULL 0
#else
#define NULL ((void*)0) /* 这是C中的做法 */
#endif
 
void* 在C中可以隐式转换到其他类型指针。
但C++不行。
 
 
或者， 更激进一点， 使用nullptr：
nullptr
因为C++0x将引入nullptr作为关键字。
使用nullptr，算是"向前兼容"吧…… 等转到C++0x时，就可以直接使用真正的nullptr了。
 
上面最后一种nullptr和C++0x中的语意最相似， 不过不一定能在所有编译器中都通过。
至少要支持成员函数模板才行。
如果不支持匿名类可以改用别的方式实现。
 
 
 
 typedef struct interface;
这是什么语法？
这也是徒增概念的地方。
 
C++程序员如果不知道下面的代码是一个interface
struct Ixxx {
    virtual ~Ixxx();
    virtual ...
};
 
将struct 换成interface对他的帮助也不大。
  回复  更多评论
  
# re: 开始把库搞起来了 2009-09-27 19:10 | OwnWaterloo
不叫"跨容器"的iterator。
而是iterator符合特定的concepts。
不过你说对了， 它确实和模板有关。
 
比如，使用一对forwarding_iterator构造vector的伪代码：
concepts
 
vector有一个构造函数模板。
只要FotIt 满足forwarding_iterator的概念，上面的构造函数就可以生成。
forwarding_iterator 要支持（但不限于）++, *, 因为上面的代码使用了这2个操作符。
vector的实现也不会是上面那样， 不会调用new 去默认构造一次。
会使用其allocator来分配，并使用uninitialized_copy。
不过那样就看不到vector() 对forwarding_iterator的要求了。
 
 
这是C++中的方式，GP的，基于concepts的方式。C#中可是没得这么爽的哦。
并且， GP的、基于concepts的方式， 也可以退化成OOP的，基于interface的方式。
反之不行， 因为concepts的偶和性更低。
 
 
不仅仅是容器。 整个STL中的组件都是通过concepts来协作而非interface。
如果你喜欢struct Iterator的方式， 或者IComparable ， 也可以这么搞一套。
代码不会比GP来得少， 效率不会比GP来得高， 也不会比GP灵活 —— GP可以退化为基于interface， 反之不行。
 
  回复  更多评论
  
# re: 开始把库搞起来了 2009-09-27 19:10 | OwnWaterloo
上面贴的代码有问题， 重新贴一下……
 
template<typename T,  >
class vector {
    T* first_;
    T* last_;
public:
    template<class ForIt>
    vector(ForIt first,ForIt last) {
        difference_type d = distance(first,last);
        first_ = new T[ d + padding ];
        last_ = first_ + d;
        for (T* p = first;first!=last;++first,++p)
            *p = *first;
    }
};
  回复  更多评论
  
# re: 开始把库搞起来了 2009-09-27 20:33 | 溪流
@OwnWaterloo

先谢过您的这么详细的指点。等我仔细看过后再来提后续问题：）  回复  更多评论
  
# re: 开始把库搞起来了 2009-09-27 22:35 | 溪流
@OwnWaterloo

1、关于 typedef

第一，我想我要写的库要保持独立性。如果去包含了 Winows.h 了，那么就失去了这一部分的独立性了。在做容器方面的东西的时候，实际上我根本不会用到 Windwos API，而这一 include，增加无畏的依赖的同时，还把平台陷死了（虽然我不准备搞多么跨平台的东西，但是明明可以不依赖的，还是不要去依赖，是吗？）

我想，库的用户可能不需要去写太多次 a::DWORD、b::DWORD，只要他们的定义是兼容的，传入的值就可以用。

其实我最头痛的就是 Windows.h 把这些名字都占去了，而且是全局的，是的用户无法简单地写一个 DWORD 来定义 Windows.h 中的 DWORD 了。我知道加前缀不是好的解决方案，可是还有其他一套如此通用的名字吗？
  回复  更多评论
  
# re: 开始把库搞起来了 2009-09-27 22:45 | OwnWaterloo
@溪流
用stdint.h。 把这个棘手的工作交给编译器提供商。
并且， 你实现容器库的时候， 需要DWORD么……


> 只要他们的定义是兼容的，传入的值就可以用。
你要去检查。 是否每个库都是兼容的。

另一种方式是只依赖于一处定义。比如stdint.h


msvc没有提供stdint.h， 因为它不支持C99。
网上有一个stdint.h for msvc， 使用BSD3条款的许可证。

或者自己写：

msvc 提供了 __intN扩展。
所以 intN_t uintN_t 很好处理
int_leastN_t， 这个本来就不能假设它的宽度， 按字面来即可。

uintptr_t, intptr_t 可以包含basetsd.h
typedef INT_PTR intptr_t;
typedef UINT_PTR uintptr_t;


现在你代码中依赖的就是：
(u)intN_t, (u)int_fastN_t ,, (u)intptr_t, (u)intmax_t 等等。  回复  更多评论
  
# re: 开始把库搞起来了 2009-09-27 23:58 | 溪流
@OwnWaterloo

是的，现在是用不着 DWORD，但是以后一些功能库会用到。
stdint.h 中的类型名称似乎也不怎么干净利索。
要不就直接用标准名称好了？只是我很不喜欢 unsigned int, size_t 这种写法。  回复  更多评论
  
# re: 开始把库搞起来了 2009-09-28 00:17 | OwnWaterloo
@溪流
这个…… 其实是个口味问题 …… all fine.
我比较懒…… 有现成的就喜欢用现成的…… so ……

  回复  更多评论
  
# re: 开始把库搞起来了 2009-09-28 00:27 | 溪流
@OwnWaterloo

打算这样，如何？

namespace xl
{
    typedef unsigned char uchar;
    typedef unsigned short ushort;
    typedef unsigned int uint;
    typedef unsigned long ulong;
    typedef long long longlong;
    typedef unsigned long long ulonglong;

    typedef wchar_t wchar;
    typedef unsigned wchar uwchar;

    typedef __int8 int8;
    typedef __int16 int16;
    typedef __int32 int32;
    typedef __int64 int64;

    typedef unsigned int8 uint8;
    typedef unsigned int16 uint16;
    typedef unsigned int32 uint32;
    typedef unsigned int64 uint64;

    struct
    {
        template<typename T>
        operator T*() const
        {
            return 0;
        }

    } nullptr;

} // namespace xl


我的目的主要是为了书写简洁，其他的其实对我来说关系不大，暂时主要考虑 Win + MSVC 平台。nullptr 的定义真的好精妙！
  回复  更多评论
  
# re: 开始把库搞起来了 2009-09-28 00:40 | OwnWaterloo
@溪流
nullptr是《eff cpp》中提到的。

对于int和指针的重载：
void f(int );
void f(void* );

f(0); // f(int );
f(NULL); // 如果是stddef.h 中的NULL， f(int );
f(nullptr); // 书中提到的那个nullptr, 会选中 f(void* );

如果还有另一种指针：

void f(int* ); nullptr 会引起歧义。

当然， 最好是避免这种重载……

  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 溪流