[fpc-pascal] Hashmap for integers
jepjoh2 at kom.aau.dk
Sun Aug 22 17:45:04 CEST 2010
Den 22-08-2010 17:36, Juha Manninen (gmail) skrev:
> On Sunday 22 August 2010 17:34:55 Andreas Schneider wrote:
>> uses fgl;
>> TIntMap = specialize TFPGMap<Integer, Integer>; //Maps Int --> Int
> Thanks. I tried that. However the class name, TFPGMap, turned out to be
> misleading. It inherits from TFPSMap which inherits from TFPSList, which is a
> list, not a map, as the name says.
> Lists should be named as "List", not as "Map".
> I already have a self-made TIntList. It has Quicksort and Find functions and
> it is as fast as can be. I made it years ago because I didn't find any proper
> alternative. (Java people don't need to do such things...)
> Is it really so there is no generics HashMap container in fgl, or in other FPC
> libraries? Someone should make it!
> And, the name "Map" should really be reserved for hash maps and not used for
> lists (= kind of poor man's map).
> My prog has a big amount of integers, thats why an integer list is not enough.
> A binary search from a sorted list is pretty fast but the problem is that I am
> adding items to the list and it must be sorted after every addition.
> My experience from string hashmaps says that the speed difference can be huge,
> compared to any list implementation.
> fpc-pascal maillist - fpc-pascal at lists.freepascal.org
I don't think the name map is misleading. It does exactly what a map
does. It maps a type Key to another type Value. A list maps an
integer(index) to a type Value The search is of course based on a list.
Hash tables, as far as I know, are usually only profitable when you have
a large number of insertions on keys that take a long time to compare
I don't think there's a generic hash table for FPC. So I'm sure many
could benefit from it if you implemented it :)
There's a string based hash table in contnrs.pp
More information about the fpc-pascal