C++ => std :: map

Osservazioni

Per usare qualsiasi di std::map o std::multimap dovrebbe essere incluso il file di intestazione <map> .
std::map e std::multimap mantengono i loro elementi ordinati secondo l'ordine crescente delle chiavi. In caso di std::multimap , non avviene alcun ordinamento per i valori della stessa chiave.
La differenza fondamentale tra std::map e std::multimap è che std::map one non consente valori duplicati per la stessa chiave dove std::multimap fa.
Le mappe sono implementate come alberi di ricerca binari. Quindi search() , insert() , erase() richiede Θ (log n) tempo medio. Per il funzionamento a tempo costante usa std::unordered_map .
size() funzioni size() e empty() hanno Θ (1) complessità temporale, il numero di nodi è memorizzato nella cache per evitare di camminare attraverso l'albero ogni volta che vengono chiamate queste funzioni.

Accesso agli elementi

Una coppia std::map accetta (key, value) come input.

Considera il seguente esempio di inizializzazione di std::map :

std::map < std::string, int > ranking { std::make_pair("stackoverflow", 2), 
                                        std::make_pair("docs-beta", 1) };

In una std::map , gli elementi possono essere inseriti come segue:

ranking["stackoverflow"]=2;
ranking["docs-beta"]=1;

Nell'esempio precedente, se lo stackoverflow della chiave è già presente, il suo valore verrà aggiornato a 2. Se non è già presente, verrà creata una nuova voce.

In una std::map , è possibile accedere direttamente agli elementi dando la chiave come indice:

std::cout << ranking[ "stackoverflow" ] << std::endl;

Si noti che l'utilizzo operator[] sulla mappa in realtà inserirà un nuovo valore con la chiave interrogata nella mappa. Ciò significa che non puoi usarlo su una const std::map , anche se la chiave è già memorizzata nella mappa. Per impedire questo inserimento, controlla se l'elemento esiste (per esempio usando find() ) o usa at() come descritto di seguito.

C ++ 11

Gli elementi di una std::map sono accessibili con at() :

std::cout << ranking.at("stackoverflow") << std::endl;

Nota che at() verrà std::out_of_range un'eccezione std::out_of_range se il contenitore non contiene l'elemento richiesto.

In entrambi i contenitori std::map e std::multimap , è possibile accedere agli elementi utilizzando gli iteratori:

C ++ 11

// Example using begin()
std::multimap < int, std::string > mmp { std::make_pair(2, "stackoverflow"),
                                         std::make_pair(1, "docs-beta"),
                                         std::make_pair(2, "stackexchange")  };
auto it = mmp.begin();
std::cout << it->first << " : " << it->second << std::endl; // Output: "1 : docs-beta"
it++;
std::cout << it->first << " : " << it->second << std::endl; // Output: "2 : stackoverflow"
it++;
std::cout << it->first << " : " << it->second << std::endl; // Output: "2 : stackexchange"

// Example using rbegin()
std::map < int, std::string > mp {  std::make_pair(2, "stackoverflow"),
                                    std::make_pair(1, "docs-beta"),
                                    std::make_pair(2, "stackexchange")  };
auto it2 = mp.rbegin();
std::cout << it2->first << " : " << it2->second << std::endl; // Output: "2 : stackoverflow"
it2++;
std::cout << it2->first << " : " << it2->second << std::endl; // Output: "1 : docs-beta"

Inizializzazione di std :: map o std :: multimap

std::map e std::multimap possono essere inizializzati fornendo coppie chiave-valore separate da virgola. Le coppie valore-chiave possono essere fornite da {key, value} o possono essere create esplicitamente da std::make_pair(key, value) . Poiché std::map non consente chiavi duplicate e l'operatore virgola va da destra a sinistra, la coppia a destra verrebbe sovrascritta con la coppia con lo stesso tasto a sinistra.

std::multimap < int, std::string > mmp { std::make_pair(2, "stackoverflow"),
                                     std::make_pair(1, "docs-beta"),
                                     std::make_pair(2, "stackexchange")  };
// 1 docs-beta
// 2 stackoverflow
// 2 stackexchange

std::map < int, std::string > mp {  std::make_pair(2, "stackoverflow"),
                                std::make_pair(1, "docs-beta"),
                                std::make_pair(2, "stackexchange")  }; 
// 1 docs-beta
// 2 stackoverflow

Entrambi possono essere inizializzati con iteratore.

// From std::map or std::multimap iterator
std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {6, 8}, {3, 4}, 
                               {6, 7} };
                       // {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 8}, {6, 7}, {8, 9}
