兔子的技術博客

兔子

:: 首頁 :: 聯系 :: 聚合

:: 管理

202 Posts :: 0 Stories :: 43 Comments :: 0 Trackbacks

留言簿(10)

隨筆分類(224)

收藏夾(13)

狡兔多窟

百度
博客園
賽迪
網易

收藏博客

CodeWay(程序數學物理)
laviewpbt 的博客（圖像算法_VB）
maozefa的博客（圖像算法）
mybios(DX,圖形圖像)
MYCP
開源C++ Web應用服務器中間件（國內開源項目）
Stephen Liu
c++，web，lua，管理等
zyl910 的博客（圖像算法_C++）
λ-calculus（編譯原理）
鋒鋒 FFLIB作者
知其然，知其所以然。熱愛IT技術，分享科技生活。專注于分布式、互聯網、游戲的開發技術。無聊夢見憂郁，找到理想不太易，理想有日達成，找到心底夢想的世界。BEYOND！
羅朝輝（飄飄白云）
關注C++，3D技術，游戲開發，移動開發（iPhone/iPad，Android等）
人月神話的BLOG（軟件工程）
算法，C++技術
小豬的網絡編程
網絡編程技術，VA破解實時發布
易飛揚
ios 開發
重劍無鋒，大巧不工
游戲開發 Flash Scaleform GFx C++
周京生的博客(VS2010 ,TFS2010)
VS2010 ,TFS2010
子龍山人
iphone 開發

閱讀排行榜

評論排行榜

STL運用的C++技術（6）——函數對象

STL是C++標準庫的重要組成部分之一，它不僅是一個可復用的組件庫，更是一個包含算法與數據結構的軟件框架，同時也是C++泛型編程的很好例子。STL中運用了許多C++的高級技術。本文介紹函數對象，其實是接上一篇的話題，因為函數對象本質上還是重載操作符。主要參考了《C++ Primer》和《STL源碼剖析》。

可以為類類型的對象重載函數調用操作符，定義了調用操作符的類，其對象稱之為函數對象（function object），即它們的行為類似函數對象。這是《C++ Primer》中的定義。下面通過一個例子來引出函數對象的使用。在我的解題筆記系列中，有一篇文章解題筆記（16）——幾個數字的問題，其中第四個問題是調整數組順序使奇數位于偶數前面（數組）。輸入一個整數數組，調整數組中數字的順序，使得所有奇數位于數組的前半部分。所有偶數位于數組的后半部分。要求時間復雜度為O(n)。這個問題不難，其中用到了函數指針。代碼如下：

view plain print ?

bool IsOdd(int x)
{
return (x & 1)? true: false;
}
//函數功能：調整數組順序使奇數位于偶數前面
//函數參數： pArray指向數組的指針，nLen為數組長度
//返回值：無
void PartionArray(int *pArray, int nLen, bool (*func)(int))
{
int i = -1;
for(int j = 0; j < nLen; j++)
{
if(func(pArray[j])) //滿足調整條件
{
i++;
int tmp = pArray[j];
pArray[j] = pArray[i];
pArray[i] = tmp;
}
}
}

傳遞一個函數指針的好處是，可以很方便的修改調整的條件，這個問題希望將奇數放在前面，偶數放在后面。如果有另外一個問題，希望將正數放前面，負數放后面，那么只需定義新的調整函數，類似 IsOdd，然后將它作為參數傳遞給PartionArray函數即可。

這里其實也可以使用函數對象，代碼如下：

view plain print ?

#include <iostream>
using namespace std;
//函數對象
template<class T>
struct IsOdd
{
bool operator() (T x){
return (x & 1)?true: false;
}
};
//函數功能：調整數組順序使奇數位于偶數前面
//函數參數： pArray指向數組的指針，nLen為數組長度
//返回值：無
template <class T, class F>
void PartionArray(T *pArray, int nLen, F func)
{
int i = -1;
for(int j = 0; j < nLen; j++)
{
if(func(pArray[j])) //滿足調整條件
{
i++;
T tmp = pArray[j];
pArray[j] = pArray[i];
pArray[i] = tmp;
}
}
}
//測試用例
int main()
{
short a[] = {1,2,3,4,5,6};
long b[] = {1,2,3,4,5,6};
PartionArray(a, 6, IsOdd<short>());
PartionArray(b, 6, IsOdd<long>());
return 0;
}

