多查找集

Question

我需要一個數據結構，我不確定要選什麼。基本上，我的需求類似於std::set，除了我需要根據多個不同的比較器同時查找相同的數據。

現在我決定去找一些kludge-一std::map<float, std::unordered_set<T>>然後std::unordered_map<T, std::unordered_set<T>*>。這應該允許O（log N）查找float和O（1）查找/刪除T。

有沒有更好的數據結構可供使用？這有「黑客」寫在它的全部。

順便說一句，此代碼是相當性能的關鍵，所以快速的東西將非常感激。

編輯：我一直在戳與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

你可以嘗試的一件事是在你的元素unordered_set和shared_ptr中使用weak_ptr。當你破壞元素時，NULL weak_ptr被留下。您需要一些方法來垃圾收集您的容器中的NULL weak_ptr條目，但該成本可能很容易攤銷。這樣，你可以避免需要使用第二個索引。