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

[Peter Dimov]

Joe Buck wrote:
> On Tue, Nov 29, 2005 at 03:56:36PM +0200, Peter Dimov wrote:
>> 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.) 
> 
> Isn't this a job for type traits?  If we had a "contiguous" trait,
> which is true for T* or vector<T>::iterator or
> vector<T>::const_iterator but false in general, this would work out
> cleanly.

Yes, in fact, I think I mentioned that.