QCore/Library說明文檔

李文超

前言

QCore/Library是一套類STL的類庫，它在標準庫的范圍內刪去了不常用的heap、deque等結構（至少我是不常用的）。并為一些容器提供了一些特殊的接口，比如vector中的push_back_unique、add和add_unique等。

Library主要分為六部分，內存調試相關、容器、算法、正則、IO和Graphic，每個模塊都有各自的分工，他們之間的耦合度極低，幾乎每個模塊都可以拆出來獨立使用，下面來分別介紹各個模塊。

內存調試

我們知道，在C/C++中內存相關的東西是極難控制的，在使用不當時可能造成各種錯誤，輕則內存泄漏，重則程序崩潰。所以，在生產環境中我們必須通過一個有效的手段來管理好內存。當然，在小塊內存頻繁new、delete的過程中也會產生大量的內存碎片，從而導致可用內存數量越來越少。應此我們設計了一個內存池來控制小塊內存的頻繁new、delete，以及做到對內存泄漏的檢測。

在內存池的設計之初，我只是簡單的設計出了可以使用的MemoryPool的最簡版本，它包含一個大塊內存的free_list和每個小塊內存的chunk_list，當時足以應付大部分的需求，而且最初用的是Visual Leak Detector來檢測內存泄漏。但隨著時間的推移，想要自己檢測內存泄漏的欲望越來越強烈，之后便有了一個use_list來保存內存塊的釋放情況。當時完成了這個patch之后，興奮的跑了一下TestCase，然后的結果我想大家應該知道了，一路的飄紅，到處是內存泄漏。

經過一天的調試，實在無法容忍的情況下，我翻閱了MSDN，查到了dbghelp.dll中可以通過許多函數來獲取調用堆棧，于是在此之下便生產出了CallStack模塊。有了它之后你就可以在任意地方保存當前的調用堆棧了，真是十分方便。當然直到現在，它還只支持在Windows下調用堆棧的獲取（稍后我會翻閱資料，實現一個like unix的版本，如果可能的話）。

這里不過多的描述實現的細節，具體可以看http://www.shnenglu.com/lwch/archive/2012/07/14/183420.html和http://www.shnenglu.com/lwch/archive/2013/01/19/197415.html兩篇文章。

最后來看allocator，這里只是簡單的為其包裝了一層。

template <typename T>

class allocator

{

public:

    allocator()

    {

    }

    allocator(const allocator<T>&)

    {

    }

    static T* allocate()

    {

        MemoryPool* pool = getPool();

        return reinterpret_cast<T*>(pool->allocate(sizeof(T), free_handler));

    }

    static T* allocate(size_t n)

    {

        MemoryPool* pool = getPool();

        return reinterpret_cast<T*>(pool->allocate(n * sizeof(T), free_handler));

    }

    static void deallocate(T* p)

    {

        MemoryPool* pool = getPool();

        pool->deallocate(p, sizeof(T));

    }

    static void deallocate(T* p, size_t n)

    {

        MemoryPool* pool = getPool();

        pool->deallocate(p, n * sizeof(T));

    }

    static void deallocateWithSize(T* p, size_t n)

    {

        MemoryPool* pool = getPool();

        pool->deallocate(p, n);

    }

    static T* reallocate(T* p, size_t old_size, size_t n)

    {

        MemoryPool* pool = getPool();

        return pool->reallocate(p, old_size, n * sizeof(T), free_handler);

    }

public:

    static void(*free_handler)(size_t);

    static void set_handler(void(*h)(size_t))

    {

        free_handler = h;

    }

protected:

    static MemoryPool* getPool()

    {

        static MemoryPool pool;

        return &pool;

    }

};

template <typename T>

void (*allocator<T>::free_handler)(size_t) = 0;

容器

