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

[François Dumont]

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