使用协程为原生 C++ 实现 Yield Return 迭代器
使用协程为原生 C++ 实现 Yield Return 迭代器
引言
C# 2.0 中的 Microsoft .NET 技术引入了一项新的语言特性——“yield return”关键字，用于迭代集合（而不仅仅是集合）。本文展示了如何在原生 C++ 中创建类似的迭代技术。与大多数（最近的）C++ 库不同，它不需要开发人员使用非常复杂的代码。
背景
“yield return”迭代器是一项语言特性，其创建的目的是为了一个原因：简单性。与编写一个复杂的自定义迭代器对象来存储其跨后续检索操作的状态相比，迭代整个集合并将其所需的所有上下文存储在局部变量中通常要容易得多。
下面提供了一个使用 yield return 迭代器的示例代码。
class Program
{
static void Main(string[] args)
{
foreach (int i in GetRandom())
Console.WriteLine(i);
}
public static IEnumerable GetRandom()
{
for (int i = 0; i < 5; i++)
yield return Random.Get();
}
}
此程序实现了一个包含五个随机数的集合。但是，迭代函数似乎永远不会返回，或者也许会返回五次！
走向原生
C++ 当然没有 foreach 关键字，但请考虑以下代码。
SomeCollection C;
Enumerator <Somecollection, int> E(C);
for (int i; E.Get(i); )
cout << i << endl;
它看起来并不比 C# 的复杂。SomeCollection 的唯一先决条件是有一个返回整数的 Enumerate 方法。此外，我们可以使用以下形式的 Enumerate 函数。
int SomeCollection::Enumerate()
{
for (int i=0; i<4; i++)
yield_return(rand());
return rand();
}
简单返回表示我们已完成迭代（事实上，在 C# 中也应该是这样），而 yield_return 设置一个中间结果。
提供的示例可能无法展示该工具的全部功能，但请尝试用它来迭代哈希表或一些复杂的树结构。请注意，您甚至可以使用递归——这使得迭代树结构变得轻而易举。
Using the Code
本文中的代码将允许您编写一个程序，其效果**完全**如上所示。无需额外的官僚主义，没有冗长的模板名称或其他不便之处。好吧，确实**有**一个性质不同的不便之处——您的代码将不可避免地包含 <windows.h>，除非应用了某种包装器并将系统相关的代码移到专用的编译单元。
协程 - 未知的力量
Windows 中一项非常强大但被严重低估的特性是协程（可能是因为在基于 UNIX 的系统中找不到类似的功能）。
协程只是线程的一个上下文。它包括一个独立的堆栈、协程本地存储以及在切换时存储寄存器值的位置。协程切换发生在用户模式，因此开销非常小。最后但同样重要的是，协程由用户调度！这意味着协程可以用作调度延迟过程调用的强大工具，这正是我们所需要的。
创建协程只需要调用 CreateFiber 并提供一些上下文信息。它不返回句柄，而是返回一个用户指针到协程，线程可以显式地切换到该协程。每个线程最初都不是协程，因此我们必须调用 ConvertThreadToFiber 来创建第一个协程并设置协程自定义数据（由 ConvertThreadToFiber 的调用者提供的任意指针值）。
切换非常简单，只需调用 SwitchToFiber(PVOID fiber)。
那么，让我们开始吧！
迭代器的实现
基本上，要构建一个能按预期工作的程序，我们需要实现两件事：yield_return 函数和 Enumerator 类的 Get() 函数。Enumerator 的类头如下所示。
template <class T>
class Enumerator
{
public:
Enumerator(T &owner) : Owner(&owner), Fiber(0), ToolFiber(0) {}
Enumerator(T *owner) : Owner(owner), Fiber(0), ToolFiber(0) {}
~Enumerator();
bool Get(R &result); // the core function
private:
static void Return(const R &value); // a function that stores result
// from yield_return
template <class R>
friend void yield_return(const R &result); // the yield_return itself
virtual void *ValidatePointer(void *_ptr) // virtual just to force evaluation
{ return *(void **)_ptr; }
static void Enumerate(Enumerator *This); // pointers to members in C++
// are nasty, so let's make it a
// little bit more comfortable
void Prepare(); // preparation step
R *pResult; // result, set to &result in Get
T *Owner; // object we iterate across
void *Fiber, *ToolFiber; // fibers
};
让我们来看看一个相当乏味的准备步骤。
template <class T, class R>
void Enumerator<T, R>::Prepare()
{
if (!Fiber)
{
Fiber=GetCurrentFiber();
__try
{
ValidatePointer(Fiber);
}
__except(EXCEPTION_EXECUTE_HANDLER)
{
Fiber=ConvertThreadToFiber(this);
}
}
if (!ToolFiber) // and our enumeration fiber goes here!
ToolFiber=CreateFiber(4096, (LPFIBER_START_ROUTINE)Enumerate, this);
}
枚举函数
template <class T, class R>
void Enumerator<T, R>::Enumerate(Enumerator *This)
{
void *Fiber=This->Fiber; // store the fiber - it may change
*This->pResult=This->Owner->Enumerate();
This->Owner=NULL; // indicate end of collection
SwitchToFiber(Fiber); // return to the original fiber
}
此函数从 ToolFiber 上下文调用，因此应该调用 SwitchToFiber(Fiber)；如果它在返回前没有切换回，线程将会终止！
万能的 Get
template <class T, class R>
bool Enumerator<T, R>::Get(R &result)
{
if (!Owner) // no object to iterate - there never was one
// or iteration has ended
return false;
pResult=&result; // set result pointer
Prepare(); // prepare
if (ToolFiber) // we are ready
{
SwitchToFiber(ToolFiber); // and let's start (or continue)
// the enumeration!
if (!Owner) // the way of the fiber to indicate end of iteration
{
DeleteFiber(ToolFiber); // delete the tool fiber
ToolFiber=Fiber=0; // cleanup
}
}
return true; // success!
}
设置结果
template <class T, class R>
void Enumerator<T, R>::Return(const R &value)
{
Enumerator *E=(Enumerator *)GetFiberData(); // get the context,
//stored in fiber data
if (E->Fiber!=GetCurrentFiber()) // check, if it is the same fiber -
// Fiber field is spoofed at cleanup
{
*E->pResult=value; // set the result
SwitchToFiber(E->Fiber); // return to main fiber
}
}
现在我们有了模拟返回——它由 Return 函数中的 SwitchToFiber(E->Fiber) 处理——它将控制权转回原始协程，原始协程可以使用 pResult 读取结果。
在一切顺利之后，我们就完成了——协程结束了，一切都很美好。但如果我们放弃了我们的迭代器怎么办？
别无他法，只能将控制权转回 ToolFiber 并继续迭代，直到集合结束，可能还要明确告知迭代过程其结果将被忽略，因此它可以返回任何内容。在我的解决方案中，迭代器只是被告知进行迭代。但是，Fiber 字段设置为 ToolFiber，因此不会发生协程切换，结果也不会被复制。这可以提高这些最终迭代的性能。
template <class T, class R>>
Enumerator<T, R>::~Enumerator()
{
if (ToolFiber)
{
Fiber=ToolFiber; // spoofing the fiber pointer
SwitchToFiber(ToolFiber); // switch to enumerator
DeleteFiber(ToolFiber); // delete the enumerator
ToolFiber=Fiber=0;
}
}
现在唯一剩下的就是规范化返回中间结果的方式。调用 Enumerator<Type, Type>::Return(value) 比 yield_result(value) 复杂得多。所以，让我们把事情变得尽可能简单。
template <class R>
inline void yield_return(const R &result)
{
Enumerator<int, R>::Return(result); // collection type is not
// needed here, so we put 'int'
}
最后说明
无论您在哪里发现伪迭代对象或迭代器本身很复杂，这种方法都适用。它有一些开销（与经典迭代器相比），但其真正的力量在于使用的简单性。如果您在您的软件中应用了此代码，请告诉我——我很乐意帮助了某人。
后记 - 最近的一个想法
我有一个想法，即应该由 yield return 返回所有值，而迭代函数本身将返回 void。这实际上将是返回空集合的唯一方法，将使代码更一致，并简化对集合结束的检测。
新的 Enumerator::Enumerate 函数将如下所示。
template <class T, class R>
void Enumerator<T, R>::Enumerate(Enumerator *This)
{
void *Fiber=This->Fiber; // store the fiber - it may change
This->Owner->Enumerate();
This->Owner=NULL; // indicate end of collection
SwitchToFiber(Fiber); // return to the original fiber
}
Enumerator::Get 也会有一个小的改动。
SwitchToFiber(ToolFiber); // and let's start (or continue)
// the enumeration!
if (!Owner) // the way of the fiber to indicate end of iteration
{
DeleteFiber(ToolFiber); // delete the tool fiber
ToolFiber=Fiber=0; // cleanup
return false;
}
- Michal Zientkiewicz 别名 Mike65536