容器占了Library的大部分，容器的作用是用來存儲對象的，容器分為線性和非線性兩種。線性的容器有vector、list、string以及用它們作為容器實現的queue、stack四種，非線性的則有rbtree、hashtable以及用它們作為容器實現的set、map、hashset、hashmap六種。對于每種容器，都必須定義出它的value_type、pointer、reference、const_reference、size_type、distance_type、const_iterator、const_reverse_iterator、iterator、reverse_iterator的類型。

所有容器必須包含以下幾個接口：size（獲取容器內元素個數）、clear（清空容器）、begin（獲取[first,last)區間中的first迭代器）、end（獲取[first,last)區間中的last迭代器）、rbegin（獲取反向的first迭代器）、rend（獲取反向的last迭代器）。

traits

traits是一種萃取技術，通過它你可以獲取某種類型的一些特性，比如是否含有默認構造函數、拷貝構造函數等。

__type_traits

__type_traits用于萃取出某種類型的一些特性，它的原型如下

template <typename T>

struct __type_traits

{

    typedef __true_type has_default_construct;

    typedef __true_type has_copy_construct;

    typedef __true_type has_assign_operator;

    typedef __true_type has_destruct;

    typedef __false_type is_POD;

};

通過特例化，可以定義出所有類型的這些屬性，比如char

template <>

struct __type_traits<char>

{

    typedef __true_type has_default_construct;

    typedef __true_type has_copy_construct;

    typedef __true_type has_assign_operator;

    typedef __false_type has_destruct;

    typedef __true_type is_POD;

};

__container_traits

__container_traits用于萃取出容器的特性，如上文所說的value_type等特性，它的代碼很簡單

template <typename T>

struct __container_traits

{

    typedef typename T::value_type value_type;

    typedef typename T::pointer pointer;

    typedef typename T::reference reference;

    typedef typename T::const_reference const_reference;

    typedef typename T::size_type size_type;

    typedef typename T::distance_type distance_type;

    typedef typename T::const_iterator const_iterator;

    typedef typename T::const_reverse_iterator const_reverse_iterator;

    typedef typename T::iterator iterator;

    typedef typename T::reverse_iterator reverse_iterator;

};

char_traits

char_traits定義了一些對于Char的操作，包括assign（賦值）、eq（相等）、lt（小于）、compare（比較兩個字符串的大小）、length（獲取字符串的長度）、move（移動）、copy（拷貝）、assign（字符串賦值）、eof（結束符），它的代碼比較簡潔，這里不做說明。

type_compare

type_compare用于對兩種類型做運行時的匹配，判斷所給定的兩種類型是否相同。同樣通過特例化技術可以很輕松的實現它的代碼。

迭代器

迭代器類是一種類似于smart pointer的東西，一般的它都會支持前置和后置的++和--操作，有一些特殊的迭代器同樣支持+=和-=操作。當然作為一種smart pointer少不了的是->和*操作，而對于比較操作，則比較的是迭代器所保存的值。

迭代器分為bidirectional_iterator和random_access_iterator兩種類型，前者只支持++和--操作而后者支持+和-運算符，之所以會定義出這兩種類型是為了提高算法的速度。對于一個迭代器來說同樣需要定義value_type、distance_type、pointer、reference、const_pointer、const_reference的類型。

反向迭代器

反向迭代器與正向的正好相反，應此我們可以類似的定義它的++為正向迭代器的--等運算符

iterator_traits

iterator_traits用于萃取出迭代器的所有特性，應此它比較簡單

template <typename Iterator>

struct iterator_traits

{

    typedef typename Iterator::value_type value_type;

    typedef typename Iterator::distance_type distance_type;

    typedef typename Iterator::pointer pointer;

    typedef typename Iterator::reference reference;

    typedef typename Iterator::const_pointer const_pointer;

    typedef typename Iterator::const_reference const_reference;

};

vector

