Why Strings as Classes?

Christopher Wright dhasenan at gmail.com
Thu Aug 28 20:39:49 PDT 2008


Dee Girl wrote:
> Christopher Wright Wrote:
> 
>> Dee Girl wrote:
>>> Christopher Wright Wrote:
>>>
>>>> Dee Girl wrote:
>>>>> I am confused to. Why is making [] do find good and making find do [] wrong? How do you make decision? To me it looks the opposite way. Because find is less demanding contract than []. In design a stronger contract can replace a weaker contract. Not the inverse. Thank you, Dee Girl
>>>> Choosing the data structure used is never the job of the code you're 
>>>> giving the data to.
>>> Yes. But code should refuse data if data does not respect an interface.
>> Correct. The question is whether you should make asymptotic complexity 
>> part of the interface. If you do, that hurts when you want to optimize 
>> for a common case but still allow some inefficient operations.
> 
> I think it is really helpful if you learn STL. Very opening for your mind. Because STL does exactly you said. For example there is function distance(). It computes distance between iterators in O(n). But if iterators are random it works in O(1). So function is as fast as possible. And has uniform interface.

The problem with your suggestions -- I have no idea whether your 
suggestions are related to STL or how, since I don't know the STL -- is 
that it's too easy for a library developer to prevent people from using 
a particular data structure just because it implements an operation in a 
slow manner.

>> If you want to define some empty interfaces, such as:
>> interface IFastIndexList : IList {}
>>
>> These would allow you to do things like:
>> bool containsSorted (IList list, Object element)
>> {
>> 	auto fast = cast(IFastIndexList)list;
>> 	if (fast) return (binarySearch(list, element) >= 0);
>> 	// default implementation here
>> }
>>
>> However, your library should not have any publicly exposed operations 
>> that only take IFastIndexList, and it's silly to define different 
>> functions for indexing in an IFastIndexList versus an IList.
> 
> Again. Why make design on your knees (I mean in a hurry) when STL has much better and beautiful design? I think STL book helps very much!

I don't know of STL's design.

A collection has a set of supported operations. A supported operation is 
one that has a correct implementation. An operation need not be 
efficient to be supported, such as opIndex for linked lists.

A collection has guarantees about asymptotic complexity. (Or maybe not.)

These are two different responsibilities. It is a terrible thing to 
conflate them.

>>> I think binary_search never should work on list. It does really bad thing when linear search is the correct thing. Do you think it should?
>> I think it should work, since the data structure implements the 
>> necessary operations. I think no sensible programmer should use it.
> 
> This is very very big misunderstanding. I see this written again. I think somebody else also explained. In concrete code you can make sensible choice. But in generic code you can not choice. I think STL book is really helpful. Also when you maintain code you need compiler to help. If code still compiles but does O(n*n) it is bad!

If you are writing generic code, then your code is not choosing the data 
structure to use. It is the responsibility of the calling code to use an 
efficient data structure for the operation or deal with the extra time 
that the operation will take.

>>>> It's the job of whatever creates the data structure. 
>>>> By giving two functions where the only difference is performance 
>>>> guarantees, you're allowing the called code to determine what data 
>>>> structures it accepts, not based on the operations the structure 
>>>> supports, but based on the performance of those data structures.
>>> I do not think there is anything wrong. And for me performance and complexity is very different words. Performance is like dmd -O -release against dmd -debug. Or asm implementation of function. Complexity is very different thing and essential for algorithm.
>>>
>>>> D's standard arrays are a bad example of this: since they're built in, 
>>>> everyone uses them, so it's difficult to replace them with a linked list 
>>>> or something else. The effect is more pronounced with associative 
>>>> arrays, since there isn't as much choice in lists as in dictionaries. 
>>>> But they're so damn useful, and the syntax is hard to match.
>>> I hope Walter adds new data structure that work with std.algorithm. I am not sure. But I think std.algorithm is make so it works with other types. Not only arrays. 
>> You can do that with templates. If you want to use classes with 
>> inheritance, or interfaces, you can no longer use templates.
> 
> I do not understand. Thank you, Dee Girl

You have builtin arrays. Nothing can inherit from them.

Assume you want your function to work with anything that has the operation:
T opIndex(int);

You can do this:
void operation(T)(T value)
{
	for (int i = 0; i < some_number; i++) do_stuff(value[i]);
}

Now you want to put this in a class and maybe override the behavior in a 
subclass. Fail; you can't; it's a template. You have to choose between 
an interface and force people to use some collection class, or a 
primitive array and force people to use arrays.



More information about the Digitalmars-d mailing list