Lambda Function

c++11 多了很多非常方便且變動很大的新功能,其中Lambda funtion 就是個很有代表性的例子,初看到這個新功能時應該會很傻眼,這到底是什麼鬼。本篇將概述lambda function 的用法。

Lambda function 的適用情境很多,最常被用在“當參數傳遞且一次性使用的function”,舉個例子來說我們如果在使用 sort function 時,會需要將自己寫好的 compare function 當做參數傳遞到 sort function,舉例來說:

bool myfunction (int i,int j) { return (i<j); } //define my own compare function
int myints[] = {32,71,12,45,26,80,53,33};
std::vector<int> myvector (myints, myints+8);               // 32 71 12 45 26 80 53 33
std::sort (myvector.begin(), myvector.end(), myfunction);   // use my own compare function

麻煩的點來啦,明明這個compare function就只使用一次(就是拿來當參數傳給 sort function),有沒有更簡單的方法呢?有的,就是 lambda function,這種 function 他不需要名字,且宣告方式簡單,有點像一次性的拋棄式function,且可以在任何地方使用,甚至是 function 內有 lambda function

先來看看他大概的樣子:

auto ff = [](){/*function content*/}; //宣告及定義一個 lambda function,ff 為一個function pointer
ff(); //call function ,可直接使用該function pointer

其中:
[]內放 capture list

說白話一點我覺得可以將它理解為該 funciton 的可視範圍,譬如說:

int main()
{
    int a = 0;
    int b = 1;
    auto ff = [](){cout<<a<<endl;}; //想cout出剛剛宣告的a
    ff(); 
}

這樣是編譯不過的,compiler 會抱怨他不知道 a 是什麼鬼。原因是他的可視範圍只有他自己的{}內部,該怎麼做才能讓他看到外層的a呢?
方法很簡單,就是宣告他的“capture list”。

capture list 可分為:
1. 沒寫:他不需要看到外層的變數
2. &:用 reference 來獲取外層變數(可更改)
3. = : 用傳值的方式獲取變數(要用特別的方式才能改)

以剛剛的例來說:

int main()
{
    int a = 0;
    int b = 1;
    auto ff = [=](){cout<<a<<endl;}; // 想 cout 出剛剛宣告的 a
    ff(); 
}

加了=後即沒有 compile error,原因是他看到了a,剛剛有提到 = 是以 “傳值"方式,也就是說function內不是不得改變a得值。否則會產生compile error。若想改變就必須使用“&”。如下:

int main()
{
    int a = 0;
    int b = 1;
    auto ff = [&](){
        a = 1;
        cout<<a<<endl;
    }; // 想 cout 出剛剛宣告的 a
    ff(); 
}

其實capture list 的使用方式非常的靈活,本篇只是間單的入門介紹,若想深入暸解capture list 可參考這篇

()表示傳入的參數列
既然都是個函式了怎麼可能沒有參數列呢?參數列的使用跟一般function相同,就不再做介紹,直接舉個例子:

int a = 100;
auto ff = [&](int a)
{
    cout << in : << a <<endl;
    a = 200;
};
cout<<out : a<<endl;
ff(a); 

結果會在螢幕顯示:
in : 100
out : 100

疑?說好的reference方式來access a 怎麼會改不了呢?原因就是a 已經被當作參數傳入了(call by value)因此內部改的 a 已經不是外層的 a。

既然都有傳入值了怎麼沒有傳回值呢?

->表示傳回值

先給個範例:

auto ff = [&](int a)->int{return a;};
int a = ff(3);
cout<<a<<endl;

這段code會在螢幕顯示3,其中的->就是在表示該function的回傳值的type。其實,以這段code為例,因為函式內容很簡單,只有一行 return 就搞定,所以->是可省略的。只有在不只 return 一行 code 時才必須非得使用 -> 不可。

lambda 的使用其實非常的靈活,除了前述的功能外,他也有可以代替{ } 去製造scope的功能等等,若有更深入的需求再去參考這篇。 😛

Function Pointer & Callback Function

Function 是一個寫程式很常用的技巧,但function pointer 是就業了之後比較常看到的招式,它很常出現在“callback function”這個技巧當中。這篇要就“callback function” 及 “function pointer” 做討論。

function pointer:
其實在 C 或 C++ 裡頭,function 代表一個address,既然如此我們當然也可以也可以用pointer去指。而這種拿來指function的pointer就稱為function pointer。function pointer 的宣告一直是大家對function pointer最望之卻步的原因,因為讀法不直覺,參考如下:

