不重复键数据的`std::unordered_map`

Question

我有一个名为 Person 的类，其中包含一个 name 属性（std::string类型）。

我想要创建一个查找表，即 std::unordered_map，以便通过名字查找 Person。然而，如果已经有一个 Person 对象，我也想要能够获取他们的名字。

这需要将 name 存储两次 - 一次作为 map 的键，并将其存储在 person 对象内部，如下面的代码所示。

由于我一次加载了许多 Person，我不想再将他们的名字存储两次。

我尝试过在 Person 类中使用引用/指针来代替键，但是当 map 被修改时，它似乎会重排数据，从而使引用失效。

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

有没有办法使 unordered map 的键和值共享相同的数据？

#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;
}

- c z

---

你必须将 name 存储在 Person 中吗？ - Vittorio Romeo

@cz - 为什么不使用带有自定义哈希函数的无序集合呢？这似乎正是您想要的。 - StoryTeller - Unslander Monica

@MichaëlRoy，那么OP只需使用C++14的std::set，但这是不同的O(n)。 - Slava

除非人物对象很大，否则在这里使用unordered_set可能是最好的选择。它具有高效的空间利用率，仍然是O(1)的。默认构造一些字段，包括向量和字符串之类的东西，非常便宜。 - Nir Friedman

我猜你的指针并没有指向unordered_map内部，而是指向栈上的临时对象。你应该在insert()或emplace()之后才设置或更新它。 - Arne Vogel

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; 

这可能看起来有点过度，但当你开始给类Person添加更多成员时，你会看到这个库的全部功能，你需要提供不同的索引来访问它们。比如说，你添加了一个电话号码，它也是唯一的（方法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; 

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

- Slava

---

我真的不确定这个解决方案是否会比简单的unordered_map占用更少的空间。一个字符串通常有3-4个单词大小，因此这意味着multi_index的开销小于4N左右，其中N是条目数。 - Nir Friedman

虽然这对你来说可能看起来不太可能，但你不能没有任何理由就直接质疑问题。引用原话：“由于我一次加载了许多人到内存中，我不想存储他们的姓名两次带来额外的开销。”。 - Nir Friedman

@NirFriedman，您假设问题中的开销是指内存开销，但这并不一定正确，对吧？在这种方法中有多个开销，而内存只是其中之一。 - Slava

@NirFriedman 在 std::unordered_set 中创建一个 Person 实例进行查找，与创建的 Person 数量不成比例。为什么 OP 对此有所担忧？对于分配器来说，测量假设示例的内存消耗是没有意义的。 - Slava

@NirFriedman，my_set 的第一个定义（即只有一个索引的定义）占用的内存与 std::unordered_set<Person> 相同，因此，是内存高效的。 - Joaquín M López Muñoz

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，因为您的代码必须获取指向它的指针。

- anatolyg

---

你提到的缺陷可能可以通过简单地使用 reference_wrapper<const std::string> 作为键来消除。 - Nir Friedman

@Nir Friedman 不。使用 rvalue 的 .find 调用是不可能的，而当复制对象和引用时，reference_wrapper 只是被复制，对象被复制，wrapper 中的引用仍然指向原始字符串。 - DrSvanHay

@DrSvanHay 你说得对，它们删除了那个重载函数，但是自己编写符合正确行为的代码很容易。我完全不理解你的第二个观点，因为它在复制方面有与指针相同的行为，这也是答案所使用的。 - Nir Friedman

Answer 3

使用 std::set，您可以使用 透明 比较器（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

演示

- Jarod42

Answer 4

如果你真的在内存方面遇到了困难，你应该使用boost::flat_set。它的内存开销非常低，唯一的问题是，如果你更新了人员集合，性能会非常差。如果你只是创建而不修改它，性能比unordered_差，但并不糟糕。

如果你坚持使用unordered_map，我认为你需要使用unordered_multiset，因为我看不出让你的类只使用一个字段来确定两个实例是否相等有什么意义。这是可能的，但非常丑陋，你需要定义自己的哈希和相等函数。

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

#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。

- NoSenseEtAl