2009-09-26 17:43:00
打算先把基础的东西组织起来，作为一个“大库”（见上一篇《小库还是大库？》）。然后填加各个实用功能，作为一个个小库或者大库，过段时间再想办法组织整理了。
首先是类型系统，我想来想去，觉得还是必须整理一下，尤其是 unsigned XXX 写起来太难看了，可是这又带来了问题——WinDef.h 把好听的名字都占去了。然后，我只能在自己的命名空间下这样来一番了：
xlDef.h
1#ifndef __XLDEF_H_44FDC6C3_12F1_4BF3_8F9F_1ABED755E8ED_INCLUDED__
2#define __XLDEF_H_44FDC6C3_12F1_4BF3_8F9F_1ABED755E8ED_INCLUDED__
3
4
5namespace xl
6{
7 typedef char CHAR;
8 typedef unsigned char UCHAR;
9 typedef short SHORT;
10 typedef unsigned short USHORT;
11 typedef int INT;
12 typedef unsigned int UINT;
13 typedef long LONG;
14 typedef unsigned long ULONG;
15 typedef long long LONGLONG;
16 typedef unsigned long long ULONGLONG;
17
18 typedef void VOID;
19 typedef bool BOOLEAN;
20 typedef INT BOOL;
21
22 typedef UCHAR BYTE;
23 typedef USHORT WORD;
24 typedef ULONG DWORD;
25 typedef ULONGLONG QWORD;
26
27 const BOOL TRUE = 1;
28 const BOOL FALSE = 0;
29 const VOID *NULL = 0;
30
31 typedef struct interface;
32
33} // namespace xl
34
35
36#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
1#ifndef __XLARRAY_H_3B18D7E2_B52A_4D57_BE4B_657F9D17320D_INCLUDED__
2#define __XLARRAY_H_3B18D7E2_B52A_4D57_BE4B_657F9D17320D_INCLUDED__
3
4
5#include "xlDef.h"
6
7namespace xl
8{
9
10 template <typename T>
11 class Array
12 {
13 public:
14 Array();
15 Array(const Array<T> &that);
16 ~Array();
17
18 public:
19 class Iterator
20 {
21 public:
22 Iterator();
23 Iterator(const Array<T> *array);
24 Iterator(Iterator &that);
25
26 private:
27 array<T> *array;
28 UINT current;
29 BOOLEAN bof;
30 BOOLEAN eof;
31
32 public:
33 T &operator * ();
34 T *operator -> ();
35
36 public:
37 Iterator &operator = (Iterator &that);
38 BOOLEAN operator == (Iterator &that);
39 BOOLEAN operator != (Iterator &that);
40
41 public:
42 Iterator operator ++ ();
43 Iterator operator ++ (int);
44 Iterator operator -- ();
45 Iterator operator -- (int);
46 };
47
48 public:
49 Iterator Bof();
50 Iterator Begin();
51 Iterator End();
52 Iterator Eof();
53
54 public:
55 Array<T> &operator=(const Array<T> &that);
56 BOOLEAN operator==(const Array<T> &that) const;
57 BOOLEAN operator!=(const Array<T> &that) const;
58
59 public:
60 T &operator[](UINT index);
61 const T &operator[](UINT index) const;
62
63 public:
64 BOOLEAN Empty();
65 UINT Count();
66
67 public:
68 VOID PushFront(const T &tValue);
69 VOID PushBack(const T &tValue);
70 VOID PopFront();
71 VOID PopBack();
72 VOID Insert(const Iterator &beforeWhich, const T &value);
73 VOID Insert(const Iterator &beforeWhich, const Iterator &firstToInsert, const Iterator &NextOfLastToInsert);
74 Iterator Delete(const Iterator &which);
75 Iterator Delete(const Iterator &firstToDelete, const Iterator &nextOfLastToDelete);
76 VOID SetValue(const Iterator &which, const T &value);
77 VOID SetValue(const Iterator &firstToDelete, const Iterator &nextOfLastToDelete, const T &value);
78
79 private:
80 T *m_pData;
81 };
82
83} // namespace xl
84
85#endif // #ifndef __XLARRAY_H_3B18D7E2_B52A_4D57_BE4B_657F9D17320D_INCLUDED__
xlList.h
1#ifndef __XLLIST_H_2BEF1B3C_A056_4EC7_B5E3_9898E7945B54_INCLUDED__
2#define __XLLIST_H_2BEF1B3C_A056_4EC7_B5E3_9898E7945B54_INCLUDED__
3
4
5#include "xlDef.h"
6
7namespace xl
8{
9 template <typename T>
10 class List
11 {
12 public:
13 List();
14 List(const List<T> &that);
15 ~List();
16
17 private:
18 struct Node
19 {
20 T value;
21 Node *prev;
22 Node *next;
23 };
24
25 public:
26 class Iterator
27 {
28 public:
29 Iterator();
30 Iterator(const List<T> *list);
31 Iterator(Iterator &that);
32
33 private:
34 List<T> *list;
35 Node *current;
36 BOOLEAN bof;
37 BOOLEAN eof;
38
39 public:
40 T &operator * ();
41 T *operator -> ();
42
43 public:
44 Iterator &operator = (Iterator &that);
45 BOOLEAN operator == (Iterator &that);
46 BOOLEAN operator != (Iterator &that);
47
48 public:
49 Iterator operator ++ ();
50 Iterator operator ++ (int);
51 Iterator operator -- ();
52 Iterator operator -- (int);
53 };
54
55 public:
56 Iterator Bof();
57 Iterator Begin();
58 Iterator End();
59 Iterator Eof();
60
61 public:
62 List<T> &operator=(const List<T> &that);
63 BOOLEAN operator==(const List<T> &that) const;
64 BOOLEAN operator!=(const List<T> &that) const;
65
66 public:
67 BOOLEAN Empty();
68 UINT Count();
69
70 public:
71 VOID PushFront(const T &tValue);
72 VOID PushBack(const T &tValue);
73 VOID PopFront();
74 VOID PopBack();
75 VOID Insert(const Iterator &beforeWhich, const T &value);
76 VOID Insert(const Iterator &beforeWhich,
77const Iterator &firstToInsert, const Iterator &NextOfLastToInsert);
78 Iterator Delete(const Iterator &which);
79 Iterator Delete(const Iterator &firstToDelete,
80const Iterator &nextOfLastToDelete);
81
82 public:
83 Node *head;
84 Node *tail;
85 };
86
87} // namespace xl
88
89#endif // #ifndef __XLLIST_H_2BEF1B3C_A056_4EC7_B5E3_9898E7945B54_INCLUDED__
xlTree.h
1#ifndef __XLTREE_H_6BB48AA6_133A_4E9F_944E_504B887B6980_INCLUDED__
2#define __XLTREE_H_6BB48AA6_133A_4E9F_944E_504B887B6980_INCLUDED__
3
4
5#include "xlDef.h"
6
7namespace xl
8{
9 template <typename T>
10 class Tree
11 {
12 public:
13 Tree();
14 Tree(const Tree<T> &that);
15 ~Tree();
16
17 private:
18 struct Node
19 {
20 T value;
21 Node *parent;
22 Node *left;
23 Node *right;
24 };
25
26 private:
27 class Iterator
28 {
29 public:
30 Iterator();
31 Iterator(const Tree<T> *tree);
32 Iterator(Iterator &that);
33
34 private:
35 Tree<T> *tree;
36 Node *current;
37 BOOLEAN bof;
38 BOOLEAN eof;
39
40 public:
41 T &operator * ();
42 T *operator -> ();
43
44 public:
45 Iterator &operator = (Iterator &that);
46 BOOLEAN operator == (Iterator &that);
47 BOOLEAN operator != (Iterator &that);
48
49 public:
50 Iterator Parent();
51 Iterator Left();
52 Iterator Right();
53 };
54
55 class PreorderIterator : public Iterator
56 {
57 public:
58 Iterator operator ++ ();
59 Iterator operator ++ (int);
60 Iterator operator -- ();
61 Iterator operator -- (int);
62 };
63
64 class InorderIterator : public Iterator
65 {
66 public:
67 Iterator operator ++ ();
68 Iterator operator ++ (int);
69 Iterator operator -- ();
70 Iterator operator -- (int);
71 };
72
73 class PostorderIterator : public Iterator
74 {
75 public:
76 Iterator operator ++ ();
77 Iterator operator ++ (int);
78 Iterator operator -- ();
79 Iterator operator -- (int);
80 };
81
82 public:
83 Iterator Bof();
84 Iterator Begin();
85 Iterator Eof();
86
87 public:
88 Tree<T> &operator=(const Tree<T> &that);
89 BOOLEAN operator==(const Tree<T> &that) const;
90 BOOLEAN operator!=(const Tree<T> &that) const;
91
92 public:
93 BOOLEAN Empty();
94 UINT Count();
95
96 public:
97 VOID InsertLeft(const Iterator &beforeWhich, const T &value);
98 VOID InsertRight(const Iterator &beforeWhich, const T &value );
99 Iterator Delete(const Iterator &which);
100
101 public:
102 Node *head;
103 };
104
105} // namespace xl
106
107#endif // #ifndef __XLTREE_H_6BB48AA6_133A_4E9F_944E_504B887B6980_INCLUDED__
（Tree 的接口还没完全考虑好，也不知道有没有必要把 Node 独立出来。）
这样是否大概足够了？敬请大家指教~
（再次重申一下，请不要来留个言说“干吗要重新发明轮子？”、“XXX 不是很好用吗？”之类的，谢谢！欢迎志同道合的朋友探讨，如能为我解惑，那么非常感谢。）
首发：http://www.cppblog.com/Streamlet/archive/2009/09/26/97303.html