前言
我們先來籠統(tǒng)的介紹一下今天的三個內(nèi)容。
-
適配器——簡單的理解就是復(fù)用，用已經(jīng)實現(xiàn)的輪子，來繼續(xù)實現(xiàn)某種功能。
-
反向迭代器——原理很簡單，就是對稱+復(fù)用（已經(jīng)造好的正向迭代器）
-
仿函數(shù)——與函數(shù)用法相同的類，用于排序，比如大堆，小堆，升序，降序。
一、適配器
適配器的功能，在我們模擬實現(xiàn)棧和對列時十分方便！
先用這兩個例子感受一下。
①模擬實現(xiàn)棧
template<class T,class Con = deque<T>>
class stack
{
public:
void push(const T& val)
{
st.push_back(val);
}
void pop()
{
st.pop_back();
}
T& top()
{
return st[st.size() - 1];
}
size_t size()
{
return st.size();
}
bool empty()
{
return st.empty();
}
private:
Con st;
};
②模擬實現(xiàn)對列
template<class T, class Con = deque<T>>
class queue
{
public:
void push(const T& val)
{
qu.push_back(val);
}
void pop()
{
qu.pop_front();
}
T& front()
{
return qu[0];
}
size_t size()
{
return qu.size();
}
bool empty()
{
return qu.empty();
}
private:
Con qu;
};
這里的模板參數(shù)：
template<class T, class Con = deque<T>>
//這就是適配器
看完這兩個例子，你可能會明白，并且可能會驚訝于適配器的方便之處。
并且這里也給了模板一個用法——缺省參數(shù)。
且如果是全缺省的話，我們示例化還是要給參數(shù)列表的。
如下：
stack<> st;
再來談?wù)刣eque，你可能會好奇，這里在棧的第二個缺省參數(shù)為啥不給vector<T>, 對列的第二個缺省參數(shù)為啥不給list<T>。
要弄清楚原因我們先得了解deque的基本結(jié)構(gòu)：
我們知道這個中控數(shù)組一旦滿了，就要考慮擴容的問題，那該如何擴呢？
只需要將中控數(shù)組進行擴容，然后將指針拷貝過去即可。
因此相較于vector無需動數(shù)據(jù)即可完成擴容！—— 提高了擴容的效率。
相較于vector，這種結(jié)構(gòu)也支持隨機訪問，不過得通過計算，這樣高頻率的隨機訪問效率會降低，緩沖命中率也有一定的下降。
相較于list，由于list是單個申請單個釋放，因此deque的緩沖命中率較高。
但是相較于list，如果deque要在中間插入數(shù)據(jù)，那效率就會降低，這一點不如list。
這樣：
- stack結(jié)構(gòu)，實現(xiàn)尾插尾刪功能，如果要考慮擴容的效率，deque的優(yōu)勢更大。
- queue結(jié)構(gòu)，實現(xiàn)尾插頭刪功能，如果要考慮到緩沖命中率，deque的優(yōu)勢更大。
因此庫里采用了deque來實現(xiàn)棧和對列！
二、反向迭代器
我們先來看庫里的實現(xiàn)方式：
- vector
- list
可以看到，這里呈現(xiàn)對稱的方式，但是如何解引用是關(guān)鍵。
庫里是這樣實現(xiàn)的：
Reverse_iterator operator* ()
{
Iterator tmp(_it);
return *--tmp;
}
這里使用了正向迭代器的拷貝構(gòu)造，然后再減減訪問反向迭代器的下一個元素，這樣實現(xiàn)了錯位，也能剛好利用實現(xiàn)好的正向迭代器。
剩余的就不難實現(xiàn)了：
template<class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{
typedef Reverse_iterator<Iterator, Ref, Ptr> self;
//自定義的類型不能被當(dāng)做類名進行使用
Reverse_iterator(const Iterator& it)
{
_it = it;
}
self& operator ++()
{
_it--;
return *this;
}
self operator ++(int)
{
self tmp(_it);
_it--;
return self;
}
Ref operator* ()
{
Iterator tmp(_it);
return *--tmp;
}
Ptr operator->()
{
return _it.operator->();
}
bool operator!=(const Reverse_iterator&it)const
{
return _it != it._it;
}
bool operator==(const Reverse_iterator& it)const
{
return _it == it._it;
}
Iterator _it;
};
然后我們只需在容器里加上下面的代碼即可完成復(fù)用！
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 <const_iterator, const T, const T*>\
const_reverse_iterator;
reverse_iterator rbegin()
{
return end();
//這里會調(diào)用拷貝構(gòu)造
}
reverse_iterator rend()
{
return begin();
}
三、仿函數(shù)
我們這里先實現(xiàn)一個優(yōu)先級對列——大堆。
template<class T,class Container = vector<T>>
class priority_queue
{
//建大堆
void AdjustDown(int parent)
{
//假設(shè)左孩子較大
size_t child = parent * 2 + 1;
//因為是往下比較，所以child應(yīng)在范圍內(nèi)
while (child < con.size())
{
//先選出來較大的孩子，當(dāng)然前提得存在。
if (child + 1 < con.size() && con[child] < con[child + 1])
{
child = child + 1;
}
//再跟父節(jié)點進行比較，如果孩子大就換
if (con[parent]< con[child])
{
swap(con[parent], con[child]);
//因為是向下比較的，所以要看parent是不是還比下面的孩子大。
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//建大堆
void AdjustUp(int child)
{
int parent = (child - 1) / 2;
while (parent >= 0)
{
if (con[parent] < con[child])
{
swap(con[parent], con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
public:
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
InputIterator it = first;
while (it != last)
{
con.push_back(*it);
it++;
}
//進行調(diào)堆
//從最后一個葉子結(jié)點的父節(jié)點開始。
//時間復(fù)雜度O(N)
for (int i = ((con.size() - 1) - 1) / 2; i >= 0; i--)
{
AdjustDown(i);
}
}
void pop()
{
swap(con[0], con[con.size() - 1]);
con.pop_back();
AdjustDown(0);
}
void push(const T& val)
{
con.push_back(val);
AdjustUp(con.size() - 1);
}
size_t size()
{
return con.size();
}
bool empty()
{
return con.empty();
}
T top()const
{
return con[0];
}
priority_queue()
{}
private:
Container con;
};
這里的大堆算是實現(xiàn)了，借助這二叉樹的一點點知識。
- 那如果我們還要實現(xiàn)小堆呢？
用不用cv一份，再改呢？其實不用，只需要寫一個仿函數(shù)即可。
template<class T>
struct Less
{
bool operator()(const T &x1 ,const T& x2)
{
return x1 < x2;
}
};
template<class T>
struct Greater
{
bool operator()(const T& x1, const T& x2)
{
return x1 > x2;
}
};
如何使用呢？用類模板+重載函數(shù)的掉用。
template<class T,class Container = vector<T>,class Compare = Less<T>>
class priority_queue
{
//建大堆
void AdjustDown(int parent)
{
//假設(shè)左孩子較大
size_t child = parent * 2 + 1;
//因為是往下比較，所以child應(yīng)在范圍內(nèi)
while (child < con.size())
{
//先選出來較大的孩子，當(dāng)然前提得存在。
if (child + 1 < con.size() && com(con[child] , con[child + 1]))
{
child = child + 1;
}
//再跟父節(jié)點進行比較，如果孩子大就換
if (com(con[parent], con[child]))
{
swap(con[parent], con[child]);
//因為是向下比較的，所以要看parent是不是還比下面的孩子大。
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//建大堆
void AdjustUp(int child)
{
int parent = (child - 1) / 2;
while (parent >= 0)
{
if (com(con[parent] , con[child]))
{
std::swap(con[parent], con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
public:
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
InputIterator it = first;
while (it != last)
{
con.push_back(*it);
it++;
}
//進行調(diào)堆
//從最后一個葉子結(jié)點的父節(jié)點開始。
//時間復(fù)雜度O(N)
for (int i = ((con.size() - 1) - 1) / 2; i >= 0; i--)
{
AdjustDown(i);
}
}
void pop()
{
swap(con[0], con[con.size() - 1]);
con.pop_back();
AdjustDown(0);
}
void push(const T& val)
{
con.push_back(val);
AdjustUp(con.size() - 1);
}
size_t size()
{
return con.size();
}
bool empty()
{
return con.empty();
}
T top()const
{
return con[0];
}
priority_queue()
{}
private:
Container con;
Compare com;
};
這樣既可以當(dāng)做大堆使用，也可以當(dāng)做小堆使用。文章來源：http://www.zghlxwxcb.cn/news/detail-600738.html
總結(jié)
?今天的分享就到這里了，如果覺得文章不錯，點個贊鼓勵一下吧！我們下篇文章再見！文章來源地址http://www.zghlxwxcb.cn/news/detail-600738.html
到了這里，關(guān)于【C++進階之路】適配器、反向迭代器、仿函數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
