Dans les cartes STL, est-il préférable d'utiliser map :: insert que []?

201

Il y a quelque temps, j'ai eu une discussion avec un collègue sur la façon d'insérer des valeurs dans les cartes STL . J'ai préféré map[key] = value; parce que ça semble naturel et clair à lire alors qu'il préférait map.insert(std::make_pair(key, value))

Je viens de lui demander et aucun de nous ne peut se souvenir de la raison pour laquelle l'insert est meilleur, mais je suis sûr que ce n'était pas seulement une préférence de style mais plutôt une raison technique comme l'efficacité. La référence SGI STL dit simplement "Strictement parlant, cette fonction membre n'est pas nécessaire: elle n'existe que par commodité."

Quelqu'un peut-il me dire cette raison, ou est-ce que je rêve juste qu'il y en ait une?

danio
la source
2
Merci pour toutes les bonnes réponses - elles ont été très utiles. C'est une excellente démonstration de débordement de pile à son meilleur. J'étais déchiré quant à la réponse qui devrait être acceptée: netjeff est plus explicite sur les différents comportements, Greg Rogers a mentionné les problèmes de performance. J'aimerais pouvoir cocher les deux.
danio
6
En fait, avec C ++ 11, il vaut probablement mieux utiliser map :: emplace qui évite la double construction
einpoklum
@einpoklum: En fait, Scott Meyers suggère le contraire dans son exposé "La recherche évolutive d'un C ++ efficace".
Thomas Eding
3
@einpoklum: C'est le cas lors de la mise en place dans une mémoire nouvellement construite. Mais en raison de certaines exigences de normes pour la carte, il y a des raisons techniques pour lesquelles le placement peut être plus lent que l'insertion. La conférence est disponible gratuitement sur YouTube, comme ce lien youtube.com/watch?v=smqT9Io_bKo @ ~ 38-40 min. Pour un lien SO, voici stackoverflow.com/questions/26446352/…
Thomas Eding
1
En fait, je discuterais avec certains de ce que Meyers a présenté, mais cela dépasse la portée de ce fil de commentaires et de toute façon, je suppose que je dois retirer mon commentaire précédent.
einpoklum

Réponses:

240

Quand tu écris

map[key] = value;

il n'y a aucun moyen de savoir si vous avez remplacé le valuefor keyou si vous en avez créé un nouveau keyavec value.

map::insert() ne fera que créer:

using std::cout; using std::endl;
typedef std::map<int, std::string> MyMap;
MyMap map;
// ...
std::pair<MyMap::iterator, bool> res = map.insert(MyMap::value_type(key,value));
if ( ! res.second ) {
    cout << "key " <<  key << " already exists "
         << " with value " << (res.first)->second << endl;
} else {
    cout << "created key " << key << " with value " << value << endl;
}

Pour la plupart de mes applications, je ne me soucie généralement pas de créer ou de remplacer, donc j'utilise le plus facile à lire map[key] = value.

netjeff
la source
16
Il faut noter que map :: insert ne remplace jamais les valeurs. Et dans le cas général, je dirais qu'il est préférable d'utiliser (res.first)->secondplutôt que valuedans le deuxième cas.
dalle
1
J'ai mis à jour pour être plus clair que map :: insert ne remplace jamais. J'ai quitté le elsecar je pense que l'utilisation valueest plus claire que l'itérateur. Ce n'est que si le type de la valeur avait une copie inhabituelle ctor ou op == que ce serait différent, et que ce type entraînerait d'autres problèmes en utilisant des conteneurs STL comme map.
netjeff
1
map.insert(std::make_pair(key,value))devrait être map.insert(MyMap::value_type(key,value)). Le type renvoyé make_pairne correspond pas au type pris par insertet la solution actuelle nécessite une conversion
David Rodríguez - dribeas
1
il existe un moyen de savoir si vous avez inséré ou simplement attribué à operator[], comparez simplement la taille avant et après. Imho étant en mesure d'appeler map::operator[]uniquement pour les types constructibles par défaut est beaucoup plus important.
idclev 463035818
@ DavidRodríguez-dribeas: Bonne suggestion, j'ai mis à jour le code dans ma réponse.
netjeff
53

Les deux ont une sémantique différente en ce qui concerne la clé déjà existante dans la carte. Ils ne sont donc pas vraiment directement comparables.

