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