std::map insérer ou std::map trouver?

Question

En supposant une carte où vous souhaitez conserver les données existantes. 20% du temps, l'entrée de l'insertion est de nouvelles données. Est-il avantageux de faire std::map::trouver puis de std::map::insert à l'aide de ce qui est retourné itérateur? Ou est-il plus rapide pour essayer de l'insérer, puis d'agir en fonction de savoir si ou de ne pas l'itérateur indique que l'enregistrement a été ou n'a pas été inséré?

Answer 1

La réponse est que vous n'avez ni. Au lieu de cela vous voulez faire quelque chose suggéré par l'Article 24, de de Efficace 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
}

Answer 2

La réponse à cette question dépend aussi de la façon dont elle est chère pour créer le type de valeur que vous voulez enregistrer 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 une valeur de type int, la ci-dessus sera plus efficace que de trouver un suivi par un insert (en l'absence d'optimisations du compilateur). Comme indiqué ci-dessus, c'est parce que la recherche par le biais de la carte n'ait lieu qu'une fois.

Toutefois, l'appel à insérer exige que vous ont déjà la nouvelle "valeur" de construction:

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 les "insérer" nous payons cher pour les appels à construire notre type de valeur - et de ce que vous avez dit dans la question, vous n'aurez pas à utiliser cette nouvelle valeur de 20% du temps. Dans le cas ci-dessus, si la modification de la valeur de la carte type n'est pas une option, alors il est plus efficace de le premier effectuer le "trouver" pour vérifier si nous avons besoin de construire l'élément.

Sinon, le type de la valeur de la carte peut être changé pour stocker des poignées pour les données à l'aide de votre préféré type pointeur intelligent. L'appel à insérer utilise un pointeur null (très bon marché, de construire), et seulement si nécessaire, est le nouveau type de données construites.

Answer 3

Il y aura à peine une différence de vitesse entre les 2, trouver retourne un itérateur, insérer fait de même et va chercher la carte de toute façon à déterminer si l'entrée existe déjà.

Donc.. de son à vos préférences personnelles. J'essaie toujours d'insérer et mettre à jour si nécessaire, mais certaines personnes n'aiment pas la manipulation de la paire qui est retourné.

Answer 4

Je pense que si vous faites une recherche insérez ensuite, le coût supplémentaire serait lorsque vous ne trouvez pas la clé et la réalisation de l'insérer après. C'est un peu comme regarder à travers les livres dans l'ordre alphabétique et de ne pas trouver le livre, puis en regardant à travers les livres de nouveau pour voir où l'insérer. Il se résume à comment vous allez gérer les clés et s'ils sont en constante évolution. Maintenant, il existe une certaine souplesse dans la mesure où si vous ne le trouvez pas, vous pouvez vous connecter, à l'exception, faire ce que vous voulez...

Answer 5

Je suis perdu sur le haut de réponse.

Trouver retourne la carte.fin() s'il ne trouve pas quelque chose 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 pas déjà dans la carte car il devront trouver deux fois. Une fois pour voir si il y est, encore une fois pour trouver la place pour mettre les chose de nouveau.