2

I'm working on a multithreaded application that uses a std::map underneath. I am aware that writing to std::map is not thread safe and I need to lock the tree when I'm writing.

However, I couldn't find a definition of "writing". Does it only include operations that insert or remove elements from the tree? Or does modifying an element's value in the tree also count as a write?

Consider std::map<int, MyClass> Test, where MyClass has a member variable int x.

Let's say MyClass& t = Test.at(7);. Is t.x++ then considered a write to the map?

Semin Park
  • 650
  • 6
  • 20
  • 2
    *Is t.x++ then considered a write to the map?* not exactly, but you still have to worry about two or more threads all hitting whatever object is being referred to by `t`. Protecting the `map` is only part of the problem. Here's some good reading on a related concept: [Why is Java Vector (and Stack) class considered obsolete or deprecated?](https://stackoverflow.com/questions/1386275/why-is-java-vector-and-stack-class-considered-obsolete-or-deprecated). – user4581301 Mar 10 '19 at 04:25
  • Yes. since `at` method returns reference. – Hanjoung Lee Mar 10 '19 at 04:26
  • @user4581301 I understand that two or more threads can modify the same element in the tree, in which case I still need a lock. However, my question is strictly regarding the modification of the value of an element in the tree. From your comment, can I assume that it is not a *write* to the **tree**? – Semin Park Mar 10 '19 at 04:29
  • My point is more the technicality of whether or not it is a write to the `map`doesn't matter. You need to protect the map and everything in it. If you aren't thinking transactionally, you're going to have nasty surprises. – user4581301 Mar 10 '19 at 04:40
  • If you're worried about integrity of read data, I'd recommend always locking, no matter if you write or read because concurrent threads reading/writing elements in the tree may very much operate on the same elements. If you read a value as someone else is writing, that's an issue. Unless you know exactly how the map is being used (e.g. no reads before writes are completed) then you should lock all time. – Everyone Mar 10 '19 at 04:55

2 Answers2

2

Is t.x++ then considered a write to the map?

Yes. You are updating the value of an item in the map. That is writing to the map.

It's analogous to updating the value of an element in an array.

int array[5] = {};
int& item = array[2];
++item;  // This is writing to the array.

In your case, 

MyClass& t = Test.at(7);

returns a reference to an item in the map. If value of t is updated, the map is also updated.

Another clue to get an answer to that question is the return value of a std::map::at() for a const object.

T& at( const Key& key );
const T& at( const Key& key ) const;

As you can see, the library doesn't allow you to modify the returned object of the call to std::map::at() for a const object. I.e. the library deems any modifications to the returned value of the function to be a modification of the std::map object.

R Sahu
  • 204,454
  • 14
  • 159
  • 270
2

What counts as “write” to std::map?

Depends on context.

Or does modifying an element's value in the tree also count as a write?

It counts as a write to that element.

It doesn't count as a modification of the tree† structure. As such, it is thread safe to modify one map element and concurrently read other elements or traverse the map - while it is indeed not safe to do so when concurrently inserting or erasing elements without synchronisation.

Whether you need synchronisation to read and modify the same element concurrently depends on whether the element object is thread safe.

† Standard doesn't explicitly require or guarantee that std::map is a tree. But it is always implemented using a tree.

eerorika
  • 232,697
  • 12
  • 197
  • 326
  • Thank you! My concern was whether the modification of a value of an element could lead to the tree being rebalanced (or anything that would lead to a change in the tree structure). Then can I assume that I only need a lock on the entire tree if I'm inserting or deleting elements from the tree? And if I'm only modifying some member variables of an element in the tree, I only need a lock for that specific element, am I correct? – Semin Park Mar 10 '19 at 05:01
  • 2
    @SeminPark The value of an element cannot force a rebalance. Balancing is based on the key, and the key is `const`. If you have built a structure where the value of the key includes the data you have just changed, key has a reference to the value for example, there is no way for `map` to know it. – user4581301 Mar 10 '19 at 05:13