प्रदर्शन क़ायम करना

Question

के बाद मैं एक VALUE_TYPE के साथ एक std::unordered_map कि एक डिफ़ॉल्ट निर्माता नहीं है तो मैं निम्नलिखित

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

मैं एक सहायक समारोह

लेखन समाप्त हो गया ऐसा नहीं कर सकते है की जांच से भी बदतर है

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

लेकिन प्रदर्शन निम्न संस्करण की तुलना में काफी खराब था (यानी मान_ प्रकार का कन्स्ट्रक्टर पेर्फ में दिखाया गया था)।

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

मैं std::unordered_map::emplace object creation कि जरूरतों को क़ायम करना आदेश अगर मौजूद है को देखने के लिए वस्तु के निर्माण के लिए से पढ़ें। लेकिन प्रतिस्थापन यह देखने के लिए जांच कर रहा है कि यह कुंजी मान जोड़ी वापस आने से पहले मानचित्र में मौजूद है या नहीं।

क्या मैं गलत तरीके से जगह का उपयोग कर रहा हूं?

1. मेरी VALUE_TYPE (मेरी पहली विधि के रूप में) हर देखने का निर्माण नहीं होगा
2. जांच नहीं करेंगे, तो VALUE_TYPE दो बार मेरे नक्शे में मौजूद है को देखने के लिए: वहाँ एक बेहतर पैटर्न मैं पालन करना चाहिए कि है (मेरी दूसरी विधि में के रूप में)

धन्यवाद

Answer 1

आपका कोड दुर्भाग्य से मानक लाइब्रेरी के लिए इष्टतम है क्योंकि यह वर्तमान में है।

समस्या यह है कि emplace आपरेशन नकल से बचने के लिए, मैप नहीं किया प्रकार के अनावश्यक निर्माण से बचने के लिए बनाया गया है। व्यावहारिक शब्दों में, क्या होता है कि कार्यान्वयन एक नोड को आवंटित करता है और बनाता है जिसमें नक्शा value_type यानी pair<const Key, T>, और है, तो यह निर्धारित करने के लिए कुंजी है कि निर्मित नोड कंटेनर में जोड़ा जा सकता है; अगर यह टकराता है तो नोड हटा दिया जाता है।

जब तक hash और equal_to बहुत महंगा नहीं है, तो आपके कोड को बहुत अधिक काम नहीं करना चाहिए।

एक वैकल्पिक आवंटक का उपयोग करना एक विकल्प है जो आपके मैप किए गए प्रकार के 0-तर्क निर्माण को रोकता है;

#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

आप क्रम में boost::optional<T> का उपयोग मैप किया प्रकार का निर्माण डिफ़ॉल्ट और फिर इसे करने के लिए एक प्रारंभ T आवंटित बाद में सक्षम होने के लिए कर सकता है।

#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

जेम्स, आपने ज्यादातर अपने प्रश्न का उत्तर दिया है।

आप या तो कार्यान्वयन में कुछ भी गलत नहीं कर रहे हैं। emplace बस find से अधिक काम करता है, खासकर जब कुंजी आपके unordered_map में पहले से मौजूद है।

यदि आपका get_value सहायक कार्य अधिकतर डुप्लिकेट प्राप्त करता है, तो emplace पर कॉल करने से हर बार एक प्रदर्शन हॉट स्पॉट होगा जैसा आपने देखा है।