Использование unordered_map, где Key является членом T - PullRequest
Новая
       78

Использование unordered_map, где Key является членом T

5 голосов
/ 16 августа 2011

Есть ли хороший способ использовать unordered_map, чтобы вы могли получить доступ к объектам через переменную-член в постоянное время (в среднем)?Следующий пример имеет эту функциональность, но требует, чтобы имя каждого Person дублировалось в качестве ключа: 

#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,вместо pair<string, Person> и unordered_map нужно знать, чтобы использовать Person::getName при хешировании и доступе к объектам.

Идеальное решение позволило бы мне установить unordered_map (или unordered_setесли это более подходящее для работы), который знает, как использовать Person::getName, чтобы получить ключ каждого объекта.Тогда я мог бы вставить их, просто предоставив объект (а не ключ, потому что он знает, как получить ключ), и получить к ним доступ, указав ключи, которые будут сравниваться с возвращаемым значением Person::getName.

* 1017.* Что-то вроде: 
// Pseudocode
std::unordered_map<Person, Person::getName> map = {p1, p2};
map["dave"].kill();

Так возможно ли создать экземпляр шаблона класса unordered_map, который может сделать это аккуратно?

Ответы [ 3 ]

3 голосов
/ 17 августа 2011

Если вы не против использования Boost , то Boost.MultiIndex делает это чрезвычайно простым, не добавляя ненужной неэффективности.Вот пример, который эффективно создает unordered_set из Person объектов, которые имеют значение Person::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> здесь без необходимости повышения.

2 голосов
/ 16 августа 2011

Очевидное решение - просто дублировать ключевую часть и использовать std::unordered_map; для небольшого локального использования это самый простой и предпочтительное решение, но нет ничего, обеспечивающего инвариант key == mapped.key_part, что усложняет поддержку кода при вставки могут происходить в нескольких местах кода.

Если вы держите на карте указатели, а не значения, вы можете оберните карту, чтобы ключ был указателем на соответствующий поле в значении. Проблема с этим, конечно, в том, что это означает сохраняя указатели, а не значения.

Если вы не измените значения, как только они появятся на карте, вы можете просто использовать std::set, а не std::map, с соответствующим хешем и функция равенства. Если вы сделаете это, вам, вероятно, придется построить фиктивный Person объект для доступа к данным.

Если вы хотите изменить значения (конечно, за исключением ключа), тогда у вас есть проблема, что std::set предоставляет только const доступ к его члены. Вы можете обойти это, используя const_cast, но это ужасно. (И подвержен ошибкам; как убедиться, что фактическая ключевая часть не изменено.)

Ни одно из этих решений не является полностью удовлетворительным. В таком случае, как твой, где нет изменяемого доступа к ключевой части (имени), я бы, наверное, используйте одно из первых двух решений, обернув unordered_map в мой собственный класс, чтобы обеспечить сохранение инвариантов.

1 голос
/ 16 августа 2011

То, что вы ищете, это unordered_set, а не карта. Набор использует значение как ключ, так и значение.

Только не меняйте «ключевую» часть значения.

...