Truyền tham số biến đổi thuật toán std theo giá trị so với tham chiếu

Question

Tôi tự hỏi tại sao trong nhiều thuật toán mẫu trong STL các đối số không được truyền theo tham chiếu mà đúng theo giá trị. Dưới đây là ví dụ từ tiêu đề <iterator>:

template<class InputIterator> 
typename iterator_traits<InputIterator>::difference_type 
distance (InputIterator first, InputIterator last); 

Khi tôi chuyển hai trình lặp cho chức năng này, chúng được sao chép. những suy nghĩ ngây thơ của tôi là rằng nó sẽ được tốt hơn để vượt qua những vòng lặp bởi const-tài liệu tham khảo để tránh sao chép các đối tượng iterator:

template<class InputIterator> 
typename iterator_traits<InputIterator>::difference_type 
distance (const InputIterator &first, const InputIterator &last); 

Người ta có thể nói rằng vòng lặp là nói chung đối tượng rất nhỏ và sao chép chúng là không tốn kém. Nhưng thậm chí vẫn còn: sao chép rẻ sẽ đắt hơn là không sao chép gì cả.

Vì vậy, lý do gì trong phiên bản STL, các trình vòng lặp được truyền theo giá trị?

Cảm ơn bạn!

Answer 1

Có một thứ xuất hiện trong tâm trí của tôi và chống lại số const trong tham chiếu: các trình vòng lặp cần được sửa đổi khi sử dụng chúng.

Chi tiết triển khai khác có thể là các trình vòng lặp thực sự chỉ được triển khai dưới dạng con trỏ. Vì vậy, là tài liệu tham khảo trong hầu hết các trường hợp. Nếu bạn vượt qua con trỏ theo giá trị, bạn sao chép nó một lần nhưng dereference nó chỉ khi cần thiết. Nếu, chính con trỏ vòng lặp được chuyển bởi con trỏ tham chiếu, sau đó trước hết phải được bỏ qua, chỉ để có được trình lặp, và điều đó phải được thực hiện mỗi khi trình vòng lặp được truy cập. Đó là thừa.

Answer 2

Đối với một số loại bản sao giá rẻ nhất, chuyển chúng theo giá trị thực sự nhanh hơn so với truyền theo tham chiếu. Sự khôn ngoan thông thường từ các hướng dẫn, vv, nói rằng bằng cách tham chiếu nhanh hơn, nhưng điều này không nhất thiết áp dụng cho các loại giá rẻ để sao chép.

Làm cách nào để truyền một đối tượng theo giá trị? Bạn tạo một bản sao của nó, có nghĩa là bạn lấy giá trị và đẩy nó vào ngăn xếp cho cuộc gọi hàm. Và làm thế nào để bạn vượt qua bằng cách tham khảo? Bạn đẩy địa chỉ bộ nhớ vào ngăn xếp, và sau đó hàm được gọi phải tìm nạp bất cứ thứ gì ở địa chỉ đó. Bây giờ, tối ưu hóa và bộ nhớ đệm có thể đi vào chơi để làm cho bộ nhớ đó tìm nạp rẻ hơn nhiều, nhưng bạn vẫn không nhận được rẻ hơn so với lấy giá trị chính xác từ ngăn xếp. Mà trong trường hợp của iterators thường là một cái gì đó đơn giản như một con trỏ đơn giản. Đó là một từ dài và rất rẻ để sao chép.

Ngoài ra, lưu ý rằng bạn đang đề xuất chuyển một tham chiếu const. Điều đó có nghĩa là nó sẽ phải được sao chép bất kỳ trong hàm được gọi để cho phép nó được sửa đổi (chẳng hạn như gia tăng trong một vòng lặp).

Answer 3

Khái niệm về các trình biến đổi là generalisation of a pointer. Các vòng lặp của các thùng chứa std thường được triển khai như một kiểu tạo thành một con trỏ đơn. Trong trường hợp loại đối số rẻ hơn để sao chép dưới dạng con trỏ, hãy chuyển đối số bằng tham chiếu là nhiều hơn đắt hơn chuyển giá trị đó theo giá trị. Một tham chiếu đến một đối tượng phải được bỏ qua trước khi giá trị của đối tượng có thể được sử dụng. Xem this answer để biết thêm chi tiết.

Bởi vì hầu như tất cả các thuật toán std cần tạo bản sao của trình lặp, để có được hiệu suất tốt nhất, điều cần thiết là một trình lặp có giá rẻ để sao chép. Vì lý do này, nó rất khác thường để tìm một trình lặp mà đắt hơn đáng kể để truyền theo giá trị hơn là tham chiếu.

Trong trường hợp std::distance - và nhiều thuật toán khác - toàn bộ thuật toán đơn giản đến nỗi cuộc gọi sẽ rất có khả năng được trình biên dịch biên dịch. Nếu cuộc gọi được gạch chân, không quan trọng liệu đối số có được chuyển bởi tham chiếu hay theo giá trị hay không. [Lưu ý rằng cuộc gọi hàm nội tuyến không giống với khai báo hàm nội tuyến!]

Trong trường hợp trình lặp có giá trị vượt quá giá trị hơn tham chiếu và hàm gọi không được gạch chân, bạn có thể thực hiện một đối số cho các trình vòng lặp đi qua bởi tham chiếu rvalue. Hiệu suất đạt được trong một trường hợp hiếm hoi như vậy có lẽ không đáng giá thêm phức tạp.

Answer 4

Hầu hết các thuật toán đều sửa đổi đối số của chúng. Ví dụ, distance có thể được thực hiện như sau :

template<class InputIterator> 
typename iterator_traits<InputIterator>::difference_type 
distance (InputIterator first, InputIterator last) { 
    typename iterator_traits<InputIterator>::difference_type result{}; 
    while (first++ != last) 
     ++result; 
    return result; 
} 

Rõ ràng điều này không có tác dụng nếu bạn vượt qua first như một tài liệu tham khảo const.

Và nó cũng không hoạt động nếu bạn vượt qua nó như là một const tài liệu tham khảo không vì trong hầu hết gọi điện thoại ngữ cảnh vật của người gọi không thể được sửa đổi (ví dụ nếu bạn vượt qua là kết quả của container.begin() đến chức năng.

Tất nhiên bạn vẫn có thể vượt qua bằng cách tham khảo const, tạo một bản sao bên trong chức năng và sau đó sửa đổi điều đó.Tại thời điểm đó, chúng tôi đã đạt được chính xác không có gì. mà nên rẻ để sao chép, nó đơn giản hơn và nhiều nhất trường hợp hiệu quả hơn để vượt qua chúng bằng giá trị:

Nhưng thậm chí vẫn còn: sao chép giá rẻ sẽ đắt hơn không sao chép gì cả.

Không đúng sự thật. Bạn cũng cần phải sao chép tham chiếu (trong đó, trong trường hợp cuộc gọi hàm không được sắp xếp, sẽ được thực hiện dưới dạng con trỏ). Và sau đó bạn cần phải dereference con trỏ đó cũng cho biết thêm chi phí. So với một bản sao thẳng có thể là làm giá rẻ khi sao chép con trỏ trong nhiều trường hợp và không phải chịu bất kỳ khoản phí hội nghị nào.

---

Tất nhiên một thực hiện thực sẽ được tối ưu hóa cho vòng lặp truy cập ngẫu nhiên để có thời gian chạy liên tục chứ không phải là tuyến tính. Việc thực hiện ở trên chỉ dành cho trình bày.