`std::unordered_map` without duplicating key data

Question

I have a Person class, which has a name property (std::string).

I want to create a lookup-table, a std::unordered_map, so I can find a Person by their name. However, given a Person, I also want to be able to get their name.

This necessitates storing the name twice - once as the key of the map, and once inside the person object, as shown in my code below.

Since I have many Persons loaded into memory at once, I don't want the overhead of storing their names twice.

I've tried using references/pointers to the keys instead inside the Person class, but this creates problems as the map seems to reshuffle its data when it is modified, and the references become invalid.

I've also tried using std::unordered_set, but this means I need to construct a whole Person object every time I want to perform a lookup.

Is there any way for the key and value of a unordered map to share the same data?

#include <iostream>
#include <unordered_map>


class Person
{
    private:
        const std::string _name;

    public:
        Person( const std::string& name ) : _name( name )
        {
        }


        const std::string& get_name() const
        {
            return _name;
        }
};


int main()
{
    auto my_set = std::unordered_map<std::string, std::shared_ptr<Person>>();

    my_set.insert( { "alice", std::shared_ptr<Person>( new Person( "alice" )) } );
    my_set.insert( { "bob", std::shared_ptr<Person>( new Person( "bob" )) } );
    my_set.insert( { "charlie", std::shared_ptr<Person>( new Person( "charlie" )) } );

    std::cout << my_set.find( "bob" )->second->get_name() << std::endl;

    return 0;
}

Answer 1

You can use Boost.Multi-index for this purpose. Though there is a learning curve for this library you will find it very usable very fast. So for your case:

namespace mpi = boost::multi_index;
boost::multi_index_container<
        Person,
        mpi::indexed_by<
           mpi::hashed_unique< mpi::const_mem_fun< Person, const std::string &, &Person::get_name > >
        >
> my_set;

Now you can use it as hashed set with a string key:

auto f = my_set.find( "bob" );
if( f != my_set.end() )
    std::cout << f->get_name() << std::endl; 

This may look like a bit overkill, but you will see full power of this library when you start to add more members to the class Person you will need to provide different index to access them by that member. Let's say you added a phone number which is also unique (method const std::string &get_phone() const):

boost::multi_index_container<
        Person,
        mpi::indexed_by<
           mpi::hashed_unique< mpi::const_mem_fun< Person, const std::string &, &Person::get_name >,
           mpi::hashed_unique< mpi::const_mem_fun< Person, const std::string &, &Person::get_phone >>
        >
> my_set;

// lookup by phone:

const auto &idx = boost::get<1>( my_set );
auto f = idx.find( "1234567890" );
if( f != my_set.end() )
    std::cout << f->get_name() << std::endl; 

Note: you can change stored data as a shared pointer instead of storing by value of course, I just omitted that for example simplicity.

Answer 2

With std::set, you might use transparent comparer (std::unordered_set doesn't seems to support that :/ ):

struct LessPerson
{
    using is_transparent = void; // enable "transparent" comparer

    template <typename T1, typename T2>
    bool operator ()(const T1& t1, const T2& t2) const
    {
        // Compare only "name".
        return toString(t1) < toString(t2);
    }

    // trivial one
    const std::string& toString(const std::string& s) const
    {
        return s;
    }

    // the one why we create the class
    const std::string& toString(const Person& p) const
    {
        return p.get_name();
    }

    // A tricky one to handle dereference of (smart) pointers.
    template <typename T,
              std::enable_if_t<std::is_same<Person, std::decay_t<decltype(*std::declval<T>())>>::value>* = nullptr>
    const std::string& toString(const T& p) const
    {
        return (*p).get_name();
    }

};

And then use it:

auto my_set = std::set<std::shared_ptr<Person>, LessPerson>();

my_set.insert( { std::make_shared<Person>("alice") } );
my_set.insert( { std::make_shared<Person>("bob") } );
my_set.insert( { std::make_shared<Person>("charlie") } );

auto it = my_set.find("bob"); // search using "bob" directly without creating a new Person

Demo