Re: [libstdc++/61347] std::distance(list.first(),list.end()) in O(1)

[François Dumont <frs dot dumont at gmail dot com>]

On 14/04/2015 14:36, Jonathan Wakely wrote:
> On 14/04/15 13:50 +0200, Marc Glisse wrote:
> > [dropping gcc-patches]
> >
> > On Tue, 14 Apr 2015, Jonathan Wakely wrote:
> >
> > > We should also look into applying the same optimisation for
> > > __gnu_debug::list, as long as we don't lose the ability to detect
> > > errors like std::distance(l1.begin(), l2.end()) where &l1 != &l2.
> >
> > It requires its own implementation (in particular to detect 
> > distance(next(it),it)). It should be quite simple. Actually, I 
> > believe it can be done generically for all debug containers, since 
> > iterators contain a pointer to the container: check _M_is_begin() on 
> > the first argument, _M_is_end() on the second, check that their 
> > containers are the same, and return size() (we would still need to 
> > disable that for forward_list).
> >
> > I am not sure how useful it is though. By not walking the list, we 
> > will always lose some verification.
>
> Yeah, we wouldn't want to stop aborting on this by turning it into
> c.size():
>
>  std::distance(c.begin()+1, c.begin());
    I am just working on some patches to get rid of the iterator debug 
wrapper when we have been able to fully validate a range. Any container 
[begin, end) range is such a case. I use it within debug containers for 
the moment but will also do it for debug algos when I start introducing 
those. I will apply the same to __distance.

    Regarding extending this optimization to all debug mode containers 
I am not sure it is such a good idea. It would be the first time debug 
mode would be faster than normal mode, users might start wondering why 
debug mode is not the default !

François