Từ ngữ chuẩn C++: Có "thông qua tất cả các trình vòng lặp trong phạm vi" ngụ ý tuần tự không?

Question

This SO question phát ra một cuộc thảo luận về std::generate và các đảm bảo được thực hiện theo tiêu chuẩn. Cụ thể, bạn có thể sử dụng đối tượng chức năng với trạng thái nội bộ và dựa trên generate(it1, it2, gen) để gọi gen(), lưu trữ kết quả trong *it, gọi lại gen() một lần nữa, lưu trữ trong *(it + 1) v.v ... hoặc có thể bắt đầu ở mặt sau chẳng hạn?

Tiêu chuẩn (n3337, §25.3.7/1) nói điều này:

Effects: Các thuật toán đầu tiên gọi hàm đối tượng gen và gán giá trị trả về của gen qua tất cả các vòng lặp trong phạm vi [first,last) . Thuật toán thứ hai gọi gen đối tượng hàm và gán giá trị trả về của gen thông qua tất cả các vòng lặp trong phạm vi [first,first + n) nếu n là tích cực, nếu không nó sẽ không làm gì cả.

Nó có vẻ như không có trật tự được đảm bảo, đặc biệt là từ các khoản khác có từ ngữ mạnh mẽ hơn, ví dụ std::for_each (Effects: Áp dụng f đến kết quả của dereferencing mỗi iterator trong khoảng [first,last), bắt đầu từ đầu và tiến tới last - 1 Nếu chúng tôi đang thực hiện điều này theo nghĩa đen, nó chỉ đảm bảo bắt đầu tại first và kết thúc tại last mặc dù - không đảm bảo về thứ tự ở giữa).

Nhưng: Cả hai Microsoft's và Apache's C++ standard library đều cung cấp ví dụ trên trang tài liệu yêu cầu đánh giá tuần tự. Và cả hai libC++ (trong algorithm) và libstdC++ (trong bits/stl_algo.h) thực hiện nó theo cách đó. Hơn nữa, bạn mất rất nhiều ứng dụng tiềm năng cho generate mà không cần đảm bảo này.

Từ ngữ hiện tại có ngụ ý tuần tự không? Nếu không, đây có phải là sự giám sát của các thành viên của ủy ban hay cố tình không?

(Tôi biết rằng không có nhiều người có thể cung cấp câu trả lời sâu sắc cho câu hỏi này mà không chỉ suy đoán hoặc thảo luận, nhưng theo quan điểm khiêm tốn của tôi, điều này không làm cho câu hỏi này 'không mang tính xây dựng' theo hướng dẫn SO .)

---

Nhờ @juanchopanza chỉ ra vấn đề này và giới thiệu tôi đến đoạn khoảng for_each.

Answer 1

Trong cuộc thảo luận của LWG475, std::for_each được so sánh với std::transform. Lưu ý rằng "transform không đảm bảo thứ tự mà đối tượng hàm của nó được gọi là". Vì vậy, có, ủy ban nhận thức được sự thiếu bảo đảm tuần tự trong tiêu chuẩn.

Không có yêu cầu ngược lại đối với hành vi không tuần tự, do đó, Microsoft và Apache được tự do sử dụng đánh giá tuần tự.

Answer 2

Bất kỳ nơi nào tiêu chuẩn không chỉ định thứ tự trên thuật toán, bạn nên giả định rằng việc triển khai có thể khai thác điều đó cho song song. Bài báo n3408 thảo luận các tùy chọn cho phép song song và trỏ tới thư viện Thrust, cả hai đều có thể sử dụng song song cho các thuật toán chuẩn và chứng minh khái niệm cho tiêu chuẩn hóa song song trong tương lai trong thuật toán.

Nhìn vào triển khai của Thrust là generate, nó gọi gen trong một vòng lặp song song bất cứ khi nào danh mục vòng lặp là truy cập ngẫu nhiên. Như bạn đã quan sát, điều này phù hợp với tiêu chuẩn, vì vậy bạn không nên giả định rằng generate sẽ luôn luôn được tuần tự. (Ví dụ, có thể sử dụng hiệu quả an toàn thread std::rand với generate và không yêu cầu trình tự tuần tự.)

Thuật toán duy nhất đảm bảo yêu cầu tuần tự là những thuật toán trong numeric; nếu mã của bạn phụ thuộc vào yêu cầu tuần tự, bạn nên sử dụng iota thay cho generate. Thích ứng với một máy phát hiện có:

template<typename F> struct iota_adapter { 
    F f; 
    operator typename std::result_of<F()>::type() { return f(); } 
    void operator++() {} 
}; 
template<typename F> iota_adapter<F> iota_adapt(F &&f) { return {f}; } 

Use as:

#include <numeric> 
#include <iostream> 

int main() { 
    int v[5], i = 0; 
    std::iota(std::begin(v), std::end(v), iota_adapt([&i]() { return ++i; })); 
    for (auto i: v) std::cout << i << '\n'; 
}