std :: map insert ou std :: map find?

Question

En supposant une carte où vous souhaitez conserver les entrées existantes. 20% du temps, l'entrée que vous insérez est constituée de nouvelles données. Y at-il un avantage à faire std :: map :: find puis std :: map :: insert en utilisant cet itérateur retourné? Ou est-il plus rapide de tenter l’insertion, puis d’agir en fonction du fait que l’itérateur indique ou non que l’enregistrement a été inséré?

Answer 1

La réponse est que vous ne faites ni l'un ni l'autre. Au lieu de cela, vous souhaitez effectuer une tâche suggérée par l’article 24 de LIST en vigueur par Scott Meyers :

typedef map<int, int> MapType;    // Your map type may vary, just change the typedef

MapType mymap;
// Add elements to map here
int k = 4;   // assume we're searching for keys equal to 4
int v = 0;   // assume we want the value 0 associated with the key of 4

MapType::iterator lb = mymap.lower_bound(k);

if(lb != mymap.end() && !(mymap.key_comp()(k, lb->first)))
{
    // key already exists
    // update lb->second if you care to
}
else
{
    // the key does not exist in the map
    // add it to the map
    mymap.insert(lb, MapType::value_type(k, v));    // Use lb as a hint to insert,
                                                    // so it can avoid another lookup
}

Answer 2

La réponse à cette question dépend également du coût de création du type de valeur que vous stockez dans la carte:

typedef std::map <int, int> MapOfInts;
typedef std::pair <MapOfInts::iterator, bool> IResult;

void foo (MapOfInts & m, int k, int v) {
  IResult ir = m.insert (std::make_pair (k, v));
  if (ir.second) {
    // insertion took place (ie. new entry)
  }
  else if ( replaceEntry ( ir.first->first ) ) {
    ir.second->second = v;
  }
}

Pour un type de valeur tel qu'un int, ce qui précède sera plus efficace qu'une recherche suivie d'un insert (en l'absence d'optimisation du compilateur). Comme indiqué ci-dessus, cela est dû au fait que la recherche sur la carte n’est effectuée qu’une seule fois.

Cependant, l'appel à insérer nécessite que vous ayez déjà la nouvelle " valeur " construit:

class LargeDataType { /* ... */ };
typedef std::map <int, LargeDataType> MapOfLargeDataType;
typedef std::pair <MapOfLargeDataType::iterator, bool> IResult;

void foo (MapOfLargeDataType & m, int k) {

  // This call is more expensive than a find through the map:
  LargeDataType const & v = VeryExpensiveCall ( /* ... */ );

  IResult ir = m.insert (std::make_pair (k, v));
  if (ir.second) {
    // insertion took place (ie. new entry)
  }
  else if ( replaceEntry ( ir.first->first ) ) {
    ir.second->second = v;
  }
}

Pour appeler "insérer", nous payons l'appel coûteux pour construire notre type de valeur - et d'après ce que vous avez dit dans la question, vous n'utiliserez pas cette nouvelle valeur 20% du temps. Dans le cas ci-dessus, si le changement du type de valeur de la carte n’est pas une option, il est alors plus efficace d’effectuer d’abord la recherche pour vérifier si nous avons besoin de construire l’élément.

Vous pouvez également modifier le type de valeur de la carte pour stocker les descripteurs dans les données à l'aide de votre type de pointeur intelligent favori. L’appel à insérer utilise un pointeur null (construction très économique) et le nouveau type de données n’est construit que si nécessaire.

Answer 3

Il y aura à peine une différence de vitesse entre les 2, find retournera un itérateur, l'insertion fera de même et recherchera quand même la carte pour déterminer si l'entrée existe déjà.

Alors ... c'est une préférence personnelle. J'essaie toujours d'insérer, puis de mettre à jour si nécessaire, mais certaines personnes n'aiment pas manipuler la paire renvoyée.

Answer 4

Je pense que si vous faites une recherche puis une insertion, le coût supplémentaire serait lorsque vous ne trouvez pas la clé et que vous ne l'insérez pas après. C'est un peu comme regarder dans les livres dans l'ordre alphabétique et ne pas trouver le livre, puis regarder à nouveau dans les livres pour voir où l'insérer. Cela dépend de la manière dont vous allez manipuler les clés et de leur évolution constante. Maintenant, il y a une certaine flexibilité dans le fait que si vous ne le trouvez pas, vous pouvez vous connecter, faire exception, faire ce que vous voulez ...

Answer 5

Je suis perdu sur la première réponse.

Rechercher renvoie map.end () s'il ne trouve rien, ce qui signifie que si vous ajoutez de nouvelles choses, alors

iter = map.find();
if (iter == map.end()) {
  map.insert(..) or map[key] = value
} else {
  // do nothing. You said you did not want to effect existing stuff.
}

est deux fois plus lent que

map.insert

pour tout élément ne figurant pas déjà dans la carte car il devra effectuer une recherche deux fois. Une fois pour voir si c'est là, encore une fois pour trouver l'endroit où mettre la nouvelle chose.

Answer 6

Si l'efficacité vous préoccupe, vous pouvez consulter hash_map < > .

Carte typique < > est implémenté comme un arbre binaire. Selon vos besoins, un hash_map peut être plus efficace.

Answer 7

Je ne semble pas avoir assez de points pour laisser un commentaire, mais la réponse cochée semble être longue pour moi - quand vous considérez que insert renvoie de toute façon l'itérateur, pourquoi aller chercher lower_bound, quand vous pouvez simplement utiliser le itérateur est revenu. Étrange.

Answer 8

Toute réponse concernant l’efficacité dépendra de la mise en œuvre exacte de votre STL. La seule façon de savoir avec certitude est de faire une analyse comparative dans les deux sens. J'imagine que la différence est peu susceptible d'être significative, alors décidez-vous en fonction du style que vous préférez.

Answer 9

map [key] - laissez stl le résoudre. C'est ce qui communique le plus efficacement possible à vos intentions.

Oui, assez bien.

Si vous effectuez une recherche, puis une insertion, vous effectuez 2 x O (journal N) lorsque vous obtenez une erreur, car la recherche vous permet uniquement de savoir si vous devez insérer ou non l'insertion dans laquelle l'insertion doit être effectuée (lower_bound pourrait vous aider vous y). Juste une insertion directe et ensuite examiner le résultat est la voie que je voudrais aller.