如何以线程安全的方式迭代容器？

Question

如何以线程安全的方式迭代容器？

c++iteratorthread-safetyiterationcontainers

10

我有一个容器（C ++），需要两种不同线程的操作：
1）添加和删除元素，
2）迭代其成员。
很明显，在进行迭代时删除元素会导致灾难性后果。代码大致如下：

class A
{
public:
   ...
   void AddItem(const T& item, int index) { /*Put item into my_stuff at index*/ }
   void RemoveItem(const T& item) { /*Take item out of m_stuff*/ }
   const list<T>& MyStuff() { return my_stuff; } //*Hate* this, but see class C
private:
   Mutex mutex; //Goes in the *Item methods, but is largely worthless in MyStuff()
   list<T> my_stuff; //Just as well a vector or deque
};
extern A a; //defined in the .cpp file

class B
{
   ...
   void SomeFunction() { ... a.RemoveItem(item); }
};

class C
{
   ...
   void IterateOverStuff()
   {
      const list<T>& my_stuff(a.MyStuff());
      for (list<T>::const_iterator it=my_stuff.begin(); it!=my_stuff.end(); ++it)
      {
          ...
      }
   }
};

再次提醒，B::SomeFunction() 和 C::IterateOverStuff() 是异步调用的。有什么数据结构可以使用以确保在迭代期间my_stuff受到添加或删除操作的“保护”？

- Matt Phillips

3个回答

5

在数据结构类中拥有私有互斥锁，然后编写类方法以使整个内容无论调用方法的代码如何都是线程安全的，我认为这是一个错误。要完全和完美地做到这一点所需的复杂性是过高的。

更简单的方法是拥有一个公共（或全局）互斥锁，调用代码负责在需要访问数据时锁定它。

这里是我关于这个主题的博客文章。

- ravenspoint

谢谢。关于可复制性和构造函数的问题，我明白了。 - Matt Phillips

3

当您返回列表时，请将其封装在一个类中，该类在其构造函数/析构函数中锁定/解锁互斥锁。大致如下：

class LockedIterable {
public:
  LockedIterable(const list<T> &l, Mutex &mutex) : list_(l), mutex_(mutex)
  {lock(mutex);}
  LockedIterable(const LockedIterable &other) : list_(other.list_), mutex_(other.mutex_) {
    // may be tricky - may be wrap mutex_/list_ in a separate structure and manage it via shared_ptr?
  }
  ~LockedIterable(){unlock(mutex);}
  list<T>::iterator begin(){return list_.begin();}
  list<T>::iterator end(){return list_.end();}
private:
  list<T> &list_;
  Mutex &mutex_;
};

class A {
  ...
  LockedIterable MyStuff() { return LockedIterable(my_stuff, mutex); }  
};

难点在于编写复制构造函数，以使您的互斥锁不必递归。或者只需使用auto_ptr。

哦，读写锁确实是比互斥锁更好的解决方案。

- user3458

谢谢，我之前也考虑过类似的方法。唯一的问题是，在迭代完成后，这就要求我销毁 LockedIterable。如果在 C::IterateOverStuff 中还有很多其他操作，那么仅仅等待它超出作用域可能不够...所以我猜这里的选择是使用 new/delete？最后，复制结构是否简单，因为 LockedIterable 没有数据成员？ - Matt Phillips

我宁愿使用额外的块 {LockedIterable l = ...;for(){...}}。这可以为您管理范围。至于没有数据成员 - 我过于简化了我的代码 - 它具有数据成员list_和mutex_。如果您不想保持锁定/解锁互斥锁和/或不想两次锁定非递归互斥锁，则复制是非平凡的。 - user3458

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Evan Teran · Accepted Answer

听起来需要一个读者/写者锁。基本上，这个想法是你可能有1个或多个读者或一个单独的写者。你永远不能同时拥有读取和写入锁。

编辑: 我认为符合您设计的使用示例涉及进行小更改。将“iterate”函数添加到拥有列表的类中，并使其成为模板，以便您可以传递用于定义每个节点要执行的操作的函数/函数对象。类似于这样（快速而肮脏的伪代码，但您明白我的意思...）：

class A {
public:
    ...
    void AddItem(const T& item, int index) {
        rwlock.lock_write();
        // add the item
        rwlock.unlock_write();
    }

    void RemoveItem(const T& item) {
        rwlock.lock_write();
        // remove the item
        rwlock.unlock_write();
    }

    template <class P>
    void iterate_list(P pred) {
        rwlock.lock_read();
        std::for_each(my_stuff.begin(), my_stuff.end(), pred);
        rwlock.unlock_read();
    }

private:
    rwlock_t rwlock;
    list<T> my_stuff; //Just as well a vector or deque
};


extern A a; //defined in the .cpp file

class B {
    ...
    void SomeFunction() { ... a.RemoveItem(item); }
};

class C {
    ...

    void read_node(const T &element) { ... }

    void IterateOverStuff() {
        a.iterate_list(boost::bind(&C::read_node, this));
   }
};

另一种选择是将读写锁公开，由调用者负责正确使用锁。但这样更容易出错。