[review] new string type (take 2)

[Andrei Alexandrescu]

On 1/15/11 11:15 CST, Steven Schveighoffer wrote:
> On Fri, 14 Jan 2011 12:03:28 -0500, Andrei Alexandrescu
> <SeeWebsiteForEmail at erdani.org> wrote:
>
>> On 1/14/11 5:06 AM, Steven Schveighoffer wrote:
>>> On Thu, 13 Jan 2011 23:03:35 -0500, Steven Wawryk <stevenw at acres.com.au>
>>> wrote:
>>>
>>>> Because at the code-point level it *isn't* a random-access range and
>>>> the index makes no sense at the code-point level, only at the
>>>> code-unit level. It's encouraging the confusion of 2 distinctly
>>>> different abstractions or "views" of the same data. All the slicing
>>>> and indexing you're artificially putting in the code-point range is
>>>> already available in the code-unit range, and its only benefit is to
>>>> allow the user to save typing ".data".
>>>
>>> I respectfully disagree. A stream built on fixed-sized units, but with
>>> variable length elements, where you can determine the start of an
>>> element in O(1) time given a random index absolutely provides
>>> random-access. It just doesn't provide length.
>>
>> I equally respectfully disagree. I think random access is defined as
>> accessing the ith element in O(1) time. That's not the case here.
>
> I'd actually go as far as saying that any container you can do a quick
> lookup given an index (O(lgn) or better) is random-access. For example,
> a dictionary file of english words sorted alphabetically can look up any
> word definition in O(lgn) time, but you can't look up the nth word in
> O(lgn) time.

Here you are trying to equate a dictionary (map/hashtable) with an 
otherwise unstructured variable length encoded array. I don't think 
there is much similarity.

> What do you call this type of container if not random access? Indexed
> maybe? Whatever term you call it, I'd call it that, and say opIndex
> belongs for that container.
>
> -Steve

I'm not sure how you can call it, but it's definitely not random access.


Andrei