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

Question

我有一個容器（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受到添加或刪除操作的「保護」？

Answer 1

聽起來像是reader/writer lock是必要的。基本上，這個想法是，你可能有一個或多個閱讀器或單個作家。永遠不可以同時擁有讀寫鎖。

編輯：我認爲適合您的設計的使用示例涉及到一個小的改變。爲擁有該列表的類添加一個「迭代」函數，並將其設置爲模板，以便可以傳遞函數/函數來定義每個節點要執行的操作。像這樣的東西（快速和骯髒的僞代碼，但你明白了吧...）：

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)); 
    } 
}; 

另一個選項將是使讀取/寫入器鎖可公開訪問，並有責任正確使用呼叫者鎖。但是這更容易出錯。

Answer 2

當您返回列表時，將其返回封閉在一個類中，該類在構造函數/析構函數中鎖定/解鎖互斥鎖。東西沿線

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。

哦，讀寫器鎖確實是一個比互斥鎖更好的解決方案。

Answer 3

恕我直言，在數據結構類中有一個私有互斥體，然後編寫類方法，以至於無論調用方法的代碼執行什麼代碼都是線程安全的，都是錯誤的。完成這項工作所需要的複雜性是完全勝任的。

更簡單的方法是在需要訪問數據時調用代碼負責鎖定的公共（或全局）互斥鎖。

Here是我在這個問題上的博客文章。