在開發HTTP相關程序時，經常會碰到從網絡鏈接URL中提取協議名、服務器、路徑等目標對象，如果使用C/C++字符串操作函數，那么則顯得有點麻煩且代碼不易維護，其實關于文本內容的解析工作，都可優先考慮使用正則表達式庫來解決處理，C++方面的正則庫也有很多種，如atl、pcre、boost。下面就使用boost中的regex來解析URL提取協議名、服務器、路徑為目標說明其用法。

協議名
   可有可無，如果有時則后面必跟著://，如果沒有，則默認為使用http協議。通常還有其它的協議如https、ssl、ftp、mailto等。因此匹配協議名的正則表達式應該是(?:(mailto|ssh|ftp|https?)://)?，注意這個表達式本身捕獲了協議名，但不包括://。
   
服務器
   或是域名，如www.csdn.net；或是IP地址，如192.168.1.1，可帶端口號，如192.168.1.1:8080。匹配域名的正則表達式為(?:[a-z0-9](?:[-a-z0-9]*[a-z0-9])?\.)+(?:com|net|edu|biz|gov|org|in(?:t|fo)|(?-i:[a-z][a-z]))，表達式"(?:com|net|edu|biz|gov|org|in(?:t|fo)"匹配了com、net、edu、biz、gov、org、int、info等常見的域名，而(?-i:[a-z][a-z])匹配了國家代碼，而且只允許小寫為合法的，如www.richcomm.com.cn。匹配IP要盡量精確，考慮到IP每部分應為數字且范圍在0-255之間，因此表達式應為(?:[01]?\d\d?|2[0-4]\d|25[0-5])\.(?:[01]?\d\d?|2[0-4]\d|25[0-5])\.(?:[01]?\d\d?|2[0-4]\d|25[0-5])\.(?:[01]?\d\d?|2[0-4]\d|25[0-5])。注意以上域名或IP的正則式本身不捕獲它們，這是為了留在后面作為整體捕獲。
   端口號的正則表達式為(?::(\d{1,5}))?，這里限制了端口號為1至5位的數字，更精確的匹配如要求在某范圍如[1024,65535]間則可參考以上IP正則模式。綜上所得，匹配服務器的正則表達式為((?:(?:[a-z0-9](?:[-a-z0-9]*[a-z0-9])?\.)+(?:com|net|edu|biz|gov|org|in(?:t|fo)|(?-i:[a-z][a-z]))|(?:[01]?\d\d?|2[0-4]\d|25[0-5])\.(?:[01]?\d\d?|2[0-4]\d|25[0-5])\.(?:[01]?\d\d?|2[0-4]\d|25[0-5])\.(?:[01]?\d\d?|2[0-4]\d|25[0-5])))(?::(\d{1,5}))?，這個正則式作為整體捕獲了域名或IP，及端口號（若有），如www.csdn.net，則得到www.csdn.net和空（沒有端口，http默認為80，https默認為443）子串；192.168.1.1:8080則得到192.168.1.1和8080子串。
   
