C++ => std :: carte

Remarques

Pour utiliser l'un des std::map ou std::multimap le fichier d'en-tête <map> doit être inclus.
std::map et std::multimap conservent leurs éléments triés en fonction de l'ordre croissant des clés. Dans le cas de std::multimap , aucun tri n'est effectué pour les valeurs de la même clé.
La différence fondamentale entre std::map et std::multimap est que std::map one n'autorise pas les valeurs en double pour la même clé, contrairement à std::multimap .
Les cartes sont implémentées comme des arbres de recherche binaires. Ainsi, search() , insert() , erase() prend en moyenne Θ (log n). Pour une opération à temps constant, utilisez std::unordered_map .
size() et empty() ont une complexité temporelle de Θ (1), le nombre de nœuds est mis en cache pour éviter de traverser un arbre à chaque appel de ces fonctions.

Accès aux éléments

Un std::map prend en entrée des paires (key, value) .

Prenons l'exemple suivant de l'initialisation std::map :

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

Dans un std::map , les éléments peuvent être insérés comme suit:

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

Dans l'exemple ci-dessus, si le stackoverflow la clé est déjà présent, sa valeur sera mise à jour à 2. S'il n'est pas déjà présent, une nouvelle entrée sera créée.

Dans une std::map , il est possible d'accéder directement aux éléments en donnant la clé en tant qu'index:

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

Notez que l'utilisation de l' operator[] sur la carte insèrera effectivement une nouvelle valeur avec la clé interrogée dans la carte. Cela signifie que vous ne pouvez pas l'utiliser sur un const std::map , même si la clé est déjà stockée dans la carte. Pour empêcher cette insertion, vérifiez si l'élément existe (par exemple en utilisant find() ) ou utilisez at() comme décrit ci-dessous.

C ++ 11

Les éléments d'un std::map peuvent être accédés avec at() :

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

Notez que at() lancera une exception std::out_of_range si le conteneur ne contient pas l'élément demandé.

Dans les deux conteneurs std::map et std::multimap , les éléments sont accessibles à l'aide d'itérateurs:

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"

Initialisation d'un std :: map ou std :: multimap

std::map et std::multimap peuvent tous deux être initialisés en fournissant des paires clé-valeur séparées par des virgules. Les paires clé-valeur peuvent être fournies par {key, value} ou peuvent être explicitement créées par std::make_pair(key, value) . Comme std::map n'autorise pas les clés en double et que l'opérateur de la virgule effectue de droite à gauche, la paire à droite sera remplacée par la paire avec la même clé à gauche.

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

Les deux pourraient être initialisés avec un itérateur.

// 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}

Supprimer des éléments

Supprimer tous les éléments:

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

Supprimer l'élément de quelque part avec l'aide de l'itérateur:

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}

Supprimer tous les éléments d'une plage:

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}

Enlever tous les éléments ayant une valeur fournie comme clé:

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}

Suppression d'éléments qui satisfont un prédicat pred :

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

Insertion d'éléments

Un élément peut être inséré dans une std::map uniquement si sa clé n'est pas déjà présente dans la carte. Étant donné par exemple:

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

Une paire clé-valeur est insérée dans une std::map via la fonction membre insert() . Il nécessite une pair en argument:
```
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 fonction insert() renvoie une pair composée d'un itérateur et d'une valeur bool :
- Si l'insertion a réussi, l'itérateur pointe sur l'élément nouvellement inséré et la valeur bool est true .
- S'il y avait déjà un élément avec la même key , l'insertion échoue. Lorsque cela se produit, l'itérateur pointe vers l'élément à l'origine du conflit, et la valeur bool est false .
La méthode suivante peut être utilisée pour combiner une opération d'insertion et de recherche:
```
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
}
```
Pour plus de commodité, le std::map fournit l'opérateur de l'indice pour accéder aux éléments de la carte et en insérer de nouveaux s'ils n'existent pas:
```
fruits_count["apple"] = 10;
```
Bien que plus simple, il empêche l'utilisateur de vérifier si l'élément existe déjà. Si un élément est manquant, std::map::operator[] crée implicitement, l'initialisant avec le constructeur par défaut avant de le remplacer par la valeur fournie.

insert() peut être utilisé pour ajouter plusieurs éléments à la fois en utilisant une liste de paires contreventée. Cette version de insert () renvoie void:
```
fruits_count.insert({{"apricot", 1}, {"jackfruit", 1}, {"lime", 1}, {"mango", 7}}); 
```
insert() peut également être utilisé pour ajouter des éléments en utilisant des itérateurs indiquant les valeurs de début et de fin de 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()); 
```

Exemple:

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 complexité temporelle pour une opération d'insertion est O (log n) car std::map est implémenté sous forme d'arborescence.

C ++ 11

Une pair peut être construite explicitement en utilisant make_pair() et emplace() :

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

Si nous savons où le nouvel élément sera inséré, nous pouvons utiliser emplace_hint() pour spécifier un hint itérateur. Si le nouvel élément peut être inséré juste avant l’ hint , l’insertion peut être effectuée à temps constant. Sinon, il se comporte comme 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);

Itération sur std :: map ou std :: multimap

std::map ou std::multimap pourrait être parcouru par les moyens suivants:

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