vector是一種比較常用的容器，它的內部是一個連續的內存塊，應此它有兩個接口分別用于獲取內存塊已使用的大小和容器的大小，它們是size和capacity，同樣它也有一個reserve接口來調整它的容量。由于vector的內部是連續的，應此它只允許從后面插入元素，所以它有push_back、push_back_unique和pop_back方法。當然為了作為queue的容器，我還為其增加了pop_front方法用于刪除前端的元素。insert和erase用于在某個地方插入和刪除元素，add和add_unique用于插入另一個vector里的內容，而unique則會將容器內重復的元素刪除。

當然vector可以像數組一樣的使用，它支持方括號的運算符與at接口來獲取某個位置上的元素值。

vector容器就先介紹到這里，它的代碼你可以在QCore/Library/vector.h中找到。

list

list的內部則是一個雙向的鏈表，應此它在刪除前端的元素時會比vector快很多，它的接口基本跟vector相同，這里就不做過多的介紹了。由于vector是內存連續的，所以它可以直接通過索引來訪問某個元素，而list是一個雙向的鏈表，應此通過制定索引去訪問某個元素時會先看這個索引的值是否小于list長度的一半來決定是從list的頭部遍歷還是從list的尾部遍歷，它的代碼你可以在QCore/Library/list.h中找到。

queue和stack

queue是一種FIFO（先進先出）的結構，應此我們建議使用list作為它的容器，通過list的push_back和pop_front可以使代碼變的高效。它擁有front和back方法來獲取隊列中隊頭和隊尾的元素值，同樣在插入隊列時，你可以不加選擇的直接插入或是插入一個不重復的值。

stack是一種FILO（先進后出）的結構，同樣它擁有push、push_unique和pop方法以及top和bottom方法用于獲取棧頂端和底部的元素值。

對于這兩種結構的代碼，你可以在QCore/Library/queue.h和QCore/Library/stack.h中找到。

rbtree

rbtree（紅黑樹）是一棵自平衡的二叉查找樹，應此它擁有較高的查找效率，紅黑樹有以下5條性質

性質1. 節點是紅色或黑色。

性質2. 根節點是黑色。

性質3 每個葉節點是黑色的。

性質4 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)

性質5. 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。

以上摘自百度百科

對于紅黑樹的每個節點，它都擁有它的key和value，當然我們是按照節點的key來排序的（廢話）。紅黑樹擁有insert_equal和insert_unique方法分別用于插入一個節點，前者允許待插入節點的key已存在于這棵樹中，而后者在插入時并不允許這個節點的key已存在于這棵樹中，應此它的返回值則是一個二元的。erase方法則提供了對于樹中某個節點的刪除操作，可以通過迭代器或某個key值來刪除其中的節點。

由于紅黑樹是一棵二叉查找樹，應此它應該具備find方法，用于在樹中查找某個節點，它返回的則是指向這個節點的一個迭代器。由于紅黑樹是有序的，應此可以通過maximum和minimum方法得到其中的最大和最小值。通過lower_bound和upper_bound可以得到屬于某個key的[first,last]區間，equal_range就是干這個活的，count方法可以得到某個key所對應的節點數。

rbtree就先介紹到這里，稍后我會在博客中繼續更新提供更完整的實現方法，它的代碼你可以在QCore/Library/rbtree.h中找到。

set和map

set是一種集合的結構，應此在集合中是不允許有重復的元素的，set是以rbtree作為容器的。應此它的insert方法對應于rbtree的insert_unique方法，同樣rbtree所具備的接口set也同樣擁有，set的key_type與value_type相同，都是給定的類型。

map則是一種key-value的directory結構，應此它的key是不允許重復的，map同樣是以rbtree作為容器的。應此它的insert方法同樣對應于rbtree的insert_unique方法，在map中除了rbtree的maximum、minimum、lower_bound、upper_bound、equal_range和count沒有之外其他接口基本全都擁有，map的key_type是給定的類型，而value_type則是一個以Key和T組成的二元組。

對于這兩種結構的代碼，你可以在QCore/Library/set.h和QCore/Library/map.h中找到。

hashtable

