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

[Marc Glisse <marc dot glisse at inria dot fr>]

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

--
Marc Glisse