C++: value_type so với make_pair, nhanh hơn để chèn bản đồ?

Question

typedef map<KeyType, ValType> KVMap; 
KVMap kvmap; 

kvmap.insert(KVMap::value_type(key, val)); 
kvmap.insert(make_pair(key, val)); 

Lựa chọn nào ở trên để chèn vào bản đồ STL luôn nhanh hơn? Tại sao?

Lưu ý: Tôi biết rõ rằng insert() nhanh hơn sử dụng []= để thêm (không cập nhật) cặp khóa-giá trị vào bản đồ. Hãy giả sử rằng truy vấn của tôi là về việc thêm, không cập nhật. Do đó tôi đã hạn chế nó để insert().

Answer 1

Rất có thể là người đầu tiên sẽ 'epsilon-nhanh', vì điều này (từ 23.3.1 trong tiêu chuẩn):

typedef pair<const Key, T> value_type; 

[...] 

pair<iterator, bool> insert(const value_type& x); 

• Trong phiên bản đầu tiên, bạn trực tiếp xây dựng loại thích hợp được mong đợi bởi std::map<K,V>::insert

• Trong phiên bản thứ hai, chuyển đổi sử dụng std::pair trình tạo mẫu có liên quan. Thật vậy, std::make_pair rất có thể sẽ suy luận các đối số mẫu của nó thành KeyType và ValType, do đó trả về một std::pair<KeyType, ValType>.

  Điều này không khớp với loại thông số std::map<K,V>::insert, là std::pair<const KeyType, ValType> (sự khác biệt là const đủ điều kiện trước). Nhà xây dựng chuyển đổi std::pair sẽ được sử dụng để tạo một std::pair<const K, V> từ std::pair<K, V>.

Để công bằng, tôi không tin bạn thậm chí có thể đo lường sự khác biệt (và tôi thậm chí không chắc chắn rằng các trình biên dịch phổ biến sẽ thực sự tạo mã khác).

Answer 2

Về cơ bản, chúng giống nhau. KVMap::value_type là typedef cho std::pair<KeyType, ValType>, vì vậy đó chỉ là gọi hàm tạo. std::make_pair là một hàm mẫu đơn giản gọi hàm tạo (nó tồn tại vì các kiểu mẫu có thể được suy ra cho các hàm miễn phí, nhưng không phải cho các hàm tạo). Một khi tất cả các tối ưu hóa tiêu chuẩn không thể tin được thực hiện, không có lý do gì để có bất kỳ sự khác biệt nào.

Tôi không biết bạn đang thử nghiệm như thế nào, nhưng có rất nhiều cách để làm điều đó sai.

Đối với insert() so với gán thông qua operator[], sau này phải làm việc nhiều hơn theo khái niệm (khi bạn thêm phần tử mới theo cách này, trước tiên nó được giả định là xây dựng phần tử mặc định và sau đó gán lên trên phần tử) , nhưng tùy thuộc vào ValType, nó có thể hình dung được tối ưu hóa về cơ bản cùng một điều nữa.

Answer 3

Có thực sự là một đối số được thực hiện cho value_type qua make_pair. Điều này là do, vì nhiều lý do phức tạp, make_pair chấp nhận đối số của nó theo giá trị. Mặt khác, value_type, một bí danh cho std::pair<const Key, value>, sẽ có hàm tạo của nó được gọi với các đối số được chuyển bởi tham chiếu const. Có khả năng mất hiệu quả tiềm năng từ giá trị vượt qua theo giá trị trong make_pair so với tính năng tham chiếu vượt qua, có thể về lý thuyết có tác động đáng chú ý đến chương trình của bạn.

Một vấn đề khác phải lo lắng về với make_pair là make_pair thường sẽ tạo ra một cặp loại std::pair<Key, Value> so với std::pair<const Key, Value> cần thiết bên trong map. Điều này có nghĩa là có thể có một bản sao không cần thiết khác đang được thực hiện, lần này là pair để chuyển đổi hoạt động chính xác.

Tóm lại, sử dụng make_pair có thể làm cho hai bản sao và giá trị không cần thiết hoàn toàn cần thực hiện, trong khi sử dụng hàm tạo value_type không có.

Answer 4

Đây chỉ là phần bổ sung.

insert(make_pair(...)) gọi hàm sao chép bản sao 4 lần theo lý do vì lý do khác người trả lời được đề cập.

insert(value_type(...)) gọi hàm tạo bản sao 2 lần.

operator[] cuộc gọi constructor mặc định một lần và copy constructor 2 lần trong việc thực hiện điển hình. hàm tạo mặc định được gọi là bên trong operator[] cho insert(value_type(..., mapped_type())). trình tạo bản sao được gọi một lần để sao chép đối số của insert() (pair), và một lần để sao chép-xây dựng một nút nội bộ của bản đồ.

Vì vậy, nếu bạn sử dụng insert với make_pair, nó có thể không thể nói rằng insert luôn nhanh hơn operator[] thậm chí còn cho thêm. Có lẽ, nó phụ thuộc vào tình hình. Như bạn có thể biết, theo quan điểm trên, emplace đã được đề xuất cho tiêu chuẩn mới.