Emplacement ou fusion sur std::unordered_set

Question

J'essaie de mettre en œuvre ce système de remplacement ou de fusion.

template<typename T>
T& EmplaceOrMerge(std::unordered_set<T>& s,
                  T&& t,
                  std::function<void(T&& a, T& b)> merge)
{
    auto it = s.emplace(std::move(t));
    T& u = const_cast<T&>(*it.first);
    if (!it.second)
        merge(std::move(t), u);
    return u;
}

La fonction de fusion modifie son deuxième argument de manière à préserver sa valeur hachée. Je m'intéresse à l'utilisation de la fonction std::move(t) dans le cas de la fusion, car le emplace l'a peut-être déjà déplacé. J'ai lu la mise en œuvre par Microsoft de unordered_set et il existe un cas particulier très intéressant, if constexpr (_In_place_key_extractor::_Extractable) . Elle reconnaît que son argument std::move(t) peut être hachée directement (et comparée à operator== directement), sans construire un autre objet T et renvoie immédiatement la valeur équivalente dans le unordered_set quand il y en a un.

Ce cas particulier se produit-il dans toutes les implémentations de la bibliothèque standard ? Si ce n'est pas le cas, j'ai un comportement non défini, et je me demande s'il y a une autre façon de coder cela. EmplaceOrMerge .

Answer 1

Non, libstdc++ n'effectue pas cette optimisation.

struct A {
    A() = default;
    A(A&&) { std::format_to(std::ostreambuf_iterator<char>(std::cout), "A(A&&)\n"); }
    bool operator==(A const&) const = default;
};
template<> struct std::hash<A> { std::size_t operator()(A const&) const { return 0; } };
int main() {
    std::unordered_set<A> s;
    A a;
    std::format_to(std::ostreambuf_iterator<char>(std::cout), "{}\n",
        s.emplace(std::move(a)).second);
    std::format_to(std::ostreambuf_iterator<char>(std::cout), "{}\n",
        s.emplace(std::move(a)).second);
}

Ce programme imprime :

A(A&&)
true
false

sous libc++ (et, vraisemblablement, sous MS-STL), mais imprime

A(A&&)
true
A(A&&)
false

sous libstdc++.

Démonstration .

---

Je me demande s'il n'y a pas une autre façon de coder cela EmplaceOrMerge .

Vous ne pouvez pas contourner le fait que libstdc++ n'appellera que Hash sur un nœud déjà construit. Si vous ne pouvez pas modifier la structure des données (par exemple, en passant à une structure std::unordered_map à partir d'une clé extraite), une option serait d'utiliser la fonction poignée de nœud ce qui permet d'éviter les effets de bord en cas d'échec de l'insertion. Son utilisation peut encore entraîner le coût d'un déplacement et d'une réaffectation de déplacement, mais il faut espérer que cela soit relativement peu coûteux :

template<class T>
auto try_emplace(std::unordered_set<T>& s, std::type_identity_t<T>&& t) {
    std::unordered_set<T> s2;
    auto nh = s2.extract(s2.insert(std::move(t)).first);
    auto const ins = s.insert(std::move(nh));
    if (not ins.inserted)
        t = std::move(ins.node.value());
    return std::pair(ins.position, ins.inserted);
}

Démonstration .

Et dans votre cas, vous pouvez raccourcir le déplacement-assignation en retour, de sorte que le surcoût n'est que d'un déplacement (et d'une allocation de nœud supplémentaire) :

template<typename T>
T& EmplaceOrMerge(std::unordered_set<T>& s,
                  T&& t,
                  std::function<void(T&& a, T& b)> merge)
{
    std::unordered_set<T> s2;
    auto nh = s2.extract(s2.insert(std::move(t)).first);
    auto const ins = s.insert(std::move(nh));
    T& u = const_cast<T&>(*ins.position);
    if (not ins.inserted)
        merge(std::move(ins.node.value()), u);
    return u;
}

Answer 2

std::unordered_set stocke des clés uniques, donc avant l'insertion, il vérifie si la clé est déjà présente dans la table de hachage. Si la clé est déjà présente, aucune insertion n'est effectuée et l'élément n'est donc pas construit sur place. Dans cppreference, la fonction emplace est décrite comme "insérer un nouvel élément dans le conteneur construit sur place avec les arguments donnés s'il n'y a pas d'élément avec la clé dans le conteneur". Plus bas, il est également écrit "l'élément peut être construit même s'il existe déjà un élément avec la clé dans le conteneur, auquel cas l'élément nouvellement construit sera détruit immédiatement". Cette action pourrait donc laisser l'élément dans un état non spécifié, en fonction de l'implémentation de son constructeur de déplacement. Le problème principal est que vous ne devriez pas utiliser emplace(Args&&...) à cause de ce que j'ai mentionné précédemment et, en particulier, il effectue une construction in-place alors que vous déplacez simplement T. Vous devez passer les arguments à emplace utiliser un transfert parfait si vous voulez vraiment construire l'élément sur place, et ne pas utiliser de transfert.

Depuis que @krisz m'a commenté une réponse intéressante au sujet de la insert(value_type&&) qui peut laisser l'élément dans un état non spécifié (elle ne garantit pas que l'opérateur d'affectation move ou le constructeur move ne sont appelés que si la clé n'existe pas et que l'insertion doit alors être effectivement réalisée), je vous conseille de modifier votre code et de vérifier si la clé existe déjà avant de l'insérer ou de la déplacer.