打算先把基礎的東西組織起來，作為一個“大庫”（見上一篇《小庫還是大庫？》）。然后填加各個實用功能，作為一個個小庫或者大庫，過段時間再想辦法組織整理了。
首先是類型系統，我想來想去，覺得還是必須整理一下，尤其是 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 又給使用帶來了麻煩。于是，似乎需要先有一個完善的智能指針作為基礎才可以。而智能指針，如果要線程安全，又必須有平臺支持，所以似乎智能指針沒法放在這么基礎的位置?！?/p>
繞了好久，也想了好久，始終還是找不到好的辦法。所以，我暫時覺得還是放棄跨容器的 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
溪流 閱讀(679)
評論(18) 編輯 收藏 引用 所屬分類:
C++