//一個名為funcptr的function pointer 只個一個吃void 回傳int 的function
int (*funcptr) (void)

以下簡單示範一個範例:

int a ()
{
    return 5;
}
int b ()
{
    return 6;
}
int main()
{
    int (* funcptr) () = a; //將functor指向 function a
    (*funcptr)();  //利用function pointer 來 call a
}

要注意的地方有兩個:
(1) 要小心不要寫成:

int (* funcptr) () = a(); //將functor指向 function a

這樣寫會直接回傳function a 的回傳值
(2) 注意 function pointer 的 type,舉例來說:

// function prototypes
int foo();
double goo();
int hoo(int x);
 
// function pointer assignments
int (*fcnPtr1)() = foo; // ok 型態相符
int (*fcnPtr2)() = goo; // wrong goo 的回傳 type 是 double 不 match
double (*fcnPtr4)() = goo; //ok 型態相符
fcnPtr1 = hoo; // wrong hoo 需要有 input
int (*fcnPtr3)(int) = hoo; // ok 型態相符

為了讓function pointer 去call function 的寫法可讀性更好,也可以直接這樣寫:

functor(); //如此一來就可以像一般call function 了

有些較舊的compile可能無法支援這種寫法。這是必須要注意的。另外也支援使用typedef增加可讀性:

typedef int (*funcptr) ()
int main()
{
    funcptr p = a; //funcptr 已經被宣告一種type
    p(); //利用上述方法直接call
}

以上是簡單介紹function pointer 的語法及觀念,但單就學習這個是沒有辦法體會它的強大。
接下來舉一個實際的使用範例:callback function

callback function:
將function A 當作參數丟到function B 在function B 中透過 pointer 去call A,此時A就是一個callback function。因為既然是pointer,理當可以當參數傳遞。
舉例來說:

#include<iostream>
using namespace std;
//定義function pointer
typedef int (*funcptr) (int,int);
int add(int a, int b)
{
 return a + b;
}
int sub(int a, int b)
{
 return a - b;
}
//要對參數a b做怎樣的操作會取決於傳入的參數 “op”,而該參數為一個function pointer
int op (funcptr op, int a, int b)
{
 return op(a, b); 
}
int main()
{
 int a = 5;
 int b = 3;
 cout << op(add, 5, 3) << endl;
}

由於op會取決於傳入的參數,我們也可以給他default值:

int op (functor op = add, int a, int b)
{
 return op(a, b); 
}

看到這裡一定會有很多人有疑惑,我幹嘛多此一舉透過一個function call 另一個function???
原因很簡單:為了擴充性。以下舉兩個例子:

範例ㄧ: 參考  Why usa a callback instead of a normal function call?

在文章中這位仁兄提到他的code:

void populate_array(int *array, size_t arraySize)
{
   for (size_t i=0; i<arraySize; i++)
      array[i] = getNextRandomValue();
}

int getNextRandomValue(void)
{
   return rand();
}

int main(void)
{
   int myarray[10];
   populate_array(myarray, 10);
   ...
}

看起來明明好好的為什麼要用function pointer???

下面一位大大就以擴充性來作討論,假設我取值的方式不止random一種,有random 奇數,random 偶數等等,我就要寫很多個populate_array 來實踐,如下:

void populate_array_RandomValue(int *array, size_t arraySize)
{
   for (size_t i=0; i<arraySize; i++)
      array[i] = getNextRandomValue();
}
void populate_array_EvenValue(int *array, size_t arraySize)
{
   for (size_t i=0; i<arraySize; i++)
      array[i] = getNextEvenValue();
}
void populate_array_OddValue(int *array, size_t arraySize)
{
   for (size_t i=0; i<arraySize; i++)
      array[i] = getNextOddValue();
}
...

然後再寫三個get function,如此一來程式不夠精簡,也不好維護。但如果透過function pointer呢?

int getNextRandomValue(void) {
    return rand();
}
int getNextEvenValue(void) {
    static int even = 2;
    return (even += 2);
}
int getNextNegativeValue(void) {
    static int neg = -1;
    return neg--;
}
int getNextValueFromUser(void) {
    int val;
    scanf("%d", &amp;val);
    return val;
}
populate_array(myarray, 10, getNextRandomValue);
populate_array(myarray, 10, getNextEvenValue);
populate_array(myarray, 10, getNextNegativeValue);
populate_array(myarray, 10, getNextValueFromUser);

如此一來是不是精簡多了?

範例二:
在物件導向的程式設計中我可以設計一個base object,並且期待使用我的人會向我註冊callback function,假設叫 child_access 好了,我就可以這樣設計我的onject:

