本主题演示如何编写基本树结构的搜索算法。
主题取消解释了并行模式库中取消的角色。 与使用 concurrency::task_group::cancel 和 concurrency::structured_task_group::cancel 方法相比，使用异常处理取消并行工作的效率较低。 但是，使用异常处理取消工作是合适的一种情况是，调用使用任务或并行算法但不提供 task_group 或 structured_task_group 对象以进行取消的第三方库。
示例：基本树类型
以下示例演示包含数据元素和子节点列表的基本 tree 类型。 以下部分显示了 for_all 方法的主体，该方法以递归方式在每个子节点上执行工作函数。
// A simple tree structure that has multiple child nodes.
template <typename T>
class tree
{
public:
explicit tree(T data)
: _data(data)
{
}
// Retrieves the data element for the node.
T get_data() const
{
return _data;
}
// Adds a child node to the tree.
void add_child(tree& child)
{
_children.push_back(child);
}
// Performs the given work function on the data element of the tree and
// on each child.
template<class Function>
void for_all(Function& action);
private:
// The data for this node.
T _data;
// The child nodes.
list<tree> _children;
};
示例：并行执行工作
下面的示例演示了 for_all 方法。 它使用 concurrency::parallel_for_each 算法在树的每个节点上并行执行工作函数。
// Performs the given work function on the data element of the tree and
// on each child.
template<class Function>
void for_all(Function& action)
{
// Perform the action on each child.
parallel_for_each(begin(_children), end(_children), [&](tree& child) {
child.for_all(action);
});
// Perform the action on this node.
action(*this);
}
示例：在树中搜索值
下面的介绍了 search_for_value 函数，它可在所提供的 tree 对象中搜索值。 此函数传递给 for_all 方法一个工作函数，其在找到包含所提供值的树节点时引发。
假设 tree 类由第三方库提供，并且无法对其进行修改。 在这种情况下，使用异常处理是适当的，因为 for_all 方法不向调用方提供 task_group 或 structured_task_group 对象。 因此，工作函数无法直接取消其父任务组。
向任务组提供的工作函数引发异常时，运行时将停止任务组中的所有任务（包括任何子任务组）并丢弃尚未开始的任何任务。 search_for_value 函数使用 try-catch 块来捕获异常，并将结果打印到控制台。
// Searches for a value in the provided tree object.
template <typename T>
void search_for_value(tree<T>& t, int value)
{
try
{
// Call the for_all method to search for a value. The work function
// throws an exception when it finds the value.
t.for_all([value](const tree<T>& node) {
if (node.get_data() == value)
{
throw &node;
}
});
}
catch (const tree<T>* node)
{
// A matching node was found. Print a message to the console.
wstringstream ss;
ss << L"Found a node with value " << value << L'.' << endl;
wcout << ss.str();
return;
}
// A matching node was not found. Print a message to the console.
wstringstream ss;
ss << L"Did not find node with value " << value << L'.' << endl;
wcout << ss.str();
}
示例：并行创建和搜索树
以下示例创建一个 tree 对象，并且并行搜索多个值。 本主题稍后会对 build_tree 函数进行介绍。
int wmain()
{
// Build a tree that is four levels deep with the initial level
// having three children. The value of each node is a random number.
mt19937 gen(38);
tree<int> t = build_tree<int>(4, 3, [&gen]{ return gen()%100000; });
// Search for a few values in the tree in parallel.
parallel_invoke(
[&t] { search_for_value(t, 86131); },
[&t] { search_for_value(t, 17522); },
[&t] { search_for_value(t, 32614); }
);
}
此示例使用 concurrency::parallel_invoke 算法并行搜索值。 有关此算法的详细信息，请参阅并行算法。
示例：已完成的异常处理代码示例
以下完整示例使用异常处理来在基本树结构中搜索值。
// task-tree-search.cpp
// compile with: /EHsc
#include <ppl.h>
#include <list>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <random>
using namespace concurrency;
using namespace std;
// A simple tree structure that has multiple child nodes.
template <typename T>
class tree
{
public:
explicit tree(T data)
: _data(data)
{
}
// Retrieves the data element for the node.
T get_data() const
{
return _data;
}
// Adds a child node to the tree.
void add_child(tree& child)
{
_children.push_back(child);
}
// Performs the given work function on the data element of the tree and
// on each child.
template<class Function>
void for_all(Function& action)
{
// Perform the action on each child.
parallel_for_each(begin(_children), end(_children), [&](tree& child) {
child.for_all(action);
});
// Perform the action on this node.
action(*this);
}
private:
// The data for this node.
T _data;
// The child nodes.
list<tree> _children;
};
// Builds a tree with the given depth.
// Each node of the tree is initialized with the provided generator function.
// Each level of the tree has one more child than the previous level.
template <typename T, class Generator>
tree<T> build_tree(int depth, int child_count, Generator& g)
{
// Create the tree node.
tree<T> t(g());
// Add children.
if (depth > 0)
{
for(int i = 0; i < child_count; ++i)
{
t.add_child(build_tree<T>(depth - 1, child_count + 1, g));
}
}
return t;
}
// Searches for a value in the provided tree object.
template <typename T>
void search_for_value(tree<T>& t, int value)
{
try
{
// Call the for_all method to search for a value. The work function
// throws an exception when it finds the value.
t.for_all([value](const tree<T>& node) {
if (node.get_data() == value)
{
throw &node;
}
});
}
catch (const tree<T>* node)
{
// A matching node was found. Print a message to the console.
wstringstream ss;
ss << L"Found a node with value " << value << L'.' << endl;
wcout << ss.str();
return;
}
// A matching node was not found. Print a message to the console.
wstringstream ss;
ss << L"Did not find node with value " << value << L'.' << endl;
wcout << ss.str();
}
int wmain()
{
// Build a tree that is four levels deep with the initial level
// having three children. The value of each node is a random number.
mt19937 gen(38);
tree<int> t = build_tree<int>(4, 3, [&gen]{ return gen()%100000; });
// Search for a few values in the tree in parallel.
parallel_invoke(
[&t] { search_for_value(t, 86131); },
[&t] { search_for_value(t, 17522); },
[&t] { search_for_value(t, 32614); }
);
}
此示例生成以下示例输出。
Found a node with value 32614.
Found a node with value 86131.
Did not find node with value 17522.
编译代码
复制示例代码，并将它粘贴到 Visual Studio 项目中，或粘贴到名为 task-tree-search.cpp 的文件中，再在 Visual Studio 命令提示符窗口中运行以下命令。
cl.exe /EHsc task-tree-search.cpp
另请参阅
PPL 中的取消操作
异常处理
任务并行
并行算法
task_group 类
structured_task_group 类
parallel_for_each 函数