Mais la version de l'opérateur [] nécessite la construction par défaut de la valeur, puis l'attribution, donc si c'est plus cher que la construction de copie, alors ce sera plus cher. Parfois, la construction par défaut n'a pas de sens, et il serait alors impossible d'utiliser la version opérateur [].

Greg Rogers
la source
1
make_pair peut nécessiter un constructeur de copie - ce serait pire que celui par défaut. +1 de toute façon.
1
L'essentiel est, comme vous l'avez dit, d'avoir une sémantique différente. Donc, ni l'un ni l'autre n'est meilleur que l'autre, utilisez simplement celui qui fait ce dont vous avez besoin.
jalf
Pourquoi le constructeur de copie serait-il pire que le constructeur par défaut suivi d'une affectation? Si c'est le cas, alors la personne qui a écrit la classe a raté quelque chose, car quoi que l'opérateur = fasse, ils auraient dû faire la même chose dans le constructeur de copie.
Steve Jessop
1
Parfois, la construction par défaut est aussi coûteuse que l'affectation elle-même. Naturellement, la construction et la copie seront équivalentes.
Greg Rogers
@Arkadiy Dans une version optimisée, le compilateur supprimera souvent de nombreux appels de constructeur de copie inutiles.
antred
35

Une autre chose à noter avec std::map:

myMap[nonExistingKey];créera une nouvelle entrée dans la carte, codée pour nonExistingKeyinitialisée à une valeur par défaut.

Cela m'a effrayé la première fois que je l'ai vu (tout en me cognant la tête contre un bug méchant). Je ne m'y serais pas attendu. Pour moi, cela ressemble à une opération get, et je ne m'attendais pas à «l'effet secondaire». Préférez map.find()lors de l'obtention de votre carte.

Hawkeye Parker
la source
3
C'est une vue décente, bien que les cartes de hachage soient assez universelles pour ce format. C'est peut-être une de ces "bizarreries que personne ne trouve étranges" simplement à cause de leur utilisation répandue des mêmes conventions
Stephen J
19

Si les performances du constructeur par défaut ne sont pas un problème, veuillez, pour l'amour de Dieu, opter pour la version plus lisible.

:)

Torlack
la source
5
Seconde! Je dois marquer ça. Trop de gens troquent l'obus pour des accélérations de nano-seconde. Ayez pitié de nous, pauvres âmes qui doivent maintenir de telles atrocités!
Mr.Ree
6
Comme l'a écrit Greg Rogers: "Les deux ont une sémantique différente en ce qui concerne la clé déjà existante dans la carte. Donc, ils ne sont pas vraiment directement comparables."
dalle
Ceci est une vieille question et réponse. Mais une "version plus lisible" est une raison stupide. Parce que ce qui est le plus lisible dépend de la personne.
vallentin
14

insert est meilleur du point de vue de la sécurité d'exception.

L'expression map[key] = valueest en fait deux opérations:

  1. map[key] - création d'un élément de carte avec la valeur par défaut.
  2. = value - copier la valeur dans cet élément.

Une exception peut se produire à la deuxième étape. En conséquence, l'opération ne sera que partiellement effectuée (un nouvel élément a été ajouté à la carte, mais cet élément n'a pas été initialisé avec value). La situation où une opération n'est pas terminée, mais l'état du système est modifié, est appelée l'opération avec «effet secondaire».

