[C++] Should the complexity of std::list::size() be O(n) or O(1)?

[Paolo Carlini]

Peter Dimov wrote:

>> At one point, all known implementations were using T* for
>> vector<T>::iterator; people made reasoning similar to the above and
>> later found that they had to re-evaluiate their assumptions.
>
> There are good arguments to be made in support of the claim that
> iterators into contiguous storage need to be pointers to allow
> algorithms to detect the case.

I'm interested in this point of yours. If I understand by and large the
issue (I'm especially sensible these days, because I'm also working on
overloads of some algorithms for deque<T>::iterator) there are no
particular problems as long as your vector<T>::iterator is a type
defined outside of vector... Besides, maybe, some tricky fall outs of
the design choice related to ADL, recently explained again in the
context of ""fixing ADL""?!? Is there something else I'm missing of the
full picture?

By the way, to the attention of Howard, in particular, I would be
interested in learning more about Metrowerks data() + n instead of
begin() + n implementation of vector<T>::operator[]... I don't see why
we couldn't (shouldn't) do that in libstdc++ too and avoid a good amount
of ADL troubles...

Paolo.