QCore/Library說(shuō)明文檔

李文超

前言

QCore/Library是一套類STL的類庫(kù)，它在標(biāo)準(zhǔn)庫(kù)的范圍內(nèi)刪去了不常用的heap、deque等結(jié)構(gòu)（至少我是不常用的）。并為一些容器提供了一些特殊的接口，比如vector中的push_back_unique、add和add_unique等。

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

內(nèi)存調(diào)試

我們知道，在C/C++中內(nèi)存相關(guān)的東西是極難控制的，在使用不當(dāng)時(shí)可能造成各種錯(cuò)誤，輕則內(nèi)存泄漏，重則程序崩潰。所以，在生產(chǎn)環(huán)境中我們必須通過(guò)一個(gè)有效的手段來(lái)管理好內(nèi)存。當(dāng)然，在小塊內(nèi)存頻繁new、delete的過(guò)程中也會(huì)產(chǎn)生大量的內(nèi)存碎片，從而導(dǎo)致可用內(nèi)存數(shù)量越來(lái)越少。應(yīng)此我們?cè)O(shè)計(jì)了一個(gè)內(nèi)存池來(lái)控制小塊內(nèi)存的頻繁new、delete，以及做到對(duì)內(nèi)存泄漏的檢測(cè)。

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

經(jīng)過(guò)一天的調(diào)試，實(shí)在無(wú)法容忍的情況下，我翻閱了MSDN，查到了dbghelp.dll中可以通過(guò)許多函數(shù)來(lái)獲取調(diào)用堆棧，于是在此之下便生產(chǎn)出了CallStack模塊。有了它之后你就可以在任意地方保存當(dāng)前的調(diào)用堆棧了，真是十分方便。當(dāng)然直到現(xiàn)在，它還只支持在Windows下調(diào)用堆棧的獲取（稍后我會(huì)翻閱資料，實(shí)現(xiàn)一個(gè)like unix的版本，如果可能的話）。

這里不過(guò)多的描述實(shí)現(xiàn)的細(xì)節(jié)，具體可以看http://m.shnenglu.com/lwch/archive/2012/07/14/183420.html和http://m.shnenglu.com/lwch/archive/2013/01/19/197415.html兩篇文章。

最后來(lái)看allocator，這里只是簡(jiǎn)單的為其包裝了一層。

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的大部分，容器的作用是用來(lái)存儲(chǔ)對(duì)象的，容器分為線性和非線性兩種。線性的容器有vector、list、string以及用它們作為容器實(shí)現(xiàn)的queue、stack四種，非線性的則有rbtree、hashtable以及用它們作為容器實(shí)現(xiàn)的set、map、hashset、hashmap六種。對(duì)于每種容器，都必須定義出它的value_type、pointer、reference、const_reference、size_type、distance_type、const_iterator、const_reverse_iterator、iterator、reverse_iterator的類型。

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

traits

traits是一種萃取技術(shù)，通過(guò)它你可以獲取某種類型的一些特性，比如是否含有默認(rèn)構(gòu)造函數(shù)、拷貝構(gòu)造函數(shù)等。

__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;

};

通過(guò)特例化，可以定義出所有類型的這些屬性，比如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用于萃取出容器的特性，如上文所說(shuō)的value_type等特性，它的代碼很簡(jiǎn)單

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定義了一些對(duì)于Char的操作，包括assign（賦值）、eq（相等）、lt（小于）、compare（比較兩個(gè)字符串的大小）、length（獲取字符串的長(zhǎng)度）、move（移動(dòng)）、copy（拷貝）、assign（字符串賦值）、eof（結(jié)束符），它的代碼比較簡(jiǎn)潔，這里不做說(shuō)明。

type_compare

type_compare用于對(duì)兩種類型做運(yùn)行時(shí)的匹配，判斷所給定的兩種類型是否相同。同樣通過(guò)特例化技術(shù)可以很輕松的實(shí)現(xiàn)它的代碼。