auto it = mmp.begin();
std::advance(it,3); //moved cursor on first {6, 5}
std::map< int, int > mp(it, mmp.end()); // {6, 5}, {8, 9}

//From std::pair array
std::pair< int, int > arr[10];
arr[0] = {1, 3};
arr[1] = {1, 5};
arr[2] = {2, 5};
arr[3] = {0, 1};
std::map< int, int > mp(arr,arr+4); //{0 , 1}, {1, 3}, {2, 5}

//From std::vector of std::pair
std::vector< std::pair<int, int> > v{ {1, 5}, {5, 1}, {3, 6}, {3, 2} };
std::multimap< int, int > mp(v.begin(), v.end()); 
                        // {1, 5}, {3, 6}, {3, 2}, {5, 1}

Eliminazione di elementi

Rimozione di tutti gli elementi:

std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
mmp.clear(); //empty multimap

Rimozione di elementi da qualche parte con l'aiuto di iteratore:

std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
                            // {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 7}, {8, 9}
auto it = mmp.begin();
std::advance(it,3); // moved cursor on first {6, 5}
mmp.erase(it); // {1, 2}, {3, 4}, {3, 4}, {6, 7}, {8, 9}

Rimozione di tutti gli elementi in un intervallo:

std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
                            // {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 7}, {8, 9}
auto it = mmp.begin();
auto it2 = it;
it++; //moved first cursor on first {3, 4}
std::advance(it2,3);  //moved second cursor on first {6, 5}
mmp.erase(it,it2); // {1, 2}, {6, 5}, {6, 7}, {8, 9}

Rimozione di tutti gli elementi con un valore fornito come chiave:

std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
                            // {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 7}, {8, 9}
mmp.erase(6); // {1, 2}, {3, 4}, {3, 4}, {8, 9}

Rimozione di elementi che soddisfano un predicato pred :

std::map<int,int> m;
auto it = m.begin();
while (it != m.end())
{
   if (pred(*it))
       it = m.erase(it);
   else
       ++it;
}

Inserimento di elementi

Un elemento può essere inserito in una std::map solo se la sua chiave non è già presente nella mappa. Dato ad esempio:

std::map< std::string, size_t > fruits_count;

Una coppia chiave-valore viene inserita in una std::map attraverso la funzione membro insert() . Richiede una pair come argomento:
```
fruits_count.insert({"grapes", 20});
fruits_count.insert(make_pair("orange", 30));
fruits_count.insert(pair<std::string, size_t>("banana", 40));
fruits_count.insert(map<std::string, size_t>::value_type("cherry", 50));
```
La funzione insert() restituisce una pair composta da un iteratore e un valore bool :
- Se l'inserimento ha avuto successo, l'iteratore punta all'elemento appena inserito e il valore bool è true .
- Se esisteva già un elemento con la stessa key , l'inserimento fallisce. Quando ciò accade, l'iteratore punta all'elemento che causa il conflitto e il valore bool è false .
Il seguente metodo può essere utilizzato per combinare operazioni di inserimento e ricerca:
```
auto success = fruits_count.insert({"grapes", 20});
if (!success.second) {           // we already have 'grapes' in the map
    success.first->second += 20; // access the iterator to update the value
}
```
Per comodità, il contenitore std::map fornisce all'operatore subscript l'accesso agli elementi nella mappa e l'inserimento di nuovi se non esistono:
```
fruits_count["apple"] = 10;
```
Benché più semplice, impedisce all'utente di verificare se l'elemento esiste già. Se manca un elemento, std::map::operator[] lo crea implicitamente, inizializzandolo con il costruttore predefinito prima di sovrascriverlo con il valore fornito.

insert() può essere usato per aggiungere più elementi contemporaneamente usando una lista di coppie rinforzate. Questa versione di insert () restituisce void:
```
fruits_count.insert({{"apricot", 1}, {"jackfruit", 1}, {"lime", 1}, {"mango", 7}}); 
```

insert() può anche essere usato per aggiungere elementi usando gli iteratori che denotano i valori di inizio e fine di value_type :

std::map< std::string, size_t > fruit_list{ {"lemon", 0}, {"olive", 0}, {"plum", 0}};
fruits_count.insert(fruit_list.begin(), fruit_list.end());

Esempio:

std::map<std::string, size_t> fruits_count;
std::string fruit;
while(std::cin >> fruit){
    // insert an element with 'fruit' as key and '1' as value
    // (if the key is already stored in fruits_count, insert does nothing)
    auto ret = fruits_count.insert({fruit, 1});
    if(!ret.second){            // 'fruit' is already in the map 
        ++ret.first->second;    // increment the counter
    }
}

