Hi,

Does anyone use the CustomSort facility of TStringList ? I am a bit troubled because it's broken by design it seems. You can sort the list with it, but searching/adding will not work properly (or be linear). I want to have a callback that gives you two strings to compare, instead of two indexes which you have to fetch anyway from the list, first.

Thoughts ?

Micha

Why not add an overloaded CustomSort method that accepts the compare function that you like.

--Bart

_________________________________________________________________ Windows Live Messenger: gratis bellen van PC naar PC http://imagine-msn.com/messenger/launch80/default.aspx?locale=nl-nl

Yeah, that is normally how I do it as well.

Graeme.

Bart van den Broek wrote

Why not add an overloaded CustomSort method that accepts the compare function that you like.

Has the code duplication, maintenance, bloat, etc. problem.

Micha

Ehm.
What has adding/searching to do with sorting ?

Michael.

Michael Van Canneyt wrote

Ehm. What has adding/searching to do with sorting ?

Adding: keep the list sorted.
Searching: ability to use binary search instead of linear.

Micha

Micha Nelissen wrote

Michael Van Canneyt wrote: > Ehm. What has adding/searching to do with sorting ? Adding: keep the list sorted.

Use Sorted:=True.

Searching: ability to use binary search instead of linear.

It is used if Sorted=True.

But not with customsearch.

The purpose of Customsearch is to sort the list once using a custom sorting algorithm.

Michael.

Michael Van Canneyt wrote

The purpose of Customsearch is to sort the list once using a custom sorting algorithm.

That reduces its usefulness, and why I said it's a broken design :).

Micha

I am not sure I understand. Do you mean the last sentence to say "I want to have a callback having the parameters as the two strings to compare, instead of two indexes, as you have to fetch the strings from the list anyway"?

Stating the obvious: but the programmer might wish to sort by the objects or by some combination of the strings and the objects (or even by entries in an external array, unrelated to the StringList) - the indexes are therefore needed in the general case.

As to the implementation being broken by design, note from Delphi help: "You must explicitly call the CustomSort method. Setting the Sorted property only sorts strings using ANSI order, as implemented in the Sort method." Whether that means it is broken or not depends on your point of view.

Of course, the efficient way to build a sorted list is to set Sorted to False and to sort the list after all the items have been added.

--------------------------------------------
Mr C.J. Cheney, Head of the Network Division
University of Cambridge Computing Service
New Museums Site, Pembroke Street
Cambridge CB2 3QH
tel: 01223 334428

Maybe, but it's implemented to be delphi compatible.

What could be done is to introduce a new property 'CompareStrings' which is a callback used by the sort function, which does what you ask. By default this can then be the 'CompareText()' function of sysutils.

But I would like to know what the impact on speed is before doing this. (although I suspect the impact to be minimal)

Michael.

Chris Cheney wrote

Stating the obvious: but the programmer might wish to sort by the objects or by some combination of the strings and the objects (or even by entries in an external array, unrelated to the StringList) - the indexes are therefore needed in the general case.

Oh right, sorting by object contents. Seems strange to me, but perhaps useful, indeed.

Of course, the efficient way to build a sorted list is to set Sorted to False and to sort the list after all the items have been added.

It doesn't matter in O-time: both are O(n log n). Nevertheless, you probably will save some function call overhead.

Micha

That highly depends on the sorting algorithm used. A plain Quicksort has a very bad worst case of O(n**2) that develops especially when the list to be sorted already is. Even Bubblesort would be faster in such a case.

Vinzent.

True, but I was too quick. Inserting in a list is O(n) of course, so it's O(n^2) for Add-Find-Insert case.

Micha

Insertion Sort is O(n^2).

Mattias

Does anyone use the CustomSort facility of TStringList ?

It's delphi compat.

I am a bit troubled because it's broken by design it seems. You can sort the list with it, but searching/adding will not work properly (or be linear).

Why would you want to add/search while sorting?

After sorting, to search efficiently, why else ?

Micha

Well, it fits with the rest of TStringList then :-)

Seriously, I wouldn't bother using TStringList. It's position in the VCL and Delphi compat and its fundamental flaws make it too difficult to enhance/improve.

(hinting on the scaling problems, the delimited functions always using space as a separator etc)