Re: [boost] [Countertree + Suballocator] New Version

Subject: Re: [boost] [Countertree + Suballocator] New Version
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2012-04-12 14:30:08

Dave Abrahams wrote:
> on Thu Apr 12 2012, Francisco José Tapia <fjtapia-AT-gmail.com> wrote:
> 
> > The iterators are random access , and you can subtract two iterators in
> > a O(log N) time for to know the number of nodes between them (even with
> > the end( ) and rend( ) iterators)
> 
> If by "are random access" you mean they satisfy the random access
> iterator requirements, then this is a contradiction.  Iterator
> subtraction is required to be O(1) for random access iterators.

If the container can store at most 2^64 elements, it can be hard to distinguish O(1) from O(log N). However, if O(log N) implies cache misses and swapping, then O(log N) may really be different from O(1) in practice.

Regards,
Thomas