La complessità temporale per un'operazione di inserimento è O (log n) perché std::map è implementata come alberi.

C ++ 11

Una pair può essere costruita esplicitamente usando make_pair() ed emplace() :

std::map< std::string , int > runs;
runs.emplace("Babe Ruth", 714);
runs.insert(make_pair("Barry Bonds", 762));

Se sappiamo dove verrà inserito il nuovo elemento, possiamo usare emplace_hint() per specificare un hint iteratore. Se il nuovo elemento può essere inserito prima del hint , l'inserimento può essere eseguito in tempo costante. Altrimenti si comporta allo stesso modo di emplace() :

std::map< std::string , int > runs;
auto it = runs.emplace("Barry Bonds", 762); // get iterator to the inserted element
// the next element will be before "Barry Bonds", so it is inserted before 'it'
runs.emplace_hint(it, "Babe Ruth", 714);

Iterating su std :: map o std :: multimap

std::map o std::multimap potrebbe essere attraversato dai seguenti modi:

std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
                               
//Range based loop - since C++11
for(const auto &x: mmp) 
    std::cout<< x.first <<":"<< x.second << std::endl;

//Forward iterator for loop: it would loop through first element to last element
//it will be a std::map< int, int >::iterator
for (auto it = mmp.begin(); it != mmp.end(); ++it)
std::cout<< it->first <<":"<< it->second << std::endl; //Do something with iterator

//Backward iterator for loop: it would loop through last element to first element
//it will be a std::map< int, int >::reverse_iterator
for (auto it = mmp.rbegin(); it != mmp.rend(); ++it)
std::cout<< it->first <<" "<< it->second << std::endl; //Do something with iterator

Durante l'iterazione su std::map o std::multimap , l'uso di auto è preferito per evitare inutili conversioni implicite (vedere questa risposta per ulteriori dettagli).

Ricerca in std :: map o in std :: multimap

Esistono diversi modi per cercare una chiave in std::map o in std::multimap .

Per ottenere l'iteratore della prima occorrenza di una chiave, è possibile utilizzare la funzione find() . Restituisce end() se la chiave non esiste.

  std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
  auto it = mmp.find(6);
  if(it!=mmp.end())
      std::cout << it->first << ", " << it->second << std::endl; //prints: 6, 5
  else
      std::cout << "Value does not exist!" << std::endl;

  it = mmp.find(66);
  if(it!=mmp.end())
      std::cout << it->first << ", " << it->second << std::endl; 
  else
      std::cout << "Value does not exist!" << std::endl; // This line would be executed.

Un altro modo per scoprire se esiste una voce in std::map o in std::multimap sta utilizzando la funzione count() , che conta quanti valori sono associati a una determinata chiave. Poiché std::map associa un solo valore a ogni chiave, la sua funzione count() può solo restituire 0 (se la chiave non è presente) o 1 (se lo è). Per std::multimap , count() può restituire valori maggiori di 1 poiché possono essere presenti più valori associati alla stessa chiave.
```
 std::map< int , int > mp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
 if(mp.count(3) > 0) // 3 exists as a key in map
     std::cout << "The key exists!" << std::endl; // This line would be executed.
 else
     std::cout << "The key does not exist!" << std::endl;
```
Se ti interessa solo che alcuni elementi esistano, find è strettamente migliore: documenta il tuo intento e, per multimaps , può fermarsi una volta trovato il primo elemento corrispondente.
Nel caso di std::multimap , potrebbero esserci più elementi con la stessa chiave. Per ottenere questo intervallo, viene utilizzata la funzione equal_range() che restituisce std::pair con l'estremo inferiore di iteratore (incluso) e il limite superiore (esclusivo) rispettivamente. Se la chiave non esiste, entrambi gli iteratori puntano a end() .
```
  auto eqr = mmp.equal_range(6);
  auto st = eqr.first, en = eqr.second;
  for(auto it = st; it != en; ++it){
      std::cout << it->first << ", " << it->second << std::endl; 
  }
      // prints: 6, 5
      //         6, 7
```

Controllo del numero di elementi

Il contenitore std::map ha una funzione membro empty() , che restituisce true o false , a seconda che la mappa sia vuota o meno. La funzione membro size() restituisce il numero di elementi memorizzati in un contenitore std::map :

std::map<std::string , int> rank {{"facebook.com", 1} ,{"google.com", 2}, {"youtube.com", 3}};
if(!rank.empty()){
    std::cout << "Number of elements in the rank map: " << rank.size() << std::endl;
}
else{
    std::cout << "The rank map is empty" << std::endl;
}

Tipi di mappe

