C++: value_type contre make_pair, qui est plus rapide pour la carte insérer?

typedef map<KeyType, ValType> KVMap;
KVMap kvmap;

kvmap.insert( KVMap::value_type( key, val ) );
kvmap.insert( make_pair( key, val ) );

Laquelle des options ci-dessus pour l'insérer à un STL carte est toujours plus rapide? Pourquoi?

Note: je suis bien conscient que insert() est plus rapide que l'utilisation []= pour l'ajout (mise à jour) des paires clé-valeur d'une carte. Veuillez supposer que ma question est à propos de l'ajout, pas de mise à jour. Donc j'ai limité à insert().

  • À moins que votre programme se compose uniquement d'inserts pour cartes, pensez-vous vraiment aucune différence de vitesse sera perceptible? Vous devriez obtenir un profil de profil de votre produit fini, propre, maintenable programme pour voir ce que la lenteur des spots sont en réalité. Et il ne devrait pas y avoir une différence, après l'in-lining.
  • GMan: La différence était minuscule. Voir mon commentaire à la manière de Karl réponse.
InformationsquelleAutor Ashwin Nanjappa | 2011-01-07
  1. 20

    Des Chances que le premier sera 'epsilon-rapide, à cause de cela (à partir de 23.3.1 dans la norme) :

    typedef pair<const Key, T> value_type;

[...]

pair<iterator, bool> insert(const value_type& x);

    • Dans la première version, vous avez directement la construction du type approprié prévu par std::map<K,V>::insert

    • Dans la deuxième version, une conversion à l'aide de std::pair modèle constructeur est impliqué. En effet, std::make_pair sera plus susceptible de déduire de ses arguments de modèle à KeyType et ValType, renvoyant ainsi une std::pair<KeyType, ValType>.

      Cela ne correspond pas au type de paramètre de std::map<K,V>::insert, qui est std::pair<const KeyType, ValType> (la différence étant le constqualifiés de la première). Le std::pair conversion constructeur est utilisé pour créer un std::pair<const K, V> de la std::pair<K, V>.

    Pour être juste, je ne crois pas que vous pouvez même mesurer la différence (et je ne suis même pas sûr que les compilateurs génèrent un code différent pour ces).

    • Et après inline?
    • honnêtement ? Aucune idée 🙁
    • Ce n'est pas inline soi, ce qui permettrait d'éliminer les frais généraux, mais plutôt la subséquente élision de la copie de la construction et des travaux etc.
    • icecrime: make_pair implique des conversions, comment est-ce qu'il epsilon-plus vite?
    • bien sûr que ce une erreur dans la première phrase 🙂 Fixe
    InformationsquelleAutor icecrime
  2. 12

    Il y a en fait un argument pour value_type sur make_pair. C'est parce que, pour diverses arcanes raisons, make_pair accepte ses arguments par valeur. D'autre part, value_type, un alias pour std::pair<const Key, value>, aura son constructeur appelé avec les arguments passés par référence const. Il y a un risque de perte d'efficacité de la passe-par-valeur en make_pair contre passé par référence, qui pourrait, en théorie, avoir un impact notable sur votre programme.

    Un autre problème à être inquiet avec make_pair est que make_pair généralement de créer une paire de type std::pair<Key, Value> par rapport à la std::pair<const Key, Value> nécessaire à l'intérieur de la map. Cela signifie qu'il pourrait y avoir une autre copie superflue étant faite, cette fois de la pair pour obtenir la conversion fonctionne correctement.

    En bref, à l'aide make_pair peut provoquer deux complètement inutile copies de la clé et la valeur sont prises, tout en utilisant la value_type constructeur n'en a aucun.

    InformationsquelleAutor templatetypedef
  3. 4

    C'est juste une supplémentation.

    insert( make_pair(...) )
    les appels de constructeur de copie 4 fois théoriquement raison de la raison que d'autres
    answerers mentionné.

    insert( value_type(...) )
    les appels de constructeur de copie 2 fois.

    operator[]
    les appels de constructeur par défaut une fois et constructeur de copie 2 fois
    dans un cadre typique de la mise en œuvre.
    constructeur par défaut est appelé à l'intérieur operator[] pour
    insert( value_type( ..., mapped_type() ) ).
    constructeur de copie est appelé une fois pour la copie insert()'argument(pair),
    et une fois de copier-construire un noeud interne de la carte.

    Donc, si vous utilisez insert avec make_pair,
    il ne peut pas être dit que insert est toujours plus rapide que operator[] même pour l'ajout.
    Probablement, cela dépend de la situation.
    Comme vous le savez peut-être, au vu de ce qui précède, emplace a été proposé pour la nouvelle
    standard.

    InformationsquelleAutor Ise Wisteria
  4. 2

    Ils sont fondamentalement la même chose. KVMap::value_type est un typedef pour std::pair<KeyType, ValType>, de sorte que c'est juste d'appeler le constructeur. std::make_pair est un modèle de fonction qui appelle simplement le constructeur (elle existe parce que les types de modèles peuvent être déduites pour les fonctions libres, mais pas pour les constructeurs). Une fois que tous les incroyablement standard optimisations sont faites, il n'y a pas de raison pour qu'il y ait une différence.

    Je ne sais pas comment vous faites des tests, mais il y a beaucoup, beaucoup de manières de faire que le mal.

    Comme pour insert() contre l'attribution par operator[], ce dernier doit faire plus de travail sur le plan conceptuel (lorsque vous ajoutez un nouvel élément de cette façon, il est supposé par défaut-la construction d'un élément, et ensuite affecter plus haut), mais en fonction de la ValType, il pourrait être optimisé en basiquement la même chose de nouveau.

    • Je crois que vous êtes un peu mal : voir ma réponse
    • Je pense que vous avez un point. C++ est une sorte de vilain de l'omi quand il s'agit de déduire const-ness. 🙂
    • Ils sont même en supposant que la clé, valeur ont les types appropriés. Il est généralement ne va pas être un problème, mais parfois, l'auto conversions peuvent être inattendu, donc je préfère utiliser value_type(clé, valeur). Exemple: Key="std::string". make_pair("Plop", 1) n'est pas d'abord de faire un value_type objet même s'il est converti par la suite et optimisations peut supprimer tous les conversions sur un bon compilateur.
    • Karl: Vous avez raison à propos de l'essai. L'un semble être un tout petit peu plus rapide pour l'insertion de 10^3 éléments et l'autre pour 10^5 éléments. Je suis en douter peut-être due à des facteurs extérieurs.
    InformationsquelleAutor Karl Knechtel