Multiple lookup set

Question

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.

Answer 1

multi_index was the winner. Unfortunately dirkgently posted as comment, not answer, or I'd accept it.

Answer 2

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.