std::map insert() indicateur d'emplacement: différence entre le c++98 et c++11
Sur l'entrée cplusplus sur map::insert() j'ai lu à propos de l'emplacement que l'on pourrait ajouter comme indice pour la fonction que la "fonction optimise son temps d'insertion Si position pointe vers l'élément qui précédera l'élément inséré" pour c++98, tandis que pour c++11 l'optimisation se produit "si position pointe vers, si ce serait le dernier)".
Cela signifie-t-il que les performances des extraits de code du la forme suivante (qui est abondante dans le code hérité sur lequel je travaille et modélisée après le "STL efficace" de Scott Meyer, Article 24) a été affectée par le passage à un compilateur compatible C++11?
auto pLoc = someMap.lower_bound(someKey);
if(pLoc != someMap.end() && !(someMap.key_comp()(someKey, pLoc->first)))
return pLoc->second;
else
auto newValue = expensiveCalculation();
someMap.insert(pLoc, make_pair(someKey, newValue)); // using the lower bound as hint
return newValue;
Quelle serait la meilleure façon d'améliorer ce modèle pour une utilisation avec C++11?
4 réponses
La spécification C++98 est un défaut de la norme. Voir la discussion dans LWG question 233 et N1780.
Rappelons que lower_bound renvoie un itérateur au premier élément avec une clé non inférieure à la clé spécifiée, tandis que upper_bound renvoie un itérateur au premier élément avec une clé supérieure à la clé spécifiée. S'il n'y a pas de clé équivalente à la clé spécifiée dans le conteneur, alors lower_bound et upper_bound renvoient la même chose - un itérateur à l'élément qui serait après clé si elle était dans la carte.
Donc, en d'autres termes, votre code actuel fonctionne déjà correctement sous la spécification C++11, et en fait serait faux sous la spécification défectueuse de C++98.
Oui, cela affectera la complexité. Donner l'indice correct fera insert() avoir amorti la complexité constante, tandis que donner et l'indice incorrect forcera la carte à rechercher la position depuis le début, donnant la complexité logarithmique. Fondamentalement, un bon indice fait que l'insertion se produit en temps constant, quelle que soit la taille de votre carte; avec un mauvais indice, l'insertion sera plus lente sur des cartes plus grandes.
La solution est, apparemment, de rechercher l'indice avec upper_bound au lieu de lower_bound.
Je pense que l'insertion correcte de l'indice de style C++11 pourrait être la suivante:
iterator it = table.upper_bound(key); //upper_bound returns an iterator pointing to the first element that is greater than key
if (it == table.begin() || (--it)->first < key) {
// key not found path
table.insert(it, make_pair(key, value));
}
else {
// key found path
it->second = value;
}
Un instantané de la fonction lambda de travail pour votre référence.
auto create_or_get_iter = [this] (const K& key) {
auto it_upper = m_map.upper_bound(key);
auto it_effective = it_upper == m_map.begin() ? it_upper : std::prev(it_upper);
auto init_val = it_effective->second;
if (it_effective == m_map.begin() || it_effective->first < key) {
return m_map.insert(it_effective, std::make_pair(key, init_val));
} else {
it_effective->second = init_val;
return it_effective;
}
};