C++开发中数据结构和算法的分离
2008-03-08 21:33:19 来源:WEB开发网 闂傚倸鍊搁崐鎼佸磹閹间礁纾归柟闂寸绾惧綊鏌熼梻瀵割槮缁炬儳缍婇弻鐔兼⒒鐎靛壊妲紒鐐劤缂嶅﹪寮婚悢鍏尖拻閻庨潧澹婂Σ顔剧磼閻愵剙鍔ょ紓宥咃躬瀵鎮㈤崗灏栨嫽闁诲酣娼ф竟濠偽i鍓х<闁绘劦鍓欓崝銈囩磽瀹ュ拑韬€殿喖顭烽幃銏ゅ礂鐏忔牗瀚介梺璇查叄濞佳勭珶婵犲伣锝夘敊閸撗咃紲闂佽鍨庨崘锝嗗瘱闂備胶顢婂▍鏇㈠箲閸ヮ剙鐏抽柡鍐ㄧ墕缁€鍐┿亜韫囧海顦﹀ù婊堢畺閺屻劌鈹戦崱娆忓毈缂備降鍔庣划顖炲Φ閸曨垰绠抽悗锝庝簽娴犻箖姊洪棃娑欐悙閻庢矮鍗抽悰顕€宕堕澶嬫櫖濠殿噯绲剧€笛囧箲閸ヮ剙钃熼柣鏂挎憸閻熷綊鏌涢…鎴濇灈妞ゎ剙鐗嗛—鍐Χ鎼粹€茬凹缂備緡鍠楅幐鎼佹偩閻戣棄纭€闁绘劕绉靛Λ鍐春閳ь剚銇勯幒鎴濐伀鐎规挷绀侀埞鎴︽偐閹绘帩浼€缂佹儳褰炵划娆撳蓟濞戞矮娌柟瑙勫姇椤ユ繈姊洪柅鐐茶嫰婢т即鏌熼搹顐e磳闁挎繄鍋涢埞鎴犫偓锝庘偓顓涙櫊閺屽秵娼幏灞藉帯闂佹眹鍊曢幊鎰閹惧瓨濯撮柛鎾村絻閸撳崬顪冮妶鍡楃仸闁荤啿鏅涢悾鐑藉Ψ瑜夐崑鎾绘晲鎼粹剝鐏嶉梺缁樻尰濞叉﹢濡甸崟顖氱疀闂傚牊绋愮花鑲╃磽娴h棄鐓愭慨妯稿妿濡叉劙骞樼拠鑼槰闂佸啿鎼崐濠毸囬弶搴撴斀妞ゆ梻銆嬪銉︺亜椤撶偛妲婚柣锝囧厴楠炴帡骞嬮弮鈧悗濠氭⒑鐟欏嫭鍎楅柛妯衡偓鐔插徍濠电姷鏁告慨鐑藉极閸涘﹥鍙忔い鎾卞灩绾惧鏌熼崜褏甯涢柍閿嬪灦閵囧嫰骞掗崱妞惧缂傚倷绀侀ˇ閬嶅极婵犳氨宓侀柛鈩冪⊕閸婄兘鏌涘┑鍡楊伀妞ゆ梹鍔曢埞鎴︽倻閸モ晝校闂佸憡鎸婚悷锔界┍婵犲洦鍤冮柍鍝勫暟閿涙粓姊鸿ぐ鎺戜喊闁告瑥楠搁埢鎾斥堪閸喓鍘搁柣蹇曞仧绾爼宕戦幘璇茬疀濞达絽鎲¢崐顖炴⒑绾懎浜归悶娑栧劦閸┾偓妞ゆ帒鍟惃娲煛娴e湱澧柍瑙勫灴閹瑩寮堕幋鐘辨闂備礁婀辨灙闁硅姤绮庨崚鎺楀籍閸喎浠虹紓浣割儓椤曟娊鏁冮崒娑氬幈闂佸搫娲㈤崝宀勬倶閻樼粯鐓曢柟鑸妼娴滄儳鈹戦敍鍕杭闁稿﹥鐗犲畷婵嬫晝閳ь剟鈥﹂崸妤€鐒垫い鎺嶈兌缁犲墽鈧厜鍋撳┑鐘辩窔閸嬫鈹戦纭烽練婵炲拑绲垮Σ鎰板箳閹冲磭鍠撻幏鐘绘嚑閼稿灚姣愰梻鍌氬€烽懗鑸电仚濠电偛顕崗妯侯嚕椤愩倖瀚氱€瑰壊鍠栧▓銊︾節閻㈤潧校缁炬澘绉瑰鏌ュ箵閹烘繄鍞甸柣鐘烘鐏忋劌顔忛妷褉鍋撶憴鍕碍婵☆偅绻傞~蹇涙惞閸︻厾锛滃┑鈽嗗灠閹碱偊锝炲鍥╃=濞达綁顥撻崝宥夋煙缁嬪灝鏆遍柣锝囧厴楠炲鏁冮埀顒傜不婵犳碍鍋i柛銉戝啰楠囬悗瑙勬尭缁夋挳鈥旈崘顔嘉ч柛鈩兠棄宥囩磽娴e壊鍎愰柛銊ュ缁顓兼径瀣偓閿嬨亜閹哄秶顦︾€殿喖鐏濋埞鎴﹀煡閸℃浠梺鍛婎焼閸曨収娲告俊銈忕到閸燁垶宕愰崹顐e弿婵☆垳鍘ф禍楣冩倵濮樼偓瀚�

核心提示:相信每一个在windows下编过程序的人都或多或少地用过位图,大多数人是从网上下载一些成熟完善的DIB类库来使用(例如CxImage、CDIB),C++开发中数据结构和算法的分离,少数人有一套自己封装好的DIB类库,方便以后的扩充和使用,究竟多出来的那部分代码只是进出栈和查表,而不是浮点除这样耗时的指令,(近几年GDI
相信每一个在windows下编过程序的人都或多或少地用过位图,大多数人是从网上下载一些成熟完善的DIB类库来使用(例如CxImage、CDIB),少数人有一套自己封装好的DIB类库,方便以后的扩充和使用。(近几年GDI+异军突起,在某些处理方面,如:缩放、旋转、渐变填充等它提供无与伦比的速度和质量,但,假如你想做一个完善的图像处理程序,直接使用它会给架构设计带来困难,你可以用adapter模式封装它后再使用)。
这时候,假如你需要一些图像处理操作你会怎么办呢?很多没有OO经验的C++程序员(例如一年前的我)可能会这样做:在类中直接添加方法。
//================================================================
int FClamp0255 (int nValue) {return max (0, min (0xFF, nValue));} // 饱和到0--255
class FCObjImage
{
public :
Invert () ;
AdjustRGB (int R, int G, int B) ;
} ;
//================================================================
void FCObjImage::Invert ()
{
if ((GetHandle() == NULL) (ColorBits() < 24))
return ;
int nSpan = ColorBits() / 8 ; // 每象素字节数3, 4
for (int y=0 ; y < Height() ; y++)
{
BYTE * pPixel = GetBits (y) ;
for (int x=0 ; x < Width() ; x++, pPixel += nSpan)
{
pPixel[0] = ~pPixel[0] ;
pPixel[1] = ~pPixel[1] ;
pPixel[2] = ~pPixel[2] ;
}
}
}
//================================================================
void FCObjImage::AdjustRGB (int R, int G, int B)
{
if ((GetHandle() == NULL) (ColorBits() < 24))
return ;
int nSpan = ColorBits() / 8 ; // 每象素字节数3, 4
for (int y=0 ; y < Height() ; y++)
{
BYTE * pPixel = GetBits (y) ;
for (int x=0 ; x < Width() ; x++, pPixel += nSpan)
{
pPixel[0] = FClamp0255 (pPixel[0] + B) ;
pPixel[1] = FClamp0255 (pPixel[1] + G) ;
pPixel[2] = FClamp0255 (pPixel[2] + R) ;
}
}
}
//================================================================
这里举了两个例子(分别实现反色,调节RGB值功能),现实中会有大量的此类操作:亮度、对比度、饱和度......现在回想一下,你添加这些方法的步骤是什么,Ooooooooo,RCP(我同事的发明,全称:rapid copy paste^-^),第一步一定是从上面复制一块代码下来,然后改掉其中的接口和处理部分。虽然这里的示范代码很短小,不会连同bug一起复制,但,定时炸弹却又多了一个。有天,你的boss告诉你:我不能忍受长时间的等待,请给我加个进度条.....。你也许会加个全局变量,也许会给每个函数加个参数,但不变的是:你必须修改所有这些处理函数的代码,内心的咒骂并不会使你少改其中的任何一个。而此时,bug已经在旁边伺机而动了...然而苦日子远没熬到头,一个月后,你心血来潮的老板会让你在其中加上区域处理的功能,再一个月后......
回头重新看看代码?没错,除了红色的代码外,其他地方一摸一样,那能不能把这些算法分离抽出来呢?可能我们马上会想到标准库中qsort和windows中常用的回调方法。好,让我们实作一下:
//================================================================void Pixel_Invert (BYTE * pPixel)
{
pPixel[0] = ~pPixel[0] ;
pPixel[1] = ~pPixel[1] ;
pPixel[2] = ~pPixel[2] ;
}
//================================================================
void FCObjImage::PixelPRocess (void(__cdecl*PixelProc)(BYTE * pPixel))
{
if ((GetHandle() == NULL) (ColorBits() < 24))
return ;
int nSpan = ColorBits() / 8 ; // 每象素字节数3, 4
for (int y=0 ; y < Height() ; y++)
{
BYTE * pPixel = GetBits (y) ;
for (int x=0 ; x < Width() ; x++, pPixel += nSpan)
{
PixelProc (pPixel) ;
}
}
}
//================================================================
void FCObjImage::Invert ()
{
PixelProcess (Pixel_Invert) ;
}
//================================================================
嗯,看样子不错,算法被剥离到一个单一函数中,我们似乎已经解决问题了。处理Invert它完成的非常好,但处理AdjustRGB时碰到了麻烦,RGB那三个调节参数怎么传进去呢?我们的接口参数只有一个,通过添加全局变量/成员变量?这是一个办法,但随着类方法的增加,程序的可读性和维护性会急剧的下降,反而倒不如改之前的效果好。

那么如何实现高度的抽象和良好的接口呢?我们现场请来OO(object orient),请它来讲一下它的实现。设计如下派生关系:

//================================================================
class FCSinglePixelProcessBase
{
public :
virtual void ProcessPixel (int x, int y, BYTE * pPixel) PURE ;
} ;
//================================================================
class FCPixelInvert : public FCSinglePixelProcessBase
{
public :
virtual void ProcessPixel (int x, int y, BYTE * pPixel) ;
} ;
void FCPixelInvert::ProcessPixel (int x, int y, BYTE * pPixel)
{
pPixel[0] = ~pPixel[0] ; pPixel[1] = ~pPixel[1] ; pPixel[2] = ~pPixel[2] ;
}
//================================================================
class FCPixelAdjustRGB : public FCSinglePixelProcessBase
{
public :
FCPixelAdjustRGB (int DeltaR, int DeltaG, int DeltaB) ;
virtual void ProcessPixel (int x, int y, BYTE * pPixel) ;
protected :
int m_iDeltaR, m_iDeltaG, m_iDeltaB ;
} ;
void FCPixelAdjustRGB::ProcessPixel (int x, int y, BYTE * pPixel)
{
pPixel[0] = FClamp0255 (pPixel[0] + m_iDeltaB) ;
pPixel[1] = FClamp0255 (pPixel[1] + m_iDeltaG) ;
pPixel[2] = FClamp0255 (pPixel[2] + m_iDeltaR) ;
}
//================================================================
然后我们修改image类如下:
//================================================================
#include "PixelProcessor.h"
class FCObjImage
{
public :
void PixelHandler (FCSinglePixelProcessBase & PixelProcessor, FCObjProgress * progress = NULL) ;
} ;
//================================================================
void FCObjImage::PixelHandler (FCSinglePixelProcessBase & PixelProcessor, FCObjProgress * progress)
{
if (GetHandle() == NULL)
return ;
int nSpan = ColorBits() / 8 ; // 每象素字节数3, 4
for (int y=0 ; y < Height() ; y++)
{
BYTE * pPixel = GetBits (y) ;
for (int x=0 ; x < Width() ; x++, pPixel += nSpan)
{
PixelProcessor.ProcessPixel (x, y, pPixel) ;
}
if (progress != NULL)
progress->SetProgress (y * 100 / Height()) ;
}
}
//================================================================
void FCObjImage::Invert (FCObjProgress * progress)
{
PixelHandler (FCPixelInvert(), progress) ;
}
void FCObjImage::AdjustRGB (int R, int G, int B, FCObjProgress * progress)
{
PixelHandler (FCPixelAdjustRGB (R,G,B), progress) ;
}
//================================================================
(以上只是一个基本框架,你可以很轻易的把区域处理的参数添加进去-通过构造时传递一个RECT参数。)
对象真的是一个很奇妙的东西,它可以对外提供一个简单的接口,而自身又可以封装上很多附加信息。
好,现在让我们来检验一下刚才的成果:添加一个给图像奇数行置黑,给偶数行置白的操作。
//================================================================class FCPixelTest : public FCSinglePixelProcessBase
{
public :
virtual void ProcessPixel (int x, int y, BYTE * pPixel) ;
} ;
void FCPixelTest::ProcessPixel (int x, int y, BYTE * pPixel)
{
if (y % 2) pPixel[0]=pPixel[1]=pPixel[2] = 0 ;
// 奇数行
else
pPixel[0]=pPixel[1]=pPixel[2] = 0xFF ;
// 偶数行
}
然后进行如下调用:
PixelHandler (FCPixelTest(), progress) ;
//================================================================
多么的和谐美妙,设计算法的人员只需写出自己的算法,而不用去考虑怎么让它支持进度条和区域这些问题。感觉这就象一把设计优良的AK,你可以不断的往里添加子弹(对象)^-^
至此,我们应该已经大功告成了。还有问题吗?
等等,别忙,有些地方不太对,我添加这个算法后,怎么编译这么久啊。
问题就出在那个不起眼的:
#include "PixelProcessor.h"
image是图像处理的最底层对象,工程中的所有文件都直接或间接地包含它,因此,任何对image.h本身及它所包含的.h的修改都会引起几乎整个工程的build,这当然是无法忍受的,解决的办法是使用“前置声明”,因为在PixelHandler接口中我们只需要它的引用(也即是说:我(接口)并不需要知道传给我的类的内部结构,给我一个32(64)的内存地址就OK了)。
因此我们把
#include "PixelProcessor.h"
替换成:
class FCSinglePixelProcessBase ; // external class 前置声明
然后在.cpp文件中再包含PixelProcessor.h,这样,对PixelProcessor.h的改变仅仅会导致.cpp文件的重新编译,大大节约了编译时间。
总结:
1)可能的话,在编程中永远也别去想“拷贝代码”这个字眼。究竟,OO就是为了抽象和代码重用才诞生的。
2)除非必要,否则类的成员变量和函数的参数尽量用指针或引用代替,这样做可以在.h中尽可能地少包含其他.h文件,而用前置声明来替代,以此来减少编译时间和以后可能会产生的交叉包含。
3)最后说一下效率问题:有些朋友可能会说每个像素都调用虚函数会影响性能,这的确,但实际的损失远没有想象的大。我实测了一下:对1024*768的图片进行反片处理,速度只有5%左右的损失,进行复杂处理(亮度/对比度/gamma)时损失可完全忽略,究竟多出来的那部分代码只是进出栈和查表,而不是浮点除这样耗时的指令。

- ››开发Android 日历教程
- ››开发学院总结 Win 8实用技巧大全
- ››开发学院原创教程:把win8的IE10放桌面上方法(非...
- ››开发者眼中的Windows Phone和Android
- ››开发学院教你用SQL 语句最快速清空MySQL 数据表的...
- ››数据结构2--数组
- ››数据结构C#版线性表(Data Structure)之单链表(Lin...
- ››数据结构C#版线性表(Data Structure)之顺序表(顺序...
- ››开发一个自己的HTML在线编辑器(一)
- ››开发一个自己的HTML在线编辑器(二)
- ››开发者在App Store上赚的钱比在Android Market上多...
- ››开发者应深入学习的10个Android开源应用项目
更多精彩
赞助商链接