performance de emplace est pire que vérifier suivie emplace

Question

J'ai un std::unordered_map avec un value_type qui ne dispose pas d'un constructeur par défaut donc je ne peux pas faire ce qui suit

auto k = get_key(); 
auto& v = my_map[k]; 

Je fini par écrire une fonction d'aide

value_type& get_value(key_type& key) 
{ 
    return std::get<0>(my_map.emplace(
           std::piecewise_construct, 
           std::forward_as_tuple(key), 
           std::forward_as_tuple(args_to_construct_value) 
        ))->second; 
} 

mais les performances étaient nettement plus mauvaises (ie le constructeur de value_type apparu dans perf) que la version suivante.

value_type& get_value(key_type& key) 
{ 
    auto it = my_map.find(key); 
    if (it == my_map.end()) 
     return std::get<0>(my_map.emplace(
            std::piecewise_construct, 
            std::forward_as_tuple(key), 
            std::forward_as_tuple(args_to_construct_value) 
         ))->second; 
    else 
     return it->second; 
} 

Je lis de std::unordered_map::emplace object creation que emplace besoins pour construire l'objet afin de voir si elle existe. Mais emplace vérifie si cette paire de valeurs de clé existe dans la carte avant son retour. Est-ce que j'utilise emplace dans le mauvais sens? Y at-il un meilleur modèle que je dois suivre que:

1. ne construira pas mon value_type chaque recherche (comme dans ma première méthode)
2. ne fera pas le chèque pour voir si value_type existe dans ma carte deux fois (comme dans ma deuxième méthode)

Merci

Answer 1

Votre code est malheureusement optimal pour la bibliothèque standard telle qu'elle est actuellement.

Le problème est que l'opération emplace est conçue pour éviter la copie, pour ne pas éviter la construction inutile du type mappé. En termes pratiques, ce qui se passe est que l'implémentation alloue et construit un nœud, contenant la carte value_type, c'est-à-dire pair<const Key, T>, et puis hache la clé pour déterminer si le nœud construit peut être lié dans le conteneur; Si cela se produit, le noeud est supprimé.

Tant que hash et equal_to ne sont pas trop chers, votre code ne devrait pas faire trop de travail supplémentaire.

Une alternative est d'utiliser un allocateur personnalisé interceptant construction 0 argument de votre type cartographié; le problème est que la détection telle construction est assez Checklist:

#include <unordered_map> 
#include <iostream> 

using Key = int; 
struct D { 
    D() = delete; 
    D(D const&) = delete; 
    D(D&&) = delete; 
    D(std::string x, int y) { std::cout << "D(" << x << ", " << y << ")\n"; } 
}; 
template<typename T> 
struct A { 
    using value_type = T; 
    using pointer = T*; 
    using const_pointer = T const*; 
    using reference = T&; 
    using const_reference = T const&; 
    template<typename U> struct rebind { using other = A<U>; }; 
    value_type* allocate(std::size_t n) { return std::allocator<T>().allocate(n); } 
    void deallocate(T* c, std::size_t n) { std::allocator<T>().deallocate(c, n); } 
    template<class C, class...Args> void construct(C* c, Args&&... args) { std::allocator<T>().construct(c, std::forward<Args>(args)...); } 
    template<class C> void destroy(C* c) { std::allocator<T>().destroy(c); } 

    std::string x; int y; 
    A(std::string x, int y): x(std::move(x)), y(y) {} 
    template<typename U> A(A<U> const& other): x(other.x), y(other.y) {} 
    template<class C, class...A> void construct(C* c, std::piecewise_construct_t pc, std::tuple<A...> a, std::tuple<>) { 
     ::new((void*)c)C(pc, a, std::tie(x, y)); } 
}; 

int main() { 
    using UM = std::unordered_map<Key, D, std::hash<Key>, std::equal_to<Key>, A<std::pair<const Key, D>>>; 
    UM um(0, UM::hasher(), UM::key_equal(), UM::allocator_type("hello", 42)); 
    um[5]; 
} 

Answer 2

Vous pouvez utiliser boost::optional<T> afin de pouvoir construire le type par défaut mappé et puis attribuez-lui une initialisation T plus tard.

#include <cassert> 
#include <unordered_map> 
#include <boost/optional.hpp> 

struct MappedType 
{ 
    explicit MappedType(int) {} 
}; 

int main() 
{ 
    std::unordered_map<int, boost::optional<MappedType>> map; 
    boost::optional<MappedType>& opt = map[0]; 
    assert(!opt.is_initialized()); 
    opt = MappedType(2); 
    assert(opt.is_initialized()); 
    MappedType& v = opt.get(); 
} 

Answer 3

James, vous avez surtout répondu à votre propre question.

Vous ne faites rien de mal dans les deux implémentations. emplace fait simplement plus de travail que find, surtout lorsque la clé existe déjà dans votre unordered_map. Si votre fonction d'assistance get_value reçoit la plupart du temps des doublons, appeler emplace à chaque fois provoquera un point chaud de performance comme vous l'avez observé.