2017 年 10 月
第 32 卷，第 10 期
本文章是由機器翻譯。
C++ - C++ 中從演算法到協同程式
沒有稱為一律上我的 iota 的 c + + 標準程式庫演算法。它具有這個名稱和有趣的函式。Word iota 是以希臘字母字母的名稱。它通常用於以英文表示非常小，而且通常的負數，沒有最少，衍生自 Matthew 新增建築活頁簿中的引號。這個概念非常少量的來說 iota 演算法的函式。它已經用來儲存，然後會遞增，直到已填入的範圍的起始值的小的量，增加的值以填滿範圍。如下所示：
#include <numeric>
int main()
{
int range[10];
// Range: Random missile launch codes
std::iota(std::begin(range), std::end(range), 0);
// Range: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
}
它通常稱為 c + + 開發人員應該刪去所有巢狀 for 迴圈，並取代演算法。Iota 演算法當然，符合它發生時的任何 C 或 c + + 開發人員有毋庸置疑地撰寫好幾千次的迴圈。您可以想像您 c + + 標準程式庫的實作可能如下：
namespace std
{
template <typename Iterator, typename Type>
void iota(Iterator first, Iterator last, Type value)
{
for (; first != last; ++first, ++value)
{
*first = value;
}
}
}
因此，[是]，不想這樣攔截與程式碼的程式碼檢閱中。除非您當然是程式庫開發人員。來說非常棒 iota 演算法不必我針對迴圈中，撰寫的但您知道什麼？我不會實際曾經使用它在生產環境中。劇本通常會像下面這樣：我需要某個範圍的值。這是在電腦科學中必須有它的標準演算法的這類基本項目。我試四處清單透過在bit.ly/2i5WZRc和 iota 在哪裡找到。嗯，它需要填入值的範圍。什麼是最便宜的範圍可以在哪裡找到 [確定]...我然後列印值以確定您得到正確使用...for 迴圈：
#include <numeric>
#include <stdio.h>
int main()
{
int range[10];
std::iota(std::begin(range), std::end(range), 0);
for (int i : range)
{
printf("%d\n", i);
}
}
若要老實說，的唯一我喜歡這段程式碼會是範圍為基礎之 for 迴圈。問題是，我只是不需要也不想要該範圍。我不想需要建立一些只是為了保存的值，以便可以逐一它們的容器。如果需要更多的值？我有太多而是只寫入的迴圈自行：
#include <stdio.h>
int main()
{
for (int i = 0; i != 10; ++i)
{
printf("%d\n", i);
}
}
若要加入種受傷，這牽涉到更少的輸入。確定應該不錯，不過，由於某種原因而無法產生的值範圍為基礎之 for 迴圈來消耗而不需要使用容器範圍 iota 類似函式一樣。我已最近瀏覽 Python 語言有關的書籍，並注意到它已內建函式呼叫的範圍。我可以在 Python 撰寫相同的程式，像這樣：
for i in range(0, 10):
print(i)
請謹慎使用該縮排。它是如何 Python 語言表示複合陳述式。我閱讀 Python 名為特定英國喜劇，而不是 nonvenomous snake 之後。我認為開玩笑作者。儘管如此，我喜歡簡潔的本質上這段程式碼。當然，我可以達到沿著這些 c + + 中的項目。事實上，這是我想 iota 演算法會提供，但是，還有。基本上，我正在尋找是一種範圍演算法，看起來像這樣：
template <typename T>
generator<T> range(T first, T last)
{
return{ ... };
}
int main()
{
for (int i : range(0, 10))
{
printf("%d\n", i);
}
}
我所知，這類函式存在，因此讓我們繼續並建置專案。第一個步驟是近似值演算法可靠的項目，可做為測試的基準。C + + 標準向量容器派上用場在此情況下：
#include <vector>
template <typename T>
std::vector<T> range(T first, T last)
{
std::vector<T> values;
while (first != last)
{
values.push_back(first++);
}
return values;
}
它也會說明您不想在一開始，建立一個容器，或甚至是找出它應該多大，而且很好。為什麼即使應該有端點嗎？不過，這非常有用因為您可以輕鬆地比較此範圍產生器，以更有效率的替代方案的輸出。嗯，其實撰寫更有效率的產生器沒有困難。看看圖 1。
圖 1 古典產生器
template <typename T>
struct generator
{
T first;
T last;
struct iterator{ ... };
iterator begin()
{
return{ first };
}
iterator end()
{
return{ last };
}
};
template <typename T>
generator<T> range(T first, T last)
{
return{ first, last };
}
範圍函式只會建立產生器中使用相同的界限值組初始化。然後產生器就可以使用這些值，來產生輕量型的迭代器，透過傳統的開始和結束成員函式。最繁瑣的部分吐痰大致未定案迭代器類型。只要迭代器可以保留指定的值，並視需要增加它。它也必須能夠描述自己標準演算法來提供一組類型別名。這並非絕對必要的範圍為基礎之 for 迴圈 」 的簡單，但它包含這有點未來校訂付款：
template <typename T>
struct generator
{
struct iterator
{
T value;
using iterator_category = std::input_iterator_tag;
using value_type = T;
using difference_type = ptrdiff_t;
using pointer = T const*;
using reference = T const&;
遞增迭代器，可以只是遞增的基礎值。後置遞增表單可以安全地刪除：
iterator& operator++()
{
++value;
return *this;
}
iterator operator++(int) = delete;
其他同樣重要函式提供的迭代器是比較。範圍架構的 for 迴圈，將使用此判斷它是否已到達範圍結尾：
bool operator==(iterator const& other) const
{
return value == other.value;
}
bool operator!=(iterator const& other) const
{
return !(*this == other);
}
最後，範圍為基礎之 for 迴圈會想要將目前的值傳回範圍中的迭代器取值 （dereference）。我無法刪除成員呼叫運算子，因為它不所需範圍為基礎之 for 迴圈 」，但其實不會限制其他演算法可使用的產生器的公用程式：
T const& operator*() const
{
return value;
}
T const* operator->() const
{
return std::addressof(value);
}
它可能會產生器和相關聯的範圍函式會搭配類似數目的物件，而不是簡單的基本項目。在此情況下，您也可以使用 helper、 位址應該類似數目的物件是播放訣竅使用運算子 & 多載。而這是所有所需。我的範圍函式現在可以正常運作：
template <typename T>
generator<T> range(T first, T last)
{
return{ first, last };
}
int main()
{
for (int i : range(0, 10))
{
printf("%d\n", i);
}
}
當然，這並不特別有彈性。我已產生的我的夢想 iota 但它仍然只 iota 的功能，就會將如果我切換齒輪，並接受協同程式。您看到，目前更簡潔的方式，而不需要撰寫新的產生器類別樣板的每一種您想要產生的範圍，您可以撰寫產生器的所有類型的協同程式。假設您只需要撰寫一個詳細的產生器，則有各種範圍類似函式來產生不同的順序，依需求。這是協同程式的啟用。而不是內嵌至產生器在原始 iota 產生的知識，您可以內嵌直接範圍函式內該知識，並有單一的產生器的類別範本，提供生產者和取用者之間黏附。就來看看它。
我開始包含協同程式標頭，提供 coroutine_handle 類別樣板的定義：
#include <experimental/coroutine>
我將使用 coroutine_handle 允許與狀態機器由協同程式互動的產生器。這將會查詢並繼續視需要允許範圍為基礎之 for 迴圈 — 或其他迴圈，該項目的 — 若要直接產生提取-而不是推入模型的資料使用協同程式的進度。在某些方面類似於傳統的產生器中的產生器是圖 1。大的差異在於，而不是直接更新值，它只是將微調協同程式往前。圖 2提供外框。
圖 2 協同程式產生器
template <typename T>
struct generator
{
struct promise_type{ ... };
using handle_type = std::experimental::coroutine_handle<promise_type>;
handle_type handle{ nullptr };
struct iterator{ ... };
iterator begin()
{
...
handle.resume();
...
}
iterator end()
{
return nullptr;
}
};
因此，會有更多這裡。有允許範圍架構 for 互動的產生器，從外部迴圈的迭代器不僅也是可讓來自內部的產生器與互動協同程式 promise_type。首先，某些內部管理：前文提過函式產生的值不是直接傳回產生器中，但而是讓開發人員使用 co_yield 陳述式為協同程式，透過產生器，從正向的值，並呼叫站台。請考慮最簡單的產生器：
generator<int> one_two_three()
{
co_yield 1;
co_yield 2;
co_yield 3;
}
請注意如何開發人員不會明確建立的協同程式的傳回型別。這是 c + + 編譯器的角色，如連結在一起的這段程式碼所代表的狀態機器。基本上，c + + 編譯器會尋找 promise_type，並使用該值來建構邏輯協同程式的畫面格。別擔心，c + + 編譯器會完成之後，可能就會消失協同程式框架的程式碼，在某些情況下進行最佳化。總之，promise_type 然後用來初始化取得傳回給呼叫端的產生器。Promise_type，我可以取得代表協同程式，以便產生器可以從磁碟機它在外部的控制代碼：
generator(promise_type& promise) :
handle(handle_type::from_promise(promise))
{
}
當然，coroutine_handle 是相當低層級建構，但不想保留產生器開發人員不慎損毀狀態機器內使用中的協同程式。方案是只實作移動語意，並禁止複製。就像這樣 （首先，我會提供給它的預設建構函式和明確刪除特殊複本成員）：
generator() = default;
generator(generator const&) = delete;
generator &operator=(generator const&) = delete;
然後我要實作移動語意只要傳送協同程式的控制代碼值，使兩個產生器永遠不會指向相同的執行協同程式，如下所示圖 3。
圖 3 實作移動語意
generator(generator&& other) : handle(other.handle)
{
other.handle = nullptr;
}
generator &operator=(generator&& other)
{
if (this != &other)
{
handle = other.handle;
other.handle = nullptr;
}
return *this;
}
現在，假設協同程式被驅動從外部的事實，務必記得產生器也已終結協同程式的責任：
~generator()
{
if (handle)
{
handle.destroy();
}
}
這實際上有多個與 final_suspend promise_type 上的結果，但我將會節省的另一個的一天。這現在是足夠簿記。我們現在看產生器的 promise_type。Promise_type 是方便 park 任何狀態，它將會包含在任何 c + + 編譯器進行協同程式的框架的配置。產生器就只是輕量級的物件，可以輕鬆地四處移動以及回頭參考該狀態所需。只有兩種真的需要從傳達協同程式中的資訊傳回給呼叫者。第一個是要產生的值，而且第二個是可能已擲回任何例外狀況：
#include <variant>
template <typename T>
struct generator
{
struct promise_type
{
std::variant<T const*, std::exception_ptr> value;
雖然是選擇性的我會傾向於包裝內 std::optional exception_ptr 物件，因為 exception_ptr Visual c + + 中的實作是更昂貴。即使空 exception_ptr 建構和解構期間呼叫 CRT。包裝內選擇性整齊，可避免額外的負荷。更精確的狀態模型是使用 variant，我只的說明，來保留目前的值或 exception_ptr，因為它們是互斥。目前的值是只在協同程式內所產生的值的指標。這是因為值唯讀的可能會產生任何暫存物件會被安全地保留時進行觀察值之外的協同程式時，將會暫止的協同程式的安全。
當協同程式一開始會傳回其呼叫端時，它會要求 promise_type 來產生傳回的值。因為可以藉由參考 promise_type 建構產生器，我可以只傳回該參考此處：
promise_type& get_return_object()
{
return *this;
}
協同程式產生的產生器不是您一般的並行存取啟用協同程式，而且這通常是只規定的存留期和執行協同程式的產生器。因此，我指示給 c + + 編譯器協同程式必須一開始暫止，以便產生器可以控制逐步執行協同程式中，所以：
std::experimental::suspend_always initial_suspend()
{
return {};
}
同樣地，我表示協同程式將會擱置傳回時，而不是具有協同程式會自動終結本身：
std::experimental::suspend_always final_suspend()
{
return {};
}
這可確保我仍然可以查詢協同程式，透過 promise_type 協同程式完成之後，配置協同程式內的狀態。這是為了讓我讀取 exception_ptr 在發生錯誤時，或甚至只是為了知道協同程式，已完成。如果協同程式會自動終結本身完成時，我不甚至能夠查詢 coroutine_handle 更別說 promise_type 中，若要繼續在其最終的暫停點協同程式呼叫。擷取要產生的值現在是相當直接：
std::experimental::suspend_always yield_value(T const& other)
{
value = std::addressof(other);
return {};
}
我只需使用 helper 的方便地址一次。Promise_type 也必須提供在 return_void 或 return_value 函式。即使不使用在此範例中，它提示該 co_yield 位於 co_await 其實只是抽象的事實：
void return_void() {}
稍後會有更多說明。接下來，我要加入的方式稍有防禦機制以防止不當使用，只是為了方便開發人員，找出發生錯誤的原因。您看到，產生器中產生的值，表示協同程式完成時，除非某個值，而可供讀取。如果協同程式包括 co_await 運算式，然後它理論上可以暫停，但不出現的值，並會有這項事實傳遞給呼叫端沒有辦法。基於這個原因，防止開發人員撰寫 co_await 陳述式，如下所示：
template <typename Expression>
Expression&& await_transform(Expression&& expression)
{
static_assert(sizeof(expression) == 0,
"co_await is not supported in coroutines of type generator");
return std::forward<Expression>(expression);
}
我總結 promise_type，只需要處理，攔截任何可能已擲回的例外狀況。C + + 編譯器可確保會呼叫 promise_type unhandled_exception 成員：
void unhandled_exception()
{
value = std::current_exception();
}
然後，我可以只是方便進行實作，提供方便的函式的選擇性地重新例外狀況擲回適當的內容中：
void rethrow_if_failed()
{
if (value.index() == 1)
{
std::rethrow_exception(std::get<1>(value));
}
}
關於 promise_type 足夠。我現在有正常運作的產生器，但我只要加入簡單的迭代器，讓我可以輕鬆地從磁碟機其範圍為基礎之 for 迴圈。如前所述，迭代器，將會擁有能夠描述自己標準演算法的未定案類型別名。不過，迭代器只會保留 coroutine_handle:
struct iterator
{
using iterator_category = std::input_iterator_tag;
using value_type = T;
using difference_type = ptrdiff_t;
using pointer = T const*;
using reference = T const&;
handle_type handle;
遞增迭代器會稍微比複雜簡單 iota 迭代器，因為這是在產生器與協同程式的互動的主要點。遞增迭代器，表示迭代器無效，而且實際上可能會遞增。由於 「 結束 」 迭代器保留 nullptr 控點，只是提供的迭代器比較，，如下所示：
bool operator==(iterator const& other) const
{
return handle == other.handle;
}
bool operator!=(iterator const& other) const
{
return !(*this == other);
}
假設它有效的迭代器，我先恢復協同程式，讓它可以執行，並產生其下一個值。還需要檢查此執行是否帶結束，協同程式，如果是的話，將傳播可能協同程式中引發任何例外狀況：
iterator &operator++()
{
handle.resume();
if (handle.done())
{
promise_type& promise = handle.promise();
handle = nullptr;
promise.rethrow_if_failed();
}
return *this;
}
iterator operator++(int) = delete;
否則，迭代器會被視為已到達它的結尾，並使它成功比對結尾迭代器，只會清除其控制代碼。小心需要採取來清除協同程式處理之前擲回任何無法攔截的例外狀況，防止任何人不小心繼續協同程式最終暫停點，因為這會導致未定義的行為。產生器的開始成員函式在執行許多相同的邏輯，以確保我可以一致地傳播到達第一個暫止的時間點之前，會擲回任何例外狀況：
iterator begin()
{
if (!handle)
{
return nullptr;
}
handle.resume();
if (handle.done())
{
handle.promise().rethrow_if_failed();
return nullptr;
}
return handle;
}
主要差異在於，開始所屬的產生器擁有的協同程式的控制代碼，並因此必須清除協同程式處理。最後，並非常簡單，我可以實作迭代器取值只要傳回 promise_type 中儲存的目前值的參考：
T const& operator*() const
{
return *std::get<0>(handle.promise().value);
}
T const* operator->() const
{
return std::addressof(operator*());
}
和我已完成。我現在可以撰寫的演算法，產生各種不同的使用此通用的產生器產生的序列。圖 4顯示參考的範圍產生器的外觀。
圖 4 所參考的範圍產生器
template <typename T>
generator<int> range(T first, T last)
{
while (first != last)
{
co_yield first++;
}
}
int main()
{
for (int i : range(0, 10))
{
printf("%d\n", i);
}
}
需要哪些人範圍有限，？我現在有提取模型，我只需要呼叫端決定當他們已經夠，如下所示圖 5。
圖 5 無限制的產生器
template <typename T>
generator<int> range(T first)
{
while (true)
{
co_yield first++;
}
}
int main()
{
for (int i : range(0))
{
printf("%d\n", i);
if (...)
{
break;
}
}
}
有無限的可能性 ！沒有，當然，更可產生器，協同程式與我已僅只會大略這裡。C + + 中，加入我如需有關協同程式的下一次。您可以透過在編譯器總管來找到這份文件的完整範例： godbolt.org/g/NXHBZR。
Kenny Kerr作者、 系統程式設計人員，以及建立者的 C + + WinRT。他也是在 Microsoft Windows 團隊版工程師他會在此設計未來的 c + + 為 Windows，讓開發人員驚人輕鬆撰寫美觀的高效能應用程式和元件。
非常感謝下列技術專家檢閱這篇文章：Gor Nishanov