Mappa normale

Una mappa è un contenitore associativo, contenente coppie chiave-valore.

#include <string>
#include <map>
std::map<std::string, size_t> fruits_count;

Nell'esempio precedente, std::string è il tipo di chiave e size_t è un valore .

La chiave agisce come un indice nella mappa. Ogni chiave deve essere unica e deve essere ordinata.

Se hai bisogno di più elementi con la stessa chiave, considera l'utilizzo di multimap (spiegato sotto)

Se il tuo tipo di valore non specifica alcun ordine, o se desideri sovrascrivere l'ordine predefinito, puoi fornire uno:

#include <string>
#include <map>
#include <cstring>
struct StrLess {
    bool operator()(const std::string& a, const std::string& b) {
        return strncmp(a.c_str(), b.c_str(), 8)<0;
               //compare only up to 8 first characters
    }
}
std::map<std::string, size_t, StrLess> fruits_count2;

Se il comparatore StrLess restituisce false per due chiavi, vengono considerate uguali anche se i loro contenuti effettivi differiscono.

Multi-Map

Multimap consente di memorizzare più coppie di valori-chiave con lo stesso tasto nella mappa. Altrimenti, la sua interfaccia e la sua creazione sono molto simili alla normale mappa.

 #include <string>
 #include <map>
 std::multimap<std::string, size_t> fruits_count;
 std::multimap<std::string, size_t, StrLess> fruits_count2;

Hash-Map (Mappa non ordinata)

Una mappa hash memorizza coppie chiave-valore simili a una mappa normale. Tuttavia, non ordina gli elementi rispetto alla chiave. Invece, viene utilizzato un valore hash per la chiave per accedere rapidamente alle coppie chiave-valore necessarie.

#include <string>
#include <unordered_map>
std::unordered_map<std::string, size_t> fruits_count;

Le mappe non ordinate sono in genere più veloci, ma gli elementi non sono memorizzati in alcun ordine prevedibile. Ad esempio, l'iterazione di tutti gli elementi in una mappa unordered_map fornisce gli elementi in un ordine apparentemente casuale.

Creazione di std :: map con tipi definiti dall'utente come chiave

Per poter utilizzare una classe come chiave in una mappa, tutto ciò che è richiesto dalla chiave è che sia copiable e assignable . L'ordinamento all'interno della mappa è definito dal terzo argomento del modello (e dall'argomento del costruttore, se usato). Il valore predefinito è std::less<KeyType> , che per impostazione predefinita è < operatore, ma non è necessario utilizzare i valori predefiniti. Basta scrivere un operatore di confronto (preferibilmente come un oggetto funzionale):

struct CmpMyType
{
    bool operator()( MyType const& lhs, MyType const& rhs ) const
    {
        //  ...
    }
};

In C ++, il predicato "confronta" deve essere un severo ordinamento debole . In particolare, compare(X,X) deve restituire false per qualsiasi X cioè se CmpMyType()(a, b) restituisce true, quindi CmpMyType()(b, a) deve restituire false e, se entrambi restituiscono false, gli elementi sono considerati uguali (membri della stessa classe di equivalenza).

Ordinamento debole rigoroso

Questo è un termine matematico per definire una relazione tra due oggetti.
La sua definizione è:

Due oggetti xey sono equivalenti se sia f (x, y) che f (y, x) sono falsi. Si noti che un oggetto è sempre (dall'invarianza dell'invarianza) equivalente a se stesso.

In termini di C ++ ciò significa che se si hanno due oggetti di un determinato tipo, si dovrebbero restituire i seguenti valori rispetto all'operatore <.

X    a;
X    b;

Condition:                  Test:     Result
a is equivalent to b:       a < b     false
a is equivalent to b        b < a     false

a is less than b            a < b     true
a is less than b            b < a     false

b is less than a            a < b     false
b is less than a            b < a     true

Il modo in cui definisci l'equivalente / meno dipende totalmente dal tipo di oggetto.

Modified text is an extract of the original Stack Overflow Documentation

Autorizzato sotto CC BY-SA 3.0

Non affiliato con Stack Overflow

C++
std :: map

Ricerca…

Osservazioni

Accesso agli elementi

Inizializzazione di std :: map o std :: multimap

Eliminazione di elementi

Inserimento di elementi

Iterating su std :: map o std :: multimap

Ricerca in std :: map o in std :: multimap

Controllo del numero di elementi

Tipi di mappe

Mappa normale

Multi-Map

Hash-Map (Mappa non ordinata)

Creazione di std :: map con tipi definiti dall'utente come chiave

Ordinamento debole rigoroso