如何使用STL PriorityQueue 优先队列
相信大家对优先队列不陌生。STL提供的PriorityQueue属于容器适配器,底层默认用vector容器来实现。实现原理是在用vector里构造一个Heap(堆),堆一般是用数组来储存的。下面是一个使用有限队列的例子,用来实现一个错误关联器,总是把优先级高的错误放在最前面。#include #include #include #include // this cl
相信大家对优先队列不陌生。
STL提供的PriorityQueue属于容器适配器,底层默认用vector容器来实现。实现原理是在用vector里构造一个
Heap(堆),堆一般是用数组来储存的。
下面是一个使用有限队列的例子,用来实现一个错误关联器,总是把优先级高的错误放在最前面。
#include <string>
#include <queue>
#include <ostream>
#include <stdexcept>
// this class is implemented as inline.
// since it is just very simple
class Error
{
public:
Error(const std::string& e, int p) : errormessage(e), priority(p) {}
std::string GetErrorMessage() const { return errormessage;}
int GetPriority() const { return priority;}
void SetErrorMessage(const std::string& s) { errormessage = s;}
void SetPriority(int p) { priority = p; }
friend bool operator<(const Error& lhs, const Error& rhs);
friend std::ostream& operator<<(std::ostream& out, const Error& e);
private:
std::string errormessage;
int priority;
};
class ErrorCorrector
{
public:
ErrorCorrector() {};
// add an error to the queue
void AddError(const Error& e);
// get error
Error GetError();
bool IsEmpty() const { return mErrors.empty();}
private:
std::priority_queue<Error> mErrors;
ErrorCorrector(const ErrorCorrector&);
ErrorCorrector& operator=(const ErrorCorrector&);
};
实现:
#include "PriorityError.h"
std::ostream& operator<<(std::ostream& out, const Error& e )
{
out << e.priority << ": " << e.errormessage << std::endl;
return out;
}
void ErrorCorrector::AddError( const Error& e )
{
mErrors.push(e);
}
Error ErrorCorrector::GetError()
{
if (mErrors.empty())
{
throw std::out_of_range("the error is not empty");
}
Error e = mErrors.top();
mErrors.pop();
return e;
}
bool operator<( const Error& lhs, const Error& rhs )
{
return lhs.priority < rhs.priority;
}
更多推荐
所有评论(0)