STL中priority_queue自定义类型使用和源码简单分析

priority_queue使用

这里说一下优先级队列的其他的用法,这里我们先看默认的究竟是建立大堆还是小堆?

#include <iostream>
#include <queue>

int main()
{
	int arr[] = { 10, 2, 1, 3, 5, 4, 0 };
	std::priority_queue<int> q;
	for (size_t i = 0; i < sizeof(arr)/sizeof(arr[0]); i++)
	{
		q.push(arr[i]);
	}
	while (!q.empty())
	{
		std::cout << q.top() << " ";
		q.pop();
	}
	return 0;
}

是大堆,那么我们应该如何让他建立成小堆呢?先来它他们的构造函数.

这个是C++98的,我们发现这里有两个,这里测试第一个,我们发现comp是一个对象,此时我们就想到了仿函数对象,那么是不是呢?直接测试.

#include <iostream>
#include <queue>
#include <vector>

int main()
{
	int arr[] = { 10, 2, 1, 3, 5, 4, 0 };
	std::priority_queue<int, std::vector<int>, std::less<int>> q;
	for (size_t i = 0; i < sizeof(arr)/sizeof(arr[0]); i++)
	{
		q.push(arr[i]);
	}
	while (!q.empty())
	{
		std::cout << q.top() << " ";
		q.pop();
	}
	return 0;
}

那么greater就是小根堆了,测试一下.

#include <iostream>
#include <queue>
#include <functional>

int main()
{
	int arr[] = { 10, 2, 1, 3, 5, 4, 0 };
	std::priority_queue<int, std::vector<int>, std::greater<int>> q;
	for (size_t i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		q.push(arr[i]);
	}
	while (!q.empty())
	{
		std::cout << q.top() << " ";
		q.pop();
	}
	return 0;
}

下面我们测试一下自定义类型的入堆操作,这里我们直接写出一个仿函数.

struct node
{
	int x;
	int y;
};

struct cmp
{
	bool operator()(const node& n1, const node& n2){
		return n1.x > n2.x;
	}
};
int main()
{
	node n1 = { 1, 2 };
	node n2 = { 2, 4 };
	node n3 = { 3, 4 };
	priority_queue<node, vector<node>, cmp>q;
	q.push(n1);
	q.push(n2);
	q.push(n3);
	
	return 0;
}

如果我们要是不想写仿函数,那么我们在结构体里面重载<操作符,看大家的喜好吧.

struct node
{
	int x;
	int y;
	bool operator<(const node& n) const
	{
		return x > n.x; // 这里可以控制是大堆还是小堆
	}
};


int main()
{
	node n1 = { 1, 2 };
	node n2 = { 2, 4 };
	node n3 = { 3, 4 };
	priority_queue<node>q;
	q.push(n1);
	q.push(n2);
	q.push(n3);

	return 0;
}

priority_queue源码

这里我们简单的分析一下源码,主要是加深一下印象.

template <class T, class Sequence = vector<T>, 
          class Compare = less<typename Sequence::value_type> >
class  priority_queue {
public:
  typedef typename Sequence::value_type value_type;
  typedef typename Sequence::size_type size_type;
  typedef typename Sequence::reference reference;
  typedef typename Sequence::const_reference const_reference;
protected:
  Sequence c;
  Compare comp;
public:
  priority_queue() : c() {}
  explicit priority_queue(const Compare& x) :  c(), comp(x) {}
    
  void push(const value_type& x) {
    __STL_TRY {
      c.push_back(x); 
      push_heap(c.begin(), c.end(), comp);
    }
    __STL_UNWIND(c.clear());
  }
};

先来得到第一个结论

试一下上面我们说的,新的构造方式,不过我们很少用.

struct node
{
	int x;
	int y;
};

struct cmp
{
	bool operator()(const node& n1, const node& n2){
		return n1.x > n2.x;
	}
	cmp(const cmp& c)
	{

	}
	cmp()
	{

	}
};
int main()
{
	node n1 = { 1, 2 };
	node n2 = { 2, 4 };
	node n3 = { 3, 4 };
	cmp c;
	priority_queue<node, vector<node>, cmp> q(c);
	q.push(n1);
	q.push(n2);
	q.push(n3);

	return 0;
}

下面我们来谈当我们数据进入数组的时候,我们调整堆的操作,这里不做具体的分析,就谈为何我们的重载了<就不用写仿函数了,应该是这个函数,我们直接来分析一下吧.

template <class RandomAccessIterator, class Distance, class T, class Compare>
void __push_heap(RandomAccessIterator first, Distance holeIndex,
                 Distance topIndex, T value, Compare comp) {
  Distance parent = (holeIndex - 1) / 2;
  while (holeIndex > topIndex && comp(*(first + parent), value)) {
    *(first + holeIndex) = *(first + parent);
    holeIndex = parent;
    parent = (holeIndex - 1) / 2;
  }
  *(first + holeIndex) = value;
}

首先我们调用的是默认的无参构造函数,此时我们的Compare的实际类型是less\<Node\>,后面我们使用比较的,那么此时我们使用的就是less类型的,也就是我们的标准提供的仿函数.

struct node
{
	int x;
	int y;
	bool operator<(const node& n) const
	{
		return x > n.x; // 这里可以控制是大堆还是小堆
	}
};


int main()
{
	node n1 = { 1, 2 };
	node n2 = { 2, 4 };
	node n3 = { 3, 4 };
	priority_queue<node>q;
	q.push(n1);
	q.push(n2);
	q.push(n3);

	return 0;
}

下面就到了观察less类型了,我们这里继续进去看.

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

看到了吗.这里面重载了括号,看到函数体内存在一个<吗?这里调用的就是我们在Node中写的<重载操作符,这里就是我们为何是这样的.那么此时我们也可以重载>,看下面的操作.

struct node
{
	int x;
	int y;
	bool operator>(const node& n) const
	{
		return x > n.x; 
	}
};


int main()
{
	node n1 = { 1, 2 };
	node n2 = { 2, 4 };
	node n3 = { 3, 4 };
	priority_queue<node, vector<node>, greater<node>>q;
	q.push(n1);
	q.push(n2);
	q.push(n3);

	return 0;
}