C++中priority_queue與仿函數(shù)實現(xiàn)方法

更新時間：2024年10月26日 09:51:27 作者：9毫米的幻想

這篇文章主要給大家介紹了關(guān)于C++中priority_queue與仿函數(shù)實現(xiàn)的相關(guān)資料,優(yōu)先級隊列是一種容器適配器,其底層通常采用vector容器,并通過堆算法來維護元素的順序,文中通過代碼介紹的非常詳細《》需要的朋友可以參考下

1 priority_queue 介紹

p r i o i r t prioirt prioirt_ q u e u e queue queue 文檔介紹

優(yōu)先級隊列是一種容器適配器，根據(jù)嚴格的弱排序標(biāo)準(zhǔn)，它的第一個元素總是它所包含的元素中最大(或最小)的
此上下文類似于堆，在堆中可以隨時插入元素，并且只能檢索最大堆元素（優(yōu)先隊列中位于定部的元素）
優(yōu)先隊列被實現(xiàn)為容器適配器，容器適配器即將特定容器類封裝作為其底層容器類， q u e u e queue queue 提供一組特定的成員函數(shù)來訪問其元素。元素從特定容器的"尾部"彈出，其稱為優(yōu)先隊列的頂部。
底層容器可以是任何標(biāo)準(zhǔn)容器類模板，也可以是其他特定設(shè)計的容器類。容器應(yīng)該可以通過隨機訪問迭代器訪問，并支持以下操作：

函數(shù)名	檢測容器是否為空
e m p t y empty empty()	檢測容器是否為空
s i z e size size()	返回容器中有效元素個數(shù)
f r o n t front front()	返回容器中第一個元素的引用
p u s h push push_ b a c k back back()	在容器尾部插入數(shù)據(jù)
p o p pop pop_ b a c k back back()	刪除容器尾部元素

標(biāo)準(zhǔn)容器類 v e c t o r vector vector 和 d e q u e deque deque 滿足這些需求。默認情況下，如果沒有為特定的 p r i o r i t y priority priority_ q u e u e queue queue 類實例化特定容器類，則使用 vector
需要支持隨機訪問的迭代器，以便始終在內(nèi)部保存堆結(jié)構(gòu)。容器適配器通過在需要時自動調(diào)用算法函數(shù) make_heap 、push_heap 和 pop_heap 來自動完成此操作

2 priority_queue 的使用

2.1 priority_queue 的函數(shù)接口

優(yōu)先級隊列默認使用 v e c t o r vector vector 作為其底層存儲數(shù)據(jù)的容器，在 v e c t o r vector vector 上又使用了堆算法將 v e c t o r vector vector 中元素構(gòu)成堆的結(jié)構(gòu)，因此 p r i o r i t y priority priority_ q u e u e queue queue 就是堆，所有需要用到堆的地方，都可以考慮使用 p r i o r i t y priority priority_ q u e u e queue queue。

注意：默認情況下 p r i o r i t y priority priority _ q u e u e queue queue 是大堆

函數(shù)聲明	接口說明
p r i o r i t y priority priority_ q u e u e queue queue()	構(gòu)造一個空的優(yōu)先級隊列
e m p t y empty empty()	檢測優(yōu)先級隊列是否為空，是返回 t r u e true true，否則返回 f a l s e false false
t o p top top()	返回優(yōu)先級隊列中最大（最?。┰?，即堆定元素
p u s h push push( x x x)	在優(yōu)先級隊列中插入元素 x x x
p o p pop pop()	刪除優(yōu)先級隊列中最大(最小)元素，即堆頂元素

2.2 priority_queue 的使用

優(yōu)先級隊列一個有三個模板參數(shù)：class T、class Container = vector<T>、class Compare = less<typename Container::value_type> 第一個參數(shù)是確定優(yōu)先級隊列的存儲類型；第二個參數(shù)確定 p r i o r i t y priority priority_ q u e u e queue queue 底層容器的結(jié)構(gòu)，默認為 v e c t o r vector vector，priority_queue也是一種適配器模式；第三個參數(shù)確定是建大堆還是小堆，默認是大堆，建立小堆的話要自己傳遞一個仿函數(shù)。

我們來簡單使用一下 p r i o r i t y priority priority_ q u e u e queue queue

void test1()
{
	priority_queue<int> pq;
	pq.push(4);
	pq.push(1);
	pq.push(5);
	pq.push(7);
	pq.push(9);

	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;
}

運行結(jié)果：

我們再來試試小堆

void test2()
{
	priority_queue<int, vector<int>, greater<int>> pq;
	pq.push(4);
	pq.push(1);
	pq.push(5);
	pq.push(7);
	pq.push(9);

	cout << " ";
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;
}

但第三個模板參數(shù)class Compare = less<typename Container::value_type> 是什么東西呢？為什么傳 g r e a t e r < i n t > greater<int> greater<int> 就從大堆變小堆了呢？這其實是一個仿函數(shù)，我們慢慢來介紹。

3 仿函數(shù)

3.1 什么是仿函數(shù)

什么是仿函數(shù)呢？仿函數(shù)本質(zhì)是一個類！它里面重載了 o p e r a t o r operator operator() 函數(shù)（即函數(shù)調(diào)用操作符：func()中的()）。

比如現(xiàn)在我想寫兩個整型的比較的仿函數(shù)，可以怎么寫呢？

class Less
{
public:
	bool operator()(int x, int y)
	{
		return x < y;
	}
};

可以看到它沒有成員變量；其實仿函數(shù)大部分都是空類，都是沒有成員變量的

我們將其改造一下就成了模板，可以支持多種類型的比較。但并不是說仿函數(shù)就是模板，仿函數(shù)類指的是它重載了 o p e r a t o r ( ) operator() operator() 函數(shù)的類

template<class T>
class Less
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};

那我們又如何調(diào)用呢？如下：

int main()
{
	Less<int> LessFunc;
	cout << LessFunc(1, 2) << endl;
	return 0
}

按照我們以前的理解，LessFunc(1, 2)是個函數(shù)調(diào)用，LessFunc是一個函數(shù)名或函數(shù)指針。但現(xiàn)在，它一個對象。

仿函數(shù)本質(zhì)是一個類，這個類重載 o p e r a t o r ( ) operator() operator()，它的對象可以像函數(shù)一樣使用
LessFunc本質(zhì)是調(diào)用了 o p e r a t o r ( ) operator() operator()

cout << LessFunc(1, 2) << endl;
cout << LessFunc.operator()(1, 2) << endl;

同樣，我們還可以實現(xiàn)一個 g r e a t e r greater greater 的仿函數(shù)

template<class T>
class Greater
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x > y;
	}
};

3.2 仿函數(shù)的應(yīng)用

那 p r i o r i t y priority priority_ q u e u e queue queue 為什么要仿函數(shù)作為模板參數(shù)呢？

我們知道堆的插入，是要調(diào)用向上調(diào)整算法的

