bearophile wrote:
> Time ago you (Andrei) told me that you don't like a function like
len() to have a different computational complexity, like O(n) or O(1),
according to the input.
This reminds me of an excellent talk by Matt Austern on STL's
singly-linked lists.
One of the interesting points of the design was around the length of the
singly-linked list. In the end, he decides not to provide one.
I think his point was that getting the length of the data structure was
not one of the main operations of a singly list. I agree that the users
who really need length can wrap it in a struct that stores the length.
Although there doesn't seem to be a slide dedicated to that point, the
presentation is here:
http://www.accu-usa.org/Slides/SinglyLinkedLists.ppt
Ali
