c++ - 優先キューではないソートされたコンテナ

Question

新しい要素を追加するときに要素の優先度によって並べ替えられた要素を保持するコンテナーが必要です。これには、id が指定された要素を取得する機能があります。

(優先度キューの問題は、優先度ではなく ID に従って要素を取得できないことです)

ありがとう

Answer 1

ブースト マルチ インデックス コンテナーを使用すると、優先順位で並べ替えられたビューと 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;
}