Множественный набор поиска

Question

Мне нужна структура данных, и я не уверен, что выбрать. По сути, моя потребность похожа на std::set, за исключением того, что мне нужно искать в соответствии с несколькими разными компараторами по тем же данным одновременно.

Сейчас я решил пойти на какой-то kludge-a std::map<float, std::unordered_set<T>>, а затем std::unordered_map<T, std::unordered_set<T>*>. Это должно разрешить поиск O (log N) для поиска float и O (1) для T.

Есть ли какие-либо лучшие структуры данных для использования? Это «взломать» все написанное.

В целом, этот код является довольно высокой критичной производительностью, поэтому что-то быстрое было бы очень оценено.

Edit: Я совал с boost::multi_index и вот, что у меня до сих пор:

boost::multi_index_container< 
    NodeType, 
    boost::multi_index::indexed_by< 
     boost::multi_index::ordered_non_unique<boost::multi_index::identity<NodeType>, decltype(node_comparator)>, 
     boost::multi_index::hashed_unique<boost::multi_index::identity<NodeType>> 
    > 
> open_set(
    boost::make_tuple(node_comparator) 
); 

где node_comparator является in_scope лямбда. Но попытка скомпилировать его приводит к некоторым славным ошибкам.

1>d:\backups\code\boost_1_47_0\boost\multi_index\detail\node_type.hpp(56): error C2903: 'node_class' : symbol is neither a class template nor a function template 
1>   d:\backups\code\boost_1_47_0\boost\mpl\aux_\preprocessed\plain\apply_wrap.hpp(49) : see reference to class template instantiation 'boost::multi_index::detail::index_node_applier::apply<IndexSpecifierIterator,Super>' being compiled 
1>   with 
1>   [ 
1>    IndexSpecifierIterator=boost::mpl::v_iter<boost::mpl::vector2<boost::multi_index::ordered_non_unique<boost::multi_index::identity<NodeType>,Wide::Sim::`anonymous-namespace'::<lambda8>>,boost::multi_index::hashed_unique<boost::multi_index::identity<NodeType>>>,0>, 
1>    Super=boost::multi_index::detail::hashed_index_node<boost::multi_index::detail::index_node_base<NodeType,std::allocator<NodeType>>> 
1>   ] 
1>   d:\backups\code\boost_1_47_0\boost\mpl\aux_\preprocessed\plain\bind.hpp(207) : see reference to class template instantiation 'boost::mpl::apply_wrap2<F,T1,T2>' being compiled 
1>   with 
1>   [ 
1>    F=boost::multi_index::detail::index_node_applier, 
1>    T1=boost::mpl::v_iter<boost::mpl::vector2<boost::multi_index::ordered_non_unique<boost::multi_index::identity<NodeType>,Wide::Sim::`anonymous-namespace'::<lambda8>>,boost::multi_index::hashed_unique<boost::multi_index::identity<NodeType>>>,0>, 
1>    T2=boost::multi_index::detail::hashed_index_node<boost::multi_index::detail::index_node_base<NodeType,std::allocator<NodeType>>> 
1>   ] 
1>   d:\backups\code\boost_1_47_0\boost\mpl\aux_\preprocessed\plain\apply_wrap.hpp(49) : see reference to class template instantiation 'boost::mpl::bind2<F,T1,T2>::apply<U1,U2>' being compiled 
1>   with 
1>   [ 
1>    F=boost::multi_index::detail::index_node_applier, 
1>    T1=boost::mpl::_2, 
1>    T2=boost::mpl::_1, 
1>    U1=boost::multi_index::detail::hashed_index_node<boost::multi_index::detail::index_node_base<NodeType,std::allocator<NodeType>>>, 
1>    U2=boost::mpl::v_iter<boost::mpl::vector2<boost::multi_index::ordered_non_unique<boost::multi_index::identity<NodeType>,Wide::Sim::`anonymous-namespace'::<lambda8>>,boost::multi_index::hashed_unique<boost::multi_index::identity<NodeType>>>,0> 
1>   ] 
1>   d:\backups\code\boost_1_47_0\boost\mpl\aux_\preprocessed\plain\apply.hpp(63) : see reference to class template instantiation 'boost::mpl::apply_wrap2<F,T1,T2>' being compiled 
1>   with 
1>   [ 
1>    F=boost::mpl::bind2<boost::multi_index::detail::index_node_applier,boost::mpl::_2,boost::mpl::_1>, 
1>    T1=boost::multi_index::detail::hashed_index_node<boost::multi_index::detail::index_node_base<NodeType,std::allocator<NodeType>>>, 
1>    T2=boost::mpl::v_iter<boost::mpl::vector2<boost::multi_index::ordered_non_unique<boost::multi_index::identity<NodeType>,Wide::Sim::`anonymous-namespace'::<lambda8>>,boost::multi_index::hashed_unique<boost::multi_index::identity<NodeType>>>,0> 
1>   ] 
1>   d:\backups\code\boost_1_47_0\boost\mpl\aux_\preprocessed\plain\reverse_iter_fold_impl.hpp(82) : see reference to class template instantiation 'boost::mpl::apply2<F,T1,T2>' being compiled 
1>   with 
1>   [ 
1>    F=boost::mpl::bind2<boost::multi_index::detail::index_node_applier,boost::mpl::_2,boost::mpl::_1>, 
1>    T1=boost::multi_index::detail::hashed_index_node<boost::multi_index::detail::index_node_base<NodeType,std::allocator<NodeType>>>, 
1>    T2=boost::mpl::v_iter<boost::mpl::vector2<boost::multi_index::ordered_non_unique<boost::multi_index::identity<NodeType>,Wide::Sim::`anonymous-namespace'::<lambda8>>,boost::multi_index::hashed_unique<boost::multi_index::identity<NodeType>>>,0> 
1>   ] 
1>   d:\backups\code\boost_1_47_0\boost\mpl\reverse_iter_fold.hpp(43) : see reference to class template instantiation 'boost::mpl::aux::reverse_iter_fold_impl<N,First,Last,State,BackwardOp,ForwardOp>' being compiled 
1>   with 
1>   [ 
1>    N=2, 
1>    First=boost::mpl::v_iter<boost::mpl::vector2<boost::multi_index::ordered_non_unique<boost::multi_index::identity<NodeType>,Wide::Sim::`anonymous-namespace'::<lambda8>>,boost::multi_index::hashed_unique<boost::multi_index::identity<NodeType>>>,0>, 
1>    Last=boost::mpl::v_iter<boost::mpl::vector2<boost::multi_index::ordered_non_unique<boost::multi_index::identity<NodeType>,Wide::Sim::`anonymous-namespace'::<lambda8>>,boost::multi_index::hashed_unique<boost::multi_index::identity<NodeType>>>,2>, 
1>    State=boost::multi_index::detail::index_node_base<NodeType,std::allocator<NodeType>>, 
1>    BackwardOp=boost::mpl::bind2<boost::multi_index::detail::index_node_applier,boost::mpl::_2,boost::mpl::_1>, 
1>    ForwardOp=boost::mpl::protect<boost::mpl::arg<1>> 
1>   ] 
1>   d:\backups\code\boost_1_47_0\boost\multi_index\detail\node_type.hpp(70) : see reference to class template instantiation 'boost::mpl::reverse_iter_fold<Sequence,State,BackwardOp>' being compiled 
1>   with 
1>   [ 
1>    Sequence=boost::multi_index::indexed_by<boost::multi_index::ordered_non_unique<boost::multi_index::identity<NodeType>,Wide::Sim::`anonymous-namespace'::<lambda8>>,boost::multi_index::hashed_unique<boost::multi_index::identity<NodeType>>>, 
1>    State=boost::multi_index::detail::index_node_base<NodeType,std::allocator<NodeType>>, 
1>    BackwardOp=boost::mpl::bind2<boost::multi_index::detail::index_node_applier,boost::mpl::_2,boost::mpl::_1> 
1>   ] 
1>   d:\backups\code\boost_1_47_0\boost\multi_index_container.hpp(75) : see reference to class template instantiation 'boost::multi_index::detail::multi_index_node_type<Value,IndexSpecifierList,Allocator>' being compiled 
1>   with 
1>   [ 
1>    Value=NodeType, 
1>    IndexSpecifierList=boost::multi_index::indexed_by<boost::multi_index::ordered_non_unique<boost::multi_index::identity<NodeType>,Wide::Sim::`anonymous-namespace'::<lambda8>>,boost::multi_index::hashed_unique<boost::multi_index::identity<NodeType>>>, 
1>    Allocator=std::allocator<NodeType> 
1>   ] 
1>   c:\repo\render\render\sim\simcontext.cpp(264) : see reference to class template instantiation 'boost::multi_index::multi_index_container<Value,IndexSpecifierList>' being compiled 
1>   with 
1>   [ 
1>    Value=NodeType, 
1>    IndexSpecifierList=boost::multi_index::indexed_by<boost::multi_index::ordered_non_unique<boost::multi_index::identity<NodeType>,Wide::Sim::`anonymous-namespace'::<lambda8>>,boost::multi_index::hashed_unique<boost::multi_index::identity<NodeType>>> 
1>   ] 

Это только первый; их много, но я хорошо осведомлен о склонности Visual Studio к тому, чтобы одна ошибка вызывала 9999999 больше.

Answer 1

multi_index был победителем. К сожалению, dirkgently отправлен как комментарий, а не ответ, или я бы принял его.

Answer 2

Одна вещь, которую вы можете попробовать - использовать weak_ptr в своих unordered_set и shared_ptr для ваших элементов. Когда вы уничтожаете элемент, остается NULL weak_ptr. Вам нужно каким-то образом обработать мусор, чтобы собрать эти NULL weak_ptr записей в вашем контейнере, но эта стоимость, вероятно, легко амортизируется. Таким образом, вы избегаете необходимости использовать второй индекс вообще.