hashtable是一種哈希結構，應此它的元素查找和插入是非常快的。在這里我用的是吊桶法來處理元素插入時的沖突，當吊桶長度過長（默認是11個元素）時，會將桶的大小翻一倍然后重建整個hashtable以提高hashtable中元素的查找速度。

同樣的在hashtable中有insert_equal和insert_unique來分別插入允許相同和不同的元素，當遇到一個已有的元素時會將這個元素插入到第一個與它值相同的節點后面，這樣做的好處是可以簡單的實現equal_range方法。同時hashtable擁有value方法用于通過一個指定的key來查找到它對應的值，find方法則是用來查找一個key所對應的迭代器的。同樣的hashtable也擁有count方法來獲取某個key所對應的值的個數，maximum和minimum則是用來獲取最大值和最小值的。

hashtable的代碼，你可以在QCore/Library/hashtable.h中找到。

hashset和hashmap

hashset和hashmap基本與set和map相同，這里不過多做介紹，關于它們的代碼，你可以在QCore/Library/hashset.h和QCore/Library/hashmap.h中找到。

basic_string

basic_string的實現方式基本和vector差不多，為了提高效率，在所有的插入操作中若新的長度的一倍小于一個定長（默認是512）字節時會申請新長度的一倍作為容器的容量。

與vector不同的是basic_string擁有c_str和data方法用于獲取字符指針，append方法往字符串尾部鏈接另一個字符串，assign方法給字符串賦值，find方法查找到第一個指定的字符串的位置，substr則用來獲取字符串中一部分的內容。

在basic_string中也有format的靜態方法來生成一個指定形式的字符串，其他用法基本與vecotr相同。它的代碼，你可以在QCore/Library/string.h中找到。

本章小結

上面介紹了所有的容器的接口和使用方法，以及在實現方式上的一些技巧。希望通過上面的介紹，讀者們能夠體會到STL為什么需要這么去設計、這么設計的好處是什么。

在我后來做regex的過程中，我深刻的體會到，選用一個合適的數據結構可以給代碼的運行效率帶來非常大的提升。比如給定NFA某個狀態，需要找出所有從這個狀態出發的邊，之前使用的是map結構來保存從某個狀態出發邊的vector，之后發現遍歷的速度非常緩慢，在換成hashmap之后，速度有顯著的提升。應此在實際編程過程中，選用一個合適的數據結構顯得尤為重要。

在使用線性結構時，一般在小數據量或不平凡插入或刪除數據的情況下，選用vector作為容器會更快一些。而在需要平凡插入或刪除數據的場合下，選用list作為容器會有更優異的結果。需要保持元素唯一性的情況下，我會優先選用set作為容器，而在數據量非常大的情況下，就會使用hashset來代替set。map則如它的名字那樣，適用于key-value的場合，而hashmap在數據量非常大的情況下使用。

算法

min和max函數分別用于求取最小值和最大值，fill_n用來填充若干個對象的值。copy_backward用來從后往前拷貝值。distance用來求給定區間[first, last)的長度。search用于在給定范圍[first1, last1)內查找符合序列[first2, last2)集合的值。swap和iterator_swap分別用于交換兩個值和兩個迭代器指向的值。sort用于將指定范圍[first, last)內的值排序，find用于在指定范圍[first, last)內查找指定的值。toArray用于將指定范圍[first, last)內的值轉換為內存連續的數組，compareArray則用于比較兩個數組內的值的個數和值是否相同。

具體的實現代碼，你可以在QCore/Library/algo.h中找到。

正則

