Ready for review: new std.uni

monarch_dodra monarchdodra at gmail.com
Sun Jan 13 03:39:35 PST 2013


On Sunday, 13 January 2013 at 10:24:17 UTC, 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

Yes, size is now "o(1)" in C++11.

However, splice's complexity remains "o(1)" if the list spliced 
from/to is the same. It only degenerates to "o(N)" if they are 
not the same list.

Also, note that with the old implementation, while length was 
"O(N)", most implementations could still cache the result it to 
give "0(1)" access, and only invalidate the cache when splicing 
with another list.

But enough off topic here I guess ;)


More information about the Digitalmars-d mailing list