stl map like container

[lithander]

Hi!

I've items that need to be stored in sorted order. The value they need to be sorted by is an integer (or even better a float) key. I'f I'd work with TList I had to call sort whenever an items key changes wich will perform a quicksort on the list. What I search for is a map where i can enter an Item together with a key like the STL map in C++. When a key changes I'd just remove the item from the map and enter a new one. This would be rather fast. (2 * O(log n))
Still i could run through all items almost as fast as in a tree via an iterator.

Is there any implementiation of such a container in Delphi?

-lith

[cairnswm]

I just use a sorted string list and convert the integer to a stirng in the list - if they need to be in the numeric order then use formatfloat to pad the start with 0s.

[marcov]

While binary trees used to be fast, this now only is so on paper.
This because each following of a link is a cache miss.

This doesn't mean you have to throw away your education, just keep in mind that larger trees (e.g. 256-ary) are more worthwhile, since the right child in a node can be searched using binary search that does not trash the cache.

I had some need for a high speed map type, I didn't clean up the code yet,
but some preliminary version is here:

http://www.stack.nl/~marcov/light.zip

Another solution is Decal (which is on SF and in Free Pascal CVS), but that is based on variants, and a bit slow. (though it mimics the STL to a very high degree)