Ready for review: new std.uni

[Chad J]

On 01/13/2013 05:23 AM, Jonathan M Davis wrote:
> 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

Thanks!

That's a good example.  It made sense once I realized that you could be 
splicing in arbitrary sections of another list, not just an entire other 
list.

If I were to used cached lengths and splice in another list with a 
cached length, then I would just add the lengths of the two lists and do 
an O(1) splice.  I can see how this wouldn't cover all cases though.