快樂的流暢：個人主頁

個人專欄：《C語言》《數據結構世界》《進擊的C++》

遠方有一堆篝火，在為久候之人燃燒！

---

一、仿函數

1.1 仿函數的介紹

仿函數，是一種特殊類型的類，它重載了（）運算符，使得這個類的使用看起來像一個函數，因此它又稱為函數對象。

具體來說，仿函數就是將函數的特性賦予到類上，使得這個類有了類似函數的行為。

1.2 仿函數的優勢

C++設計仿函數之初，其實就是想替代龐雜難懂的函數指針，將函數指針替換為簡單易懂的仿函數。

這里列舉兩個常用的仿函數——less和greater

template<class T>
struct less
{bool operator()(const T& x, const T& y){return x < y;}
};template<class T>
struct greater
{bool operator()(const T& x, const T& y){return x > y;}
};

二、priority_queue

細節：

1. priority_queue也是容器適配器，默認容器使用vector
2. 其底層數據結構是堆，并且默認情況為大堆
   如果不了解堆，可以先看往期【數據結構】【版本2.0】【樹形深淵】——二叉樹入侵
3. 為了能方便調整大小堆，增加了仿函數的模板

template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue
{
public:
private:Container _con;
};

悄悄說一句：其實容器模板和仿函數模板位置互換，才更加合理！（平時不怎么會換默認容器，但是會經常換仿函數來控制大小堆）

2.1 push

入堆

細節：

1. 先尾插元素
2. 再使用向上調整算法

void push(const T& x)
{_con.push_back(x);adjust_up(_con.size() - 1);
}

向上調整算法

細節：

• 構造一個仿函數模板對象，再利用重載的（）運算符進行比較（當然，也可以使用匿名對象）

void adjust_up(int child)
{Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

2.2 pop

出堆

細節：

1. 先首尾元素互換
2. 再尾刪元素
3. 最后使用向下調整算法

void pop()
{swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);
}

向下調整算法

細節：

• 構造一個仿函數模板對象，再利用重載的（）運算符進行比較（當然，也可以使用匿名對象）

void adjust_down(int parent)
{Compare com;int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child], _con[child+1])){++child;}if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}

2.3 top

獲取堆頂元素

const T& top() const
{return _con[0];
}

2.4 size

獲取堆中有效元素個數

size_t size() const
{return _con.size();
}

2.5 empty

判斷堆是否為空

bool empty() const
{return _con.empty();
}

三、反向迭代器

其實，反向迭代器也是一種適配器，它是根據不同容器的正向迭代器，來生成對應的反向迭代器。

同時，反向迭代器追求一種對稱美，rbegin()在end()，rend()在begin()。

3.1 成員變量與默認成員函數

細節：

1. 仍然使用struct，標明公有屬性
2. 成員變量是一個正向迭代器
3. 提供帶參構造函數（其余的默認成員函數不用顯式定義，淺拷貝即可）

template<class Iterator, class Ref, class Ptr>
struct __reverse_iterator
{typedef __reverse_iterator self;Iterator _cur;__reverse_iterator(Iterator it): _cur(it){}
};

3.2 operator*

細節：

1. 迭代器先自減，再解引用返回
2. 返回引用，為了區別普通迭代器和const迭代器

Ref operator*()
{Iterator tmp = _cur;return *--tmp;
}

3.3 operator->

細節：

1. 直接調用operator*()，根據不同容器的數據取地址返回
2. 返回指針，為了區別普通迭代器和const迭代器

Ptr operator->()
{return &(operator*());
}

3.4 operator++

細節：

1. 反向迭代器的++，就是正向迭代器的- -
2. 為了區分前置和后置，后置參數加上int（無實際意義，以示區分）
3. 前置傳引用返回，后置傳值返回

self& operator++()
{--_cur;return *this;
}self operator++(int)
{Iterator tmp = _cur;--_cur;return tmp;
}

3.5 operator- -

細節：同上

self& operator--()
{++_cur;return *this;
}self operator--(int)
{Iterator tmp = _cur;++_cur;return tmp;
}

3.6 relational operators

bool operator!=(const self& s)
{return _cur != s._cur;
}bool operator==(const self& s)
{return _cur == s._cur;
}

四、反向迭代器的適用

4.1 vector

template<class T>
class vector
{
public:typedef T* iterator;typedef const T* const_iterator;typedef __reverse_iterator<iterator, T&, T*> reverse_iterator;typedef __reverse_iterator<iterator, const T&, const T*> const_reverse_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}//...
}

4.1.1 rbegin

reverse_iterator rbegin()
{return reverse_iterator(end());
}const_reverse_iterator rbegin() const
{return const_reverse_iterator(end());
}

4.1.2 rend

reverse_iterator rend()
{return reverse_iterator(begin());
}const_reverse_iterator rend() const
{return const_reverse_iterator(begin());
}

4.2 list

template<class T>
class list
{
public:typedef __list_node<T> node;typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;typedef __reverse_iterator<iterator, T&, T*> reverse_iterator;typedef __reverse_iterator<iterator, const T&, const T*> const_reverse_iterator;iterator begin(){return iterator(_head->_next);}const_iterator begin() const{return const_iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator end() const{return const_iterator(_head);}//...
}

4.2.1 rbegin

reverse_iterator rbegin()
{return reverse_iterator(end());
}const_reverse_iterator rbegin() const
{return const_reverse_iterator(end());
}

4.2.2 rend

reverse_iterator rend()
{return reverse_iterator(begin());
}const_reverse_iterator rend() const
{return const_reverse_iterator(begin());
}

總結

這次學習了仿函數的概念和基本用法，對于升降序、大小堆等轉換具有極大便利。同時實現了新的容器適配器——priority_queue（優先級隊列），實際上就是堆。并且也完美實現了同為適配器的反向迭代器，至此，對于適配器有了更深一步的了解和運用。

真誠點贊，手有余香