Thread safe C++ std::set that supports add, remove and iterators from multple threads

Question

I'm looking for something similar to the CopyOnWriteSet in Java, a set that supports add, remove and some type of iterators from multiple threads.

Answer 1

All I can think of is to use OpenMP for parallelization, derive a set class from std's and put a shell around each critial set operation that declares that operation critical using #pragma omp critical.

Answer 2

Qt's QSet class uses implicit sharing (copy on write semantics) and similar methods with std::set, you can look its implementation, Qt is lgpl.

Answer 3

You can also take a look at ACE library which has all thread safe containers you might ever need.

Answer 4

Why not just use a shared mutex to protect concurrent access? Be sure to use RAII to lock and unlock the mutex:

{
   Mutex::Lock lock(mutex);
   // std::set manipulation goes here
}

where Mutex::Lock is a class that locks the mutex in the constructor and unlocks it in the destructor, and mutex is a mutex object that is shared by all threads. Mutex is just a wrapper class that hides whatever specific OS primitive you are using.

I've always thought that concurrency and set behavior are orthogonal concepts, so it's better to have them in separate classes. In my experiences, classes that try to be thread safe themselves aren't very flexible or all that useful.

Answer 5

Thread safety and copy on write semantics are not the same thing. That being said...

If you're really after copy-on-write semantics the Adobe Source Libraries has a copy_on_write template that adds these semantics to whatever you instantiate it with.

Answer 6

there isn't one that I know of, the closest is in thread building blocks which has concurrent_unordered_map

The STL containers allow concurrent read access from multiple threads as long as you don't aren't doing concurrent modification. Often it isn't necessary to iterate while adding / removing.

The guidance about providing a simple wrapper class is sane, I would start with something like the code snippet below protecting the methods that you really need concurrent access to and then providing 'unsafe' access to the base std::set so folks can opt into the other methods that aren't safe. If necessary you can protect access as well to acquiring iterators and putting them back, but this is tricky (still less so than writing your own lock free set or your own fully synchronized set).

I work on the parallel pattern library so I'm using critical_section from VS2010 beta boost::mutex works great too and the RAII pattern of using a lock_guard is almost necessary regardless of how you choose to do this:

template <class T>
class synchronized_set
{
    //boost::mutex is good here too
    critical_section cs;
public:
    typedef set<T> std_set_type;
    set<T> unsafe_set;
    bool try_insert(...)
    {
        //boost has a lock_guard
        lock_guard<critical_section> guard(cs);
    }
};

Answer 7

You don't want internal locking, as your invariants will often require multiple operations on the data structure, and internal locking only prevents the steps happening at the same time, whereas you need to keep the steps from different macro-operations from interleaving.