Ready for review: new std.uni

[Jonathan M Davis]

On Sunday, January 13, 2013 04:58:16 Chad J wrote:
> On 01/13/2013 02:28 AM, Jonathan M Davis wrote:
> > I really should ask Andrei why he made length require O(log n) instead
> > O(1)...
> > 
> > - Jonathan M Davis
> 
> Are there cases where it can't be O(1)?

Most definitely. Take a doubly linked list for example. Either length can be 
O(1) and splicing is then O(n), or length is O(n) and splicing is then O(1). 
That's because if you want to keep track of the length, you have to count the 
number of elements being spliced in. For instance, it's a relatively common 
mistake in C++ to use std::List's size function and compare it with 0 to see 
whether the list is empty, because size is O(n). The correct thing to do is to 
call empty and check its result.

You _could_ make std::list's size function be O(1), but that would mean that 
splicing becomes O(n), which C++98 definitely did not do (though I hear that 
C++11 made the interesting choice of changing how std::list works so that size 
is O(1) and splicing is O(n); I don't know if that's good or not).

std.container.slist and std.container.dlist don't define length precisely 
because it can't be O(1) given their design.

- Jonathan M Davis