//我設計的
class father
{
    public:
        father(functor foo)
        {
            child_access = foo;
        }
        father_access()
        {
            child_access();
        }
    private:
        funcptr child_access;
}
//a programmer 可以這樣宣告並使用
father a(foo_a);
//b programmer 可以這樣宣告並使用
father b(foo_b);
//c programmer 可以這樣宣告並使用
father c(foo_c);

如上所示,每個實作的人都可以定義自己的access function,並解無痛得和我的calss 接上,是不是很精簡呢?

callback function 還有很多妙用之後再來作介紹~

reference:
[1] function pointer
[2] Why usa a callback instead of a normal function call?

Include Guard

公司與學校的最大不同就是公司裡的專案通常是很多人一起合作完成的,多人合作時有很多必須要注意到的眉眉角角。譬如今天要講的include guard(heard guard)。
舉個wiki 的例子來說: 在"grandfather.h"中寫道:

#ifndef GRANDFATHER_H
#define GRANDFATHER_H

struct foo {
    int member;
};

#endif /* GRANDFATHER_H */

 

其中的 ifdef、define 和 endif 就是所謂的include guard

 

而在father.h中寫道:

#include "grandfather.h"

 

在child.c中寫道:

#include "grandfather.h"
#include "father.h"

 

如此一來 child.c 就不會發生 redefine 的compile error。若我沒有用include guard 作保護,我的 child.c 中在 include grandfather.h 時,pre-processor 會將 grandfather.h 的內容展開,會定義一次 foo ,接下來,在 include father.h 時,會再展開一次 (因為 father.h 也 include 了 grandfather.h) ,如此一來再定義了一次 foo,因此造成了compile error。

解憂雜貨店

作者:東野圭吾

說到東野大家第一印象是推理小說作家,且擅長科學犯案及推理.這本解憂雜貨店看書名就知道跟以往很不一樣.去書店很多次都有看到這本書但因書名並不吸引我,所以遲遲沒有看過。是某次因緣際會之下被推薦才想說嘗試看看,沒想到一看就一次看到完且後勁很強。

本書裡頭有五個小故事,彼此之間既分離又密切相關,每個故事的主角都面臨著人生的難題而向雜貨店尋求解答。有糾結該陪重病男友還是出國圓夢的運動家、違背家裡期待執意出門闖天下的音樂家、為了夢想需要金錢而想轉行當酒家女的OL。其實我們都像書裡的角色一樣面對很多徬徨,期待有間解惑雜貨店來引導人生的路,尤其是剛職場的我感觸更加深刻,但我相信就像書裡描述一般,天下無巧合,凡事皆因緣,所有的事都是最好的安排!

C++ Specialization

C++ 的樣板特化是一個非常powerful的工具。前面曾提到說C++有意減少programmer對於macro的使用。配合他物件的概念,C++提供了"樣板"及其輔助功能"特化"。簡而言之,當你使用樣板大量製造各式 type 的 function 時,若遇到某種type需要特別處理,無法一致性的使用樣板時,你可以使用特化 – specialization。

原文參考自 : Expression parameters and template specialization

 

using namespace std;
 
template <typename T>
class Storage
{
private:
    T m_tValue;
public:
    Storage(T tValue)
    {
         m_tValue = tValue;
    }
 
    ~Storage()
    {
    }
 
    void Print()
    {
        std::cout << m_tValue << std::endl;;
    }
};
int main()
{
   // Define some storage units
    Storage<int> nValue(5);
    Storage<double> dValue(6.7);
 
    // Print out some values
    nValue.Print();
    dValue.Print();
}

這段 code 配置了一個 buffer,並提供了存取的介面,這個 buffer 的 class 為一個標準的樣板。
 
main function 裡 demo 了兩種 type 的使用方式。分別是 int 以及 double。template 簡化了我們對於相同行為的程式開發,但為了顧及彈性,樣板特話就用在這個地方。假設所有的型態中,唯獨 double 型態的輸出模式想要改成 “科學記號" ,在以前我們只能再多寫一種樣板,但有了specialization,我們可以不必這麼做。看以下範例:

void Storage<double>::Print()
{
    std::cout << std::scientific << m_tValue << std::endl;
}

當 compiler 編譯到 Print() 時發現你的 type 是 double 而且妳已經有對 double 的 Print() 做定義,他將會以你特化的code為主,如此一來將可達到使用樣板但有保有彈性了!!

C++ Friend & Operator Overloading

  1. friend function : C++ 提供讓 free function (不定義在 class 內的 function) 也可以 access 到某 class 之 private member 的方法。
  2. operator overloding : 是讓 programmer 自己去重新定義既有的運算元

最近遇到一個case會用到這兩個功能。

sample code:

#include<iostream>
class Cents
{
    private:
        int m_nCents;
        
    public:
        Cents(int nCents): m_nCents(nCents){}
        int show() { std::cout << m_nCents << std::endl; } 
        bool operator > (Cents& c1, Cents& c2)
        {
            return (c1.m_nCents > c2.m_nCents) ? true: false;
        }
};

Cents max(Cents tX, Cents tY)
{
    return (tX > tY) ? tX : tY;
}

int main(void)
{
    Cents cNickle(5);
    Cents cDime(10);
    Cents cBigger = max(cNickle, cDime);
    cBigger.show();
}

我 overloading 了 > 希望可以對自定義的Cents type 比大小。 自以為看起來很美好但得到了以下compile error message:

error_msg

第一個錯,operator > 只能吃一個參數,但我給了兩個。" > " 是個 binary 的 operator 理當吃兩個參數,compiler 怎麼會該呢??

因為第一個錯導致第二個問題 : 他找不到適合的 max function

解法:

要存取 class 的 private member 的 operator overloading 有以下兩種做法

  1. 將 > operator overloading 做成Cents 的member function
  2. 將 > operator overloading 做成 free function (不在 Cents 的 scope 內)

將 > operator overloading 做成Cents 的member function:

class Cents
{
    private:
        int m_nCents;

    public:
        Cents(int nCents): m_nCents(nCents){}
        int show() { std::cout << m_nCents << std::endl; } 
        bool operator > (Cents& c2)
        {
            return (m_nCents > c2.m_nCents) ? true: false;
        }
};

Cents max(Cents tX, Cents tY)
{
    return (tX > tY) ? tX : tY;
}

int main(void)
{
    Cents cNickle(5);
    Cents cDime(10);
    Cents cBigger = max(cNickle, cDime);
    cBigger.show();
}

跟原先寫法相同的是 > operator overloading 都是 Cents 的 member function,但不同的是改只吃一個參數,因為其中一個參數"已經是自己",access m_nCents 的方式也由 c1.m_nCents 改為直接寫 m_nCents 。

將 > operator overloading 做成 free function (不在 Cents 的 scope 內)

class Cents
{
    private:
        int m_nCents;

    public:
        Cents(int nCents): m_nCents(nCents){}
        int show() { std::cout << m_nCents << std::endl; } 
        friend bool operator > (Cents& c1, Cents& c2)
        {
            return (c1.m_nCents > c2.m_nCents) ? true: false;
        }
};

Cents max(Cents tX, Cents tY)
{
    return (tX > tY) ? tX : tY;
}

int main(void)
{
    Cents cNickle(5);
    Cents cDime(10);
    Cents cBigger = max(cNickle, cDime);
    cBigger.show();
}

這種寫法雖然把 bool operator > (Cents& c1, Cents& c2) 定義在 Cents 裡面,但他並非 Cents 的member function。但他可以access private member 是因為用了 " friend " 關鍵字。另一個重點是,因為此 overloading 已不是 member 所以他 “需要兩個運算元"。

小小程式碼藏了很多C++的設計觀念,紀錄一下。

延伸閱讀:

  1. (原創) 如何使用Operator Overloading? (C/C++)
  2. C++ Beginner – ‘friend’ functions and << operator overloading: What is the proper way to overload an operator for a class?
  3. Unary and binary operator overloading

C++ Function Template

C++ 有一個設計趨勢,他設計了很多方法想減少 programmer 使用MACRO。Template 就是一個很好的例子,template 分成
function template、class template 等等。。。 接下來幾篇文章將以這" template " 為出發點 ,介紹這個C++很大的特色。

以下文章素材取自 : LearnCPP.com

試想一種情況,我要實現一個加法的function,但我的input 可能是兩個int 相加,可能是兩個 double, 以前的做法可能是實現兩種加法function:

//add for int

int add(int a, int b)
{
    return a + b;
}

//add for double

double add(double a, double b)
{
    return a + b;
}

有些人可能會採用macro 的方式撰寫,但macro也有不少缺點,讓很多人望之卻步。大家的心聲C++聽到了,因此他提供了template這個功能。所謂的template中文是"模板",直接以下面的範例做解釋:

template  // this is the template parameter declaration
Type max(Type tX, Type tY)
{
return (tX >; tY) ? tX : tY;
}

