wydajność emplace jest gorsza niż czekiem następnie emplace

Question

mam std::unordered_map z VALUE_TYPE że nie ma domyślnego konstruktora, więc nie mogę wykonać następujące czynności

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

skończyło się na napisanie funkcji pomocnika

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

ale wydajność była znacznie gorsza (tj. Konstruktor value_type pojawił się w perf) niż następująca wersja.

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

czytam od std::unordered_map::emplace object creation że emplace potrzeby do budowy obiektu w celu sprawdzenia, czy istnieje. Ale emplace sprawdza, czy ta para wartości klucza istnieje na mapie przed jej zwróceniem.

Czy używam emplace w niewłaściwy sposób? Czy istnieje lepszy wzorzec powinien wynikać, że:

1. nie zbuduje mój VALUE_TYPE każdego odnośnika (jak w moim pierwszym metody)
2. nie zrobi czek, aby zobaczyć czy VALUE_TYPE istnieje w mojej mapie dwukrotnie (jak w moim drugim sposobie)

Dzięki

Answer 1

Twój kod jest niestety optymalny dla standardowej biblioteki, tak jak jest obecnie.

Problem polega na tym, że operacja emplace została zaprojektowana w celu uniknięcia kopiowania , aby uniknąć niepotrzebnej konstrukcji zmapowanego typu. W praktyce chodzi o to, że implementacja przydziela i konstruuje węzeł zawierający mapę value_type, to jesti , a następnie miesza klucz, aby ustalić, czy skonstruowany węzeł może być połączony z pojemnikiem; jeśli to się zderza, wówczas węzeł zostanie usunięty.

Dopóki hash i equal_to nie są zbyt drogie, Twój kod nie powinien wykonywać zbyt dużo dodatkowej pracy.

Alternatywą jest użycie niestandardowego przydziału, który przechwytuje konstrukcję odwzorowanego typu 0; problemem jest to, że wykrycie takiej konstrukcji jest dość skomplikowanego:

#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

można użyć boost::optional<T> aby móc skonstruować domyślnie odwzorowany typ, a następnie przypisać zainicjowany T do niego później.

#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, w większości odpowiedziałeś na własne pytanie.

Nie robisz nic złego w żadnej z implementacji. emplace po prostu robi więcej pracy niż find, zwłaszcza gdy klucz już istnieje w twoim unordered_map.

Jeśli twoja funkcja pomocnika get_value przeważnie odbiera duplikaty, wywołanie emplace za każdym razem spowoduje, że zaobserwujesz gorącą wydajność.