Hello,

this patch makes std::distance(list.first(),list.end()) a constant time 
operation when optimizing, with no penalty for other calls. We could do 
the test always (no __builtin_constant_p) but then it will add a small 
runtime penalty for other calls, someone else can take responsibility for 
that. I could protect the whole overload with #ifdef __OPTIMIZE__ (at -O0 
the compiler does not remove the test ++end==first as dead code), but I 
assume it is better to minimize differences. There are other ways to 
specialize distance, but overloading __distance seems to have the least 
drawbacks (most others involve a new extra file). From an optimization 
POV, it would be a bit better to avoid the while loop and instead call a 
separate function that does it (say the regular __distance), it would make 
the function smaller and thus easier to inline, but it is simpler this way 
and works.

We could do something similar for std::set, but C++ will not let us find 
the address of _Rb_tree_impl::_M_node_count from that of 
_Rb_tree_impl::_M_header, except when _Key_compare is pod, which luckily 
is an easily available information. Avoiding this complication is why I 
insisted on wrapping the size of std::list in a _List_node<size_t> for 
gcc-5, which may look a bit strange at first sight.

2015-04-13  Marc Glisse  <marc.glisse@inria.fr>

 	PR libstdc++/61347
 	* include/bits/stl_iterator_base_funcs.h (distance): Do not
 	qualify the call to __distance.
 	* include/bits/stl_list.h (__distance): New overloads for
 	_List_iterator and _List_const_iterator.
 	* testsuite/23_containers/list/61347.cc: New testcase.

-- 
Marc Glisse