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

[Victor Bazarov]

You can always use 'distance' or 'advance' to hide the loop. Since map
(or multimap) iterators aren't direct-access variety, you'll have to use
some kind of loop anyway, explicit or implicit.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[Juha Nieminen]

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]

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

[Andrew Koenig]

"Leon" <le...@poczta.onet.pl> wrote in message
news:geaa1v$8fm$2...@news.onet.pl...

> 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]

On Oct 30, 12:13 am, Juha Nieminen <nos...@thanks.invalid> wrote:
> Leon wrote:
> > 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.

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.)

--
James Kanze (GABI Software) email:james...@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34