[M3devel] STL algorithms? sort/unique?

[Rodney M. Bates]

On 09/29/2012 01:29 PM, mika at async.caltech.edu wrote:
> Well that depends on how you maintain the vector, no?
>
> SortedTable uses "treaps" which are supposed to be good data structures.
> Too new to have made it into Knuth, last I checked.  The amortized cost
> of your operations shouldn't be much worse than with your method, with
> the additional benefit that the sorted order is maintained dynamically.
>
> The separation of algorithms from containers sounds a bit like a bug.
> You have to be careful so you don't shoot yourself in the foot there!
> (Sorting a list using an algorithm that randomly accesses elements,
> say...)
>
> The Modula-3 approach is that you figure out what you want to do, pick
> the ADT you want that provides the minimal set of operations, import
> that interface, then instantiate a more carefully chosen implementation
> of the ADT.  The language itself obviously can be coaxed into supporting the
> algorithm/data structure separation but no one uses it that way as
> far as I know.  (Modula-3 generics are not that well explored, actually.
> I suspect there are many things you can do with them that no one has
> tried.)
>
>       Mika
>
>

I do think the ability to easily and inadvertently create mashups with
horrible asymptotic efficiency problems is a fundamental problem with
abstractions of any kind.  Just plain old-fashioned procedural abstractions
give plenty of opportunity.  Write one loop and call your code O(n).
Call something inside the loop. That guy did the same.  Quickly, you
can O(n^3) etc., and nobody realizes it.

Functional style abstractions are often just oh-so-easy to use, but
they can hide a lot.  Even Modula-3 Text operations, immeasurably
more versatile and easy than when you have to worry about allocation,
have created some unpleasant surprises.  Documenting the performance
characteristics in comments seems to be only solution.  This has been
done in some places by both C++ and Modula-3 library writers.