En itérant sur un std::map ou un std::multimap , l'utilisation de auto est préférable pour éviter les conversions implicites inutiles (voir cette réponse SO pour plus de détails).

Recherche dans std :: map ou dans std :: multimap

Il existe plusieurs façons de rechercher une clé dans std::map ou dans std::multimap .

Pour obtenir l'itérateur de la première occurrence d'une clé, la fonction find() peut être utilisée. Il retourne end() si la clé n'existe pas.

  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.

Une autre façon de déterminer si une entrée existe dans std::map ou dans std::multimap consiste à utiliser la fonction count() , qui compte le nombre de valeurs associées à une clé donnée. Puisque std::map n'associe qu'une seule valeur à chaque clé, sa fonction count() ne peut renvoyer que 0 (si la clé n'est pas présente) ou 1 (si elle est présente). Pour std::multimap , count() peut renvoyer des valeurs supérieures à 1 car il peut y avoir plusieurs valeurs associées à la même clé.
```
 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;
```
Si vous vous souciez de savoir si un élément existe, find est strictement meilleur: il documente votre intention et, pour les multimaps , il peut s'arrêter une fois que le premier élément correspondant a été trouvé.
Dans le cas de std::multimap , il pourrait y avoir plusieurs éléments ayant la même clé. Pour obtenir cette plage, la fonction equal_range() est utilisée, qui renvoie respectivement std::pair avec une limite inférieure d'itérateur (inclus) et une limite supérieure (exclusive). Si la clé n'existe pas, les deux itérateurs pointe vers la 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
```

Vérification du nombre d'éléments

Le conteneur std::map a une fonction membre empty() , qui renvoie true ou false , selon que la carte est vide ou non. Le membre function size() renvoie le nombre d'éléments stockés dans un 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;
}

Types de cartes

Carte régulière

Une carte est un conteneur associatif contenant des paires clé-valeur.

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

Dans l'exemple ci-dessus, std::string est le type de clé et size_t est une valeur .

La clé agit comme un index dans la carte. Chaque clé doit être unique et doit être commandée.

Si vous avez besoin de plusieurs éléments avec la même clé, pensez à utiliser le multimap (expliqué ci-dessous)

Si votre type de valeur ne spécifie aucun ordre ou que vous souhaitez remplacer le classement par défaut, vous pouvez en fournir un:

#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;

Si le comparateur StrLess renvoie false pour deux clés, elles sont considérées comme identiques même si leur contenu réel est différent.

Multi-Map

Multimap permet de stocker plusieurs paires clé-valeur avec la même clé dans la carte. Sinon, son interface et sa création sont très similaires à la carte normale.

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

Hash-Map (carte non ordonnée)

Une carte de hachage stocke des paires clé-valeur similaires à une carte normale. Cependant, il ne commande pas les éléments par rapport à la clé. Au lieu de cela, une valeur de hachage pour la clé est utilisée pour accéder rapidement aux paires clé-valeur nécessaires.

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

Les cartes non ordonnées sont généralement plus rapides, mais les éléments ne sont pas stockés dans un ordre prévisible. Par exemple, l'itération de tous les éléments d'un unordered_map donne les éléments dans un ordre apparemment aléatoire.

Création de std :: map avec les types définis par l'utilisateur comme clé

Pour pouvoir utiliser une classe comme clé dans une carte, il copiable que la clé soit copiable et assignable . L'ordre dans la carte est défini par le troisième argument du modèle (et l'argument du constructeur, s'il est utilisé). Par défaut, std::less<KeyType> , par défaut l'opérateur < , mais il n'est pas nécessaire d'utiliser les valeurs par défaut. Il suffit d'écrire un opérateur de comparaison (de préférence en tant qu'objet fonctionnel):

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

En C ++, le prédicat "compare" doit être un ordre faible strict . En particulier, compare(X,X) doit retourner false pour tout X Si CmpMyType()(a, b) renvoie true, alors CmpMyType()(b, a) doit retourner false, et si les deux renvoient false, les éléments sont considérés égaux (membres de la même classe d'équivalence).

Strict Commande Faible

C'est un terme mathématique pour définir une relation entre deux objets.
Sa définition est la suivante:

Deux objets x et y sont équivalents si f (x, y) et f (y, x) sont faux. Notez qu'un objet est toujours (par l'invariant de l'irréflexivité) équivalent à lui-même.

En termes de C ++, cela signifie que si vous avez deux objets d'un type donné, vous devez renvoyer les valeurs suivantes par rapport à l'opérateur <.

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

Comment vous définissez équivalent / moins dépend totalement du type de votre objet.

Modified text is an extract of the original Stack Overflow Documentation

Sous licence CC BY-SA 3.0

Non affilié à Stack Overflow

C++
std :: carte

Recherche…

Remarques

Accès aux éléments

Initialisation d'un std :: map ou std :: multimap

Supprimer des éléments

Insertion d'éléments

Itération sur std :: map ou std :: multimap

Recherche dans std :: map ou dans std :: multimap

Vérification du nombre d'éléments

Types de cartes

Carte régulière

Multi-Map

Hash-Map (carte non ordonnée)

Création de std :: map avec les types définis par l'utilisateur comme clé

Strict Commande Faible