Re: no upper_bound() for unordered_multimap
On 2010-10-18 11:45:49 -0400, Ralf Goertz said:
Pete Becker wrote:
upper_bound gives you an iterator that guarantees that every element
that comes before the key is in front of that iterator. While that can
be done, for an unsorted sequence it's not particularly useful:
{ 1, 4, 3, 2 };
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,
which would return an iterator that points to 4. If I mislead you with
my mis-statement of what upper_bound does, I apologize. Rephrasing what
I said earlier, it returns an iterator that points to the first element
for which every preceding value is less than or equal to the target key.
I think that is the one I get with equal_range(3).second. As I
said in my OP I don't see why there is equal_range() for
unordered_multimap but no upper/lower_bound().
equal_range searches for one particular value. upper_bound searches for
the end of a sequence of values, and that end point is not particularly
usefull if the original sequence is not ordered.
As to why I need upper bound: I use equal_range to visit all elements in
a multithreaded program. There will be no inserts into the
unordered_multimap (which could invalidate iterators) during the
multithreading. There are only erases. And that is the problem. I can't
be sure that the upper_bound-element still exists. Another thread might
have erased the element. That's why I want to check if my just
incremented iterator is equal to the upper_bound for that key. Maybe this
example explains it:
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.
Without knowing the details of the problem, I'd be more inclined to use
a vector or list for each thread, with a master map that maps a thread
key to the appropriate vector. Accesses to the master map have to be
externally synchronized, but accesses to the individual vectors don't.
Unless, of course, multiple threads can update the same vector
simultaneously, in which case I don't think there's an easy solution
short of brute force locking.
--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)