[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: strings draft

This page is part of the web mail archives of SRFI 50 from before July 7th, 2015. The new archives for SRFI 50 contain all messages, not just those from before July 7th, 2015.

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.