C的++
本文為那些年我們追過的語言之C++篇个曙。C語言的命名來源于其參考的B語言. 而C++的命名, 正因為所有C的思想和規(guī)律基本都被保留下來, 并且引入了類的概念, 以及封裝, 繼承, 多態(tài)的思想. 關(guān)鍵是觀念的轉(zhuǎn)變. 系統(tǒng)學(xué)習(xí), 推薦 C++ Primer .
黑魔法
1. 模板 (Template)
雖然類是C++與C最直觀的區(qū)分方式, 但本文并不打算在其耗費筆墨. 相較類, 多態(tài)的特性更吸引我. 模板是一種對類型進(jìn)行參數(shù)化的工具, 通常有兩種形式: 針對參數(shù)類型不同的函數(shù)模板, 以及針對屬性和操作類型不同的類模板. 使用模板可以為類或函數(shù)聲明構(gòu)造一種通用模式, 使類中某些成員或者函數(shù)的參數(shù)及返回值類型任意芦缰。深入學(xué)習(xí)請閱讀 C++ Templates .
2. 標(biāo)準(zhǔn)模板庫 (STL)
STL (Standard Template Library) 的核心部件包括: 容器 (Container), 算法 (Algorithms), 迭代器 (Iterator). 簡單來說, 它們各自表示結(jié)構(gòu), 操作, 指針. STL的一個重要特性是它不是面向?qū)ο蟮? 它基于模板而不是OOP中的封裝, 繼承, 多態(tài). 關(guān)于STL的內(nèi)容請參考學(xué)習(xí):
在C++ STL中, 很多部分 (set, multiset, map, multimap) 應(yīng)用了紅黑樹的變體. 紅黑樹操作具有良好的最壞情況復(fù)雜度, 在實踐中, 它可以進(jìn)行O(log n)時間內(nèi)的查找，插入和刪除等操作. 紅黑樹是每個節(jié)點都帶有紅色或黑色的二叉平衡查找樹. 具有如下性質(zhì):
- 節(jié)點是紅色或黑色.
- 根節(jié)點是黑色.
- 每個葉節(jié)點 (NIL節(jié)點) 是黑色.
- 每個紅色節(jié)點的兩個子節(jié)點都是黑色, 從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點.
- 從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點.
這些性質(zhì)確定了紅黑樹的關(guān)鍵性質(zhì): 從根到葉子的最長可能路徑不多于最短可能路徑的兩倍長. 其好處是既保持了樹的相對平衡, 又比AVL的插入刪除操作的復(fù)雜性低許多. 紅黑樹的插入及刪除操作會破壞性質(zhì), 因此需要通過旋轉(zhuǎn)來維護(hù). 直觀了解維護(hù)操作請看紅黑樹從頭至尾插入和刪除結(jié)點的全程演示圖. 該文作者所寫的紅黑樹專題非常翔實, 值得研讀.
3. 回調(diào) (Callback)
更準(zhǔn)確的說, 回調(diào)是C的性質(zhì). 首次接觸回調(diào)函數(shù)是在ns-3中, 其作用是讓某函數(shù)以函數(shù)指針的形式成為某個類的屬性, 以供該類在適當(dāng)?shù)臅r候調(diào)用該函數(shù). 引用ns-3的Tutorial中的講解:
The goal of the Callback system in ns-3 is to allow one piece of code to call a function (or method in C++) without any specific inter-module dependency. This ultimately means you need some kind of indirection – you treat the address of the called function as a variable. This variable is called a pointer-to-function variable.
舉個ns-3中遇到的關(guān)于wifi中mac層收包的例子, 為保證原汁原味, 代碼中部分與回調(diào)無關(guān)的內(nèi)容并未刪去:
class MacRxMiddle{
typedef Callback<void, Ptr<Packet>, const WifiMacHeader*> ForwardUpCallback;
ForwardUpCallback m_callback;
void SetForwardCallback (ForwardUpCallback callback);
void Receive (Ptr<Packet> packet, const WifiMacHeader *hdr);
...
};
void MacRxMiddle::SetForwardCallback (ForwardUpCallback callback){
m_callback = callback;
}
void MacRxMiddle::Receive (Ptr<Packet> packet, const WifiMacHeader *hdr){
NS_LOG_FUNCTION (packet << hdr);
NS_ASSERT (hdr->IsData () || hdr->IsMgt ());
OriginatorRxStatus *originator = Lookup (hdr);
if (!(SequenceNumber16 (originator->GetLastSequenceControl ()) < SequenceNumber16 (hdr->GetSequenceControl ()))) NS_LOG_DEBUG ("Sequence numbers have looped back. last recorded=" << originator->GetLastSequenceControl () << " currently seen=" << hdr->GetSequenceControl ());
if(IsDuplicate (hdr, originator))
NS_LOG_DEBUG ("duplicate from=" << hdr->GetAddr2 () <<", seq=" << hdr->GetSequenceNumber () <<", frag=" << hdr->GetFragmentNumber ());
return;
}
Ptr<Packet> agregate = HandleFragments (packet, hdr, originator);
if (agregate == 0) return 0;
if (!hdr->GetAddr1 ().IsGroup ()) originator->SetSequenceControl (hdr->GetSequenceControl ());
m_callback (agregate, hdr);
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
class RegularWifiMac : public WifiMac{
RegularWifiMac ();
virtual void Receive (Ptr<Packet> packet, const WifiMacHeader *hdr);
MacRxMiddle *m_rxMiddle;
...
};
RegularWifiMac::RegularWifiMac (){
m_rxMiddle->SetForwardCallback (MakeCallback (&RegularWifiMac::Receive, this));
...
}
void RegularWifiMac::Receive (Ptr<Packet> packet, const WifiMacHeader *hdr){
NS_LOG_FUNCTION (this << packet << hdr);
Mac48Address to = hdr->GetAddr1 ();
Mac48Address from = hdr->GetAddr2 ();
if (to != GetAddress ()) return;
if (hdr->IsMgt () && hdr->IsAction ()){
NS_ASSERT (m_qosSupported);
WifiActionHeader actionHdr;
packet->RemoveHeader (actionHdr);
switch (actionHdr.GetCategory ()){
case WifiActionHeader::BLOCK_ACK:
...
default:
NS_FATAL_ERROR ("Unsupported Action frame received");
return;
}
}
NS_FATAL_ERROR ("Don't know how to handle frame (type=" << hdr->GetType ());
}
這段代碼中包含兩個類MacRxMiddle和RegularWifiMac. 首先, MacRxMiddle中有一個回調(diào)變量ForwardUpCallback m_callback;, 同時具有兩個操作, 用于設(shè)置m_callback的SetForwardCallback函數(shù), 及用于處理收包行為的操作Receive函數(shù). 并且, Receive函數(shù)最后的語句m_callback (agregate, hdr);, 是一個調(diào)用回調(diào)函數(shù)的語句. 然后, 分析類RegularWifiMac, 它包含一個MacRxMiddle類的實例化指針MacRxMiddle *m_rxMiddle;. 并且, 在初始化時, 通過m_rxMiddle->SetForwardCallback (MakeCallback (&RegularWifiMac::Receive, this));將RegularWifiMac::Receive函數(shù)關(guān)聯(lián)剛剛提到的MacRxMiddle中的m_callback. 簡單來說, 以上程序使用回調(diào)達(dá)到效果是, MacRxMiddle::Receive中的m_callback (agregate, hdr);可以替換為RegularWifiMac::Receive (agregate, hdr);. 那么, 到底為什么要使用回調(diào)函數(shù), 而不是直接在MacRxMiddle中編寫RegularWifiMac::Receive函數(shù)呢? 因為RegularWifiMac類需要的是RegularWifiMac::Receive行為, 但是其他類中的MacRxMiddle實例, 需要的可能就是其他收包行為. 這便是回調(diào)的魅力.
結(jié)束語
雖然new過那么多個object, 然而這并沒有什么...
