On Tuesday, 28 May 2013 at 18:16:48 UTC, Jonathan M Davis wrote:
Now, that being said, I don't see a splice operation on either
SList or DList
(and I don't think that splicing an SList can be done in O(1)
anyway), so it
would appear that the implementation is optimizing for an
operation that it
doesn't currently support.
SList can be spliced, but the semantics are a bit more
complicated. In most cases, if you need to splice, you'd use a
DList anyway: SList is really for particular use cases.
I think that if splice is not in DList, it is only because it is
not *yet* in DList. I have an implementation ready to submit,
which adheres to Andrei's proposed container semantics. I have
not yet submitted it though, because fixing DList is more
important that inserting more functionality.
It's current semantics are neither value nor ref. It's...
something else. My fault for inserting it when trying to fix
previous clusterfuck. I've since submitted fix that gives it
classic semantics, but it's kind of just sitting there...
We should *really* see to getting it (or something else) pulled
through.
The same situation exists with C++'s std::list type though -
size() is O(n)
and splicing is O(1). However, we opted for not having
containers implement
inefficient operations like that (which C++ mostly did as well,
but not in this
case).
- Jonathan M Davis
That was in C++03. In C++11, length was reduced to 0(1). And
splice was increased to 0(N) (I think, I don't remember the exact
details, but it was definitely changed).
I'll look up the exact requirement later tonight.
