相信大家对优先队列不陌生。STL提供的PriorityQueue属于容器适配器，底层默认用vector容器来实现。实现原理是在用vector里构造一个Heap(堆)，堆一般是用数组来储存的。下面是一个使用有限队列的例子，用来实现一个错误关联器，总是把优先级高的错误放在最前面。#include #include #include #include // this class is implemented as inline.// since it is just very simpleclass 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 queuevoid AddError(const Error& e);// get errorError GetError();bool IsEmpty() const { return mErrors.empty();}private:std::priority_queue 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;}
