Multiple lookup set
-
04-06-2021 - |
题
I need a data structure, and I'm unsure of what to choose. Fundamentally, my need is similar to std::set
, except I need to look up according to multiple different comparators over the same data at the same time.
Right now I've decided to go for some kludge- a std::map<float, std::unordered_set<T>>
and then a std::unordered_map<T, std::unordered_set<T>*>
. This should permit O(log N) lookup for a float
and O(1) lookup/removal for a T
.
Are there any better data structures to use? This has "hack" written all over it.
As an aside, this code is fairly performance critical, so something fast would be very appreciated.
Edit: I've been poking with boost::multi_index
and here's what I've got so far:
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)
);
where node_comparator
is an in_scope lambda. But attempting to compile it results in some glorious errors.
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> ]
This is just the first; there are many, but I'm well aware of Visual Studio's propensity to let one error cause 9999999 more.
解决方案 2
multi_index
was the winner. Unfortunately dirkgently
posted as comment, not answer, or I'd accept it.
其他提示
One thing you can try is to use a weak_ptr
in your unordered_set
, and shared_ptr
for your elements. When you destruct the element, a NULL weak_ptr
is left behind. You would need some way to garbage collect those NULL weak_ptr
entries in your container, but that cost is likely easily amortized. This way, you avoid needing to use a second index at all.