9

I want to be able to read and write in a std::map from multiple threads. Is there a way to do that without mutex (maybe with std::atomic)?

If not, what's the simplest way to do that in C++11?

MartinMoizard
  • 6,600
  • 12
  • 45
  • 75
  • You need to protect your map with mutex. You may also look at this template class: https://github.com/Kicer86/openlibrary/blob/master/src/putils/ts_resource.hpp which wraps any object and makes it threadsafe. – Michał Walenciak Apr 27 '15 at 09:41
  • Looks to be a [duplicate](http://stackoverflow.com/questions/14338732/is-it-possbile-to-implement-lock-free-map-in-c) – holtavolt Apr 27 '15 at 09:46
  • @holtavolt: my impression is that this question explores whether some level of threaded operation can be achieved using `std::map` without `mutex`, while the other question looks at alternatives to `std::map` (i.e. non-Standard associative maps) for when it's decided `std::map` is insufficiently flexible. The answer to this question may well lead readers to the other question.... – Tony Delroy Apr 27 '15 at 10:59
  • @Tony D - fair point - retracted, and you've provided a good answer to constraints of the std::map – holtavolt Apr 27 '15 at 11:23

2 Answers2

7

If the values are std::atomic<>, you can modify and read them from arbitrary threads, but you'll need to have saved their addresses somehow - pointers, references or iterators - and you'll need to know no other thread will call erase on them....

Still, even atomic values won't make it safe to modify the container (e.g. inserting or erasing elements), while other threads are also doing modifications or lookups or iteration. Even the "const" functions - like size(), empty(), begin(), end(), count(), and iterator movement - are unsafe, because the mutating operations may be in the middle of rewiring the inter-node links or updating the same data.

For anything more than the above, you will need a mutex.

For a concrete example, say you've inserted a node with std::string key "client_counter" - you could start a thread that gets an iterator to that element and does atomic updates to the counter, while other threads can find the element and read from it but must not erase it. You could still have other nodes inserted in the map, with other updaters and readers, without any extra synchronisation with the client_counter-updating thread.

Tony Delroy
  • 102,968
  • 15
  • 177
  • 252
  • So really, if you want to use a std::map concurrently, you'll need a _readers-writer lock_. – Gerard Apr 27 '15 at 09:57
  • @Gerard: "so really" makes it sound like you are offering a handy summary of my answer, but your comment dismisses atomic ops on values and introduces a new topic - whether reader-writer locks are always preferable to the humble mutex. While atomic access to values is *very* restrictive, I'll leave it to the OP and other readers to determine utility in their specific scenarios, and to decide on exactly which non-lockfree synchronisation mechanism to use... that's another question. Cheers. – Tony Delroy Apr 27 '15 at 10:12
1

If you don't want to use mutex then you need to wait for concurrent containers (C++17?). If you want to use std::atomic operations inside std::map then you probably want to make or found on the Internet fully implementation of concurrent atomic std::map.

If you want to use std::map of std::atomic then you probably need to know that this will protect only elements inside std::map, but not std::map in self.

senfen
  • 877
  • 5
  • 21