迭代器

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

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

反向迭代器

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

iterator_traits

iterator_traits用于萃取出迭代器的所有特性，應(yīng)此它比較簡(jiǎn)單

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是一種比較常用的容器，它的內(nèi)部是一個(gè)連續(xù)的內(nèi)存塊，應(yīng)此它有兩個(gè)接口分別用于獲取內(nèi)存塊已使用的大小和容器的大小，它們是size和capacity，同樣它也有一個(gè)reserve接口來(lái)調(diào)整它的容量。由于vector的內(nèi)部是連續(xù)的，應(yīng)此它只允許從后面插入元素，所以它有push_back、push_back_unique和pop_back方法。當(dāng)然為了作為queue的容器，我還為其增加了pop_front方法用于刪除前端的元素。insert和erase用于在某個(gè)地方插入和刪除元素，add和add_unique用于插入另一個(gè)vector里的內(nèi)容，而unique則會(huì)將容器內(nèi)重復(fù)的元素刪除。

當(dāng)然vector可以像數(shù)組一樣的使用，它支持方括號(hào)的運(yùn)算符與at接口來(lái)獲取某個(gè)位置上的元素值。

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

list

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

queue和stack

queue是一種FIFO（先進(jìn)先出）的結(jié)構(gòu)，應(yīng)此我們建議使用list作為它的容器，通過(guò)list的push_back和pop_front可以使代碼變的高效。它擁有front和back方法來(lái)獲取隊(duì)列中隊(duì)頭和隊(duì)尾的元素值，同樣在插入隊(duì)列時(shí)，你可以不加選擇的直接插入或是插入一個(gè)不重復(fù)的值。

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

對(duì)于這兩種結(jié)構(gòu)的代碼，你可以在QCore/Library/queue.h和QCore/Library/stack.h中找到。

rbtree

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

性質(zhì)1. 節(jié)點(diǎn)是紅色或黑色。

性質(zhì)2. 根節(jié)點(diǎn)是黑色。

性質(zhì)3 每個(gè)葉節(jié)點(diǎn)是黑色的。

性質(zhì)4 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色。(從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn))

性質(zhì)5. 從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。

以上摘自百度百科

對(duì)于紅黑樹的每個(gè)節(jié)點(diǎn)，它都擁有它的key和value，當(dāng)然我們是按照節(jié)點(diǎn)的key來(lái)排序的（廢話）。紅黑樹擁有insert_equal和insert_unique方法分別用于插入一個(gè)節(jié)點(diǎn)，前者允許待插入節(jié)點(diǎn)的key已存在于這棵樹中，而后者在插入時(shí)并不允許這個(gè)節(jié)點(diǎn)的key已存在于這棵樹中，應(yīng)此它的返回值則是一個(gè)二元的。erase方法則提供了對(duì)于樹中某個(gè)節(jié)點(diǎn)的刪除操作，可以通過(guò)迭代器或某個(gè)key值來(lái)刪除其中的節(jié)點(diǎn)。

由于紅黑樹是一棵二叉查找樹，應(yīng)此它應(yīng)該具備find方法，用于在樹中查找某個(gè)節(jié)點(diǎn)，它返回的則是指向這個(gè)節(jié)點(diǎn)的一個(gè)迭代器。由于紅黑樹是有序的，應(yīng)此可以通過(guò)maximum和minimum方法得到其中的最大和最小值。通過(guò)lower_bound和upper_bound可以得到屬于某個(gè)key的[first,last]區(qū)間，equal_range就是干這個(gè)活的，count方法可以得到某個(gè)key所對(duì)應(yīng)的節(jié)點(diǎn)數(shù)。

rbtree就先介紹到這里，稍后我會(huì)在博客中繼續(xù)更新提供更完整的實(shí)現(xiàn)方法，它的代碼你可以在QCore/Library/rbtree.h中找到。

set和map

set是一種集合的結(jié)構(gòu)，應(yīng)此在集合中是不允許有重復(fù)的元素的，set是以rbtree作為容器的。應(yīng)此它的insert方法對(duì)應(yīng)于rbtree的insert_unique方法，同樣rbtree所具備的接口set也同樣擁有，set的key_type與value_type相同，都是給定的類型。

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

對(duì)于這兩種結(jié)構(gòu)的代碼，你可以在QCore/Library/set.h和QCore/Library/map.h中找到。

hashtable

hashtable是一種哈希結(jié)構(gòu)，應(yīng)此它的元素查找和插入是非常快的。在這里我用的是吊桶法來(lái)處理元素插入時(shí)的沖突，當(dāng)?shù)跬伴L(zhǎng)度過(guò)長(zhǎng)（默認(rèn)是11個(gè)元素）時(shí)，會(huì)將桶的大小翻一倍然后重建整個(gè)hashtable以提高h(yuǎn)ashtable中元素的查找速度。

同樣的在hashtable中有insert_equal和insert_unique來(lái)分別插入允許相同和不同的元素，當(dāng)遇到一個(gè)已有的元素時(shí)會(huì)將這個(gè)元素插入到第一個(gè)與它值相同的節(jié)點(diǎn)后面，這樣做的好處是可以簡(jiǎn)單的實(shí)現(xiàn)equal_range方法。同時(shí)hashtable擁有value方法用于通過(guò)一個(gè)指定的key來(lái)查找到它對(duì)應(yīng)的值，find方法則是用來(lái)查找一個(gè)key所對(duì)應(yīng)的迭代器的。同樣的hashtable也擁有count方法來(lái)獲取某個(gè)key所對(duì)應(yīng)的值的個(gè)數(shù)，maximum和minimum則是用來(lái)獲取最大值和最小值的。

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

hashset和hashmap

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

basic_string

basic_string的實(shí)現(xiàn)方式基本和vector差不多，為了提高效率，在所有的插入操作中若新的長(zhǎng)度的一倍小于一個(gè)定長(zhǎng)（默認(rèn)是512）字節(jié)時(shí)會(huì)申請(qǐng)新長(zhǎng)度的一倍作為容器的容量。

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

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

本章小結(jié)

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

在我后來(lái)做regex的過(guò)程中，我深刻的體會(huì)到，選用一個(gè)合適的數(shù)據(jù)結(jié)構(gòu)可以給代碼的運(yùn)行效率帶來(lái)非常大的提升。比如給定NFA某個(gè)狀態(tài)，需要找出所有從這個(gè)狀態(tài)出發(fā)的邊，之前使用的是map結(jié)構(gòu)來(lái)保存從某個(gè)狀態(tài)出發(fā)邊的vector，之后發(fā)現(xiàn)遍歷的速度非常緩慢，在換成hashmap之后，速度有顯著的提升。應(yīng)此在實(shí)際編程過(guò)程中，選用一個(gè)合適的數(shù)據(jù)結(jié)構(gòu)顯得尤為重要。

在使用線性結(jié)構(gòu)時(shí)，一般在小數(shù)據(jù)量或不平凡插入或刪除數(shù)據(jù)的情況下，選用vector作為容器會(huì)更快一些。而在需要平凡插入或刪除數(shù)據(jù)的場(chǎng)合下，選用list作為容器會(huì)有更優(yōu)異的結(jié)果。需要保持元素唯一性的情況下，我會(huì)優(yōu)先選用set作為容器，而在數(shù)據(jù)量非常大的情況下，就會(huì)使用hashset來(lái)代替set。map則如它的名字那樣，適用于key-value的場(chǎng)合，而hashmap在數(shù)據(jù)量非常大的情況下使用。

算法

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

具體的實(shí)現(xiàn)代碼，你可以在QCore/Library/algo.h中找到。

正則

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

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

IO

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

對(duì)于標(biāo)準(zhǔn)輸入輸出流來(lái)說(shuō)，實(shí)際上是對(duì)stdin、stdout、stderr的一些封裝，當(dāng)然里面也有一些比較特殊的接口，比如setColor（用于設(shè)置輸入輸出流的字體顏色）以及一些顏色相關(guān)的函數(shù)。

對(duì)于fstream來(lái)說(shuō)它是針對(duì)所有文件的，應(yīng)此它會(huì)多一個(gè)readAll接口用于一次性的讀出這個(gè)文件的所有內(nèi)容，為了節(jié)省頻繁讀寫磁盤所造成的性能損耗，我們給它定義了兩個(gè)buffer用來(lái)做cache，當(dāng)你要寫入文件時(shí)，它并不是馬上就直接往磁盤里寫的，而會(huì)加到buffer當(dāng)中，當(dāng)達(dá)到一個(gè)預(yù)值時(shí)才真正的寫入到磁盤。

那么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中找到。

結(jié)束

上文介紹了大部分模塊的實(shí)現(xiàn)過(guò)程與實(shí)現(xiàn)過(guò)程中的心得，讓我們來(lái)按照順序回顧一下。

首先介紹了內(nèi)存池的實(shí)現(xiàn)過(guò)程，以及在實(shí)現(xiàn)過(guò)程中遇到的一些問(wèn)題，比如如何檢測(cè)內(nèi)存泄漏、如何獲取調(diào)用堆棧等。

然后介紹了traits技術(shù)，它是用來(lái)萃取出一些特性用的，通過(guò)traits技術(shù)你可以得到一個(gè)類型是否為POD是否有默認(rèn)構(gòu)造函數(shù)等特性。而__container_traits則萃取出了容器的一些特性，比如值類型等等。通過(guò)char_traits我們得到了一些關(guān)于字符串的操作，比如求字符串的長(zhǎng)度等。

之后又通過(guò)特例化，我們實(shí)現(xiàn)了一種比較兩個(gè)變量類型是否相同的手段。

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

最后我們介紹了所有比較常用的容器，以及在某些場(chǎng)合下應(yīng)該使用哪種容器來(lái)達(dá)到高效的目的。比如在數(shù)據(jù)量較大時(shí)使用hashset要比使用set在插入和查找速度要更快一些，而且時(shí)間負(fù)責(zé)度更穩(wěn)定一些。

之后我們又介紹了一些常用算法，通過(guò)這些算法足以解決一些簡(jiǎn)單的問(wèn)題。比如排序和求取一個(gè)范圍[first, last]的長(zhǎng)度等。

在正則這一章中，介紹了我們是如何通過(guò)一些運(yùn)算符的重載來(lái)構(gòu)造出某個(gè)正則表達(dá)式的狀態(tài)機(jī)的，以及如何通過(guò)運(yùn)行這些狀態(tài)機(jī)來(lái)分析給定的字符串。

最后介紹了IO模塊，其中分為標(biāo)準(zhǔn)輸入輸出流和文件流，通過(guò)重載<<和>>運(yùn)算符，可以直觀的看到是從流中講內(nèi)容輸入到一個(gè)變量或是從一個(gè)變量中講內(nèi)容輸入到流中。

希望通過(guò)本文可使讀者體會(huì)到作者在設(shè)計(jì)這個(gè)庫(kù)的時(shí)候所考慮的問(wèn)題，以及對(duì)這個(gè)庫(kù)有一個(gè)大概的認(rèn)識(shí)，稍后我會(huì)在我的博客中補(bǔ)齊所有沒(méi)有介紹過(guò)的模塊是如何實(shí)現(xiàn)的。

修改記錄

2013.4.23第一次編寫

2013.4.24添加容器的說(shuō)明

2013.4.25添加hashtable、hashset、hashmap和basic_string結(jié)構(gòu)的說(shuō)明

2013.4.28添加算法和正則的說(shuō)明

2013.4.30添加IO的說(shuō)明，完結(jié)此文