5

有什么好方法可以使用 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它自己，而不是 apair<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可以巧妙地做到这一点的模板类呢？

4

3 回答 3

3

如果您不反对使用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。

于 2011-08-16T23:43:42.580 回答
2

显而易见的解决方案是复制关键部分，然后使用 std::unordered_map; 对于小型的本地化使用，这是最简单和首选的解决方案，但没有强制执行不变量 key == mapped.key_part，当插入可能发生在代码中的多个不同位置时，这会使代码更难维护。

如果您在映射中保留指针而不是值，则可以包装映射以将键安排为指向值中相应字段的指针。当然，这样做的问题在于它意味着保留指针，而不是值。

如果值在映射中后不修改，则可以使用 std::set, 而不是std::map, 以及适当的哈希和相等函数。如果这样做，您可能必须构造一个虚拟Person对象才能访问数据。

如果您想修改值（当然不包括键），那么您将遇到std::set仅提供const对其成员的访问权限的问题。您可以使用 来解决这个问题const_cast，但它很难看。（而且容易出错；你如何确保实际的关键部分没有被修改。）

这些解决方案中没有一个是完全令人满意的。在像您这样的情况下，没有对关键部分（名称）的可变访问，我可能会使用前两个解决方案之一，将其包装unordered_map在我自己的类中以确保维护不变量。

于 2011-08-16T09:39:32.977 回答
1

您要查找的是unordered_set，而不是地图。该集合使用该值作为键和值。

只是不要更改值的“关键”部分。

于 2011-08-16T08:44:14.903 回答