quote:Original post by Tommy Carlier
I hear (read?) everyone say (write?) that to find list[x] in a linked list, you need to loop over every element until you have i=x, and that this is very slow.
Yes, this method is very slow, but it doesn't mean that list[x] should be slow. I think one could create a pretty fast lookup-mechanism for finding list[x] in a linked list.

What if the first element of a linked list contains a pointer to the element with index = length/2? And that element contains a pointer to index = length/4 and index = length * 3/4? Wouldn't it produce a much faster list[x]?

That's called a tree and there are many different ways to build them. What you are suggesting is known as a "threaded tree" which allows for O(n) non-recursive forward transversal (the list allows this) and also O(log(n)) look-ups (basic trees give you this).

The reason you thread a tree is to obtain the simple O(n) forward transversal. Using the horrible [] implementation dicussed in this thread completely defeats the intention.

quote:
I hope this doesn't seem too stupid.

It's not stupid at all. The only criticism that threaded trees receive is the extra overhead of the additional pointers needed, which is only relevant if the size of the elements is small and there will be many of them.


...
The proposed std list implementations use a lazy-evaluated size() with a cached result so it's constant time when possible, linear time when it needs to re-tally and then splice is always constant time. The only time the size needs to be tallied is after a partial-list splice has been executed. This can still be a fully constant time operation if you tell it how many elements you are splicing in. This requires more programming complexity, but no extra O() work because you typically perform an iteration to determine the boundry conditions of the splice (thus you can keep count of how many are included). Very complicated, very efficent, but optional.

[edited by - Magmai Kai Holmlor on April 7, 2004 9:02:01 AM]

quote:Original post by DrPizza
In the original 1998 standard, no, it couldn't be a linear-time operation -- the performance constraints were simply impossible (list.size() must be constant time, and so must list.splice() even for splicing partial lists, which cannot be done). The 2003 standard may fix this, I don't remember.

This is unfortunate, but I'm not sure that anything can be done about it. list.size() (unlike indexed access) could at least be constant time on average, which though a weaker constraint is still better than forcing people to use std::distance(l.begin(), l.end()) every time.

Further, the size of a list is a property it has -- it does not require the invention of bogus indices.

quote:So why make size() for a list but not operator[]?

Because it can offer better performance guarantees than a non-member could.

quote:Original post by Magmai Kai Holmlor
The proposed std list implementations use a lazy-evaluated size() with a cached result so it's constant time when possible, linear time when it needs to re-tally and then splice is always constant time. The only time the size needs to be tallied is after a partial-list splice has been executed. This can still be a fully constant time operation if you tell it how many elements you are splicing in. This requires more programming complexity, but no extra O() work because you typically perform an iteration to determine the boundry conditions of the splice (thus you can keep count of how many are included). Very complicated, very efficent, but optional.

Ah, thanks guys for the additional info! Makes more sense now why they did that.


- Houdini

[edited by - Houdini on April 7, 2004 10:18:45 AM]