Re: sampling using iterators
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.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34