Evitare la memorizzazione duplicata della chiave della mappa

Question

Diciamo che ho uno std::map<std::string, T> (o unordered_map) e voglio accedere alla chiave da un iteratore/riferimento/puntatore al contenuto.

C'è un modo per farlo senza avere due copie della chiave std::string (una di proprietà della mappa, una all'interno dell'oggetto contenuto)? Si può essere un riferimento all'altro?

Answer 1

Entrambi possono essere un riferimento allo stesso valore. Per esempio:

#include <stdio.h> 
#include <string> 
#include <map> 

struct xx { std::string mykey; int value; }; 

int main (int argc, char **argv) 
{ 
    std::string      key1("the-key"); 
    std::map<std::string, xx>  map; 

    map[key1].mykey = key1; 
    map[key1].value = 13; 

    std::string &lookup_key = map[key1].mykey; 

    printf("%d\n", map[lookup_key].value); 
} 

Answer 2

Perché non creare due oggetti:

std::set<std::string> wordSet; 
std::map<std::string*, T> yourMap; 

T deve contenere puntatore a std :: string, e yourMap ha bisogno di confronto personalizzato. Inoltre puoi avvolgere tutto questo in qualche classe.

Answer 3

Prenderesti in considerazione l'utilizzo di boost :: bimap? Di seguito è riportato un semplice esempio:

#include <boost/bimap.hpp> 
#include <string> 
struct Person 
{ 
    Person() 
    {} 
    Person(const std::string& f, const std::string& l, int a) : first(f), last(l), age(a) 
    {} 
    std::string first; 
    std::string last; 
    int age; 
}; 

bool operator <(const Person& lhs, const Person& rhs) 
{ 
    if(lhs.last < rhs.last) 
     return true; 
    return false; 
} 

std::ostream& operator << (std::ostream& os, const Person& p) 
{ 
    os << "First Name: " << p.first << " Last Name: " << p.last << " Age: " << p.age; 
    return os; 
} 

int main() 
{ 
    typedef boost::bimap<std::string, Person> people; 
    typedef people::value_type value; 

    people m; 
    m.insert(value("12345",Person("fred", "rabbit", 10))); 
    m.insert(value("67890",Person("benjamin", "bunny", 12))); 

    Person p = m.left.at("12345"); 
    std::cout << "Person with serial no. 12345 is: " << p << "\n"; 
    std::cout << "Serial number of " << p << " is: " << m.right.at(p) << "\n"; 

} 

Answer 4

Il motivo per cui l'hanno reso difficile è perché è pericoloso. È necessario GARANTIRE che nessuno dei membri std::string con chiave disattivata non cambierà mai valore, o l'intera mappa non sarà più valida. Interessante, la prima soluzione che mi viene in mente sembra follemente hacker, e sembra come UB, ma credo che scrupolosamente segua l'UB.

struct key_type { 
    mutable const char* ptr;  
}; 
bool operator<(const key_type& lhs, const key_type& rhs) 
{return strcmp(lhs.ptr, rhs.ptr)<0;} 

struct person { 
    std::string name; 
    int age; 
}; 
person& people_map_get(std::map<key_type, person>& map, const char* name) { 
    auto it = map.insert(name, person{name}).first; //grab, possibly insert 
    if->first.ptr = it->second.name.c_str(); //in case of insert, fix ptr 
    return it->second; 
} 
person& people_map_assign(std::map<key_type, person>& map, person p) { 
    auto pair = map.insert(name, p); //grab, possibly insert 
    auto it = pair.first;  
    if (pair.second == false) 
     it->second = std::move(p); 
    if->first.ptr = it->second.name.c_str(); //ptr probably invalidated, so update it 
    return it->second; 
} 

int main() { 
    std::map<key_type, person> people; 
    people_map_assign(people, person{"ted"}); 
    person frank = people_map_get(people, "frank"); 
} 

Come spero sia chiaro, questo è pazzo vicino al UB, e molto non è raccomandato. Fondamentalmente, durante un insert/find, i punti chiave sul tuo oggetto temporaneo o sulla stringa di input, e quindi non appena l'oggetto viene inserito/trovato, la chiave viene cambiata in modo che punti al valore contenuto nel membro della stringa, e fino a quando non fai mai nulla che invalida il valore di ritorno di .c_str() su qualsiasi oggetto person contenuto, tutto funziona a malapena. Credo.