[boost] Re: change to linked_ptr release

From: Gavin Collings (gcollings_at_[hidden])
Date: 2000-02-08 06:25:42

> All the operations of linked_ptr are O(1).
> 
> The time required to make a call to release() is constant, it does not
> matter if there are 2 nodes or 2 million nodes in the linked_ptr list.
> 
> It is true that because of a call to release, each node in the list
> might have to do a tiny bit of work at some later time, this still
does
> not account into the efficiency of the individual operation.  Each of
> the subsequent operations is also O(1).

Well, let's agree to disagree on accounting policy.  Maybe this best
sums it up: -

  operation time         O(1)
  associated overhead    O(N) (7..20)/100 * N by your figures
  associated side effect O(N) small constant.

I'm more interested in the amortized effect that an operation has on
the algorithm from which it is invoked (which is O(N)).

Gavin