C++

String Processing⚓︎

int isalnum(int c);⚓︎

這個函數返回非零值，如果c是一個數字或字母，否則為0。

int tolower(int c);⚓︎

這個函數返回小寫相當於c，如果存在的值，否則c保持不變。返回值可以隱式char為int值。

int isalpha(int c);⚓︎

這個函數返回非零值，如果c是一個字母，否則為0

Compare Operation⚓︎

greater< int >⚓︎

greater<int>函式被包在#include <functional>中，理論上是一個比較式a>b;，但實際上記憶成和原本排序相反比較好。舉個例子，默認sort排序由小到大，也就是用了less<int>:

C++

int main(){
    int arr[] = { 60, 10, 80, 40, 30,
                  20, 50, 90, 70 };
    int n = sizeof(arr) / sizeof(arr[0]);

    // To sort the array in decreasing order
    // use greater <int>() as an third arguments
    sort(arr, arr + 9, greater<int>());

    // Print array elements
    printArray(arr, n);

    return 0;    
}

Bash Session

90 80 70 60 50 40 30 20 10

但是我們總是能找一個反例，像是priority_queue的排序默認是由大到小，所以用了greater<int>會反過來，變成由小到大:

C++

// C++ program to illustrate std::greater

#include <functional>
#include <iostream>
#include <queue>
using namespace std;

// Function to print elements of priority_queue
void showpq(priority_queue<int, vector<int>,
                           greater<int> >
                pq)
{
    priority_queue<int,
                   vector<int>,
                   greater<int> >
        g;
    g = pq;

    // While priority_queue is not empty
    while (!g.empty()) {

        // Print the top element
        cout << g.top() << ' ';

        // Pop the top element
        g.pop();
    }
}

// Driver Code
int main()
{
    // priority_queue use to implement
    // Max Heap, but using function
    // greater <int> () it implements
    // Min Heap
    priority_queue<int, vector<int>,
                   greater<int> >
        gquiz;

    // Inserting Elements
    gquiz.push(10);
    gquiz.push(30);
    gquiz.push(20);
    gquiz.push(5);
    gquiz.push(1);

    // Print elements of priority queue
    cout << "The priority queue gquiz is : ";
    showpq(gquiz);
    return 0;
}

Bash Session

The priority queue gquiz is : 1 5 10 20 30

Data Structure⚓︎

Vector⚓︎

Max Element⚓︎

可在引用max_element(a.begin(), a.end());來找最大值，複雜度為\(O(n)\)。

C++

// C++ program to find the max
// of Array using *max_element() in STL

#include <bits/stdc++.h>
using namespace std;

int main()
{
    // Get the vector
    vector<int> a = { 1, 45, 54, 71, 76, 12 };

    // Print the vector
    cout << "Vector: ";
    for (int i = 0; i < a.size(); i++)
        cout << a[i] << " ";
    cout << endl;

    // Find the max element
    cout << "\nMax Element = "
         << *max_element(a.begin(), a.end());//Max Element = 76
    return 0;
}

Heap⚓︎

在c++中，heap可以大約用priority_queue實作。常見操作如下:

C++

//heap.push() O(log(n))
//heap.top()  O(1)
//heap.pop()  O(1)
int main(){
    priority_queue<int> max_heap;
    max_heap.push(3);//[3]
    max_heap.push(1);//[3,1]
    max_heap.push(2);//[3,2,1]
    max_heap.top();//3
    max_heap.pop()//[2,1]
    return 0;
}

而priority_queue默認為max heap。如果要使用min_heap，可以加入greater<int>。

C++

//heap.push() O(log(n))
//heap.top()  O(1)
//heap.pop()  O(1)
int main(){
    priority_queue<int, vector<int>, greater<int>> min_heap;
    min_heap.push(3);//[3]
    min_heap.push(1);//[1,3]
    min_heap.push(2);//[1,2,3]
    min_heap.top();//1
    min_heap.pop()//[2,3]
    return 0;
}

OOP⚓︎

Smart Pointer⚓︎

一般的指針需要我們去new和delete，不少程序員都會漏還一些memory。而智能指針只需要處理new的部分，delete的部分程式會自動歸還。

至於如何實作，智能指針其實就是一個object，constructor的部分就是new，destructor的部分就是delete。我們知道當一個object結束後，就會自動呼叫destructor，智能指針透過這個特性達到memory自動歸還的動作。

其實智能指針實作上也有許多細節，不過C++ library已經有寫好的API了。常見的智能指針有:

weak_ptr
unique_ptr
shared_ptr

如果有特別顧及程式的安全性，需要用到智能指針，我這裡推薦使用shared_ptr，功能比較完整，比較沒有奇怪的特性。

RAII⚓︎

RAII (Resource Acquisition Is Initialization) 是利用object特性的簡單技術，它可以確保指針建立失效時，解決其他指針沒有歸還，或是解決指針指到被刪除object的問題。

舉個例子

C++

class PrettyMenu{
    public:
        ...
        void changeBackground(std::istream& imgSrc); //改變背景圖片
        ...
    private:
        Mutex mutex;//加入互斥鎖
        Image* bgImage;//目前的背景圖片
        int imageChanges;//背景圖片被改變的次數
}

如果是在多線程的情況下，void changeBackground(std::istream& imgSrc);的實作方式可能如下:

C++

PrettyMenu::void changeBackground(std::istream& imgSrc){
    lock(&mutex);
    delete bgImage;
    imageChanges++;
    bgImage = new Image(imgSrc);
    unlock(&mutex);
}

但上述的函數其實很糟，假如 bgImage = new Image(imgSrc);異常，除了mutex永遠不會unlock，bgImage會指向一個被刪除的object外，iamgeChanges還會加一。

為了解決上述的問題，我們引用了RAII的技術，將圖片和mutex都用智能指針管理。順便將iamgeChanges變數放到函數最後面。

C++

class Lock{
    public:
        explicit Lock(Mutex* pm)//explicit的目的就是不能隱性轉型
        : mutexPtr(pm, unlock){//將unlock函數做為刪除器
            lock(mutexPtr.get());
        }
    private:
        std::tr1::shared_ptr<Mutex> mutexPtr;
}

class PrettyMenu{
    public:
        ...
        void changeBackground(std::istream& imgSrc); //改變背景圖片
        ...
    private:
    Mutex mutex;//加入互斥鎖
    std::tr1::shared_ptr<Image> bgImage;//目前的背景圖片
    int imageChanges;//背景圖片被改變的次數
}

PrettyMenu::void changeBackground(std::istream& imgSrc){
    lock(&mutex);
    bgImage.reset(new Image(imgSrc));
    imageChanges++;
}

前一節有提到智能指針的特性，就是當object正常結束(像說函數退出)或異常退出時，智能指針就會叫出destructor，對指針自我刪除並指向空值。就能確保函數很安全。
而上面程式碼中的mutex，巧妙的將智能指針的destructor設置成unlock，也就能避免掉會鎖死的情況發生。

Reference⚓︎

Effective C++, Third Edition