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

Question

Есть ли хороший способ использовать 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.

Что-то вдоль линий:

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

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

Answer 1

Если вы не против использования 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 -reference, а не по значению, ради эффективности, в но изменение не является строго обязательным.)

---

следует отметить, что поддержка 14 C++ для transparent comparators позволит использовать std::unordered_set<Person> здесь без необходимости Boost.

Answer 2

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

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

Answer 3

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

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

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

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

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