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

[Peter Dimov]

Paolo Carlini wrote:
> 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?

The basic idea is this:

template<class It> void f( It first, It last )
{
    // generic implementation
}

template<class T> void f( T * first, T * last )
{
    // optimized implementation
    // takes advantage of the fact that [first, last)
    // is guaranteed contiguous
}

template<class C> void g( C & c )
{
    g( c.begin(), c.end() );
}

If all containers that keep their elements in a contiguous block of memory 
(std::vector, std::string, std::valarray, user-defined array, string, matrix 
types) return pointers from begin/end, this code will automatically be 
optimal.

Otherwise, g() needs specific overloads for every container, in order to 
pass pointers to f() (using data() for string, &v[0] for vector, and so on.)

It is not possible to do the optimization by adding overloads to f(), 
because in

template<class T> void f( vector<T>::iterator first, vector<T>::iterator 
last );

T is a nondeduced context (*). You _can_ do the optimization in the 
implementation of the C++ library, but not in user code.

One alternative solution is to add a Contiguous iterator category that 
refines Random Access.

(*) typename omitted for brevity. :-)