使用unordered_map,其中Key是T的成员

Question

有没有什么好方法可以使用unordered_map,以便您可以在常量时间(平均大小写)中通过成员变量访问对象？以下示例具有此功能,但要求将每个名称Person重复为Key:

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

class Person {
 public:
  Person() : name_("") {}
  Person(const std::string& name) : name_(name) {}
  std::string getName() const { return name_; }
  void kill() const { std::cout << name_ << " is dead!" << std::endl; }
 private:
  std::string name_;
};

int main(int argc, const char* argv[]) {
  Person p1("dave");
  Person p2("bob");

  std::unordered_map<std::string, Person> map = {
    {p1.getName(), p1}, // Duplicating the
    {p2.getName(), p2}  // keys here
  };

  map["dave"].kill();
  return 0;
}

我在想,不管怎么说,它value_type需要是Person自己的,而不是a,pair<string, Person>并且unordered_map需要知道Person::getName在散列和访问对象时使用它们.

理想的解决方案将允许我设置unordered_map(或者unordered_set如果它更适合作业)知道Person::getName用于获取每个对象的密钥.然后我可以简单地通过给出对​​象来插入它们(并且没有键因为它知道如何获取键)并通过给出比较等于返回值的键来访问它们Person::getName.

有点像:

// Pseudocode
std::unordered_map<Person, Person::getName> map = {p1, p2};
map["dave"].kill();

那么可以实例化一个unordered_map可以巧妙地做到这一点的模板类吗？

Answer 1

如果您不反对使用Boost，那么Boost.MultiIndex会使这变得非常简单，而不会增加任何不必要的低效率。下面是一个有效创建以 的值为键的对象unordered_set的示例：PersonPerson::getName()

#include <string>
#include <iostream>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/indexed_by.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/mem_fun.hpp>

namespace bmi = boost::multi_index;

struct Person
{
    Person() = default;
    Person(std::string const& name) : name_(name) { }
    std::string const& getName() const noexcept { return name_; }
    void kill() const { std::cout << name_ << " is dead!\n"; }

private:
    std::string name_;
};

typedef bmi::multi_index_container<
    Person,
    bmi::indexed_by<
        bmi::hashed_unique<
            bmi::const_mem_fun<Person, std::string const&, &Person::getName>
        >
    >
> PersonUnorderedSet;

int main()
{
    Person p1("dave");
    Person p2("bob");

    PersonUnorderedSet set;
    set.insert(p1);
    set.insert(p2);

    set.find("dave")->kill();

    // for exposition, find is actually returning an iterator
    PersonUnorderedSet::const_iterator iter = set.find("bob");
    if (iter != set.end())
        iter->kill();

    // set semantics -- newly_added is false here, because
    // the container already contains a Person named 'dave'
    bool const newly_added = set.insert(Person("dave")).second;
}

（请注意，为了提高效率，我将 的签名更改Person::getName()为按引用返回const，而不是按值返回，但并不严格要求进行更改。）

应该注意的是，C++14 对透明比较器的支持将允许您在此处使用std::unordered_set<Person>而不需要 Boost。