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

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

La réponse est que vous ne faites ni l'un ni l'autre. Au lieu de cela, vous voulez faire quelque chose suggéré par l'article 24 de Effective STL 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
}

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 valeur tel qu'un int, ce qui précède sera plus efficace qu'une recherche suivie d'une insertion (en l'absence d'optimisations du compilateur). Comme indiqué ci-dessus, cela est dû au fait que la recherche sur la carte n'a lieu qu'une seule fois.

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

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;
  }
}

Afin d'appeler «insert», 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 la modification 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 devons construire l'élément.

Vous pouvez également modifier le type de valeur de la carte pour stocker les poignées des données à l'aide de votre type de pointeur intelligent préféré. L'appel à insérer utilise un pointeur nul (très bon marché à construire) et seulement si nécessaire le nouveau type de données est construit.

Il n'y aura pratiquement aucune différence de vitesse entre les 2, find renverra un itérateur, insert fait de même et cherchera quand même sur la carte pour déterminer si l'entrée existe déjà.

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

Je pense que si vous faites une recherche puis insérez, le coût supplémentaire serait lorsque vous ne trouvez pas la clé et effectuez l'insertion après. C'est un peu comme regarder les livres par ordre alphabétique et ne pas trouver le livre, puis regarder à nouveau les livres pour voir où l'insérer. Cela se résume à la façon dont vous gérerez les clés et si elles changent constamment. Maintenant, il y a une certaine flexibilité en ce que si vous ne le trouvez pas, vous pouvez vous connecter, exception, faire ce que vous voulez ...

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

Find 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 qui ne figure pas déjà sur la carte car il devra rechercher deux fois. Une fois pour voir si c'est là, encore une fois pour trouver l'endroit où mettre la nouvelle chose.

Si vous êtes préoccupé par l'efficacité, vous pouvez consulter hash_map <> .

Typiquement, la carte <> est implémentée sous la forme d'un arbre binaire. Selon vos besoins, un hash_map peut être plus efficace.

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

Toute réponse sur l'efficacité dépendra de la mise en œuvre exacte de votre STL. La seule façon de savoir avec certitude est de le comparer dans les deux sens. Je suppose que la différence ne sera probablement pas significative, alors décidez en fonction du style que vous préférez.

map [key] - laissez stl le trier. C'est communiquer votre intention le plus efficacement.

Ouais, assez bien.

Si vous faites une recherche, puis une insertion, vous effectuez 2 x O (log N) lorsque vous obtenez un échec car la recherche vous permet seulement de savoir si vous devez insérer pas où l'insert doit aller (lower_bound pourrait vous aider) . Juste un insert direct et ensuite examiner le résultat est la voie que j'irais.