thực hiện đặt vào một chỗ là tồi tệ hơn séc tiếp theo đặt vào một chỗ

Question

Tôi có một std::unordered_map với một value_type mà không có một constructor mặc định vì vậy tôi không thể làm như sau

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

tôi đã kết thúc viết một hàm helper

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

nhưng hiệu suất kém hơn rõ rệt (tức là hàm tạo của value_type xuất hiện trong trạng thái hoàn hảo) so với phiên bản sau.

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

Tôi đọc từ std::unordered_map::emplace object creation mà emplace cần xây dựng đối tượng để xem có tồn tại không. Nhưng emplace đang kiểm tra xem liệu cặp giá trị khóa này tồn tại trong bản đồ trước khi nó trả về.

Tôi có đang sử dụng địa điểm không đúng cách không? Có một mô hình tốt hơn tôi nên làm theo rằng:

1. Sẽ không xây dựng value_type tôi mỗi tra cứu (như trong phương pháp đầu tiên của tôi)
2. Sẽ không làm việc kiểm tra cho thấy nếu value_type tồn tại trong bản đồ của tôi hai lần (như trong phương pháp thứ hai của tôi)

Cảm ơn

Answer 1

Mã của bạn không may là tối ưu cho thư viện chuẩn như hiện tại.

Vấn đề là hoạt động emplace được thiết kế để tránh sao chép, không để tránh việc xây dựng không cần thiết loại ánh xạ. Trên thực tế, điều xảy ra là việc triển khai phân bổ và xây dựng một nút, chứa bản đồ value_type tức là pair<const Key, T> và sau đó băm khóa để xác định liệu nút được xây dựng có thể được liên kết trong vùng chứa hay không; nếu điều này va chạm thì nút sẽ bị xóa.

Miễn là hash và equal_to không quá đắt, mã của bạn không được thực hiện quá nhiều công việc phụ.

Cách khác là sử dụng trình phân bổ tùy chỉnh ngăn chặn việc xây dựng 0 đối số của loại ánh xạ của bạn; vấn đề là phát hiện xây dựng như vậy là khá khó sử dụng:

#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

Bạn có thể sử dụng boost::optional<T> để có thể để mặc định xây dựng các loại bản đồ và sau đó gán một khởi T để nó sau này.

#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, bạn chủ yếu trả lời câu hỏi của riêng bạn.

Bạn không làm gì sai trong việc triển khai. emplace chỉ hoạt động hiệu quả hơn find, đặc biệt khi khóa đã tồn tại trong unordered_map của bạn.

Nếu chức năng trợ giúp get_value của bạn hầu hết nhận được bản sao, sau đó gọi emplace mỗi lần sẽ gây ra một điểm nóng hiệu năng như bạn đã quan sát.