Why Strings as Classes?

[Nick Sabalausky]

"Don" <nospam at nospam.com.au> wrote in message 
news:g95ks5$2aon$1 at digitalmars.com...
> Nick Sabalausky wrote:
>> "Dee Girl" <deegirl at noreply.com> wrote in message 
>> news:g94j7a$2875$1 at digitalmars.com...
>>> I appreciate your view point. Please allow me explain. The view point is 
>>> in opposition with STL. In STL each algorithm defines what kind of 
>>> iterator it operates with. And it requires what iterator complexity.
>>>
>>> I agree that other design can be made. But STL has that design. In my 
>>> opinion is much part of what make STL so successful.
>>>
>>> I disagree that algorithm that knows complexity of iterator is concrete. 
>>> I think exactly contrary. Maybe it is good that you read book about STL 
>>> by Josuttis. STL algorithms are the most generic I ever find in any 
>>> language. I hope std.algorithm in D will be better. But right now 
>>> std.algorithm works only with array.
>>>
>>>> If an algoritm uses [] and doesn't know the
>>>> complexity of the []...good! It shouldn't know, and it shouldn't care. 
>>>> It's
>>>> the code that sends the collection to the algoritm that knows and 
>>>> cares.
>>> I think this is mistake. Algorithm should know. Otherwise "linear find" 
>>> is not "linear find"! It is "cuadratic find" (spell?). If you want to 
>>> define something called linear find then you must know iterator 
>>> complexity.
>>>
>>
>> If a generic algorithm describes itself as "linear find" then I know damn 
>> well that it's referring to the behavior of *just* the function itself, 
>> and is not a statement that the function *combined* with the behavior of 
>> the collection and/or a custom comparison is always going to be O(n).
>>
>> A question about STL: If I create a collection that, internally, is like 
>> a linked list, but starts each indexing operation from the position of 
>> the last indexing operation (so that a "find first" would run in O(n) 
>> instead of O(n*n)), is it possible to send that collection to STL's 
>> generic "linear find first"? I would argue that it should somehow be 
>> possible *even* if the STL's generic "linear find first" guarantees a 
>> *total* performance of O(n) (Since, in this case, it would still be O(n) 
>> anyway). Because otherwise, the STL wouldn't be very extendable, which 
>> would be a bad thing for a library of "generic" algorithms.
>
> Yes, it will work.
>
>> Another STL question: It is possible to use STL to do a "linear find" 
>> using a custom comparison? If so, it is possible to make STL's "linear 
>> find" function use a comparison that just happens to be O(n)? If so, 
>> doesn't that violate the linear-time guarantee, too? If not, how does it 
>> know that the custom comparison is O(n) instead of O(1) or O(log n)?
>
> This will work too.
>
> IF you follow the conventions THEN the STL gives you the guarantees.

I'm not sure that's really a "guarantee" per se, but that's splitting hairs.

In any case, it sounds like we're all arguing more or less the same point:

Setting aside the issue of "should opIndex be used and when?", suppose I 
have the following collection interface and find function (not guaranteed to 
compile):

interface ICollection(T)
{
    T getElement(index);
    int getSize();
}

int find(T)(ICollection(T) c, T elem)
{
    for(int i=0; i<c.size(); i++)
    {
 if(c.getElement(i) == elem)
            return i;
    }
}

It sounds like STL's approach is to do something roughly like that and say:

"find()'s parameter 'c' should be an ICollection for which getElement() is 
O(1), in which case find() is guaranteed to be O(n)"

What I've been advocating is, again, doing something like the code above and 
saying:

"find()'s complexity is dependant on the complexity of the ICollection's 
getElement(). If getElement()'s complexity is O(m), then find()'s complexity 
is guaranteed to be O(m * n). Of course, this means that the only way to get 
ideal complexity from find() is to use an ICollection for which getElement() 
is O(1)".

But, you see, those two statements are effectively equivilent.