Associative array with multiple keys types, possible?

Question

Ive got a large bunch of objects (potentially 1000's) which I need to store in a container. I need to be able to find specific instances in two ways, either by its ID number (64bit unsigned int), or its name (std::string). Generally by ID will be the most common, however in some cases the name is known, but not the ID.

std::map can provide a single <-> value, however I'm not sure if having 2 sets of std::map containers, one for the Ids and another for the strings is the best approach here.

EDIT - REVISED code and error:

Ok, I figured i'd give the multi index a try since I have boost anyways, however I can't seem to get it to compile even though I've done it exactly the same as in the documentation as far as I can tell :(

test code:

namespace common
{
    class MyBaseClass
    {
    public:
        typedef boost::uint64_t Id;

        //name and id are constant, at least for the period im intrested in
        //when I want it in the container...
        const std::string &getName()const{return name;}
        Id getId()const{return id;}

        ...other stuff...
    };
}

class MyClass : public common::MyBaseClass
{
    ...other stuff...
};

typedef boost::multi_index_container
<
    MyClass*,
    boost::indexed_by
    <
        boost::ordered_unique<boost::const_mem_fun<MyBaseClass, MyBaseClass::Id,    &MyBaseClass::getId  > >,
        boost::ordered_unique<boost::const_mem_fun<MyBaseClass, const std::string&, &MyBaseClass::getName> >
    >
>MyClassList;

and your average boost template error...

c:\lib\c++\boost\boost\aligned_storage.hpp(69) : error C2872: 'detail' : ambiguous symbol
could be 'boost::detail'
or 'boost::multi_index::detail'
c:\lib\c++\boost\boost\multi_index\detail\index_node_base.hpp(42) : see reference to class template instantiation 'boost::aligned_storage' being compiled
with
[
size_=4,
alignment_=4
]
c:\lib\c++\boost\boost\multi_index\detail\index_node_base.hpp(47) : see reference to class template instantiation 'boost::multi_index::detail::pod_value_holder' being compiled
with
[
Value=MyClass *
]
c:\lib\c++\boost\boost\multi_index\detail\ord_index_node.hpp(582) : see reference to class template instantiation 'boost::multi_index::detail::index_node_base' being compiled
with
[
Value=MyClass *,
Allocator=std::allocator
]
c:\lib\c++\boost\boost\multi_index\ordered_index.hpp(137) : see reference to class template instantiation 'boost::multi_index::detail::ordered_index_node' being compiled
with
[
Super=boost::multi_index::detail::index_node_base>
]
c:\lib\c++\boost\boost\multi_index\ordered_index.hpp(119) : see reference to class template instantiation 'boost::multi_index::detail::ordered_index' being compiled
with
[
KeyFromValue=boost::multi_index::const_mem_fun,
Compare=std::less,std::allocator>>,
SuperMeta=boost::multi_index::detail::nth_layer<2,MyClass *,boost::multi_index::indexed_by>,boost::multi_index::ordered_unique>>,std::allocator>,
TagList=boost::mpl::vector0,
Category=boost::multi_index::detail::ordered_unique_tag
]
c:\lib\c++\boost\boost\multi_index_container.hpp(86) : see reference to class template instantiation 'boost::multi_index::detail::ordered_index' being compiled
with
[
KeyFromValue=boost::multi_index::const_mem_fun,
Compare=std::less,
SuperMeta=boost::multi_index::detail::nth_layer<1,MyClass *,boost::multi_index::indexed_by>,boost::multi_index::ordered_unique>>,std::allocator>,
TagList=boost::mpl::vector0,
Category=boost::multi_index::detail::ordered_unique_tag
]
c:\projects\bad_angle_studios\brak3\trunk\source\source\server\MyClass.cpp(18) : see reference to class template instantiation 'boost::multi_index::multi_index_container' being compiled
with
[
Value=MyClass *,
IndexSpecifierList=boost::multi_index::indexed_by>,boost::multi_index::ordered_unique>>
]
c:\lib\c++\boost\boost\aligned_storage.hpp(53) : error C2872: 'detail' : ambiguous symbol
could be 'boost::detail'
or 'boost::multi_index::detail'
c:\lib\c++\boost\boost\aligned_storage.hpp(56) : see reference to class template instantiation 'boost::detail::aligned_storage::aligned_storage_imp::data_t' being compiled
with
[
size_=4,
alignment_=4
]
c:\lib\c++\boost\boost\aligned_storage.hpp(69) : see reference to class template instantiation 'boost::detail::aligned_storage::aligned_storage_imp' being compiled
with
[
size_=4,
alignment_=4
]
c:\lib\c++\boost\boost\aligned_storage.hpp(73) : error C2872: 'detail' : ambiguous symbol
could be 'boost::detail'
or 'boost::multi_index::detail'
c:\projects\bad_angle_studios\brak3\trunk\source\source\server\MyClass.cpp(44) : error C2676: binary '[' : 'MyClassList' does not define this operator or a conversion to a type acceptable to the predefined operator

Answer 1

boost::multi_index is the answer to your problem. See there for more information on how to use it.

Answer 2

The approach of two maps (one with ID as key, and the second with name as key), seems good to me. It is simple to implement, and will work well.

I saw that other answers recommended boost libraries. If you already use boost in your project, then it could be a good solution. If you don't - I'm not sure it is worth adding boost to your project just for this simple case.

Answer 3

You could store the data in a std::vector and use the std::find algorithm to find your items. The find algorithm accepts different comparators, so just define one that matches ids and another that matches names.

The find algorithm is slower than std::map and std::set's find method, so if performance is a big concern then you're probably better off trading space for speed and either using 2 maps or using boost

edit, just had a thought. Store the data in a map, using the id as a key, as this is the common case. Then use the std::find algorithm and a predicate that matches on name for the uncommon case. That should reduce (but not remove)the performance issues

Answer 4

Here is another alternative to the above, which solution you pick depends on your needs. Grab SqlLite store the data about your objects in a database and run queries for them.

Answer 5

Fire Lancer, you're not qualifying Boost.MultiIndex names correctly, instead of for instance boost::indexed_by you've got to write boost::multi_index::indexed_by, etcetera.