初次看到上方的code可能會覺得很奇怪。template 是個關鍵句,他會告訴compiler下面這個function的type要依照input 的type而定。也就是說,當你寫:

int nValue = max(100, 230); // calls max(int, int)

他就會變成 :

int max(int tX, int tY)
{
    return (tX > tY) ? tX : tY;
}

如果你寫 :

double dValue = max(6.34, 18.523); // calls max(double, double)

他會變成 :

double max(double tX, double tY)
{
    return (tX > tY) ? tX : tY;
}

樣板函式的type支援所有built in type,一個樣板函式在compile時和一般函式並無不同,也就是說所有的operator compiler都必須要知道。舉個例子來說:

class Cents
{
    private:
        int m_nCents;
    public:
        Cents(int nCents) : m_nCents(nCents){}
};

Cents cNickle(5);
Cents cDime(10);
 
cout<<max(cNickle, cDime);

編譯器會compile成:

Cents max(Cents tX, Cents tY)
{
    return (tX > tY) ? tX : tY;
}

你一定會拿到一個compile error,因為compiler偵測到: 你根本沒有說兩個cent type 的 tX 和 tY 怎麼比大小。因此必須要自己明確定義,就如同一般function 的使用方式。需改寫成:

class Cents
{
private:
    int m_nCents;
public:
    Cents(int nCents)
        : m_nCents(nCents)
    {
    }
 
    friend bool operator>(Cents& c1, Cents& c2)
    {
        return (c1.m_nCents > c2.m_nCents) ? true: false;
    }
};

自己定義 > 是甚麼意思,跟一般function的使用一樣。值得注意的是operator overloading 的 "friend" 字眼。可參考 : friend function for operator overloading

紅黑樹(3) – 證明

前篇文章有提到,紅黑樹的操作都在O(logn)的複雜度,在這裡談談他的證明。

先證明: 一個有n個node的紅黑樹, 最高高度為2 log(n+1)

看到這裡想必心中一定已經冒出了大問號 : 我不是要證明操作的複雜度嗎?幹嘛證明上面這個鬼東西?原因很簡單,以前的人發現只要知道這個定理就可以很簡單推出複雜度~

先證 node x底下的subtree最少有2bh(x)-1個internal node – 特性1

證明方式: 歸納法

  • 則x底下應該有: (2bh(x)-1 -1) + (2bh(x)-1 -1 ) + 1 = 2bh(x) -1 成立
  • 假設小孩的subtree都至少有2bh(x)-1 -1個internal node
  • 當x為高度為正整數的node, 且有兩個小孩,每個小孩的高度為bh(x) or bh(x)-1 <- 視其為黑或紅
  • 當x為高度為0的葉子, bh(x) = 0, 2^0 – 1 = 0, 確實子樹有0個node

再證有n個node的紅黑樹, 最高高度為2 log(n+1)

  • 紅黑樹的規則有提到過"如果一個node是紅的, 則它的children都是黑的
  • 這句話的另一種解釋為"從任一node到leaf, 至少一半以上的node是黑的
  • 假設h 是樹的高度,則bh(root) >= (h/2)
  • 又由特性1可推知: root 底下的node數 >= 2bh(root)-1 又 bh(root) >= (h/2) 所以 :
    2bh(root)-1 >= 2(h/2)-1
  • 假設node數為n,n>= 2(h/2)-1
  • 可推出原式 h <= 2log(n+1)

以上證明即可說明:

(1) 找尋特定點

(2) 找最大/小點

的複雜度皆為O(logn)

疑?那插入和刪除呢? 請接著看下一篇

ref:

[1]. 紅黑樹

紅黑樹(2) – Definition

上一篇聊過了紅黑樹基本特性,接下來要正式介紹它的定義。下面就直接先來個實例:

example

src : Red–black tree

關於紅黑樹的定義,若該樹為一紅黑樹則無時無刻都要符合下列幾點:

(1). 每個node不是紅就是黑

(2). root 必黑

(3). 每個葉子*都是黑

(4). 如果一個node是紅的, 則它的children都是黑的

(5). 對每個node來說, 從它到他的所有子孫葉子node的路徑上含有一樣數目的黑色node

* 紅黑樹中每個沒有child 的 node 都需補上nil 當作葉子

符合這樣結構的tree 我們就可稱它為一棵紅黑樹。下一篇將對它的操作複雜度做解釋。

reference:

[1]. https://www.csie.ntu.edu.tw/~hsinmu/courses/_media/dsa1_10fall/lecture15.pdf

[2]. Red–black tree