Threadsafe Vector class for C++

Question

Does anyone know a quick and dirty threadsafe vector class for c++? I am multithreading some code, and I believe the problem I have is related to the way the vectors are used. I plan to rewrite the code, but before I go crazy redoing the code, I would like to test it with a threadsafe vector to be sure. I also figure if such a thing is out there, it would be much easier than writing my own version.

Answer 1

As Scott Meyers explains in the effective STL book, by a thread safe container you can expect that:

• Multiple reads are safe
• Multiple writes to different containers are safe.

Thats all. You can not expect many other things such as multiple writes to the same container be thread safe. If this is all what you want then you can take a look at STLPort. If not then the only option I see is to contain the vector in a class that synchronizes the access to the vector.

Answer 2

You can check out TBB (like concurrent_vector). I've never used it though, honestly, I find putting the scope guard objects around access easier (especially if the vector is properly encapsulated).

Answer 3

I think you'll find it far easier to continue to use std::vector, but to protect concurrent access using some kind of mutex or other operating system synchronization object. You'll also definitely want to use RAII if you are using a mutex.

Answer 4

This is difficult because of algorithms.

Suppose you wrapped vector so that all its member functions are serialised using a mutex, like Java synchronized methods. Then concurrent calls to std::remove on that vector still wouldn't be safe, because they rely on looking at the vector and changing it based on what they see.

So your LockingVector would need to specialize every template in the standard algorithms, to lock around the whole thing. But then other algorithms like std::remove_if would be calling user-defined code under the lock. Doing this silently behind the scenes is a recipe for locking inversion as soon as someone starts creating vectors of objects which themselves internally take locks around all their methods.

In answer to your actual question: sorry, no, I don't know of one. For a quick test of the kind you need, I recommend that you start out with:

template <typename T>
class LockedVector {
    private:
    SomeKindOfLock lock;
    std::vector<T> vec;
};

Then drop it in as a replacement container, and start implementing member functions (and member typedefs, and operators) until it compiles. You'll notice pretty quickly if any of your code is using iterators on the vector in a way which simply cannot be made thread-safe from the inside out, and if need be you can temporarily change the calling code in those cases to lock the vector via public methods.

Answer 5

I forget who discussed this, but one strategy for making a thread-safe container is as follows:

1. All your class's public methods must lock the vector, and must return a boolean for if they succeeded (and they might not succeed!). So instead of using f = myvec[i], use if (myvec.tryGet(i, &f)) {...} and implement the class accordingly.
2. Do not provide a count method. Users must use iterators to traverse the vector.

Note: Be careful with iteration. You must be clever about maintaining a never-shrinking vector with bounds-checking iterators or you might have code that has buffer-overflow type errors.

The lame and easy way to provide a "thread-safe" vector is to just take a standard vector and lock the vector on every method. But if you do this, you could still end up with broken code (e.g. a loop that iterates from 0 to vec.count may have count change while it is iterating).

A 2nd means of providing "thread-safe" containers is to create immutable containers (every method returns a new container. This was definitely discussed by Eric Lippert. It's C#, but easily translates to C++ code, mostly. You'll still need to lock the container when you use it, but all the scary issues involving buffer overflows when iterators break and whatnot go away. Implementing an immutable container is probably relatively 2nd nature to those who are experienced with functional programming.