c++ - 不是优先级队列的已排序容器

Question

我们需要一个容器，在添加新元素时保持其元素按元素的优先级排序，它能够检索给定 id 的元素。

（优先级队列的问题在于它不能让您根据 id 而不是优先级来检索元素）

谢谢

Answer 1

boost 多索引容器使您能够获得优先级排序视图和 ID 排序视图。

一个小例子：

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>
#include <iostream>
#include <vector>
#include <cstddef>
#include <iterator>

struct elem {
  std::size_t id;
  int priority;
};

int main()
{
  using namespace boost::multi_index;

  typedef multi_index_container<
  elem,
  indexed_by<
    ordered_unique<member<elem,std::size_t,&elem::id> >,
    ordered_non_unique<member<elem,int,&elem::priority> >
    >
  > elem_container;


  // just for show
  std::vector<elem> elems = 
    {{0, 25}, 
     {1, 10}, 
     {2, 100}, 
     {3, 6}
    };
  elem_container elemc(begin(elems), end(elems));
  // by id
  std::cout << "By ID: " << std::endl;
  for(auto& x : elemc.get<0>()) { 
    std::cout << "id: " << x.id << "priority: " << x.priority << std::endl;
  }

  // by priority
  std::cout << "By Priority: " << std::endl;
  for(auto& x : elemc.get<1>()) { 
    std::cout << "id: " << x.id << "priority: " << x.priority << std::endl;
  }
  return 0;
}