stable priority queue

STL priority queue를 써보려고 찾아보다 발견한 정보.

 

 

stable priority queue

STL의 priority_queue 사용시 동일한 prirority를 갖는 원소들은  push한 순서데로 나오지 않습니다. 

이를 push한 순서데로 보장하기 위한 방법에 대한 내용을 일부 가져온 것으로 아래 사이트(원문)를 필히 봐야 합니다.

 

원문 : http://www.s34.co.jp/cpptechdoc/article/stable_pq/

번역 : http://jacking.tistory.com/320

 

 

증상 확인

눈으로 확인하기 위해 위의 글데로 따라해 봤습니다.

 

[ main.cpp ]

#include <iostream>
#include <tchar.h>
#include <queue>

using namespace std;

typedef struct _QueueData
{
	unsigned int priority;
	char* data;
	unsigned int dataLen;
	_QueueData() : priority(0), data(0), dataLen(0) {}
}QueueData, *PQueueData;

struct QueueDataCompareDESC
{
	bool operator()(const QueueData& a, const QueueData& b)
	{
		return a.priority < b.priority;
	}
};

struct QueueDataCompareASC
{
	bool operator()(const QueueData& a, const QueueData& b)
	{
		return a.priority > b.priority;
	}
};

int main(void)
{
	priority_queue<QueueData, vector<QueueData>, QueueDataCompareASC> que;
	//priority_queue<QueueData, vector<QueueData>, greater<vector<QueueData>::value_type> > que;

	for (int i = 0; i < 10; i++)
	{
		QueueData qData;
		qData.priority = i / 4;
		qData.data = new char(65 + i); //A, B, C, D.. 알파벳 순서데로 push
		que.push(qData);
	}

	while (!que.empty())
	{
		char c = *que.top().data;
		cout << c << ", p: " << que.top().priority << endl;
		que.pop();
	}

	return 0;
}​

[ 결과 ]

data: A, priority: 0 data: C, priority: 0 data: B, priority: 0 data: D, priority: 0 data: G, priority: 1 data: F, priority: 1 data: E, priority: 1 data: H, priority: 1 data: I, priority: 2 data: J, priority: 2 계속하려면 아무 키나 누르십시오 . . .

A, B, C, D .. 순으로 넣었는데 A, C, B, D .. 이런식으로 나옵니다.

우선순위(priority)는  보장되나 진짜 push한 순서데로는 안나옵니다.

 

 

 

 

stable_priority_queue 따라해보기

원문의 소스데로 바꿔봤습니다.

 

[ stable_priority_queue.h ]

#include <algorithm>
#include <iterator>
#include <functional>

template <class T, class Container = std::deque<T>, class Compare = std::less<Container::value_type> >
class stable_priority_queue
{
public:
	typedef Container container_type;
	typedef typename Container::value_type value_type;
	typedef typename Container::size_type size_type;

protected:
	Container c;
	Compare comp;

private:
	template<class InputIterator>
	void push(InputIterator first, InputIterator last)
	{
		for (; first != last; ++first) push(*first);
	}

public:
	explicit stable_priority_queue(const Compare& pp = Compare(), const Container& cc = Container())
		: comp(pp)
	{
		push(cc.begin(), cc.end());
	}

	template <class InputIterator>
	stable_priority_queue(InputIterator first, InputIterator last, const Compare& pp = Compare())
		: comp(pp)
	{
		push(first, last);
	}

	bool empty() const { return c.empty(); }
	size_type size() const { return c.size(); }
	const value_type& top() const { return c.back(); }
	void pop() { c.pop_back(); }

	void push(const value_type& x)
	{
		c.insert(std::lower_bound(c.begin(), c.end(), x, comp), x);
	}
};​

[ main.cpp ] 

#include <iostream>
#include <vector>
using namespace std;

#include "stable_priority_queue.h"

typedef struct _QueueData
{
 unsigned int priority;
 char* data;
 unsigned int dataLen;
 _QueueData() : priority(0), data(0), dataLen(0) {}
}QueueData, *PQueueData;

struct QueueDataCompareDESC
{
 bool operator()(const QueueData& a, const QueueData& b)
 {
 return a.priority < b.priority;
 }
};

struct QueueDataCompareASC
{
 bool operator()(const QueueData& a, const QueueData& b)
 {
 return a.priority > b.priority;
 }
};


int main() {
 stable_priority_queue<QueueData, vector<QueueData>, QueueDataCompareASC> que;
 //priority_queue<QueueData, vector<QueueData>, greater<vector<QueueData>::value_type> > que;

 for (int i=0; i<10; i++)
 {
 QueueData qData;
 qData.priority = i/4;
 qData.data = new char(65+i); //A, B, C, D.. 알파벳 순서데로 push
 que.push(qData);
 }

 while(!que.empty())
 {
 cout << "data: " << *que.top().data << ", ";
 cout << "priority: " << que.top().priority << endl;
 que.pop();
 }
  return 0;
} 

(생각없이 vector를 넣어버림. deque을 해야 더 빠를텐데.. ==;)

[ 실행 결과 ]

data: A, priority : 0
data : B, priority : 0
data : C, priority : 0
data : D, priority : 0
data : E, priority : 1
data : F, priority : 1
data : G, priority : 1
data : H, priority : 1
data : I, priority : 2
data : J, priority : 2
계속하려면 아무 키나 누르십시오 . .​

A, B, C, D .. 순서데로 잘 나옵니다.

 

 

필요에 따라 성능 측정이나 thread-safty를 고려하면 되겠습니다.

원문을 쓰신 일본 분, 번역하신 분 모두 존경스럽다.