路徑
   最簡單的形式為(/.*)?，更精確的形式為/[^.!,?;"'<>()\[\]{}\s\x7F-\xFF]*(?:[.!,?]+[^.!,?;"'<>()\[\]{}\s\x7F-\xFF]+)*。
   
   以上所有正則表達式均為ascii字符集，對于unicode字符集則在其前加L即可。
   
   為方便使用，封裝成了兩個自由模板函數，如下所示    
   測試示例如下          對URL的解析，因時間有限，本文所述不盡詳細，只是略作分析，以點帶面，更多的精確匹配則依賴于實際的應用需求。      摘要:    在《基于stl序列容器實現的通用集合類》一文中，已經講到了具體實現，近來因再次用到它又改進完善了，主要體現在以下幾點：1）增加了查找操作方法，支持按值類型和謂詞條件兩種方式。2）增加重載了按值類型和謂詞條件2種方式刪除元素的方法。3）增加了2個模板參數以支持線程安全，一個是線程模型模板類，一個是互斥鎖類，使用loki庫來實現，因此所有方法現在都是線程安全的，當需...  閱讀全文      摘要:    本文講述雙端堆的5個公開泛型操作算法：make_dheap（原位構造雙端堆）、push_dheap（插入元素）、pop_max_dheap（刪除最大元素）、pop_min_dheap（刪除最小元素），is_dheap（堆驗證），每個算法都提供<小于運算符和仿函數比較2個版本，要注意的是比較必須是嚴格弱序的，即對于<版本存在a<b為真且b<...  閱讀全文      摘要:    在《基于雙端堆實現的優先級隊列（1）：原理》一文中講述了雙端堆的相關原理，本文則詳細講述具體的內部實現，便于區分，內部函數名稱都以雙下劃線作為前綴，在這里，有幾個關鍵問題需要說明    1）怎么求一個結點的對稱結點：如果完全二叉樹根結點從索引1開始但不存儲元素，那么最小堆根結點則在索引2，最大堆根結點則在索引3，4和5為2的左右孩...  閱讀全文 前言
   眾所周知，stl中的優先級隊列是基于最大堆實現的，能夠在對數時間內插入元素和獲取優先級最高的元素，但如果要求在對數時間內還能獲取優先級最低的元素，而不只是獲取優先級最高的元素，該怎么實現呢？可以用最大堆-最小堆或雙端堆數據結構來實現，最大堆-最小堆和雙端堆都是支持雙端優先隊列的插入、刪除最小元素和最大元素等操作的堆，在這些操作上，時間復雜度都是對數時間，但是雙端堆的操作比最大堆-最小堆的相應操作還要快一個常數因子，而且算法更加簡單，因此本文講述選擇使用雙端堆實現優先級隊列的原理。

定義與性質
   雙端堆是一顆完全二叉樹，該完全二叉樹要么為空，要么滿足以下性質：
 （1）根結點不包含元素
 （2）左子樹是一個最小堆
 （3）右子樹是一個最大堆
 （4）如果右子樹不為空，則令i是左子樹中任一結點，j是i在右子樹中的對應結點，如果i在右子樹中的對應結點不存在，則j為i的父結點在右子樹中的對應結點，  對于結點i和j，i的關鍵字值小于等于j的關鍵字值。
   從以上性質可以推出：對于左子結中的任一結點i，設j為i的對稱結點，則由最小元素到i，i到j，j到最大元素的路徑上元素是非遞減有序的。在雙端堆上的操作算法核心就是為了保證這樣的單向路徑上元素必須是非遞減有序的。
   例如下圖所示，就是一個雙端堆
操作算法
 （1）插入元素：設所插結點為i，其對稱結點為j，要分2種情況 a）當i處于最小堆時，則j處于最大堆中，如果KeyValue(i)>KeyValue(j)，則設置value= KeyValue(i)，KeyValue(i)=KeyValue(j)，并執行在最大堆中位置j處插入值value的操作；否則執行在最小堆中位置i處插入值KeyValue(i)的操作。b）當i處于最大堆時，則j處于最小堆中，如果KeyValue(i)<KeyValue(j)，則設置value=KeyValue(i)，KeyValue(i)=KeyVaue(j)，并執行在最小堆中位置i處插入值value的操作；否則執行在最大堆中位置j處插入值KeyValue(i)的操作。

 （2）刪除最小元素：首先在最小堆中執行一個向下回溯過程，這個過程執行的堆大小要比原來的堆小1，從最小元素結點開始，每次選取關鍵字值較小的孩子結點，并用其值更新父結點值，直到底部沒有孩子結點，執行的結果是在底部某葉子結點i處形成一個空洞（形象說法，這個空洞需要后續操作來調整填補，下同），i的對稱結點j在最大堆中，設最末元素結點為e，如果KeyValue(e)>KeyValue(j)，則設置KeyValue(i)=KeyValue(j)，并執行在最大堆中位置j處插入值KeyValue(e)的操作；否則執行在最小堆中位置i處插入值KeyValue(e)的操作。

 （3）刪除最大元素：這個操作比刪除最小元素要麻煩一點，和刪除最小元素類似，先執行一個向下回溯過程得到空洞結點i，其對稱結點為j，為了保證能滿足雙端堆的性質，需要考慮以下幾種情況：a）j只存在一個孩子，如下圖第1個所示。 b）j存在兩個孩子，如下圖第2個所示。 c）j不存在孩子，但存在左兄弟（可能存在孩子），如下圖第3個所示。 d）j不存在孩子，但存在右兄弟，如下圖最后一個所示。
令min為具有較小值的結點，max為具有較大值的結點，最末元素結點為e，value=KeyValue(e)，如果j存在孩子結點，則 min為孩子中關鍵字值較小的結點，max為關鍵字值較大的結點；否則min為j和其兄弟結點中關鍵字值較小的結點，max為關鍵字值較大的結點。如果KeyValue(min)<value而且value<KeyValue(max)，在這種情況下，只需調整i或其父結點、max的值即可，操作如下：如果KeyValue(i)<KeyValue(max)，則設置KeyValue(parent(i))=KeyValue(max)，否則設置KeyValue(i)=KeyValue(max)，最后設置KeyValue(max)=value；如果KeyValue(max)<=value，在這種情況下，則執行在最大堆中位置i處插入值value的操作；如果value<=KeyVlaue(min)，在這種情況下，先調整i或其父結點、max的值（見上），再執行在最小堆中位置min處插入值value的操作。

 （4）構造堆：給定一個元素大小為N的序列S，在這個序列空間上構造堆，一般有兩種實現方法，一是循環N-1次，每次插入元素S[i]，也就是自頂向下構建堆，時間復雜度為O(NlgN)。另一種是從最后一個內部結點N/2左右開始，執行調整堆操作，直到第一個元素，也就是自底向上構建堆，時間復雜度為O(N)。

 （5）最大堆（最小堆）插入：這是一個向上回溯過程，和單個最大堆（最小堆）操作是一樣的，從底部某處開始，比較待插元素和結點關鍵字值大小，直到前者不大于（不小于）后者時或碰到最大堆（最小堆）頂部為止，這時就找到了插入位置，將待插元素放到這個位置即可。

   設雙端堆元素個數為N，由于完全二叉樹高度為O(lgN)，則插入元素操作時間復雜度為O(lgN)，刪除最小元素和最大元素為不超過2O(lgN)，實現這些操作最重要的一點就是要保證性質4，只有當性質4滿足時，雙端堆才有意義，才能保證獲取最大元素和最小元素操作的對數時間，具體的實現詳見下文。      摘要: 類型定義     在多叉樹中，深度遍歷迭代器有只讀、讀寫、只讀反轉、讀寫反轉4種，在mtree容器中的定義如下： Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ -->1&n...  閱讀全文    一、default constructor---默認構造函數，亦即無參構造函數。從對象構造語義上講，可分為以下2種：1）trivial 平凡的，可以理解為淺構造  2）notrivial 非平凡的，可以理解為深構造。當一個class沒有顯式地(explicitly)聲明或定義任何constructor的時候，一個default constructor就會被編譯器隱式地（implicitly)聲明或定義出來。那么這個implicitly default constructor到底是trivial還是notrivial的呢？對于一個class，當存在以下4種情況時，其implicitly default constructor就是notrivial的。
   （1）class內含一個或多個成員對象(member object)，且這些member object中至少一個存在default constructor（無論是顯式的default constructor還是隱式的notrival default constructor）
   （2）class派生自一個繼承串鏈，其中至少有一個base class存在default constructor（再次強調，無論是顯式的default constructor還是隱式的notrival default constructor）
   （3）class聲明一個或多個虛函數(virtual function)
   （4）class派生自一個繼承串鏈，其中至少有一個虛基類(virtual base class)，而不管這些virtual base class是否存在default constructor
   顯而易見，這4種情況是正交的，當不存在以上4種情況時，其implicitly default constructor就是trivial的。只有notrivial的default constructor才會被編譯器真正生成，而trivial的不會生成。

   二、copy constructor---拷貝構造函數，亦即帶有當且僅有一個參數，類型為同類對象的構造函數。從對象拷貝語義上講，可分為以下2種：1）bitwise copy 位拷貝，可以理解為淺拷貝  2）no bitwise copy 非位拷凡，可以理解為深拷貝。當一個class沒有顯式地聲明或定義copy constructor時，一個copy constructor就會被編譯器隱式地聲明或定義出來。那么這個implicitly copy constructor到底是bitwise copy還是no bitwise copy的呢？對于一個class，當存在以下4種情況時，其implicitly copy constructor就是no bitwise copy的。
   （1）class內含一個或多個成員對象，且這些member object中至少一個存在copy constructor（無論是顯式的copy constructor還是隱式的no bitwise copy constructor）
   （2）class派生自一個繼承串鏈，其中至少有一個base class存在copy constructor（再次強調，無論是顯式的copy constructor還是隱式的no bitwise copy constructor）
   （3）class聲明一個或多個虛函數
   （4）class派生自一個繼承串鏈，其中至少有一個虛基類，而不管這些virtual base class是否存在copy constructor
   顯而易見，這4種情況是正交的，當不存在以上4種情況時，其implicitly copy constructor就是bitwise copy的。只有no bitwise copy的copy constructor才會被編譯器真正生成，而bitwise copy的不會生成。

   三、對于defualt constructor，當一個class內顯式地存在constructor（包括default constructor）時，編譯器不會再生成它，但如果這個class滿足以上4種情況至少一種時，編譯器就需要負責執行相關的初始化：對于(1)要調用成員對象的default constructor；對于(2)要調用基類的default constructor；對于(3)要設定虛函數表的指針；對于(4)要設定虛基類的指針和偏移量。而這些初始化在用戶代碼執行前。
        
   四、對于copy constructor，當一個class內顯式地存在copy constructor時，編譯器不會再生成它，但如果這個class滿足以上情況(3)或(和)(4)時，編譯器就需要負責執行相關的拷貝：對于(3)要決定怎么設定虛函數表指針。對于(4)要決定怎么設定虛基類的指針和偏移量。同理類推，如果這個class滿足情況(1)或(和)(2)，而且其成員對象或基類子對象又滿足情況(3)或(和)(4)時，編譯器也需要負責執行相關的拷貝了。而這些拷貝在用戶代碼執行前。      摘要: Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->  1/***************************************************************************************&...  閱讀全文      摘要: 類型定義    在多叉樹中，葉子遍歷迭代器有只讀、讀寫、只讀反轉、讀寫反轉4種，在mtree容器中的定義如下： Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->1  &nb...  閱讀全文      摘要: 類型定義    在多叉樹中，兄弟遍歷迭代器有只讀、讀寫、只讀反轉、讀寫反轉4種，在mtree容器中的定義如下： Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->1   ...  閱讀全文