template<class T, class Container = vector<T>>
class priority_queue
{
public:
	void AdjustUp(int child)
	{		
		int parent = (child - 1) / 2;
		while (child > 0)
		{
			if (_con[parent] < _con[child])
			{
				swap(_con[child], _con[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
				break;
		}
	}

private:
	Container _con;
};

上述實現(xiàn)的向上調(diào)整算法，判斷條件是if (_con[parent] < _con[child])建的是大堆，那如果我想建小堆怎么辦？自己手動改代碼嗎？那也太離譜了吧。

這時，仿函數(shù)的作用就出來了。

我們再增加一個模板參數(shù)： C o m p a r e Compare Compare， C o m p a r e Compare Compare 是一個類型，傳遞一個仿函數(shù)。我們還可以給一個缺省值

template<class T, class Container = vector<T>, class Compare = Less<T>>

這時，我們就可以將比較邏輯寫成泛型

if (Compare(_con[parent], _con[child]))

如果我們想建大堆，比較邏輯是 < ，傳遞 Less<T> 類型；反之傳遞 Greater<T> 類型。（庫中是 l e s s less less<T> 和 g r e a t e r greater greater<T>）

int main()
{
	Priority_queue<int, vector<int>, Less<int>> p3;
	Priority_queue<int, vector<int>, Greater<int>> p4;

	return 0;
}

注：模板模板實例化時傳遞的是類型，而函數(shù)模板傳參時需要傳的是對象

如：寫一個向上調(diào)整算法的函數(shù)模板

template<class Compare>
void AdjustUp(int* a, int child, Compare com)
{
	
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (com(a[child], a[parent]))
		{
			swap(a[child], a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

int main()
{
	int a[] = { 1 };

	Less<int> LessFunc;
	AdjustUp(a, 1, LessFunc);//傳遞有名對象
	
	AdjustUp(a, 1, Less<int>());//傳遞匿名對象
	
	return 0;
}

4 需自己寫仿函數(shù)的情況

庫中是幫我們實現(xiàn)了仿函數(shù) l e s s less less 和 g r e a t e r greater greater 的，也就是說一般情況下我們是不用自己實現(xiàn)仿函數(shù)，這直接調(diào)用庫里的就好了

less

greater

但有些情況時需要我們自己寫的。

4.1 類類型不支持比較大小

class Date
{ 
public :
	Date(int year = 1900, int month = 1, int day = 1)
		: _year(year)
		, _month(month)
		, _day(day)
	{}

private:
	int _year;
	int _month;
	int _day;
};

int main()
{
	priority_queue<Date> q1;
	q1.push(Date(2018, 10, 29));
	q1.push(Date(2018, 10, 28));
	q1.push(Date(2018, 10, 30));
	
	return 0;
}

D a t e Date Date類中并沒有重載 o p e r a t o r operator operator< 和 o p e r a t o r operator operator> 的函數(shù)，編譯就會報錯

這時，就需要我們自己實現(xiàn) l e s s less less 和 g r e a t e r greater greater 仿函數(shù)

4.2 類中支持的比較方式不是我們想要的

class Date
{ 
public :
	Date(int year = 1900, int month = 1, int day = 1)
		: _year(year)
		, _month(month)
		, _day(day)
	{}
	bool operator<(const Date& d)const
	{
		return (_year < d._year) ||
			(_year == d._year && _month < d._month) ||
			(_year == d._year && _month == d._month && _day < d._day);
	} 
	bool operator>(const Date& d)const
	{
		return (_year > d._year) ||
			(_year == d._year && _month > d._month) ||
			(_year == d._year && _month == d._month && _day > d._day);
	}
private:
	int _year;
	int _month;
	int _day;
};

現(xiàn)在 D a t e Date Date類中支持了比較方式，但如果我們這樣傳參呢？

int main()
{
	priority_queue<Date*> q1;
	q1.push(new Date(2018, 10, 29));
	q1.push(new Date(2018, 10, 28));
	q1.push(new Date(2018, 10, 30));
	
	cout << *q1.top() << endl;
	q1.pop();
	cout << *q1.top() << endl;
	q1.pop();
	cout << *q1.top() << endl;
	q1.pop();

	return 0;
}

你會發(fā)現(xiàn)，每次的結(jié)果都不一樣，我們控制不住。這時因為我們傳遞的是指針，它是按指針大小來比較

這時就需要我們自己實現(xiàn)仿函數(shù)

class DateLess
{
	bool operator()(Date* p1, Date* p2)
	{
		return *p1 < *p2;
	}
};

5 priority_queue 的模擬實現(xiàn)

namespace my_priority_queue
{
   
    template <class T, class Container = vector<T>, class Compare = less<T> >
    class priority_queue
    {
    public:
       template <class InputIterator>
       priority_queue(InputIterator first, InputIterator last)
       {
           InputIterator it = first;
           while (it != last)
           {
               push(*it);
               ++it;
           }
       }

        priority_queue() {}
        

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

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

        const T& top() const
        {
            return _c.front();
        }

        T& top()
        {
            return _c.front();
        }

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

        void AdjustUp(int child)
        {          
            int parent = (child - 1) / 2;

            while (child > 0)
            {
                if (_comp(_c[parent], _c[child]))
                {
                    swap(_c[parent], _c[child]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else
                    break;
            }
        }

        void AdjustDown(int parent, int end)
        {
            int child = parent * 2 + 1;

            while (child <= end)
            {
                if (child + 1 <= end && _comp(_c[child], _c[child + 1]))
                    ++child;

                if (_comp(_c[parent], _c[child]))
                {
                    std::swap(_c[parent], _c[child]);
                    parent = child;
                    child = parent * 2 + 1;                
                }
                else
                    break;
            }
        }

        void pop()
        {
            assert(!empty());

            std::swap(_c[0], _c[size() - 1]);
            _c.pop_back();

            AdjustDown(0, size() - 1);
        }

    private:
        Container _c;
        Compare _comp;
    };
}

總結(jié)

到此這篇關(guān)于C++中priority_queue與仿函數(shù)實現(xiàn)方法的文章就介紹到這了,更多相關(guān)C++ priority_queue與仿函數(shù)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: