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