https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61347
Bug ID: 61347
Summary: std::distance(list.first(),list.end()) in O(1)
Product: gcc
Version: 4.10.0
Status: UNCONFIRMED
Severity: enhancement
Priority: P3
Component: libstdc++
Assignee: unassigned at gcc dot gnu.org
Reporter: glisse at gcc dot gnu.org
Depends on: 49561
Hello,
since C++11 is making list::size O(1) (never mind my opinion on that), I think
it would be nice to try and make std::distance(list.first(),list.end()) benefit
from that through an overload. Indeed, a number of algorithms take iterator
arguments and first compute their distance, without giving users a chance to
pass list.size() and avoid that O(n) traversal.
The way list is implemented, when we see a call distance(a,b) between list
iterators, we can test ++b==a (preferably not literally) and if it is true I
think it means that a is l.first() and b is l.end(). From l.end() we can
determine the address of the list l and call l.size(). However, instead of
using some kind of ugly offsetof, it may be nicer to change _List_Impl::_M_node
to a _List_node<size_t> and store the size there. I am filing this PR now
because it may influence the exact way PR 49561 will be fixed.
If the cost of testing for this special case seems excessive, I think it would
be ok to make it a __builtin_constant_p test, it should still catch a number of
cases.
