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

[Howard Hinnant]

On Nov 28, 2005, at 4:25 PM, Jonathan Wakely wrote:

> On Tue, Nov 29, 2005 at 01:58:11AM +0100, Gabriel Dos Reis wrote:
>>
>>    (1) what would have been more interesting is the percentage of
>>        those usage that are not "hookey usage" of list<>.  I take  
>> that
>>        percentage to be far compelling.
>
> I think we all agree that if performance of anything except  
> splicing is
> really important, then std::list is often the wrong choice, right?

I disagree.  The intent of my pointing out the code using list::size  
was to point out that there is a lot of reasonable code out there  
that runs just fine everywhere but gcc.

> The fact that good programmers do rely on O(1) list::size() in real  
> code
> doesn't change the fact that such code is buggy (or, at least,
> sub-optimal).

Yes, such code is buggy with respect to the standard since the  
standard says that list::size() can be O(N).  The standard also says  
the following functions can be O(N).  All code that relies on these  
being O(1) is also buggy:

list::swap
list::max_size
deque::size
deque::max_size
deque::swap
vector::size
vector::max_size
vector::swap
map::size
map::max_size
map::swap
multimap::size
multimap::max_size
multimap::swap
set::size
set::max_size
set::swap
multiset::size
multiset::max_size
multiset::swap

... or maybe the standard itself has a bug ...

> If libstdc++ did provide an O(1) list::size() programmers still
> couldn't rely on it in portable code - so they still *shouldn't* rely
> on it.  So only sub-optimal, non-portable code would be helped.

And what if the standard gets changed?

-Howard