C的++
本文为那些年我们追过的语言之C++篇。C语言的命名来源于其参考的B语言. 而C++的命名, 正因为所有C的思想和规律基本都被保留下来, 并且引入了类的概念, 以及封装, 继承, 多态的思想. 关键是观念的转变. 系统学习, 推荐 C++ Primer .
黑魔法
1. 模板 (Template)
虽然类是C++与C最直观的区分方式, 但本文并不打算在其耗费笔墨. 相较类, 多态的特性更吸引我. 模板是一种对类型进行参数化的工具, 通常有两种形式: 针对参数类型不同的函数模板, 以及针对属性和操作类型不同的类模板. 使用模板可以为类或函数声明构造一种通用模式, 使类中某些成员或者函数的参数及返回值类型任意。深入学习请阅读 C++ Templates .
2. 标准模板库 (STL)
STL (Standard Template Library) 的核心部件包括: 容器 (Container), 算法 (Algorithms), 迭代器 (Iterator). 简单来说, 它们各自表示结构, 操作, 指针. STL的一个重要特性是它不是面向对象的. 它基于模板而不是OOP中的封装, 继承, 多态. 关于STL的内容请参考学习:
在C++ STL中, 很多部分 (set, multiset, map, multimap) 应用了红黑树的变体. 红黑树操作具有良好的最坏情况复杂度, 在实践中, 它可以进行O(log n)时间内的查找，插入和删除等操作. 红黑树是每个节点都带有红色或黑色的二叉平衡查找树. 具有如下性质:
- 节点是红色或黑色.
- 根节点是黑色.
- 每个叶节点 (NIL节点) 是黑色.
- 每个红色节点的两个子节点都是黑色, 从每个叶子到根的所有路径上不能有两个连续的红色节点.
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点.
这些性质确定了红黑树的关键性质: 从根到叶子的最长可能路径不多于最短可能路径的两倍长. 其好处是既保持了树的相对平衡, 又比AVL的插入删除操作的复杂性低许多. 红黑树的插入及删除操作会破坏性质, 因此需要通过旋转来维护. 直观了解维护操作请看红黑树从头至尾插入和删除结点的全程演示图. 该文作者所写的红黑树专题非常翔实, 值得研读.
3. 回调 (Callback)
更准确的说, 回调是C的性质. 首次接触回调函数是在ns-3中, 其作用是让某函数以函数指针的形式成为某个类的属性, 以供该类在适当的时候调用该函数. 引用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中遇到的关于wifi中mac层收包的例子, 为保证原汁原味, 代码中部分与回调无关的内容并未删去:
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中有一个回调变量ForwardUpCallback m_callback;, 同时具有两个操作, 用于设置m_callback的SetForwardCallback函数, 及用于处理收包行为的操作Receive函数. 并且, Receive函数最后的语句m_callback (agregate, hdr);, 是一个调用回调函数的语句. 然后, 分析类RegularWifiMac, 它包含一个MacRxMiddle类的实例化指针MacRxMiddle *m_rxMiddle;. 并且, 在初始化时, 通过m_rxMiddle->SetForwardCallback (MakeCallback (&RegularWifiMac::Receive, this));将RegularWifiMac::Receive函数关联刚刚提到的MacRxMiddle中的m_callback. 简单来说, 以上程序使用回调达到效果是, MacRxMiddle::Receive中的m_callback (agregate, hdr);可以替换为RegularWifiMac::Receive (agregate, hdr);. 那么, 到底为什么要使用回调函数, 而不是直接在MacRxMiddle中编写RegularWifiMac::Receive函数呢? 因为RegularWifiMac类需要的是RegularWifiMac::Receive行为, 但是其他类中的MacRxMiddle实例, 需要的可能就是其他收包行为. 这便是回调的魅力.
结束语
虽然new过那么多个object, 然而这并没有什么...
