C++ 容器的兩把利器之優(yōu)先級隊列與反向迭代器實現(xiàn)原理解析
-------------反向迭代器------------
1、適配器模式
要實現(xiàn)反向迭代器，就不得不提到適配器模式
在上一篇內容中，我們學習的 stack 和 queue 就是典型的容器適配器；而今天要講的反向迭代器，則是一種迭代器適配器
2、反向迭代器原理
反向迭代器是一個迭代器適配器，它包裝了一個正向迭代器，把 ++ 操作映射成原迭代器的 --，把 -- 操作映射成原迭代器的 ++，從而實現(xiàn)反向遍歷的效果
反向迭代器在容器中的指向：
3、反向迭代器的實現(xiàn)
namespace ljh
{
//typedef iterator<iterator, T& , T*> iterator;
//typedef iterator<iterator, const T& , const T*> iterator;
template<class Iterator, class Ref, class Ptr>
struct ReverseIterator
{
typedef ReverseIterator<Iterator, Ref, Ptr> Self;
Iterator _it;
ReverseIterator(Iterator it)
:_it(it)
{
}
Ref operator*()
{
Iterator tmp = _it;
return *(--tmp);
}
Ptr operator->()
{
return &(operator*());
}
Self& operator++()
{
--_it;
return *this;
}
//由于沒寫析構函數(shù)，所以不用擔心拷貝構造是淺拷貝
Self operator++(int)
{
Self tmp(*this);
--_it;//正向迭代器--，反向迭代器++
return tmp;
}
Self& operator--()
{
++_it;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
++_it;
return tmp;
}
bool operator!=(const Self& s) const
{
return _it != s._it;
}
};
typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<const_iterator, const T&, const T*const_reverse_iterator;
/*===================反向迭代器=====================*/
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
const_reverse_iterator rbegin()const
{
return reverse_iterator(end());
}
const_reverse_iterator rend() const
{
return reverse_iterator(begin());
}
}3.1 模板參數(shù)解析
template<class Iterator, class Ref, class Ptr> struct ReverseIterator
Iterator：被適配的正向迭代器類型（比如 vector::iterator）
Ref：迭代器取值（*it）時返回的引用類型（比如 T& 或 const T&）
Ptr：迭代器箭頭訪問（it->）時返回的指針類型（比如 T* 或 const T*）
3.2 類型別名與成員變量
typedef ReverseIterator<Iterator, Ref, Ptr> Self; Iterator _it;
Self：簡化自身類型的書寫，避免重復寫長模板名
_it：內部持有的正向迭代器，是反向迭代器的 “核心數(shù)據(jù)”
3.3 構造函數(shù)
ReverseIterator(Iterator it) : _it(it) {}用一個正向迭代器來初始化反向迭代器，把傳入的迭代器保存到 _it 中。
3.4 取值運算符operator*
Ref operator*()
{
Iterator tmp = _it;
return *(--tmp);
}這是反向迭代器的核心適配邏輯。
它先拷貝一份內部迭代器 _it，對拷貝做 -- 移動到前一個位置，再取值返回。
這樣保證了 rbegin() 能正確指向容器的最后一個元素。
3.5 箭頭運算符operator->
Ptr operator->()
{
return &(operator*());
}
復用 operator* 的結果，取其地址返回，支持 it->member 這樣的指針訪問語法。
3.6 前置 ++ 運算符operator++
Self& operator++()
{
--_it;
return *this;
}
反向迭代器的 ++ 對應內部正向迭代器的 --，實現(xiàn) “向后移動”（在反向遍歷中是向前走）。
3.7 后置 ++ 運算符operator++(int)
Self operator++(int)
{
Self tmp(*this);
--_it;
return tmp;
}
先創(chuàng)建一個當前對象的副本，再移動內部迭代器，最后返回副本。
這是后置 ++ 的標準實現(xiàn)，保證返回的是 “移動前” 的迭代器。
3.8 前置 -- 運算符operator--
Self& operator--()
{
++_it;
return *this;
}
反向迭代器的 -- 對應內部正向迭代器的 ++，實現(xiàn) “向前移動”（在反向遍歷中是向后退）。
3.9 后置 -- 運算符operator--(int)
Self operator--(int)
{
Self tmp(*this);
++_it;
return tmp;
}
邏輯同后置 ++，先拷貝再移動，返回移動前的迭代器。
3.10 不等比較運算符operator!=
bool operator!=(const Self& s) const
{
return _it != s._it;
}
bool operator==(const Self& s) const
{
return _it == s._it;
}直接比較兩個反向迭代器內部持有的正向迭代器，判斷它們是否指向不同位置。
// 先定義反向迭代器的類型別名（依賴之前的 ReverseIterator 適配器）
typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;
// 1. 普通版 rbegin()：可讀寫反向迭代器起點
reverse_iterator rbegin()
{
// 核心：用正向迭代器的 end() 初始化反向迭代器，指向容器最后一個元素
return reverse_iterator(end());
}
// 2. 普通版 rend()：可讀寫反向迭代器終點
reverse_iterator rend()
{
// 核心：用正向迭代器的 begin() 初始化反向迭代器，指向第一個元素之前
return reverse_iterator(begin());
}
// 3. const版 rbegin() const：只讀反向迭代器起點
const_reverse_iterator rbegin() const
{
// 核心：邏輯同普通版，但返回 const 版本，僅支持讀操作
return const_reverse_iterator(end());
}
// 4. const版 rend() const：只讀反向迭代器終點
const_reverse_iterator rend() const
{
// 核心：邏輯同普通版，但返回 const 版本，僅支持讀操作
return const_reverse_iterator(begin());
}
-------------優(yōu)先級隊列------------
1、仿函數(shù)
仿函數(shù)（Functor）是 C++ 中一種特殊的類對象，核心特點是重載（重載）了 operator() 運算符，使得對象可以像函數(shù)一樣被調用（用 對象名(參數(shù)) 的形式）。
簡單說：仿函數(shù)是 “像函數(shù)的對象”，本質是帶 operator() 的類實例。
template<class T>
class small
{
public:
bool operator()(const T& x,const T& y)
{
return x < y;
}
};
template<class T>
class big
{
public:
bool operator()(const T& x,const T& y)
{
return x > y;
}
};
int main()
{
small<int> s;
big<int> b;
cout << s(1,2) << endl;
cout << b(1, 2) << endl;
return 0;
}
對初次接觸的讀者來說，仿函數(shù)的調用方式（比如 s(1,2)）確實顯得有些陌生，和我們熟悉的 +、= 等運算符重載的寫法很不一樣。你可能暫時會疑惑它的實際價值，這很正常 —— 當我們后續(xù)用它來定制優(yōu)先級隊列的比較規(guī)則時，這種設計的靈活性和必要性就會清晰地展現(xiàn)出來。
2、優(yōu)先級隊列介紹
priority_queue 是 C++ 標準庫中的一個容器適配器，底層默認用 vector 存儲數(shù)據(jù)，內部維護一個堆結構，確保隊首元素始終是優(yōu)先級最高的（默認是最大值）。
核心特點：
只能訪問隊首的最大元素，不能遍歷或隨機訪問其他元素。
插入新元素時，會自動調整堆結構以維持優(yōu)先級順序。
彈出隊首元素后，剩余元素也會自動重新調整。
底層原理：通過調用 make_heap、push_heap、pop_heap 等算法函數(shù)來維護堆的特性。
默認行為：默認是大頂堆（最大元素優(yōu)先），可以通過傳入仿函數(shù)（如 greater<T>）改為小頂堆。
3、優(yōu)先級隊列的實現(xiàn)
namespace ljh
{
// 仿函數(shù)/函數(shù)對象
template<class T>
class Less
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
class Greater
{
public:
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
template<class T,class Container = vector<T> , class Compare = Less<T> >
class priority_queue
{
private:
//默認建大堆
void AdjustDown(int parent)
{
Compare com;//仿函數(shù)對象
int child = parent * 2 + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
{
++child;
}
if (com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//向上調整算法
void AdjustUp(int child)
{
Compare com;//仿函數(shù)對象
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;
}
}
}
public:
//默認構造
priority_queue()
{
}
//范圍構造
template<class InputIterator>
priority_queue(InputIterator first,InputIterator last)
{
while (first!=last)
{
_con.push_back(*first);
first++;
}
//建堆-向下調整建堆（默認建立大堆）
//N
for (int i = (_con.size() - 2) / 2; i >= 0; i--)
{
//向下調整算法
AdjustDown(i);
}
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
void push(const T& x)
{
_con.push_back(x);
AdjustUp(_con.size() - 1);
}
const T& top()
{
return _con[0];
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
private:
Container _con;
};
}3.1 類模板定義
template<class T, class Container = vector<T>, class Compare = Less<T>> class priority_queue
這是整個優(yōu)先級隊列的模板定義，有三個模板參數(shù)：
T：隊列中存儲的元素類型。
Container：底層存儲數(shù)據(jù)的容器，默認用 vector，也可以換成 deque 等支持隨機訪問的容器。
Compare：比較規(guī)則的仿函數(shù)，默認是 Less<T>（大頂堆），可以換成 Greater<T> 實現(xiàn)小頂堆。
3.2AdjustDown向下調整算法
void AdjustDown(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[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}這是維護堆結構的核心函數(shù)，用來在堆頂元素被移除后，把新的堆頂向下調整到正確位置：
先創(chuàng)建一個比較規(guī)則的仿函數(shù)對象 con。
從 parent 的左孩子 child = parent*2+1 開始。
先在左右孩子中，用 com 比較出優(yōu)先級更高的那個，作為真正要交換的 child。
然后用 com 比較父節(jié)點和這個孩子節(jié)點，如果父節(jié)點優(yōu)先級更低，就交換它們，并繼續(xù)向下調整。
如果父節(jié)點優(yōu)先級已經(jīng)更高，說明調整完成，直接跳出循環(huán)。
3.3AdjustUp向上調整算法
void AdjustUp(int child)
{
Compare com;
int parent = (child - 1) / 2;
while (child > 0)
{
if (com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}這個函數(shù)用來在新元素插入堆尾后，把它向上調整到正確位置：
創(chuàng)建比較規(guī)則的仿函數(shù)對象 con。
計算當前 child 節(jié)點的父節(jié)點 parent = (child-1)/2。
用 con 比較父節(jié)點和孩子節(jié)點，如果父節(jié)點優(yōu)先級更低，就交換它們，并繼續(xù)向上調整。
如果父節(jié)點優(yōu)先級已經(jīng)更高，說明調整完成，跳出循環(huán)。
3.4 默認構造函數(shù)
priority_queue()
{}
空的默認構造函數(shù)，底層容器 _con 會自己調用默認構造，不需要額外操作。
3.5 范圍構造函數(shù)
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
while (first != last)
{
_con.push_back(*first);
first++;
}
for (int i = (_con.size() - 2) / 2; i >= 0; i--)
{
AdjustDown(i);
}
}這個構造函數(shù)可以用一段迭代器區(qū)間來初始化隊列：
先把區(qū)間里的所有元素都插入到底層容器 _con 中。
然后從最后一個非葉子節(jié)點開始，依次調用 AdjustDown，把整個容器調整成一個合法的堆結構。
3.6 pop彈出堆頂元素
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
彈出堆頂元素的步驟：
先把堆頂元素（_con[0]）和堆尾元素交換。
然后刪除堆尾元素（也就是原來的堆頂）。
最后對新的堆頂元素調用 AdjustDown，重新維護堆的結構。
3.7push插入新元素
void push(const T& x)
{
_con.push_back(x);
AdjustUp(_con.size() - 1);
}
插入新元素的步驟：
先把新元素插入到底層容器的尾部。
然后對這個新插入的元素調用 AdjustUp，把它向上調整到正確的位置，以維持堆的性質。
3.8top獲取堆頂元素
const T& top()
{
return _con[0];
}
直接返回底層容器的第一個元素，也就是堆頂元素。因為堆頂始終是優(yōu)先級最高的元素。
3.9empty判斷隊列是否為空
bool empty()
{
return _con.empty();
}
直接調用底層容器的 empty() 方法，判斷隊列是否為空。
3.10size獲取隊列元素個數(shù)
size_t size()
{
return _con.size();
}
直接返回底層容器的大小，也就是隊列中元素的個數(shù)。
到此這篇關于C++ 容器的兩把利器之優(yōu)先級隊列與反向迭代器實現(xiàn)原理解析的文章就介紹到這了,更多相關C++ 優(yōu)先級隊列與反向迭代器內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要為大家詳細介紹了基于MFC和OpenCV實現(xiàn)角點檢測，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-03-03
這篇文章主要給大家介紹了關于c++實現(xiàn)新年煙花效果的相關資料,文中給出了詳細完整代碼,適合初學C語言/C++的小伙伴學習研究,需要的朋友可以參考下2023-11-11
本篇文章是對C語言字符串操作進行了詳細的總結分析，需要的朋友參考下2013-05-05
下面小編就為大家?guī)硪黄猚++10進制轉換為任意2-16進制數(shù)字的實例。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-06-06
本文主要介紹了C++中string流的具體使用,包括istringstream、ostringstream、stringstream這三種類型的使用,具有一定的參考價值,感興趣的可以了解一下2025-06-06
MFC實現(xiàn)在文件尾追加數(shù)據(jù)的方法
這篇文章主要介紹了MFC實現(xiàn)在文件尾追加數(shù)據(jù)的方法,涉及MFC文件操作的相關技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-09-09
本文介紹了如何通過鼠標拖動移動圖片以及使用鼠標滾輪進行圖片縮放的技術實現(xiàn),包括完整的解決方案,ImageWidget.h、ImageWidget.cpp和main.cpp的編寫,以及詳細的函數(shù)解釋,如paintEvent()重繪圖片,以及平滑縮放和偏移量的應用等,需要的朋友可以參考下2024-10-10
這篇文章主要介紹了C++ assert()函數(shù)用法案例詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-09-09
C語言FlappyBird飛揚的小鳥實現(xiàn)開發(fā)流程
因為在家宅了好多天，隨手玩了下自己以前做的一些小游戲，說真的，有幾個游戲做的是真的劣質，譬如 flappybird 真的讓我難以忍受，于是重做了一波分享給大家2022-11-11
以前了解過c++的棧內存溢出，沒想到在c#里被我遇到了，問題看似不大，如何被恰好相鄰的四個字節(jié)是返回地址，說不定危害不小??！看來c#的互操作還是得小心為好2013-10-10