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

[Howard Hinnant <hhinnant at apple dot com>]

On Nov 28, 2005, at 3:16 PM, Peter Dimov wrote:

> Howard Hinnant wrote:
> > On Nov 25, 2005, at 9:06 PM, Gabriel Dos Reis wrote:
> >
> > > An error was made in putting it there in the first place.  I rather
> > > sequester that error instead of spreading through over the rest of
> > > the interface.
> >
> > I'll grant you that putting list::size in may have been an error.
>
> size() is part of Table 65. Is this an error?
>
> template<class C> void f( C & c )
> {
>    c.size(); // error?
>    std::distance( c.begin(), c.end() ); // "proper"?
> }
>
> Note how this penalizes _all_ containers that have O(1) size() and  
> non-random access iterators.

Actually I was thinking that size() may have better fit into the  
"Optional sequence operations" table (i.e. only if O(1)).  And so  
yes, if f positively needed the size information, c.size() would  
generate an error if C could not provide it (same rationale as for  
all other members of the optional sequence operations).  The compile  
time error in this case would be a feature, not a bug.  If we also  
relaxed the requirements about pointing to member functions of  
std::containers, then f could easily set up a compile-time detection  
trait for size(), and if it did not exist, perhaps perform an  
alternate algorithm, perhaps involving distance, perhaps not.  There  
are algorithms that would be written completely differently depending  
on whether size() is available as an O(1) operation or not.

Your concern about penalizing all containers that have O(1) size()  
and non-random access iterators is a valid concern, but I believe one  
that could be easily avoided with an optional size().

-Howard