Are there better ways to erase elements from tbb::concurrent_hash_map than using keys?

[xamidi]

I am looking for a good way to erase elements from a huge tbb::concurrent_hash_map<std::string, std::string> object.

In an effort to replace tbb::concurrent_unordered_map by tbb::concurrent_hash_map (because the former does not support concurrent modification of elements), I came across the issue that tbb::concurrent_hash_map cannot erase elements via iterator, but only via accessor or key.

But my keys are strings (more precisely, formulas that are conclusions of a proof given as the value) and I would prefer to not collect a lot of them to merely remember which are to be erased, because this may result in millions of long strings to pollute the memory.

My code concurrently iterates over tbb::concurrent_hash_map<string, string> representativeProofs in a specific way while not modifying it in order to find elements that should be removed, to then subsequently remove these elements.

• For tbb::concurrent_unordered_map, I simply used iterators. I found no guarantees for tbb::concurrent_hash_map that iterators remain valid when other elements are removed, otherwise for iterator it I could use erase(it->first) (this still would require key-lookups, though).
• I expected that erasing by accessors wouldn't require another lookup, so I experimented with something like this:

tbb::concurrent_unordered_map<const string*, tbb::concurrent_hash_map<string, string>::const_accessor> toErase;
tbb::parallel_for(representativeProofs.range(), [&](tbb::concurrent_hash_map<string, string>::range_type& range) {
	for (tbb::concurrent_hash_map<string, string>::const_iterator it = range.begin(); it != range.end(); ++it) {
		// [...]
		if (redundant) {
			// the key's address is good to use while 'representativeProofs' remains untouched
			tbb::concurrent_hash_map<string, string>::const_accessor& rAcc = toErase[&it->first];
			if (rAcc.empty())
				representativeProofs.find(rAcc, it->first); // lookups in parallel
				// TODO: Can we somehow construct a read accessor directly from an iterator?

			// [...]
		}
	}
});
// [...]
for (pair<const string* const, tbb::concurrent_hash_map<string, string>::const_accessor>& p : toErase)
	representativeProofs.erase(p.second); // sequential erasures ; should also work in parallel

But somehow this results in undefined behavior. [Edit: Probably a lock around 'find()' would fix this?]

• Is there a way to construct read accessors directly from iterators in order to avoid the extra lookups?
• Can we emplace an empty const_accessor so that toErase[&it->first] can be avoided?
• How to make this code safe and performant? Which of my assumptions are wrong? For example,
  • is erase(const_accessor) faster than erase(key),
  • shouldn't const_accessors remain valid while other elements are removed, and
  • are const_iterators really invalidated upon erasure of other elements?

I could not find a documentation stating which guarantees can be made on the validity of iterators and accessors after which operations.
Or a safe code example of how to best remove elements while or after iterating.

So far the only reliable method seems to be erasure by stored keys (i.e. many erase(const string&) here).
But I suspect erasure via keys is also fine in parallel (in contrast, erasure is not thread-safe for tbb::concurrent_unordered_map).
Is copying and using (a potentially huge number of) the keys really the one and only best method?

[omalyshe]

FYI @kboyarinov