Re: [Boost-users] [BGL] complexity of random_vertex/random_edge

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2005-05-18 21:15:01

On May 16, 2005, at 4:28 PM, martin f krafft wrote:
>
> Given a random access iterator and the number of elements,
> retrieving a random member should be doable in constant time. Is the
> complexity guarantee here based on the worst case of the lists only
> being directionally accessible? If yes, does using container class
> implementing the RandomAccessIterator concept automatically select
> constant-time versions of these random retrievers?

They should be constant time for random access traversal iterators, but 
unfortunately they are not. I've logged this as a bug and will try to 
fix it after 1.33.0 is released.

        Doug