Algorithmic complexity of len (list)?

[Roy Smith]

In article <ccebgm$f6g$1 at panix3.panix.com>, aahz at pythoncraft.com (Aahz) 
wrote:

> In article <roy-4C2E61.19182002072004 at reader2.panix.com>,
> Roy Smith  <roy at panix.com> wrote:
> >
> >Is the length of a list stored in the object, or does len() have to 
> >count the elements each time you call it?  In other words, is len (list) 
> >O(1) or O(n)?
> 
> Consider that if it weren't, operations such as l.pop() and l[-3:] would
> also be O(N)...
> 
> (I couldn't resist making a comment because I'm currently using your
> .sig. ;-)

Well, I take that as meaning, "you really should have been able to 
figure that out yourself if you just took the time to think about it".  
I disagree.  I can guess, I can even make intelligent informed guesses, 
but it would still just be a guess.

One could think of implementations where l.pop() and l[-3:] are O(1), 
but len(l) is O(n).  I could, for example, keep a pointer to the tail of 
the list, but not keep track of the number of elements.

Why would somebody want to implement it that way?  I don't know, but 
it's possible.  Maybe they felt that accessing the ends of lists was 
something that needed to be done fast, but computing their length 
wasn't, and saving the extra bit of memory for each list was important.

Iterators sort of look like lists, but I can't get their length quickly 
(or even idempotently, it would appear).  If they didn't think getting 
the length of an iterator was important, then maybe they didn't think 
getting the length of a list was important either.

I can make measurements, or download the source and look at it, but I 
shouldn't have to.  Likewise, I shouldn't have to engage in a deep 
analytic guessing game of what the designer had in mind when designing 
the container.  I want a tool, not a hobby. One of the (few) things I 
like about the C++ STL is that it documents these types of things.  Is 
there any reason Python couldn't?