文章目錄
- 1. stack的介紹和使用
- 2. queue的介紹和使用
- 3. priority_queue的介紹和使用
- 3.1模擬實作priority_queue
- 4.仿函式
1. stack的介紹和使用
2. queue的介紹和使用
3. priority_queue的介紹和使用
優先級佇列默認使用vector作為其底層存盤資料的容器，在vector上又使用了堆演算法將vector中元素構造成大堆的結構，
傳入less是大堆，傳入greater是小堆，和我們常識是相反的，
3.1模擬實作priority_queue
#pragma once
template<class T>
struct Less//仿函式
{
bool operator()(const T& a, const T& b)
{
return a < b;
}
};
template<class T>
struct Greater//仿函式
{
bool operator()(const T& a, const T& b)
{
return a > b;
}
};
namespace my_priority
{
template<class T, class Container = vector<T>, class Compare = Greater<T>>
class priority_queue
{
public:
/*priority_queue()
{}*/
//和priority_queue()等價，都是強制編譯器生成一個默認的建構式，用來初始化成員
priority_queue() = default;
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
:_con(first, last)//在這里傳迭代器進行初始化
{
//方法一：構建默認大堆
for (size_t i = (size() - 1 - 1) / 2; i >= 0; --i)
{
Adjustdown(i);
}
//方法二
/*for (size_t i = 1; i < size(); ++i)
{
Adjustup(i);
}*/
}
const T& top() const
{
return _con.front();
}
//向上調整
void Adjustup(int child)
{
Compare _com;
int parent = (child - 1) / 2;
while(child > 0)
{
if (_com(_con[child], _con[parent]))
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//插入元素
void push(const T& x)
{
_con.push_back(x);
Adjustup(size()-1);//向上調整
}
//向下調整
void Adjustdown(int parent)
{
size_t child = parent * 2 + 1;
Compare _com;
while (child < size())
{
if (child+1 < size() && _com(_con[child + 1], _con[child]))
{
child++;
}
if (_com(_con[child], _con[parent]))
{
swap(_con[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//頭刪
void pop()
{
assert(size() > 0);
swap(_con.front(), _con.back());
_con.pop_back();
Adjustdown(0);
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
Container _con;
};
}
4.仿函式
所謂的仿函式(functor)，是通過多載()運算子模擬函式行為的類，
因此，這里需要明確兩點：
1 仿函式不是函式，它是個類；
2 仿函式多載了()運算子，使得它的物件可以像函式那樣子呼叫(代碼的形式好像是在呼叫函式)，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/278920.html
標籤：區塊鏈
上一篇：非對稱加密演算法