Différence entre les std::list<std::pair>, et std::map en C++ stl

Pouvez-vous me dire la différence entre les std::list<std::pair>, et std::map. Puis-je utiliser la méthode find sur la liste?

Merci.

-- Clarification

Question modifié afin d'être plus clair.

  • Votre titre ne correspond pas au contenu de votre question.
InformationsquelleAutor Boolean | 2010-08-02
  1. 109

    std::map<X, Y>:

    • est une structure ordonnée à l'égard de clés (par exemple, lorsque vous effectuer une itération sur elle, les clés seront toujours croissantes).
    • prend en charge les clés uniques (Xs) de
    • offre rapide find() méthode (O(log n)) qui trouve la paire Clé-Valeur par Clé
    • propose une indexation de l'opérateur map[key], qui est aussi rapide

    std::list<std::pair<X, Y> >:

    • est une simple séquence de paires de Xs et Ys. Ils restent dans l'ordre que vous mettez dans.
    • peut contenir n'importe quel nombre de doublons
    • trouver une touche particulière dans un list est O(N) (aucune méthode particulière)
    • offre la splice méthode.
    • +1: Compact, correct, compréhensible.
    • Pour être complet: std::vector<std::pair<X, Y> > offre de O(log n) de recherche, et est plus petit (et devrait être plus rapide) qu'une carte de données immuables. Utile par exemple pour un statique, souvent utilisés de recherche. Mais l'utilisation d'une carte jusqu'à ce que vous montrez de l'optimisation procurent de réels avantages.
    • std::vector<std::pair<X, Y> > offre de O(log n) recherche UNIQUEMENT quand il est trié
    • oui en effet, c'est O(n) pour insérer une fois triés et donc meilleur pour les données statiques
    InformationsquelleAutor jpalecek
  2. 20

    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 un "conteneur générique" par le TSL (et le code) pour agréger les deux valeurs en même temps sans avoir à redéfinir encore un autre struct.

    std::map

    std::map est basé sur un modèle conteneur associatif, associe dans ce cas des clés et des valeurs. La méthode la plus simple (mais pas la plus efficace) exemple :

    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.

    La std::map fonctions des besoins de retour des itérateurs pour les clés et valeurs dans le même temps, pour rester efficace... Donc, la solution évidente est de retour itérateurs de 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.

    Donc, au premier abord, une carte de paires et d'une liste de paires semblent les mêmes. Mais ce n'est pas le cas:

    La carte est intrinsèquement commandé par le foncteur fourni, alors que la liste va garder les paires de [A,B] vers la droite endroit où vous les placez. Cela rend l'insertion O(log n) pour la carte, tandis que les premières d'insertion à l'intérieur d'une liste est une constante de la complexité (la recherche de l'emplacement d'insertion c'est un autre problème).

    Vous pouvez simuler un peu le comportement d'une carte à l'aide d'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, l'algorithme comme la dichotomie travaillera beaucoup plus vite, à une carte que dans une liste.

    Ainsi, la recherche d'un élément dans une carte est O(log n), tandis que dans une liste non ordonnée, il est O(n). Et si la liste est ordonnée, et que vous souhaitez utiliser dichotomie, vous n'aurez pas attendu d'augmentation des performances, comme la traversée de la liste des éléments est effectuée élément par élément, de toute façon.

    (Dans un projet, j'ai travaillé sur il y a un an, nous avons remplacé une liste des produits commandés par une série de des articles commandés, et il a contribué à la performance. L'ensemble ayant la même arborescence que celle de la carte, je suppose que le même boost s'appliquerait ici)

    • ayy c'est cool. 😀
    InformationsquelleAutor paercebal
  3. 3

    (Édité après clarification)

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

    std::list<std::pair> est une simple liste chaînée, et donc ne supporte élément par élément de la traversée. Vous pourrait utiliser les séparer std::find algorithme, ou std::find_if avec un prédicat qui examine seulement la first membre pour mieux correspondre à la sémantique de std::map::find, mais ce serait très lente. En fait, il faut regarder chaque paire dans la liste en cas de panne de recherche, et sur la moitié de la moyenne pour la réussite de tout un.

    InformationsquelleAutor Walter Mundt
  4. 2

    std:pair détient exactement deux objets. std:map stocker une collection d'objets liés.

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

    Mise à JOUR:
    En supposant que vous avez voulu dire la différence entre map<> et list<pair<> >: la Carte doit être mis en œuvre pour la recherche rapide sur le key membre. list a juste une simple liste linéaire. À la recherche d'un élément dans une liste nécessite l'exécution par le biais de l'ensemble de la liste. Cependant, std::find() permet de travailler sur les deux.

    InformationsquelleAutor James Curran
  5. 1

    STL cartes sont des tableaux associatifs sont généralement mis en oeuvre en tant que hashmaps à l'intérieur. Si vous souhaitez obtenir une itération sur un STL carte il va revenir STL paire.

    #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 vous suggère de le googler et de la lecture complète de la STL l'API de référence depuis STL (à l'exception de stocker des valeurs booléennes dans des vecteurs et autres bizarreries comme ça) met en œuvre un grand nombre de données de la structure de la fonctionnalité que vous souhaitez utiliser dans n'importe quel programme sans avoir à réinventer la roue.

    • STL maps ne sont pas mises en œuvre par hashmaps, mais le rouge-noir (ou comme) des arbres.
    • Il y a quelques endroits où la STL documentation ne correspond pas aux exigences définies par la norme C++, donc, la lecture de la STL l'API peut vous ne sont pas réellement l'utiliser.
    InformationsquelleAutor Novikov
  6. 0

    std::pair est juste pour le regroupement exactement 2 objets (par exemple, "coordonnées sur une page" est formée de X et de Y).

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

    Il n'y a pas de point d'essayer d'utiliser une méthode de recherche sur une paire, comme ce qui est le point de trouver quelque chose dans une liste de deux choses dont vous savez l'ordre, même si cette méthode existe dans une paire de la classe dont il ne fait pas.

    Toutefois, vous POUVEZ utiliser std::pair en tant que valeur de la carte si c'est ce que vous voulez.

    InformationsquelleAutor DVK
  7. 0

    Carte peut donner le meilleur temps de recherche dans la plage de O(log n),
    whilw liste peut avoir le temps de recherche de O(n).

    InformationsquelleAutor Udhay