相比函數指針，函數對象的優勢在于能很好的滿足STL的抽象要求，同時更為靈活。上面這個例子算是一個引子，引出STL中函數對象的運用。

STL中的函數對象并不是孤立的，而是與STL的算法緊密聯系在一起。舉個簡單的例子就明白了，比如我們希望利用STL的算法為一個數組排序，我們可以這樣做。

view plain print ?

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int a[] = {1,3,2,4,5,7};
sort(&a[0], &a[6]);
for(int i = 0; i < 6; i++)
cout<<a[i]<<' ';
cout<<endl;
return 0;
}

這個排序算法默認是遞增排序，那么如果希望是遞減排序呢？很方便，在函數實參中加入一個函數對象即可。記住需包含頭文件 #include <functional>

view plain print ?

#include <iostream>
#include <functional>
#include <algorithm>
using namespace std;
int main()
{
int a[] = {1,3,2,4,5,7};
sort(&a[0], &a[6], greater<int>());
for(int i = 0; i < 6; i++)
cout<<a[i]<<' ';
cout<<endl;
return 0;
}

可以說在STL中，函數對象扮演著重要的角色，發揮著巨大的作用。下面列出了幾個常用的函數對象，摘自HP的STL源碼，做了部分修改。STL定義了兩個類，作為一元操作和二元操作的基類，這兩個基類僅僅是使用了內嵌型別技術，為什么要這樣子呢？后面介紹函數適配器時有說明，可以看到它的強大之處。

view plain print ?

//用來定義一元操作的參數類別和返回值類別
template <class Arg, class Result>
struct unary_function {
typedef Arg argument_type; //內嵌型別技術
typedef Result result_type;
};
//用來定義二元操作的參數類別和返回值類別
template <class Arg1, class Arg2, class Result>
struct binary_function {
typedef Arg1 first_argument_type;
typedef Arg2 second_argument_type;
typedef Result result_type;
};
//一元操作，就兩個
template <class T>
struct negate : public unary_function<T, T> {
T operator()(const T& x) const { return -x; }
};
template <class T>
struct logical_not : public unary_function<T,bool> {
bool operator()(const T& x) const { return !x; }
};
//加減乘除取模
template <class T>
struct plus : public binary_function<T, T, T> {
T operator()(const T& x, const T& y) const { return x + y; }
};
template <class T>
struct minus : public binary_function<T, T, T> {
T operator()(const T& x, const T& y) const { return x - y; }
};
template <class T>
struct multiplies : public binary_function<T, T , T> {
T operator()(const T& x, const T& y) const { return x * y; }
};
template <class T>
struct divides : public binary_function<T ,T, T> {
T operator()(const T& x, const T& y) const { return x / y; }
};
template <class T>
struct modulus : public binary_function<T, T, T> {
T operator()(const T& x, const T& y) const { return x % y; }
};
//關系運算
template <class T>
struct equal_to : public binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x == y; }
};
template <class T>
struct not_equal_to : public binary_function<T, T,bool> {
bool operator()(const T& x, const T& y) const { return x != y; }
};
template <class T>
struct greater : public binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x > y; }
};
template <class T>
struct less : public binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x < y; }
};
template <class T>
struct greater_equal : public binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x >= y; }
};
template <class T>
struct less_equal : public binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x <= y; }
};
//邏輯運算
template <class T>
struct logical_and : public binary_function<T, T, bool>{
bool operator()(const T& x, const T& y) const { return x && y; }
};
template <class T>
struct logical_or : public binary_function<T, T, bool>
{
bool operator()(const T& x, const T& y) const { return x || y; }
};

上面這些函數對象都比較簡單，接下來介紹幾個稍微復雜點的，它們被稱為函數適配器（function adapter），用于特化和擴展一元和二元函數對象。分為兩類，第一是綁定器（binder），它通過將一個操作數綁定到給定值而將二元函數對象轉換為一元函數。第二是求反器（negator），它將謂詞函數對象的真值求反。這些定義來自《C++ Primer》一書。書上還給了兩個例子，這里羅列一下：

view plain print ?

#include <iostream>
#include <functional>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> vec(10, 1);
int count1 = count_if(vec.begin(), vec.end(), bind2nd(less_equal<int>(), 10)); //求容器中小于等于10的元素個數
int count2 = count_if(vec.begin(), vec.end(), not1(bind2nd(less_equal<int>(), 10))); //求容器中不小于等于10的元素個數，正好是上面結果的取反
cout<<count1<<' '<<count2<<endl; //10 0
return 0;
}

