Quel est le moyen le plus rapide de l'insertion/mise à jour std::unordered_map éléments sans l'aide d'un si?

J'ai actuellement beaucoup de code qui ressemble à ceci:

std::unordered_map<int,int> my_dict;
.
.
.
//If the key does exist in the dictionary
if(my_dict.count(key) == 1){
    my_dict[key] = value;
}

//If its a new key
else{
    my_dict.insert(std::make_pair(key,value));
}

Est il possible que je peux de la vitesse d'écrasement de la valeur à chaque fois?

  • On dirait que vous devez utiliser une carte
  • Je veux O(1) moment de l'insertion? Je ne veux pas d'un arbre O log(N)
  • le [] est-ce. cplusplus.com/reference/unordered_map/unordered_map/operator[] bien sûr, la complexité doit être linéaire. Si vous voulez moins de l'insertion, l'utilisation d'une carte
  • my_dict[key] = value; est tout que vous avez besoin d'aide, si nécessaire.
  • linéaire est que le pire des cas. si vous êtes uniquement intéressé au coût amorti, le passage à la carte est une très mauvaise idée.
  • Les chances d'être linéaire, est extrêmement dérivés cas. Il la plupart des cas, il sera O(1) ou très proche.
  • Vous avez raison, je viens de réaliser que non ordonnée carte utilise aussi certains seau comme mécanisme de stockage.
  • ont ajouté un edit
  • Utilisation (*my_dict_ptr)[key] ou my_dict_ptr->operator[](key) ensuite.
  • Si vous souhaitez mettre à jour la valeur à chaque fois, puis il suffit d'aller pour my_dict[clé] = valeur. Toutefois, si vous ne voulez pas mettre à jour la valeur d'une clé existante, puis votre code est correct (et plus rapide).

InformationsquelleAutor user997112 | 2013-10-05
  1. 47

    Vous venez de le faire (pour map et unordered_map)

    mydict[key]=value;
    • à l'aide de if-else serait plus rapide si et seulement si le défaut de construction de value est très cher. Cependant, dans la plupart des cas operator[] fait le travail.
    InformationsquelleAutor Joe
  2. 17

    Je pense qu'il pourrait être plus rapide comme ceci:

    auto it = my_dict.find(key);
if( it != my_dict.end() ) {
    *it = value;
}
else {
    my_dict.insert(std::make_pair(key,value));
}

    de cette façon, vous ne modifiez pas la structure de la unordered_map si le key existe déjà et vous n'avez qu'une recherche.

    Une autre option dans le cas où vous n'avez pas besoin d'accès/value après:

    my_dict[key] = std::move(value);

    Ce peut-être mieux dans les cas où la cession de value est cher et les avantages de se déplacer-sémantique.

    • Pourquoi le faire si operator[] fait exactement ce déjà?
    • Pour la plupart, mais dans l'insert cas, il insère d'abord un défaut de la valeur construite, puis l'affecte. Le ci-dessus évite que les frais généraux.
    • J'aimerais faire un peu de sérieux mesure de le cas simple (foo[key]=value;) avant d'aller dans cette voie.
    • Oui. Sans l'exécution d'un profil qui montre que c'est un problème, optez pour le code plus lisible. Que aurait ont été ma réponse quand cette question de l'absence de la "performance" de la balise 🙂
    • Mon expérience est la plupart des gens qui interprètent mal les choses sont à la traîne sur leurs performances. J'imagine que la différence de performances entre les OP du code et solution ici pour être très petites, dans un unordered_map...
    • Le value_type est pair<const int, int>. Toute surcharge de la plus susceptible d'être optimisé à l'écart.
    • Pour cet exemple, oui. Je pensais à propos du cas générique.

    InformationsquelleAutor Daniel Frey
  3. 4

    De mise à jour pour le C++17, vous pouvez utiliser:

    std::unordered_map::insert_or_assign()

    http://en.cppreference.com/w/cpp/container/unordered_map/insert_or_assign

    InformationsquelleAutor htmlboss
  4. 1

    Habituellement, vous éviter la saisie de texte supplémentaire par le biais de la définition d'une fonction qui vous évite de taper le même.
    Si vous n'avez pas accès à C++17 insert_or_assign(), vous pouvez mettre en place quelque chose comme ça par vous même:

    bool InsertOrAssign(std::unordered_map& m, int key, int value) {
  //Your code or one of the suggested answers goes here
}
    InformationsquelleAutor Serge Rogatch