摘要:    在《基于stl序列容器實(shí)現(xiàn)的通用集合類》一文中，已經(jīng)講到了具體實(shí)現(xiàn)，近來因再次用到它又改進(jìn)完善了，主要體現(xiàn)在以下幾點(diǎn)：1）增加了查找操作方法，支持按值類型和謂詞條件兩種方式。2）增加重載了按值類型和謂詞條件2種方式刪除元素的方法。3）增加了2個模板參數(shù)以支持線程安全，一個是線程模型模板類，一個是互斥鎖類，使用loki庫來實(shí)現(xiàn)，因此所有方法現(xiàn)在都是線程安全的，當(dāng)需...  閱讀全文      摘要:    本文講述雙端堆的5個公開泛型操作算法：make_dheap（原位構(gòu)造雙端堆）、push_dheap（插入元素）、pop_max_dheap（刪除最大元素）、pop_min_dheap（刪除最小元素），is_dheap（堆驗(yàn)證），每個算法都提供<小于運(yùn)算符和仿函數(shù)比較2個版本，要注意的是比較必須是嚴(yán)格弱序的，即對于<版本存在a<b為真且b<...  閱讀全文      摘要:    在《基于雙端堆實(shí)現(xiàn)的優(yōu)先級隊(duì)列（1）：原理》一文中講述了雙端堆的相關(guān)原理，本文則詳細(xì)講述具體的內(nèi)部實(shí)現(xiàn)，便于區(qū)分，內(nèi)部函數(shù)名稱都以雙下劃線作為前綴，在這里，有幾個關(guān)鍵問題需要說明    1）怎么求一個結(jié)點(diǎn)的對稱結(jié)點(diǎn)：如果完全二叉樹根結(jié)點(diǎn)從索引1開始但不存儲元素，那么最小堆根結(jié)點(diǎn)則在索引2，最大堆根結(jié)點(diǎn)則在索引3，4和5為2的左右孩...  閱讀全文 前言
   眾所周知，stl中的優(yōu)先級隊(duì)列是基于最大堆實(shí)現(xiàn)的，能夠在對數(shù)時間內(nèi)插入元素和獲取優(yōu)先級最高的元素，但如果要求在對數(shù)時間內(nèi)還能獲取優(yōu)先級最低的元素，而不只是獲取優(yōu)先級最高的元素，該怎么實(shí)現(xiàn)呢？可以用最大堆-最小堆或雙端堆數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)，最大堆-最小堆和雙端堆都是支持雙端優(yōu)先隊(duì)列的插入、刪除最小元素和最大元素等操作的堆，在這些操作上，時間復(fù)雜度都是對數(shù)時間，但是雙端堆的操作比最大堆-最小堆的相應(yīng)操作還要快一個常數(shù)因子，而且算法更加簡單，因此本文講述選擇使用雙端堆實(shí)現(xiàn)優(yōu)先級隊(duì)列的原理。

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

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

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

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

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

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

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

   三、對于defualt constructor，當(dāng)一個class內(nèi)顯式地存在constructor（包括default constructor）時，編譯器不會再生成它，但如果這個class滿足以上4種情況至少一種時，編譯器就需要負(fù)責(zé)執(zhí)行相關(guān)的初始化：對于(1)要調(diào)用成員對象的default constructor；對于(2)要調(diào)用基類的default constructor；對于(3)要設(shè)定虛函數(shù)表的指針；對于(4)要設(shè)定虛基類的指針和偏移量。而這些初始化在用戶代碼執(zhí)行前。
        
   四、對于copy constructor，當(dāng)一個class內(nèi)顯式地存在copy constructor時，編譯器不會再生成它，但如果這個class滿足以上情況(3)或(和)(4)時，編譯器就需要負(fù)責(zé)執(zhí)行相關(guān)的拷貝：對于(3)要決定怎么設(shè)定虛函數(shù)表指針。對于(4)要決定怎么設(shè)定虛基類的指針和偏移量。同理類推，如果這個class滿足情況(1)或(和)(2)，而且其成員對象或基類子對象又滿足情況(3)或(和)(4)時，編譯器也需要負(fù)責(zé)執(zhí)行相關(guān)的拷貝了。而這些拷貝在用戶代碼執(zhí)行前。      摘要: Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->  1/***************************************************************************************&...  閱讀全文      摘要: 類型定義    在多叉樹中，葉子遍歷迭代器有只讀、讀寫、只讀反轉(zhuǎn)、讀寫反轉(zhuǎn)4種，在mtree容器中的定義如下： Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->1  &nb...  閱讀全文      摘要: 類型定義    在多叉樹中，兄弟遍歷迭代器有只讀、讀寫、只讀反轉(zhuǎn)、讀寫反轉(zhuǎn)4種，在mtree容器中的定義如下： Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->1   ...  閱讀全文 方法1：使用find和xargs命令
     find dir | xargs grep str，dir是指某個目錄
     find file | xargs grep str，file是指某個文件
   注意：這種方法，會遞歸搜索子目錄

方法2：直接使用grep命令
     grep str dir/*，dir是指某個目錄，但不遞歸搜索其子目錄
     grep -r str dir/*，使用-r選項(xiàng)，遞歸搜索其子目錄
     grep str file，file是指某個文件

方法3：綜合以上兩種，寫一個shell腳本，代碼如下 

 1#! /bin/bash
 2# findstr.sh   
 3
 4if [ $# -lt "2" ]; then
 5   echo "Usage: `basename $0` path name [option]"
 6   exit 1
 7fi   
 8
 9path=$1
10name=$2  
11shift 
12shift   
13
14for option in "$@"
15do
16   case $option in
17   -r) dir_op="-r"
18   ;;
19   -i) lu_op="-i"
20   ;;
21   *) if [ -n "$option" ]; then
22         echo "invalid option"
23         exit 1
24       fi
25   ;;
26  esac
27done    
28
29grep_str_of_file()
30{
31     file=$1
32     str=$2
33     out=$(grep -n $lu_op "$str" "$file")
34     if [ -n "$out" -a "$file" != "$0" ]; then
35        echo "$file: $out"
36     fi
37}    
38
39find_str()
40{
41  if [ -d "$1" ]; then
42     for file in $1/*
43      do
44        if [ "$dir_op" = "-r" -a -d "$file" ]; then
45            find_str $file $2
46        elif [ -f "$file" ]; then
47           grep_str_of_file $file $2
48        fi
49     done
50 elif [ -f "$1" ]; then
51   grep_str_of_file $1 $2    
52 fi
53}  
54
55find_str $path $name

  這樣一來，不管$1參數(shù)是目錄還是文件，都能處理，使用示例如下：
    findstr /usr/include main          不遞歸搜索子目錄，大小寫敏感
    findstr /usr/include main -i       不遞歸搜索子目錄，忽略大小寫
    findstr /usr/include main -r       遞歸搜索子目錄，大小寫敏感
    findstr /usr/include main -r  -i   遞歸搜索子目錄，忽略大小寫 
    findstr main.cpp main              在文件中搜索，大小寫敏感
    findstr main.cpp main -i           在文件中搜索，忽略大小寫 

  上面所述的示例中，str不限于特定的文本，可以是帶正則表達(dá)式的匹配模式。而第3種方法，也可以用sed替換grep來顯示文本行，在此基礎(chǔ)上能作更多的處理，比如格式化顯示、統(tǒng)計匹配的文本個數(shù)、搜索策略等，在此就不詳究了。