Hiệu quả của std :: get with std :: tuple

Question

Tôi rất tò mò về thời gian tra cứu cuộc gọi đến std::get<> trên số std::tuple<> mất. Một số googling ngắn gọn (bao gồm cả các trang tham khảo thường có thông tin này) không có kết quả.

Trực giác ban đầu của tôi (và sợ) là cấu trúc đệ quy của bộ dữ liệu (nếu được thực hiện dưới dạng mẫu biến thể) sẽ dẫn đến yêu cầu tìm kiếm N (gọi tới get<3>(t) trông giống như t.rest().rest().first(). hy vọng tôi cách tắt ở đây ...

Sau đó, một lần nữa, tôi hy vọng các trình biên dịch sẽ có thể tối ưu hóa này để trực tiếp trả lại đúng bù đắp mà không có sự cần thiết của việc N của các cuộc gọi.

về cơ bản những gì tôi muốn : có bảo đảm xác định về thời gian chạy không? điều này có hạn chế cách thực hiện std::tuple không?

Answer 1

Đặc tả C++ không đảm bảo về hiệu suất thời gian chạy của mọi chức năng. Ngay cả khi nó đưa ra các yêu cầu tiệm cận, chỉ đảm bảo số lượng hoạt động tương đối, không phải là hiệu suất của các hoạt động đó. O (1) không có nghĩa là nhanh, cũng không O (n) có nghĩa là chậm.

Bạn có thể tin tưởng trình biên dịch/trình tối ưu hóa/triển khai thư viện chuẩn của mình hoặc bạn có thể tự viết lại tất cả để có được hiệu suất mong muốn. std::get, theo trình biên dịch hợp lý nhất (với tối ưu hóa trên), nên thực hiện nhiều hơn hoặc ít hơn tương đương để trực tiếp truy cập vào giá trị từ một cấu trúc. Nhưng thông số kỹ thuật không yêu cầu tại bất kỳ điểm nào.

Answer 2

Hiệu quả sẽ được so sánh với việc truy cập một thành viên của một cấu trúc. Các get<> được giải quyết tại thời gian biên dịch.

Answer 3

Câu trả lời cho câu hỏi đầu tiên (khoảng thời gian std::get mất) tùy thuộc vào cách thư viện của bạn chọn triển khai std::tuple và std::get. Nhưng thông thường, các thư viện sẽ chọn sử dụng cách tiếp cận không đệ quy, tương tự như cách được nêu ở đây: http://mitchnull.blogspot.com/2012/06/c11-tuple-implementation-details-part-1.html. Với kiểu tiếp cận đó, thời gian truy cập của std::get sẽ không đổi và tương đương với thời gian cần thiết để truy cập thành viên của cấu trúc.

Để trả lời xem liệu tiêu chuẩn có cung cấp bất kỳ sự đảm bảo nào không: như những người khác đã nói, không, tiêu chuẩn không đảm bảo ở đây. Một nhà văn thư viện ác có thể chọn để làm cho số mũ std::get trong N và chúng vẫn tuân thủ tiêu chuẩn.