Boost logo

Boost Users :

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


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

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at