摘要：通過分析股市行情中排序問題的具體問題，滿足目前軟件快速開發(fā)的需求，結(jié)合STL技術(shù)給出解決問題的具體實現(xiàn)方法，并討論STL技術(shù)在未來軟件開發(fā)中的發(fā)展趨勢。

關(guān)鍵詞：STL容器；定時排序；即時排序；股市

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)08-10ppp-0c

股民在使用股票分析軟件的過程中需要及時獲得到股票的各種指標排名，例如今日漲幅排名、今日量比排名等，因此股票服務(wù)器軟件為了滿足用戶需求要把從交易所得到的原始數(shù)據(jù)按照相應(yīng)計算公式得出排名發(fā)送給客戶端軟件，由于客戶端同時登錄服務(wù)器的數(shù)量比較大，這就需要在實現(xiàn)排名功能時服務(wù)器要保證的效率和穩(wěn)定性，因此開發(fā)選擇采用C++STL技術(shù)，需要用到STL中的 vector、mulset等容器來輔助實現(xiàn)。

1 對用到的名詞進行解釋：

1.1 STL介紹：

Standard Template Library ，標準模板庫，從根本上說，STL是一些“容器”的集合，這些“容器”有l(wèi)ist，vector，set，map等，STL也是算法和其他一些組件的集合。容器、算法、和允許算法工作在容器中的元素上的iterator，這就是STL所有的東西。

1.2 定時排序方法：

也稱作時間驅(qū)動排序，就是指服務(wù)器分析軟件從交易所獲得股票信息的原始數(shù)據(jù)后整理計算后保存在容器中，設(shè)置一定的時間間隔例如10秒鐘，當設(shè)置的時間到后就對容器中的所有信息按照一定規(guī)則進行排序，然后把排序結(jié)果供股票分析軟件客戶端的調(diào)用取排序數(shù)據(jù)，達到指標排序的功能。

1.3 即時排序方法：

也稱數(shù)據(jù)驅(qū)動排序，就是指當股票分析軟件服務(wù)器從交易所獲得到的每一筆股票信息的原始數(shù)據(jù)整理計算后調(diào)用相應(yīng)算法插入到排序結(jié)果容器中去，滿足股票分析軟件客戶端的調(diào)用取排序數(shù)據(jù)，達到指標排序的功能。

2 簡化股市排序問題提取模型：

由于股票交易過程中各種指標的數(shù)量相當多，為了方便闡述排序方法的實現(xiàn)過程，把股票指標簡化為商品GoodID屬性和最新價格Price屬性，因此抽象定義要排序的原子體為

class SortItem

{

public:

SortItem();

~SortItem();

// 設(shè)置商品的最新價格屬性

int SetPriceValue(int nPrice);

// 重載小于運算符，保證兩個對象的比較

bool operator<(const SortItem Item) const;

private:

int m_nGoodId;

int m_nPrice;

};

重載函數(shù)的實現(xiàn)定義如下：

bool SortItem::operator<(const SortItem Item) const

{

return m_lValue < Item.m_lValue;

}

3 具體實現(xiàn)：

3.1 簡單介紹定時排序具體實現(xiàn)方法：

首先選擇vector容器存儲SortItem對象，當新商品的數(shù)據(jù)到達后采用vector 自帶的push_back方法把對象插入到容器中，如果某一商品的更新數(shù)據(jù)到達后需要從容器中查找到此商品GoodID的存儲位置，調(diào)用類SortItem的SetPriceValue方法對數(shù)據(jù)進行更新。

由于排序要實現(xiàn)的是針對SortItem類中的m_nPrice成員變量的大小比較，而從交易所獲得到的更新數(shù)據(jù)，是針對 m_nGoodId成員變量把vector中同一商品GoodID對象的m_nPrice值更改，達到數(shù)據(jù)的更新，如果不考慮存儲策略，每次來新數(shù)據(jù)后都遍歷vector比較m_nGoodId成員，效率比較低，因此采用MAP容器，針對每個商品ID，存儲此商品ID和此商品ID在vector容器中的位置，即 MAP; 如圖1所以：

MAPm_MapGoodID; vector m_DataVec;

圖1 定時排序存儲結(jié)構(gòu)

當設(shè)置的排序時間到達后調(diào)用 STL的排序方法 stl::stable_sort(m_DataVec.begin()，m_DataVec.end()); 對原子對象進行排序，并把排序結(jié)果復制到結(jié)果容器中去。

具體實現(xiàn)如下：

void NormalSortInsertData(SortItem tmpItem)

{

MAP::itertor m_MapIter;

m_MapIter = m_MapGoodID.find(tmpItem.m_nGoodsID);

if(m_MapIter != m_MapGoodID.end()) //找到

{

m_DataVec[m_MapIter->second].SetPriceValue(tmpItem.m_nPrice);

}

else//沒找到

{

m_DataVec.push_back(tmpItem);

m_MapGoodID.insert(std::map::value_type(tmpItem.m_nGoodsID， m_DataVec.size()-1));

}

}

3.2 著重討論即時排序方法：

首先定義存儲結(jié)構(gòu)：分析由于即時排序就需要來了數(shù)據(jù)馬上進行排序，不可能采用定時排序的存策略，來了數(shù)據(jù)push到容器中，然后馬上調(diào)用 sort方法，在進行復制數(shù)據(jù)，這樣會帶來太大的CPU和內(nèi)存的開銷，因此要改變存儲結(jié)構(gòu)，綜觀STL的所有容器最終確定為 set 。首先 set是自動排序的，來了數(shù)據(jù)只需要調(diào)用set的內(nèi)部方法 insert插入數(shù)據(jù)即可，但由于set是采用鏈表存儲，因此更新數(shù)據(jù)時如果不采取措施會帶來很大開銷，需要遍歷鏈表找到所在的位置后才能進行刪除，然后再插入新的對象。這樣每次遍歷查找花費大量CPU時間，采取的對策是：

用 MAP存儲商品ID和此商品ID的當前對象即， 如圖2 所示，當某商品的新的數(shù)據(jù)到來，針對商品ID在MAP中查找到對應(yīng)的信息，用臨時對象保存存取的 SortItem 屬性值，然后根據(jù)臨時SortItem 去set容器中查找，調(diào)用set的erase函數(shù)，把臨時對象從容器中查找并刪除，然后調(diào)用set的insert方法把新的SortItem對象插入，同時并更新MAP容器重此商品的SortItem 屬性值。達到新來的數(shù)據(jù)的排序功能。

MAP m_MapGoodID;vectorm_DataVec;

圖2 即時排序存儲結(jié)構(gòu)

由于排序是對 m_nPrice成員進行排序，因此重寫的< ，由于set容器需要存儲的元素大小不能一樣，故重載比較函數(shù)

bool SortItem::operator<(const SortItem Item) const

{

if(m_lValue == Item.m_lValue)

return m_nGoodsID < Item.m_nGoodsID ;

else

return m_lValue < Item.m_lValue;

}

說明：當比較的商品m_lValue相同的時候再對m_nGoodsID進行比較，由于每個商品記錄數(shù)唯一，因此改寫的比較函數(shù)能保證mulset容器元素的唯一性。

具體實現(xiàn)如下：

// 快速排序插入SortItem對象

void QuickSortInsertData(SortItem tmpItem)

{

SortItem oldItem; // 定義一臨時SortItem對象，用來保存MAP容器中原存儲的SortItem 對象

MAP::itertor m_MapIter; // 定義MAP容器的迭代器指針

m_MapIter = m_MapGoodID.find(tmpItem.m_nGoodsID); // 在m_MapGoodID MAP容器中根據(jù)商品ID信息查找

if(m_MapIter != m_MapGoodID.end()) //找到

{

oldItem = m_MapIter->second; // 把原來SortItem對象賦給臨時變量

m_MapIter->second = tmpItem; // 把待插對象插入到MAP容器中

if(m_SetSortData.erase(oldItem) == 1)// 從SET中刪除臨時對象

{

m_SetSortData.insert(tmpItem);// 把待插對象插入到MULSETP容器中，達到排序的效果

}}

else//沒找到

{

// 把商品ID和待插對象插入到MAP容器中 m_MapGoodID.insert(std::map::value_type(nGoodsID， tmpItem));

m_SetSortData.insert(tmpItem);// 把待插對象插入到SET容器中，達到排序的效果

}} // 結(jié)束

4 兩個方法的優(yōu)缺點比較：

定時排序方法：實現(xiàn)思路比較簡單，結(jié)構(gòu)清晰，相比起來容易實現(xiàn)，存儲數(shù)據(jù)采用Vector容器，定時器時間到后調(diào)用STL 的sort方法，

缺點是：

(1)數(shù)據(jù)精度不準確，因為每個商品容器中只能存在一條記錄，會存在這樣的情況，在定時間隔內(nèi)，同一商品來了兩筆數(shù)據(jù)，后面的數(shù)據(jù)會把前面的覆蓋掉，這樣導致數(shù)據(jù)精度出現(xiàn)問題。

(2)占用大量的存儲空間，因為在排序完成后需要用到內(nèi)存拷貝技術(shù)把排序結(jié)構(gòu)做拷貝供客戶端調(diào)用，這樣新來的原始數(shù)據(jù)不會覆蓋掉排序結(jié)果。

定時排序方法：不存在上面定時排序的缺點，但是實現(xiàn)起來比較繁瑣，主要是數(shù)據(jù)存儲結(jié)構(gòu)的組織，和插入數(shù)據(jù)排序過程與取數(shù)據(jù)過程要做到合理的同步，當用戶取數(shù)據(jù)時不能做插入操作，否則用戶會取得無效的數(shù)據(jù)。

在用戶對精度要求不是很準確的時候還是采用定時排序方法，結(jié)果股市行情的具體情況在很短的時間間隔內(nèi)不會存在極大的變動，因此定時排序的精度誤差在允許的范圍內(nèi)，而且程序執(zhí)行起來比較穩(wěn)定，容易做出控制，不同客戶端顯示的結(jié)果是一致的。實際工作的系統(tǒng)中采用定時方案實現(xiàn)，達到功能需求的目標。

5 總結(jié)：

在當今軟件需要快速開發(fā)的時代，以從網(wǎng)上搜索一些比較著名的開源軟件項目，可以發(fā)現(xiàn)幾乎都是使用C++進行開發(fā)的。從它們高品質(zhì)的源碼可以看出，C++ STL標準模板庫技術(shù)使用得非常廣泛。頗負盛名的3D圖形渲染引擎OGRE，就很好地應(yīng)用了C++ STL庫提供的數(shù)據(jù)結(jié)構(gòu)和算?，F(xiàn)在C++ STL已被納入C++的編程環(huán)境中，成為C++標準庫的一個重要組成部分。用戶不必再像以往那樣經(jīng)常翻閱資料，只需寥寥數(shù)行代碼的調(diào)用，即可實現(xiàn)常用的數(shù)據(jù)結(jié)構(gòu)和算法。因此STL技術(shù)在未來軟件開發(fā)中將會起到舉足輕重的作用。

參考文獻：

[1]P J Plauger，普勞格，等. 王昕，譯.C++STL中文版[M].北京:中國電力出版社，2002.

[2]SCOTT MEYERS.潘愛民，等，譯.EFFECTIVE STL中文版[M].北京:清華大學出版社，2006.

[3]WILLIAM J COLLINS.周翔，譯.數(shù)據(jù)結(jié)構(gòu)與STL[M].北京:機械工業(yè)出版社，2004.

[4]侯捷.STL源碼剖析[M].華中科技大學出版社，2002.

[5]葉至軍.C++ STL開發(fā)技術(shù)導引[M].人民郵電出版社，2007.

[6]余祥宣，等.計算機算法基礎(chǔ)[M].華中科技大學出版社，2006.

[7]嚴蔚敏，等.數(shù)據(jù)結(jié)構(gòu)(C語言版)[M].清華大學出版社，1997.