Re: no upper_bound() for unordered_multimap
Pete Becker wrote:
On 2010-10-18 11:45:49 -0400, Ralf Goertz said:
Pete Becker wrote:
What should upper_bound return for a key of 3? Yes, it could return
an iterator pointing to the first element, but what can you sensibly
do with that iterator?
It should return the iterator that comes after the iterator for "3".
That is the iterator that I get when I traverse the whole unordered
multimap.
That's a different definition of upper_bound than the current one,
I know that upper_bound might be a misleading name, it is just
convenient to have an interface to unordered_multimap that is as similar
to multimap as possible. In fact the problem arose when I changed a
multimap to unordered_multimap in a working program. I am not
particularly interested in the iterator ub returned by upper_bound. I
just use it to make sure I haven't left the equal_range. Therefore I
don't care whether the key of ub is greater or less than the key I am
currently working on. I just want ub to be the same iterator that comes
*after* the last interesting iterator so that comparison i!=ub returns
false.
typedef unordered_multimap<int,int> UM;
UM m;
//m is filled and then multithreading begins
pair<UM::iterator,UM::iterator> itp=m.equal_range(thread_specifik key);
for(;itp.first!=itp.second;++itp.first) // does itp.second still exist?
{
//possibly erase(itp.first)
}
Even if you could use upper_bound to get the value you want, this code
formally has data races. Erasing from the container in one thread while
another thread is incrementing an iterator into the same container is a
data race, and results in undefined behavior. For example, suppose one
thread is inside the call to equal_range, and happens to hold an
iterator to element X when a context switch occurs, and the new thread
erases element X; now there's serious trouble.
I know that. That's why (using OMP for multithreading) every change of
the map is guarded by a
#pragma omp critical
directive.