sampling using iterators

[Leon]

using
multimap<int,int>::iterator itlow = pq.lower_bound (x);
multimap<int,int>::iterator itup = pq.upper_bound (y);

I obtain lower and upper bound from the multimap, and having these two
iterators I would like to sample one element with uniform distribution.
It a way do to this using iterators? I can of course draw an integer and
loop over the sequence until I meet the drawn value, but it is not a
very nice solution. Can sample directly using iterators?

thanks

 

[Juha Nieminen]

using
multimap<int,int>::iterator itlow = pq.lower_bound (x);
multimap<int,int>::iterator itup = pq.upper_bound (y);

I obtain lower and upper bound from the multimap, and having these two
iterators I would like to sample one element with uniform distribution.
It a way do to this using iterators? I can of course draw an integer and
loop over the sequence until I meet the drawn value, but it is not a
very nice solution. Can sample directly using iterators?

I don't really understand what do you mean by "sample". If you mean
that you want (constant-time) random access to the range above, that's
just not possible with multimap iterators, as they are not random access
iterators.

If you *really* need that (eg. for efficiency reasons) then one
solution might be to instead of using a multimap, use a regular map with
a vector (or deque) as element, so that each element with the same key
is put into the vector correspondent to that key. Then you can
random-access the vector when you need to.

(Of course the downside of this is that inserting and removing
elements is not, strictly speaking, O(lg n) anymore... But you can't
have everything at once.)

 

[Leon]

I don't really understand what do you mean by "sample". If you mean
that you want (constant-time) random access to the range above, that's
just not possible with multimap iterators, as they are not random access
iterators.

If you *really* need that (eg. for efficiency reasons) then one
solution might be to instead of using a multimap, use a regular map with
a vector (or deque) as element, so that each element with the same key
is put into the vector correspondent to that key. Then you can
random-access the vector when you need to.

(Of course the downside of this is that inserting and removing
elements is not, strictly speaking, O(lg n) anymore... But you can't
have everything at once.)

Yes, since the iterator is not random for multimap I have to loop
anyway. Thanks!

 

[Andrew Koenig]

using
multimap<int,int>::iterator itlow = pq.lower_bound (x);
multimap<int,int>::iterator itup = pq.upper_bound (y);

I obtain lower and upper bound from the multimap, and having these two
iterators I would like to sample one element with uniform distribution. It
a way do to this using iterators?

Assume you have a function nrand that takes an integer n and returns a
uniform random integer k such that 0 <= k < n.

Then I think this code will do what you want:

assert (itlow != itup); // necessary for a result to be possible

multimap<int,int>::iterator result;
int n = 0;
while (itlow != itup) {
if (nrand(++n) == 0)
result = itlow;
++itlow;
}

Note that the first call to nrand will be nrand(++n) with n initially 0,
which is effectively nrand(1). By definition, nrand(1) is always 0, so
result will always be initialized the first time through the loop.
Moreover, the loop will always execute at least once because of the assert.
Therefore, there is no risk that result might not be initialized.

 

[James Kanze]

I don't really understand what do you mean by "sample". If you
mean that you want (constant-time) random access to the range
above, that's just not possible with multimap iterators, as
they are not random access iterators.

If you *really* need that (eg. for efficiency reasons) then
one solution might be to instead of using a multimap, use a
regular map with a vector (or deque) as element, so that each
element with the same key is put into the vector correspondent
to that key. Then you can random-access the vector when you
need to.

He seems to be looking for a range (lower_bound and upper_bound
are called with different arguments), not just a single key.
But using a sorted vector, with the library functions
lower_bound and upper_bound, would definitely be a possible
solution. As you say, insertion would be more expensive, but a
lot depends on the other use he makes of the structure, and how
expensive copying or swapping the elements might be. (Using
lower_bound on a sorted vector is actually significantly faster
than map.lower_bound, at least with the implementations I've
tested.)