Re: strings draft

[bear <bear@xxxxxxxxx>]

On Thu, 22 Jan 2004, bear wrote:


>The loss is that referring to an indexed character in a string is
>O(n).  The win is that inserting or deleting characters is also
>O(n) and I can avoid spending a lot of storage on copies and a lot
>of CPU on making copies since different strings can share strands.


Erf. 'scuse me, I shoulda said O(log n), not O(n). Vector strings
have O(n) insert and delete and O(1) lookup and random-access set.
Tree strings have O(log N) for all of these things.