insertl'opération donne une forte garantie, signifie qu'elle n'a pas d'effets secondaires ( https://en.wikipedia.org/wiki/Exception_safety ). insertest soit complètement terminé, soit il laisse la carte dans un état non modifié.

http://www.cplusplus.com/reference/map/map/insert/ :

Si un seul élément doit être inséré, il n'y a pas de changement dans le conteneur en cas d'exception (garantie forte).

anton_rh
la source
1
plus important encore, l'insertion ne nécessite pas que la valeur soit constructible par défaut.
UmNyobe
13

Si votre application est critique en termes de vitesse, je vous conseillerai d'utiliser l'opérateur [] car elle crée au total 3 copies de l'objet d'origine dont 2 sont des objets temporaires et tôt ou tard détruits au fur et à mesure.

Mais dans l'insert (), 4 copies de l'objet d'origine sont créées dont 3 sont des objets temporaires (pas nécessairement "temporaires") et sont détruites.

Ce qui signifie du temps supplémentaire pour: 1. Une allocation de mémoire d'objets 2. Un appel de constructeur supplémentaire 3. Un appel de destructeur supplémentaire 4. Une désallocation de mémoire d'objets

Si vos objets sont grands, les constructeurs sont typiques, les destructeurs font beaucoup de libération de ressources, les points ci-dessus comptent encore plus. En ce qui concerne la lisibilité, je pense que les deux sont assez justes.

La même question m'est venue à l'esprit mais pas la lisibilité mais la vitesse. Voici un exemple de code grâce auquel j'ai appris le point que j'ai mentionné.

class Sample
{
    static int _noOfObjects;

    int _objectNo;
public:
    Sample() :
        _objectNo( _noOfObjects++ )
    {
        std::cout<<"Inside default constructor of object "<<_objectNo<<std::endl;
    }

    Sample( const Sample& sample) :
    _objectNo( _noOfObjects++ )
    {
        std::cout<<"Inside copy constructor of object "<<_objectNo<<std::endl;
    }

    ~Sample()
    {
        std::cout<<"Destroying object "<<_objectNo<<std::endl;
    }
};
int Sample::_noOfObjects = 0;


int main(int argc, char* argv[])
{
    Sample sample;
    std::map<int,Sample> map;

    map.insert( std::make_pair<int,Sample>( 1, sample) );
    //map[1] = sample;
    return 0;
}

Sortie lorsque insert () est utilisé Sortie lorsque l'opérateur [] est utilisé

Rampal Chaudhary
la source
4
Exécutez à nouveau ce test avec les optimisations complètes activées.
attente le
2
Considérez également ce que l'opérateur [] fait réellement. Il recherche d'abord dans la carte une entrée qui correspond à la clé spécifiée. S'il en trouve un, il remplace la valeur de cette entrée par celle spécifiée. Si ce n'est pas le cas, il insère une nouvelle entrée avec la clé et la valeur spécifiées. Plus votre carte est grande, plus il faudra de temps à l'opérateur [] pour rechercher la carte. À un certain point, cela compensera largement un appel de copie supplémentaire (si cela reste même dans le programme final après que le compilateur ait fait sa magie d'optimisation).
antred
1
@antred, insertdoit faire la même recherche, donc aucune différence dans celle de [](car les clés de carte sont uniques).
Sz.
Belle illustration de ce qui se passe avec les impressions - mais que font réellement ces 2 bits de code? Pourquoi 3 copies de l'objet original sont-elles nécessaires?
rbennett485
1. doit implémenter l'opérateur d'affectation, sinon vous obtiendrez de mauvais numéros dans le destructeur 2. utilisez std :: move lors de la construction de la paire pour éviter un excès de construction de copie "map.insert (std :: make_pair <int, Sample> (1, std: : move (échantillon))); "
Fl0
10

Maintenant, en c ++ 11, je pense que la meilleure façon d'insérer une paire dans une carte STL est:

typedef std::map<int, std::string> MyMap;
MyMap map;

auto& result = map.emplace(3,"Hello");

Le résultat sera une paire avec:

  • Premier élément (result.first), pointe vers la paire insérée ou pointe vers la paire avec cette clé si la clé existe déjà.

  • Deuxième élément (result.second), vrai si l'insertion était correcte ou fausse si quelque chose s'est mal passé.

PS: Si vous ne vous souciez pas de la commande, vous pouvez utiliser std :: unordered_map;)

Merci!

GutiMac
la source
9

Un gotcha avec map :: insert () est qu'il ne remplacera pas une valeur si la clé existe déjà dans la carte. J'ai vu du code C ++ écrit par des programmeurs Java où ils s'attendaient à ce que insert () se comporte de la même manière que Map.put () en Java où les valeurs sont remplacées.

Anthony Cramp
la source
2

Une remarque est que vous pouvez également utiliser Boost .

using namespace std;
using namespace boost::assign; // bring 'map_list_of()' into scope

void something()
{
    map<int,int> my_map = map_list_of(1,2)(2,3)(3,4)(4,5)(5,6);
}
rlbond
la source
1

Voici un autre exemple, montrant que operator[] remplace la valeur de la clé si elle existe, mais .insert ne remplace pas la valeur si elle existe.

void mapTest()
{
  map<int,float> m;


  for( int i = 0 ; i  <=  2 ; i++ )
  {
    pair<map<int,float>::iterator,bool> result = m.insert( make_pair( 5, (float)i ) ) ;

    if( result.second )
      printf( "%d=>value %f successfully inserted as brand new value\n", result.first->first, result.first->second ) ;
    else
      printf( "! The map already contained %d=>value %f, nothing changed\n", result.first->first, result.first->second ) ;
  }

  puts( "All map values:" ) ;
  for( map<int,float>::iterator iter = m.begin() ; iter !=m.end() ; ++iter )
    printf( "%d=>%f\n", iter->first, iter->second ) ;

  /// now watch this.. 
  m[5]=900.f ; //using operator[] OVERWRITES map values
  puts( "All map values:" ) ;
  for( map<int,float>::iterator iter = m.begin() ; iter !=m.end() ; ++iter )
    printf( "%d=>%f\n", iter->first, iter->second ) ;

}
bobobobo
la source
1