下面分析一下STL是如何實現函數適配器的，先給出STL的源碼。已經整理過了。

view plain print ?

//綁定第一個參數
template <class Operation>
class binder1st: public unary_function<typename Operation::second_argument_type, typename Operation::result_type> {
public:
binder1st(const Operation& x, const typename Operation::first_argument_type& y) : op(x), value(y) {} //構造函數
typename Operation::result_type operator()(const typename Operation::second_argument_type& x) const {
return op(value, x); //固定第一個參數
}
protected:
Operation op;
typename Operation::first_argument_type value;
};
//綁定第二個參數
template <class Operation>
class binder2nd: public unary_function<typename Operation::first_argument_type,typename Operation::result_type> {
public:
binder2nd(const Operation& x, const typename Operation::second_argument_type& y) : op(x), value(y) {}
typename Operation::result_type operator()(const typename Operation::first_argument_type& x) const {
return op(x, value); //固定第二個參數
}
protected:
Operation op;
typename Operation::second_argument_type value;
};
//外部接口
template <class Operation, class T>
inline binder1st<Operation> bind1st(const Operation& fn, const T& x) {
typedef typename Operation::first_argument_type Arg1_type;
return binder1st<Operation>(fn,Arg1_type(x));
}
//外部接口
template <class Operation, class T>
inline binder2nd<Operation> bind2nd(const Operation& fn, const T& x) {
typedef typename Operation::second_argument_type Arg2_type;
return binder2nd<Operation>(fn, Arg2_type(x));
}

view plain print ?

//一元操作求反
template <class Predicate>
class unary_negate: public unary_function<typename Predicate::argument_type, bool> {
protected:
Predicate pred;
public:
explicit unary_negate(const Predicate& x) : pred(x) {}
bool operator()(const typename Predicate::argument_type& x) const {
return !pred(x);
}
};
//二元操作求反
template <class Predicate>
class binary_negate : public binary_function<typename Predicate::first_argument_type, typename Predicate::second_argument_type,bool> {
protected:
Predicate pred;
public:
explicit binary_negate(const Predicate& x) : pred(x) {}
bool operator()(const typename Predicate::first_argument_type& x, const typename Predicate::second_argument_type& y) const {
return !pred(x, y);
}
};
//外部接口
template <class Predicate>
inline unary_negate<Predicate> not1(const Predicate& pred)
{
return unary_negate<Predicate>(pred);
}
//外部接口
template <class Predicate>
inline binary_negate<Predicate> not2(const Predicate& pred)
{
return binary_negate<Predicate>(pred);
}

到這里，我們可以回答之前的一個問題，就是STL為什么要定義兩個基類，里面僅僅是內嵌型別。通過上面代碼，不難發現，原來是用來萃取函數對象所操作的數據類型。比如 binder1st 這個類，它的模板中只有一個形參，它繼承自unary_function，而unary_function的模板有兩個形參。如何實現這種繼承關系呢？內嵌型別技術，因為binder1st 的模板實參是個函數對象，繼承自unary_function或binary_function，通過內嵌型別技術很容易萃取出數據類型。

再進一步，函數適配器是如何工作的呢？

view plain print ?

include <iostream>
#include <functional>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> vec(10, 1);
int count1 = count_if(vec.begin(), vec.end(), bind2nd(less_equal<int>(), 10)); //求容器中小于等于10的元素個數
int count2 = count_if(vec.begin(), vec.end(), not1(bind2nd(less_equal<int>(), 10))); //求容器中不小于等于10的元素個數，正好是上面函數的取反
cout<<count1<<' '<<count2<<endl; //10 0
return 0;
}

還是以這個程序為例，介紹一下count_if(vec.begin(), vec.end(), bind2nd(less_equal<int>(), 10))具體執行。首先執行bind2nd(less_equal<int>(), 10)這個函數，這個函數會返回一個binder2nd的函數對象，注意構造這個函數對象的時候，binder2nd(const Operation& x, const typename Operation::second_argument_type& y) : op(x), value(y) {} 。第二個參數value的值設置為10，而第一個參數op設置成less_equal<int>()這個函數對象。

