Come evitare i valori duplicati nelle mappe utilizzando C++

Question

Sto cercando di scrivere un programma in cpp utilizzando le mappe ...

Il mio obiettivo è quello di evitare gli stessi valori ripetuti nelle mappe ..

se la chiave è lo stesso, possiamo usare le mappe per evitare le chiavi duplicate. Per consentire chiavi duplicate, usiamo multimaps

In caso se il valore è lo stesso, come possiamo evitare?

Il programma che ho scritto consente valori duplicati

typedef std::map<int, std::string> MyMap; 

int main() 
{ 
    MyMap map; 
    MyMap::iterator mpIter; 

    int key; 
    string value; 

    int count; 
    for(count = 0; count < 3;count++) 
    { 
     cin >> key; 
     cin >> value; 

     std::pair<MyMap::iterator, bool> res = map.insert(std::make_pair(key,value)); 
    } 

    for (mpIter=map.begin(); mpIter != map.end(); ++mpIter) 
     cout << " " << (*mpIter).second << endl; 
} 

Answer 1

Un modo per farlo è quello di mantenere un separato std::set dei valori. Quando si inserisce un valore in un set, viene restituito un valore std::pair<iterator, bool>. Il valore bool è true se il valore non era già nel set. Questo ti dice se è sicuro di anche mettere il valore sulla mappa.

Prima, però, è necessario assicurarsi che il key è unico perché la stessa key potrebbe già essere stato inserito con un diverso valore di:

typedef std::map<int, std::string> MyMap; 

int main() 
{ 
    MyMap map; 
    MyMap::iterator mpIter; 

    int key; 
    string value; 
    int count; 

    // keep track of values with a std::set 
    std::set<std::string> values; 

    for(count = 0; count < 3; count++) 
    { 
     cin >> key; 
     cin >> value; 

     auto found = map.find(key); 

     if(found != map.end()) // key already in map 
      continue; // don't add it again 

     // now try to add it to the set 
     // only add to the map if its value is not already in the set 
     if(values.insert(value).second) 
      map.insert(std::make_pair(key, value)); 
    } 

    for(mpIter = map.begin(); mpIter != map.end(); ++mpIter) 
     cout << " " << (*mpIter).second << endl; 
} 

Answer 2

Un modo (inefficiente) per do it è quello di creare una mappa inversa (con <string,int>) e inserire l'input in ordine inverso come quello di MyMap in esso. Se ok, quindi inserire in MyMap
Ecco il codice di lavoro.

Answer 3

Rendi il valore parte della chiave e/o utilizza un set ma potrebbe non risolvere il problema. Non è possibile definire facilmente un contenitore che abbia sia valori unici di chiavi che valori, se questo è ciò che si desidera. Tuttavia, potresti ancora costruirne uno. Ecco un esempio molto semplice per illustrare ciò che è necessario:

// Assuming keys are KEY and values are VAL 

class MyMap { 
public: 
    std::set<KEY> keyset; 
    std::set<VAL> valset; 

    std::map<KEY,VAL> theRealMap; 

    // assuming existence of function HAS(S,V) 
    // which returns true if v is in set S 
    bool MyInsert(KEY ky, VAL val) { 
     if (HAS(keyset, ky) return false; 
     if (HAS(valset, val) return false; 
     keyset.insert(ky); 
     valset.insert(vl); 
     return theRealMap.insert(std::pair<KEY,VAL>(ky, val)); 
    } 
: 
: 

Poiché questo è un esempio non è destinato ad essere copiato. Probabilmente vorrai includere la funzionalità fornita da std: map. Un modo semplice sarebbe quello di utilizzare std :: map come classe base, ma sarà necessario nasconderlo (rendendolo privato) o implementare un codice simile per ciascuna variante dell'inserto, altrimenti si potrebbe ottenere inserimenti involontari che potrebbero non essere univoci.

Nota: questo richiede il doppio delle dimensioni di una singola mappa. È possibile risparmiare spazio utilizzando la funzione Ricarica anziché un set separato per il set di chiavi. Un altro modo sarebbe quello di cercare la mappa ma questo sacrifica il tempo per lo spazio. È la tua chiamata.