Garanzie sull'unicità della chiave in std :: unordered_multimap

Question

Mi chiedevo l'unicità di un oggetto chiave all'interno di un std::unordered_multimap quando si tratta dell'iterazione.

Cercherò di spiegare il punto: ho bisogno di associare alcuni dati con il tipo di chiave nella mappa, questi dati non dovrebbe essere considerata in Hash o KeyEqual elementi, ma ho bisogno di evitare di memorizzare una mappa separata con (per scopi di ottimizzazione).

Quindi il codice associato con la mia idea è la seguente:

struct Key { 
    void* data; 
    mutable bool attribute; 

    Key(void* data) : data(data), attribute(false) { } 
    bool operator==(const Key& other) const { 
    return data == other.data; 
    } 
}; 

struct KeyHash { 
    size_t operator()(const Key& key) const { 
    return std::hash<void*>()(key.data); 
    } 
}; 

class Foo { 
public: 
    int i; 
    Foo(int i) : i(i) { } 
}; 

std::unordered_multimap<Key, Foo, KeyHash> map; 

Il problema deriva dal fatto che, anche se questo funziona bene, non ci sono garanzie circa il fatto che la chiave recuperata come il primo elemento di la mappatura std::pair<const Key, Foo> in un singolo elemento è sempre la stessa. Essendo un pair di const Key suona come che ogni elemento della mappa ha la sua copia della chiave per valore, in modo che se faccio

void* target = new int(); 
map.emplace(std::make_pair(target, Foo(1))); 
map.emplace(std::make_pair(target, Foo(2))); 


auto pit = map.equal_range(target); 
pit.first->first.attribute = true; 
std::cout << std::boolalpha << (++pit.first)->first.attribute << endl; 

Questo produce false che si conferma quello che stavo pensando. Quindi c'è davvero molto spazio sprecato per memorizzare le chiavi se si hanno più valori con la stessa chiave (che è ciò che si desidera dal momento che si utilizza uno std::unordered_map).

non vedo altra soluzione, piuttosto che qualcosa di simile

struct Value 
{ 
    std::vector<Foo> foos; 
    bool attribute; 
}; 

std::unordered_map<void*, Value> map; 

che mi permette di accoppiare l'attributo con la chiave, ma rende tutto meno pulito dal momento che richiede di lavorare con due livelli di iteratori.

Ci sono altre soluzioni che non vedo?

Answer 1

23.5.5.1 Classe panoramica unordered_multimap template [unord.multimap.overview]

1 Un unordered_multimap è un contenitore associativo non ordinata che supporta le chiavi equivalenti (un'istanza di unordered_multimap può contenere più copie di ciascun valore della chiave) e che associa i valori di un altro tipo mappato con tipo con le chiavi. La classe unordered_multimap supporta gli iteratori forward.

Un unordered_multimap può contenere più copie della chiave, se vuoi una sola copia della chiave quindi potenzialmente potrebbe essere più appropriato un unordered_map<K, vector<V>>.