[C++] Should the complexity of std::list::size() be O(n) or O(1)?
Howard Hinnant
hhinnant@apple.com
Tue Nov 29 03:11:00 GMT 2005
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
More information about the Libstdc++
mailing list