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

[Joe Buck]

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.