C++ Thread-Safe Map

Question

Does anyone know where I can find an implimentation that wraps a std::map and makes it thread safe? When I say thread safe I mean that it offers only serial access to the map, one thread at a time. Optimally, this map should use only the standard-library and / or boost constructs.

Solution 1

Does not meet the criteria that you have specified, but you could have a look at the TBB containers. There is so called concurrent_hash_map which allows multiple threads to access concurrently the data in the map. There are some details, but everything is nicely documented and can give you an idea of the "concurrent container". Depending on your needs this might be totally inappropriate...

Solution 2

The boost shared_mutex would provide the best multiple reader/single writer approach to wrapping a standard map given your constraints. I don't know of any "pre-built" implementations that marry these two since the task is generally trivial.

Solution 3

You might look at Thread Safe Template Library

Solution 4

Try this library

http://www.codeproject.com/KB/threads/lwsync.aspx

It is implemented in a modern c++ policy based approach.

Here is some cut from the link to show the idea with the 'vector' case

typedef lwsync::critical_resource<std::vector<int> > sync_vector_t;
sync_vector_t vec;

// some thread:
{
   // Critical resource can be naturally used with STL containers.
   sync_vector_t::const_accessor vec_access = vec.const_access();
   for(std::vector<int>::const_iterator where = vec_access->begin();
         where != vec_access->end();
         ++where;
        )
   std::cout << *where << std::endl;
}

sync_vector_t::accessor some_vector_action()
{
   sync_vector_t::accessor vec_access = vec.access();
   vec_access->push_back(10);
   return vec_access;
   // Access is escalated from within a some_vector_action() scope
   // So that one can make some other action with vector before it becomes
   // unlocked.
}

{
   sync_vector_t::accessor vec_access = some_vector_action();
   vec_access->push_back(20);
   // Elements 10 and 20 will be placed in vector sequentially.
   // Any other action with vector cannot be processed between those two
   // push_back's.
}

Solution 5

I came up with this (which I'm sure can be improved to take more than two arguments):

template<class T1, class T2>
class combine : public T1, public T2
{
public:

    /// We always need a virtual destructor.
    virtual ~combine() { }
};

This allows you to do:

// Combine an std::mutex and std::map<std::string, std::string> into
// a single instance.
combine<std::mutex, std::map<std::string, std::string>> lockableMap;

// Lock the map within scope to modify the map in a thread-safe way.
{
    // Lock the map.
    std::lock_guard<std::mutex> locked(lockableMap);

    // Modify the map.
    lockableMap["Person 1"] = "Jack";
    lockableMap["Person 2"] = "Jill";
}

If you wish to use an std::recursive_mutex and an std::set, that would also work.

View more solutions

Comments

[Oliver]

Is this Library Intel CPU dependent ?

[einpoklum]

Can you please explain why making thread-safe containers was a mistake?

[Dan Breslau]

Better late to respond than never, I guess? A common error pattern that I saw in Java with the original Hashtable, etc. (which were supposed to be thread-safe) was code that iterated over the table without explicitly locking it before and after the loop. This leaves other threads free to access the table concurrently. If either the first thread (the one that's iterating) or any of the others are modifying the table, this will lead to race conditions. I believe that the fact that Hashtable was advertised as "thread-safe by design" encouraged that bug pattern.

[Etienne de Martel]

Why do you always need a virtual destructor? Also, the map is not "thread safe" in itself, it just carries its lock with it, so you still need to manually lock the map. And while it's not a necessarily a bad idea to have a "map and lock in the same object" thing, I'd really prefer composition rather than inheritance for that.

[Jerry]

Although there are certain situations where you can get away with it, it's considered short-sighted to presume that a class won't be subclassed. Without a virtual destructor, a pointer/reference to a descendent instance of the subclass could be destructed causing destructors of all descendants to be skipped. This would typically cause a memory/resource leaks -- or worse. The cost of not declaring a destructor virtual can be quite high whereas the cost of declaring it virtual is near-zero. The rule-of-thumb is to always declare destructors virtual and you'll never get in trouble.

[Jerry]

To your second point, agreed. This template allows you to combine two classes that support default constructors into a single instance. In this example, it gives you the power to treat a single instance in a thread-safe way, but doesn't inherently make any of its methods thread-safe. All threads would have to lock the map before performing any non-reentrant method on the map.

[justhecuke]

That's a bit of a nonsense explanation. "thread-safe" just means that you won't get data corruption, crashes, and such when concurrently accessing the object. It doesn't mean an absence of race conditions or transactions or something else like that. Much like how single-thread-safe collections do not somehow cause your code to not have bugs. That there are bad programmers out there who aren't good at multi-threading doesn't mean that having thread-safe data structures is a bad idea. Indeed, without that safety the program would likely be significantly worse.

[Dan Breslau]

@justhecuke I didn't explain it well, to be sure. WRT the Java classes, what I should have focused on is that in the original Java container classes, the consumer always pays the cost for synchronization. But when synchronization is actually needed, they will (often to usually) still have to do extra work to get it right. In effect, those containers offer the worst of both worlds. But I don't even know why 12-years-younger me said that thread-safe containers would be a mistake in C++; especially if implemented as a wrapper around non-synchronized containers.