Différence entre std:: list et std:: map en C++ stl

std::pair

std::pair est basé sur un modèle n-uplet de la structure limitée à 2 éléments, appelé première et la deuxième:

std::pair<int, std::string> myPair ;
myPair.first = 42 ;
myPair.second = "Hello World" ;

std::pair est utilisé comme "conteneur générique" par le STL (et autre code) pour agréger deux valeurs en même temps sans avoir à redéfinir encore un autre struct.

std::map

std::map est un conteneur associatif, associant des clés et des valeurs. L'exemple le plus simple (mais pas le plus efficace) est :

std::map<int, std::string> myMap ;
myMap[42] = "Fourty Two" ;
myMap[111] = "Hello World" ;
// ...
std::string strText ;  // strText is ""
strText = myMap[111] ; // strText is now "Hello World"
strText = myMap[42] ;  // strText is now "Fourty Two"
strText = myMap[23] ;  // strText is now "" (and myMap has
                       // a new value "" for key 23)

std::pair et std::map

Note: C'était la réponse à l'originale, inédite question.

std::map les fonctions doivent retourner les itérateurs aux clés et aux valeurs en même temps pour rester efficaces... La solution évidente est donc de renvoyer les itérateurs à des paires:

std::map<int, std::string> myMap ;
myMap[42] = "Fourty Two" ;
myMap[111] = "Hello World" ;

myMap.insert(std::make_pair(23, "Bye")) ;

std::map<int, std::string>::iterator it = myMap.find(42) ;
std::pair<int, std::string> keyvalue = *it ;    // We assume 42 does
                                                // exist in the map
int key = keyvalue.first ;
int value = keyvalue.second ;

std::list<std::pair<A,B> > et std::map<A,B>

Remarque: les modifications apportées après l'édition de la question.

ainsi, à première vue, une carte de paires et une liste de paires semblent identiques. Mais ce n'est pas le cas:

la carte est intrinsèquement ordonnée par le foncteur fourni, alors que la liste gardera les paires de [A,B] où vous les mettez. Cela rend l'insertion O (log n) Pour la carte, alors que l'insertion brute à l'intérieur d'une liste est une constante complexité (chercher où l'insérer est un autre problème).

vous pouvez simuler un peu le comportement d'une carte en utilisant une liste de paires, mais notez que la carte est généralement mis en œuvre comme un arbre d'éléments, tandis que la liste est une liste chaînée d'éléments. Ainsi, un algorithme comme la dichotomie fonctionnera beaucoup plus rapidement dans une carte que dans une liste.

ainsi, trouver un article dans une carte est O(log n), Alors que dans une liste non ordonnée, C'est O(n). Et si la liste est commandée, et que vous voulez utiliser la dichotomie, vous n'obtiendrez pas l'augmentation de performance attendue, car la traversée de la liste des éléments se fait point par point de toute façon.

( dans un projet I il y a un an, nous avons remplacé une liste d'articles commandés par un ensemble des mêmes articles commandés, et cela a stimulé la performance. L'ensemble ayant la même arborescence que celle de la carte, je suppose que le même boost s'appliquerait ici)

std:pair contient exactement deux objets. std:map conservez une collection d'objets appariés.

vous ne pouvez pas utiliser find() sur la paire, parce qu'il n'y a rien à trouver. L'objet que vous voulez est soit pair.First ou pair.Second

mise à jour: En supposant que vous vouliez dire la différence entre map<> et list<pair<> >: Map doit être implémenté pour une recherche rapide sur le key membre. list n'a qu'une simple liste linéaire. La recherche d'un élément dans une liste nécessite de parcourir toute la liste. Cependant, std:: find () fonctionne sur les deux.

(révisé après clarification)

std::map est optimisé pour la recherche rapide. Il a son propre find méthode qui utilise sa structure interne pour fournir une bonne performance. En général, il ne fera qu'inspecter log(N) touches, où N est le nombre d'éléments dans la carte.

std::list<std::pair> est une simple liste liée, et ne supporte donc qu'élément par élément transversal. Vous utilisez le std::find algorithme, ou std::find_if avec un prédicat qui seulement examine l' first membre pour mieux correspondre à la sémantique de std::map::find, mais ce serait très lente. En fait, il faut regarder les tous les paire dans la liste pour toute recherche ratée, et regardera la moitié en moyenne pour toute recherche réussie.

les cartes STL sont des tableaux associatifs, généralement implémentés sous forme de hashmaps à l'intérieur. Si vous voulez obtenir iterate au-dessus d'une carte de STL il retournera une paire de STL.

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
        map<string, int> myMap;
        myMap["myKey"] = 1337;

        map<string, int>::iterator myIterator = myMap.begin();

        pair<string, int> myPair = *myIterator;

        cout<<"the key \""<<myPair.first<<"\" maps to the value of "<<myPair.second<<endl;
        cout<<"the key \"myKey"\" maps to the value of "<<myMap["myKey"]<<endl;
        return 0;
}

je suggère de googler et de lire la référence complète de L'API STL puisque STL (à l'exception de stocker des booléens dans des vecteurs et autres bizarreries comme ça) implémente beaucoup de fonctionnalités de structure de données que vous voudriez utiliser dans n'importe quel programme sans réinventer la roue.

std::pair est juste pour regrouper exactement 2 objets (disons, "coordonnées sur une page" est comprisé de X et Y).

std::map est une correspondance entre un ensemble d'objets à un autre.

il n'y a pas de raison d'essayer d'utiliser une méthode de recherche sur une paire, car à quoi ça sert de trouver quelque chose dans une liste de deux choses dont vous connaissez l'ordre, même si cette méthode de recherche existait dans une classe de paire ce qu'elle ne fait pas.

cependant, vous pouvez utiliser std:: pair comme une carte valeur si c'est ce que vous voulez.

Map peut fournir le meilleur temps de recherche dans la gamme de o (log n), whilw list peut avoir le temps de recherche de O (n).