`std::unordered_map` 不复制关键数据

Question

我有一个 Person class，它有一个 name 属性 (std::string).

我想创建一个查找 -table，一个 std::unordered_map，这样我就可以通过他们的名字找到一个 Person。但是，给定一个Person，我也希望能够得到他们的名字。

这需要存储 name 两次 - 一次作为地图的键，一次在 person 对象中，如下面的代码所示。

因为我有很多 Person 一次加载到内存中，我不希望两次存储它们的名字的开销。

我试过使用 references/pointers 代替 Person class 中的键，但这会产生问题，因为地图在修改时似乎会重新排列其数据，并且引用无效。

我也尝试过使用 std::unordered_set，但这意味着我每次要执行查找时都需要构建一个完整的 Person 对象。

有没有办法让无序map的key和value共享同一个数据？

#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

您可以使用 Boost.Multi-index 来达到这个目的。虽然这个库有一个学习曲线，但你会发现它非常有用，非常快。所以对于你的情况：

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;

现在您可以将它用作带有字符串键的散列集：

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

这可能看起来有点矫枉过正，但是当您开始向 class 添加更多成员时，您将看到这个库的全部功能 Person 您将需要提供不同的索引来访问他们由那个成员。假设您添加了一个 phone 数字，该数字也是唯一的（方法 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;

注意：您可以将存储的数据更改为共享指针，而不是按值存储，当然，为了简单起见，我只是省略了它。

Answer 2

如果您的 "persons" 从未被复制或移动，并且它们的名称也从未被复制或移动，您可以使用指向 string 而不是 string 的指针作为您的密钥。这需要使用自定义 hash 和 equal 函子。

struct myhash
{
    unsigned operator()(std::string* s) const
    {
        return std::hash<std::string>()(*s);
    }
};

struct myequal
{
    unsigned operator()(std::string* s1, std::string* s2) const
    {
        return *s1 == *s2;
    }
};
...
auto my_set = std::unordered_map<std::string*, std::shared_ptr<Person>, myhash, myequal>();

这也使查找变得有点复杂：您必须查找指向 string.

的指针

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

这里不可能让字符串 bob 内联，因为您的代码必须获得指向它的指针。

Answer 3

使用 std::set，您可以使用 transparent 比较器（std::unordered_set 似乎不支持 :/ ）：

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();
    }

};

然后使用它：

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

Answer 4

如果您真的在记忆力方面很吃力，您应该使用 boost::flat_set。它的内存开销非常低，唯一的问题是如果你更新你的一组人，它的性能会很糟糕。如果你只是创建并且从不修改它，性能会比 unordered_ 差，但并不可怕。

如果你坚持使用 unordered_map 我认为你需要使用 unordered_multiset 因为我认为让你的 class 只使用一个字段来确定是否有 2 个实例是没有意义的平等的。这是可能的，但是very ugly，你需要定义你自己的散列函数和相等函数。

另一个更简单但更容易出错的解决方案是像这样使用散列作为键：

#include <string>
#include <iostream>
#include <unordered_map>

class Person {

public:
    Person(const std::string& name, const int age) : name_(name), age_(age) {}
public:
    const std::string& name() const { return name_; }
    int age() const { return age_; }
private:
    std::string name_;
    int age_;
};

int main()
{
    Person p1("Joe", 11), p2("Jane", 22), p3("James", 33), p4("Joe", 44);
    std::unordered_multimap<size_t, Person> persons{ {std::hash<std::string>()(p1.name()), p1}, {std::hash<std::string>()(p2.name()), p2},{std::hash<std::string>()(p3.name()), p3}, {std::hash<std::string>()(p4.name()), p4} };
    auto potential_joes = persons.equal_range(std::hash<std::string>()("Joe"));
    for (auto it = potential_joes.first; it != potential_joes.second; ++it) {
        if (it->second.name() == "Joe") {
            std::cout << it->second.name() << " is " << it->second.age() << " years old" << std::endl;
        }
    }
}

只有当您的字符串很长，您实际测量了内存使用情况并且您对编写自定义比较器感到不舒服时，我才会使用它。正如您从代码中看到的那样，您自己重新实现了很多 unordred_map 逻辑，很容易搞砸。

重要说明 如果您的密钥取决于您在地图中的值，您必须确保不要修改值。因此，例如在我发布的代码中，您可能应该创建成员 name_ const 并评论为什么它是 const.

`std::unordered_map` 不复制关键数据

`std::unordered_map` without duplicating key data

c++

unordered-map

stdmap

c++11