我不知道 Boost 是否适合您,但我会查看 Boost Mutli Index。 http://www.boost.org/doc/libs/1_53_0/libs/multi_index/doc/index.html
您可以保留一个 in 优先级索引,以便您快速获取这些索引以及插入元素。对于 MRU/LRU 情况,我类似地使用了 boost mutli 索引。
#include <iostream>
#include <string>
#include <algorithm>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/optional.hpp>
struct bypriority{};
struct byseq{};
struct MyElement{
typedef int priority_type;
typedef std::string name_type;
name_type name;
priority_type priority;
MyElement(const name_type& name, const priority_type& priority):name(name),priority(priority){};
};
std::ostream& operator<<(std::ostream& os, const MyElement& e){
os << "Name: " << e.name << " Priority: " << e.priority;
return os;
}
using namespace boost;
using namespace boost::multi_index;
template<typename Element>
struct Container{
typedef multi_index_container<
Element,
indexed_by<
//sequenced
sequenced<tag<byseq> >,
//ordered by priority
ordered_non_unique<tag<bypriority>,member<Element,typename Element::priority_type,&Element::priority>, std::greater<typename Element::priority_type> >
>
> Elements;
void insert(const Element& e){
typename Elements::template index<byseq>::type& list_view = elements.get<byseq>();
list_view.push_back(e);
}
boost::optional<Element> peek() const{
boost::optional<Element> res;
typename Elements::template index<bypriority>::type::iterator it = elements.get<bypriority>().begin();
if(it != elements.get<bypriority>().end()){
res.reset(*it);
}
return res;
}
boost::optional<Element> pop() {
boost::optional<Element> res;
typename Elements::template index<bypriority>::type& priority_index = elements.get<bypriority>();
typename Elements::template index<bypriority>::type::iterator it = elements.get<bypriority>().begin();
if(it != elements.get<bypriority>().end()){
res.reset(*it);
priority_index.erase(it);
}
return res;
}
void print_in_order(std::ostream& os) const{
typedef typename Elements::template index<byseq>::type elements_by_sequence;
for(typename elements_by_sequence::iterator it = elements.get<0>().begin(); it != elements.get<0>().end(); it++){
os << *it << std::endl;
}
}
protected:
Elements elements;
};
using namespace std;
int main(int argc, char *argv[]) {
Container<MyElement> c;
c.insert(MyElement("Bob",10));
c.insert(MyElement("Alice",100));
c.insert(MyElement("Fred",20));
c.print_in_order(std::cout);
cout << endl << "Highest Priority is " << endl << *c.peek() << endl;
boost::optional<MyElement> alice = c.pop();
if(alice){
cout << "Popped results are " << *alice << endl;
}
cout << endl << "Now the contents are" << endl;
c.print_in_order(std::cout);
}
将输出:
Name: Bob Priority: 10
Name: Alice Priority: 100
Name: Fred Priority: 20
Highest Priority is
Name: Alice Priority: 100
Popped results are Name: Alice Priority: 100
Now the contents are
Name: Bob Priority: 10
Name: Fred Priority: 20