接著count_if 執行時，下面是它的源碼。執行時，pred(*first)其實就是binder2nd中的運算，而這個運算的第二個參數是固定的，也就是10，所以pred只傳遞了一個實參進去就可以了。

view plain print ?

template <class InputIter, class Predicate, class Size>
void count_if(InputIter first, InputIter last, Predicate pred, Size& n) {
for ( ; first != last; ++first)
if (pred(*first))
++n;
}
template <class InputIter, class Predicate>
typename iterator_traits<InputIter>::difference_type count_if(InputIter first, InputIter last, Predicate pred) {
typename iterator_traits<InputIter>::difference_type n = 0;
for ( ; first != last; ++first)
if (pred(*first))
++n;
return n;
}

下面把上述綜合起來，通過修改STL，寫個完整的測試程序。如下所示，注意這里用的都是自定義的代碼，沒有包含STL的函數對象和函數。

view plain print ?

#include <iostream>
#include <vector>
using namespace std;
//count_if函數
template <class InputIter, class Predicate, class Size>
void count_if(InputIter first, InputIter last, Predicate pred, Size& n) {
for ( ; first != last; ++first)
if (pred(*first))
++n;
}
//用來定義一元操作的參數類別和返回值類別
template <class Arg, class Result>
struct unary_function {
typedef Arg argument_type;
typedef Result result_type;
};
//用來定義二元操作的參數類別和返回值類別
template <class Arg1, class Arg2, class Result>
struct binary_function {
typedef Arg1 first_argument_type;
typedef Arg2 second_argument_type;
typedef Result result_type;
};
//本測試之用到關系函數對象
template <class T>
struct less_equal : public binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x <= y; }
};
//綁定第二個參數
template <class Operation>
class binder2nd: public unary_function<typename Operation::first_argument_type,typename Operation::result_type> {
public:
binder2nd(const Operation& x, const typename Operation::second_argument_type& y) : op(x), value(y) { cout<<"binder2nd Constructor"<<endl; }
typename Operation::result_type operator()(const typename Operation::first_argument_type& x) const {
cout<<"binder2nd's operator()"<<endl;
return op(x, value); //固定第二個參數
}
protected:
Operation op;
typename Operation::second_argument_type value;
};
//外部接口
template <class Operation, class T>
inline binder2nd<Operation> bind2nd(const Operation& fn, const T& x) {
typedef typename Operation::second_argument_type Arg2_type;
return binder2nd<Operation>(fn, Arg2_type(x));
}
//一元操作求反
template <class Predicate>
class unary_negate: public unary_function<typename Predicate::argument_type, bool> {
protected:
Predicate pred;
public:
explicit unary_negate(const Predicate& x) : pred(x) { cout<<"unary_negate Constructor"<<endl; }
bool operator()(const typename Predicate::argument_type& x) const {
cout<<"unary_negate's operator()"<<endl;
return !pred(x);
}
};
//外部接口
template <class Predicate>
inline unary_negate<Predicate> not1(const Predicate& pred)
{
return unary_negate<Predicate>(pred);
}
//測試程序
int main()
{
vector<int> vec(10, 1);
int count1 = 0, count2 = 0;
count_if(vec.begin(), vec.end(), bind2nd(less_equal<int>(), 10),count1); //求容器中小于等于10的元素個數
count_if(vec.begin(), vec.end(), not1(bind2nd(less_equal<int>(), 10)),count2); //求容器中不小于等于10的元素個數，正好是上面函數的取反
cout<<count1<<' '<<count2<<endl; //10 0
return 0;
}

出處 http://blog.csdn.net/wuzhekai1985
原文：http://blog.csdn.net/wuzhekai1985/article/details/6658940

posted on 2011-09-06 10:42 會飛的兔子閱讀(1370) 評論(0) 編輯收藏引用所屬分類: C++庫，組件

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: C++操作mysql數據庫文章資料匯總 lua靜態庫的編譯 Metatable In Lua 淺嘗輒止自己編譯lua5.2.1 失效迭代器（Invalidating Iterators）標準C/C++程序通過gSOAP調用WebService 跑步的好處 VC的MySQL編程 Lua的C++封裝應用boost::filesystem遞歸拷貝目錄樹

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

兔子的技術博客

留言簿(10)

隨筆分類(224)

收藏夾(13)

狡兔多窟

收藏博客

最新評論

閱讀排行榜

評論排行榜