通過重載+（相加）、-、|、+（前置）、*(前置）、!以及opt函數來生成正則表達式的ε-NFA，然后通過buildDFA函數生成DFA。通過parse和match可分析給定的字符串是否符合這個正則表達式，parse從頭開始跑DFA看這個字符串的開頭是否有符合這個正則表達式的字符串，而match則會找[first, last)區間內符合這個正則表達式的第一個字符串的相關結果。

具體的實現方法，你可以看http://www.shnenglu.com/lwch/archive/2013/02/15/197848.html和http://www.shnenglu.com/lwch/archive/2013/02/23/198043.html兩篇文章，而代碼則可在QCore/Library/regex/regex.h中找到。

IO

IO模塊包含文件IO和標準輸入輸出IO，首先有兩個基類分別是basic_istream和basic_ostream分別作為輸入和輸出stream的基類,其中分別定義了運算符>>和<<，通過這兩個運算符可以直觀的看到是從stream輸出到變量或是從變量輸入到stream中。之后有stdstream_basic和fstream_basic都繼承自basic_istream和basic_ostream分別作為basic_stdstream和basic_fstream的基類，它們都有open、size、tell、seek、read、write和flush方法，它們都是對底層C函數的一些封裝。而在下一層的basic_stdstream和basic_fstream中則實現了運算符>>和<<的所有重載，這樣做的好處是可以使代碼更有條理性，并方便閱讀。

對于標準輸入輸出流來說，實際上是對stdin、stdout、stderr的一些封裝，當然里面也有一些比較特殊的接口，比如setColor（用于設置輸入輸出流的字體顏色）以及一些顏色相關的函數。

對于fstream來說它是針對所有文件的，應此它會多一個readAll接口用于一次性的讀出這個文件的所有內容，為了節省頻繁讀寫磁盤所造成的性能損耗，我們給它定義了兩個buffer用來做cache，當你要寫入文件時，它并不是馬上就直接往磁盤里寫的，而會加到buffer當中，當達到一個預值時才真正的寫入到磁盤。

那么IO模塊就先介紹到這里了，它們的代碼你可以在QCore/Library/ios.h、QCore/Library/istream.h、QCore/Library/ostream.h、QCore/Library/fstream.h、QCore/Library/stdstream.h、QCore/Library/iostream.h和QCore/Library/iostream.cpp中找到。

結束

上文介紹了大部分模塊的實現過程與實現過程中的心得，讓我們來按照順序回顧一下。

首先介紹了內存池的實現過程，以及在實現過程中遇到的一些問題，比如如何檢測內存泄漏、如何獲取調用堆棧等。

然后介紹了traits技術，它是用來萃取出一些特性用的，通過traits技術你可以得到一個類型是否為POD是否有默認構造函數等特性。而__container_traits則萃取出了容器的一些特性，比如值類型等等。通過char_traits我們得到了一些關于字符串的操作，比如求字符串的長度等。

之后又通過特例化，我們實現了一種比較兩個變量類型是否相同的手段。

接下來我們介紹了迭代器和反向迭代器，它們是一種類似于smart pointer的東西，我們可以通過一個[first, last]前閉后開區間來表示一個容器內的所有元素。然后我們通過iterator_traits萃取出了迭代器的一些特性，比如值類型等。

最后我們介紹了所有比較常用的容器，以及在某些場合下應該使用哪種容器來達到高效的目的。比如在數據量較大時使用hashset要比使用set在插入和查找速度要更快一些，而且時間負責度更穩定一些。

之后我們又介紹了一些常用算法，通過這些算法足以解決一些簡單的問題。比如排序和求取一個范圍[first, last]的長度等。

在正則這一章中，介紹了我們是如何通過一些運算符的重載來構造出某個正則表達式的狀態機的，以及如何通過運行這些狀態機來分析給定的字符串。

最后介紹了IO模塊，其中分為標準輸入輸出流和文件流，通過重載<<和>>運算符，可以直觀的看到是從流中講內容輸入到一個變量或是從一個變量中講內容輸入到流中。

希望通過本文可使讀者體會到作者在設計這個庫的時候所考慮的問題，以及對這個庫有一個大概的認識，稍后我會在我的博客中補齊所有沒有介紹過的模塊是如何實現的。

修改記錄

2013.4.23第一次編寫

2013.4.24添加容器的說明

2013.4.25添加hashtable、hashset、hashmap和basic_string結構的說明

2013.4.28添加算法和正則的說明

2013.4.30添加IO的說明，完結此文