On Wed, 27 Jun 2012 14:46:36 -0400, Roman D. Boiko <[email protected]> wrote:
On Wednesday, 27 June 2012 at 18:26:46 UTC, Steven Schveighoffer wrote:
The thing that makes SList useless is the O(n) removal. Nobody will
ever use SList when they can write a replacement that has O(1) removal
in 10 minutes.
Do you mean something like indexed/sorted dictionary? It doesn't seem to
be that easy to implement. Or some other data structure with O(1)
removal?
struct Link
{
int val;
Link *next;
removeNext() {assert(next); next = next.next;}
}
O(1) removal, easy as that.
Look up SList docs, even with a reference to a *specific element*, you
cannot do O(1) removal.
Only recently did it add O(1) insertion, but only after a specific
element. Good luck implementing a way to do insert *before* that element
in O(1), it will be possible, but really obtuse.
-Steve