C'est un cas assez restreint, mais à en juger par les commentaires que j'ai reçus, je pense que cela vaut la peine d'être noté.

J'ai déjà vu des gens utiliser des cartes sous forme de

map< const key, const val> Map;

pour éviter les cas d'écrasement accidentel de valeur, mais continuez à écrire dans d'autres bits de code:

const_cast< T >Map[]=val;

Si je me souviens bien, c'est parce qu'ils étaient sûrs que dans ces certains morceaux de code, ils n'écraseraient pas les valeurs de la carte; par conséquent, aller de l'avant avec la méthode plus «lisible» [].

En fait, je n'ai jamais eu de problème direct avec le code qui a été écrit par ces personnes, mais je pense fermement jusqu'à aujourd'hui que les risques - aussi petits soient-ils - ne devraient pas être pris lorsqu'ils peuvent être facilement évités.

Dans les cas où vous avez affaire à des valeurs de carte qui ne doivent absolument pas être écrasées, utilisez insert. Ne faites pas d'exceptions simplement pour la lisibilité.

dk123
la source
Plusieurs personnes différentes ont écrit cela? Certainement utilisez insert(not input), car le const_castfera écraser toute valeur précédente, ce qui est très non constant. Ou, ne marquez pas le type de valeur comme const. (Ce genre de chose est généralement le résultat ultime de const_cast, donc c'est presque toujours un drapeau rouge indiquant une erreur ailleurs.)
Potatoswatter
@Potatoswatter Vous avez raison. Je vois juste que const_cast [] est utilisé avec des valeurs const map par certaines personnes lorsqu'elles sont sûres qu'elles ne remplaceront pas une ancienne valeur dans certains bits de code; puisque [] lui-même est plus lisible. Comme je l'ai mentionné dans la dernière partie de ma réponse, je recommanderais d'utiliser insertdans les cas où vous souhaitez empêcher l'écrasement des valeurs. (Vient de changer le inputen insert- merci)
dk123
@Potatoswatter Si je me souviens bien, les principales raisons pour lesquelles les gens semblent utiliser const_cast<T>(map[key])étaient 1. [] est plus lisible, 2. ils ont confiance en certains morceaux de code, ils ne remplaceront pas les valeurs, et 3. ils ne le font pas veulent que d'autres bits de code inconnu écrasent leurs valeurs - d'où le const value.
dk123
2
Je n'ai jamais entendu parler de cela. Où avez-vous vu cela? L'écriture const_castsemble plus que nier la "lisibilité" supplémentaire de [], et ce genre de confiance est presque suffisant pour licencier un développeur. Les conditions d'exécution difficiles sont résolues par des conceptions pare-balles, et non par des sentiments intestinaux.
Potatoswatter
@Potatoswatter Je me souviens que c'était au cours de l'un de mes précédents emplois dans le développement de jeux éducatifs. Je n'ai jamais pu amener les gens à écrire le code pour changer leurs habitudes. Vous avez absolument raison et je suis tout à fait d'accord avec vous. D'après vos commentaires, j'ai décidé que cela valait probablement plus la peine d'être noté que ma réponse d'origine et je l'ai donc mise à jour pour refléter cela. Merci!
dk123
1

Le fait que la fonction std :: map insert()n'écrase pas la valeur associée à la clé nous permet d'écrire du code d'énumération d'objet comme ceci:

string word;
map<string, size_t> dict;
while(getline(cin, word)) {
    dict.insert(make_pair(word, dict.size()));
}

C'est un problème assez courant lorsque nous devons mapper différents objets non uniques à certains identifiants dans la plage 0..N. Ces identifiants peuvent être utilisés ultérieurement, par exemple, dans des algorithmes de graphe. Une alternative avec operator[]semblerait moins lisible à mon avis:

string word;
map<string, size_t> dict;
while(getline(cin, word)) {
    size_t sz = dict.size();
    if (!dict.count(word))
        dict[word] = sz; 
} 
mécatron
la source