search

Tessil / ordered-map

C++ hash map and hash set which preserve the order of insertion
MIT License
512 stars 66 forks source link

Thread safety for changing values of keys already in `ordered_map` #46

Open ericonr opened 7 months ago

ericonr commented 7 months ago

Hi!

I'm using this project's ordered_map. The values under the keys can change, but after the map is first populated, the keys always remain the same. In that situation, in a multithreaded program, is it safe to overwrite the value under one key from thread 1 while accessing another key from thread 2?

I took a look at https://tessil.github.io/ordered-map/classtsl_1_1ordered__map.html#details

insert, emplace, emplace_hint, operator[]: when a std::vector is used as ValueTypeContainer and if size() < capacity(), only end(). Otherwise all the iterators are invalidated if an insert occurs.

From that quote, is it correct that simply changing the value under one key isn't an "insertion" (as defined in something like cplusplus docs for std::unordered_map: adding a new element to the map) and therefore even an ordered_map using std::deque isn't invalidating its iterators (and therefore, can access values under other keys from another thread safely)?

If my understanding is correct and you think it makes sense, I could try my hand at updating the docs to make them clearer on this point.

Cheers!

ericonr commented 5 months ago

@Tessil ping :)

Tessil commented 5 months ago

Hi @ericonr

Sorry for the delay. Yes, your understanding is right.

Using insert or emplace on an existing key will not modify the map and as long as both threads are not trying to read and update the value of the same key, everything should be thread safe.

The documentation could effectively be updated to make the distinction between an actual insert and an insert call with an existing key (which will just return an iterator to the existing element similarly to find).

ericonr commented 5 months ago

Sorry for the delay. Yes, your understanding is right.

No worries, I know how easily things can slip up :) And that's great to know!

The documentation could effectively be updated to make the distinction between an actual insert and an insert call with an existing key (which will just return an iterator to the existing element similarly to find).

I will try and find the time to make a PR, then :)