Re: [Boost-users] [multi-index] using std::distance() with ordered indices

Subject: Re: [Boost-users] [multi-index] using std::distance() with ordered indices
From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2011-06-23 10:26:42

dv <dv <at> pseudoterminal.org> writes:

> 
> Hello,
> 
> I need to find out the size of a range defined by two ordered_non_unique 
> iterators . Right now I just use std::distance() for this, however, the 
> time complexity in this case is O(n). Is there some special way for 
> calculating distances between multi-index container iterators?

No, I'm afraid there's no other option but to use std::distance
and this is O(n). If this particular operation is of special relevance
to you you can consider replacing your ordered_index with a
random_access index and keep this sorted manually (basically by
choosing the point of insertion with std::lower_bound): in this
scenario, getting the distance between iterators is constant time.

HTH,

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo