Avi Bryant a écrit :
> On 5/25/07, nicolas cellier <ncellier at ifrance.com> wrote:
> 
>> Yes, it transforms cost from O(N) to O(1).
>> That was some provocation.
>> Though, i tried using them once, they are not generic.
>> Only a specific thing tailored for Process List.
>> I should be ashamed to say that, but C++ std::list are really easier to
>> use than current LinkedList (I mean i cannot replace OrderedCollection
>> with LinkedList transparently).
> 
> Either you can have transparency, or you can have O(1)
> insertion/removal, but I don't see how you can have both.  To get
> O(1), you have to have a reference to the link you want to remove or
> insert after, which isn't transparent; if you just had a regular
> object like you would put in an OrderedCollection, you would have to
> do a linear scan through the list to find the right link, and you're
> back to O(n).  No?
> 
> Avi
> 
> 

Right.
If you want 0(1) in C++ you have to deal with iterators.
And iterators are transparent because used on all other containers 
(collection). You just ignore underlying links (a special species of 
iterator).

Nicolas