c++ - 多线程树数据结构的只读函数..我需要什么才能使线程安全

Question

我有一个树数据结构。除了正常的插入和删除功能外，我还有一个 COMPUTE 函数，它计算树中存在的节点的某些值。插入和移除函数影响树。但是 COMPUTE 函数不会修改树。 COMPUTE 函数有自己的内部队列，并向这些队列添加和删除节点。在这里，我展示了计算函数的简化伪代码:

class tree{
    vector<int> value;
    tree * children
}

tree::COMPUTE(vector<int> inputValue)
{
    Set currentSet;
    Set nextSet
    currentSet.add(root);

    foreach (node in currentSet)
    {
        if(node has children)
            foreach(childNode of node)
            {
                if(CONDITION_SATISFIED(childNode))
                    add childNode to nextSet;
            }
        else
            output childNode
    }


}

因此 COMPUTE 函数简单地遍历树，将节点添加到它自己的内部集合数据结构中并进行一些计算。

现在我想对 COMPUTE 函数进行多线程处理。由于它不修改树，我想这很容易做到。每个线程都给出自己的值并获得自己的 COMPUTE 输出。代码是用 C++ 编写的。

我的问题是:

如果我这样调用它:

void * threadRoutine
{
    tree.COMPUTE(thisThreadVal);
}

int main()
{
    tree myTree();

    //Insertion Code here

    call N threads each with different parameters but the same tree.
}

我不认为这是正确的。这是因为所有线程都会调用同一个树对象的同一个成员函数。因此，内部数据结构(如 COMPUTE 方法中使用的集合)将被破坏。

我认为我应该在树的外部编写计算函数，而不是作为树的成员函数。谁能告诉我这是否正确。

顺便说一句:如果有人好奇，我将使用的确切树称为 Cover Tree。它是一种相对较新的数据结构，用于查找最近邻查询。

Answer 1

所采用的方法对于多个 COMPUTE(全大写是什么？)调用是安全的，只要使用的集合是本地集合，或者在堆中，但本地指针或对它们的引用是唯一的此类指针或引用 - 因此它们将远离彼此。

(在其他情况下它可以是线程安全的，但证明它会变得更加复杂)。

当另一个线程正在执行添加或删除的工作时，这样做是不安全的；计算可以安全地与其他计算一起发生，但不能与修改一起发生。如果发生这种情况，您需要某种同步，或者将所有可能的操作放在一起考虑并使它们都是线程安全的。

函数是成员函数还是外部完全无关。