prestazioni del colloco è peggiore di controllo seguita da colloco

Question

Ho un std::unordered_map con un value_type che non ha un costruttore di default, quindi non posso fare quanto segue

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

ho finito per scrivere una funzione di supporto

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; 
} 

ma la prestazione è stata nettamente peggiore (ovvero il costruttore value_type si è mostrato in perf) rispetto alla seguente versione.

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; 
} 

Ho letto da std::unordered_map::emplace object creation che colloco esigenze per costruire l'oggetto per vedere se esiste. Ma emplace sta controllando per vedere se questa coppia di valori chiave esiste nella mappa prima che ritorni.

Sto usando emplace nel modo sbagliato? C'è un modello migliore che devo seguire:

1. non costruirà il mio value_type ogni ricerca (come nel mio primo metodo)
2. non farà il controllo per per vedere se value_type esiste nella mia mappa due volte (come nel mio secondo metodo)

Grazie

Answer 1

Il tuo codice è purtroppo ottimale per la libreria standard così com'è attualmente.

Il problema è che l'operazione emplace è progettata per evitare la copia , non per evitare la costruzione non necessaria del tipo mappato. In pratica, ciò che accade è che l'implementazione alloca e costruisce un nodo, contenente la mappa value_type, ovvero pair<const Key, T> e quindi hash la chiave per determinare se il nodo costruito può essere collegato nel contenitore; se questo collide, il nodo viene eliminato.

Finché hash e equal_to non sono troppo costosi, il tuo codice non dovrebbe fare troppo lavoro extra.

Un'alternativa è utilizzare un allocatore personalizzato che intercetta la costruzione di argomenti 0 del tipo mappato; il problema è che la rilevazione tale costruzione è piuttosto laborioso:

#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

si potrebbe usare boost::optional<T> per essere in grado di default costruire il tipo mappato e quindi assegnare un inizializzato T in un secondo momento.

#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, hai risposto per lo più alla tua stessa domanda.

Non stai facendo nulla di sbagliato in entrambe le implementazioni. emplace fa semplicemente più lavoro di find, soprattutto quando la chiave esiste già nel tuo unordered_map.

Se la tua funzione di supporto get_value riceve principalmente duplicati, chiamare emplace ogni volta causerà un punto caldo di prestazioni come hai osservato.