Forum > General
Using generics
jmm72:
Greetings
I want to move a bit deeper in FPC with maps and hashlists. I've seen this thing of generics but I don't see much documentation around, and reading the sources doesn't really help me much at my stage, probably because I can't grasp certain concepts specifically. Is a map something like a hashed array of elements where each element has another element associated with it?
My intention for now is to use something as a dictionary, an associative array of key elements containing other value elements. I think the best way would be fgl and:
TMyMap = specialize TFPGMap<string,integer>
But the scarce examples I find around don't set the light on all the things I want to do:
* Add a new element with its value (well actually I think I have this one covered).
* Check whether a certain element is in the map (important), and if so, get its value.
* Change the value of a certain element to another element.
* Delete a certain element from the map.
* Iterate through all the elements in the map.
I'm not really sure if I can do some of these, like maybe I check for a key 'whatever' in the map and I don't know if it was there or not, all I get is a 0. And maybe I can't delete an element, just set its value to 0 and know that 0 means 'key not set'? And maybe I'm just not getting all these things about maps and hashsets and voodoo chickens, because I have no idea if I can iterate through the elements. I would do with a real example showing these five actions, if you can point me to one, because I feel really lost.
Also, is there some kind of fast & easy & painless "double map"? Something like I have the key element, I can get the value element; and if I have the value element, I can get the key element. I guess I could do it using two synchronized TFPGMap where one stores key,value and the other stores value,key, but that would consume double the memory and the overhead of keeping them in sync. Maybe the fgl unit has something like this but I'm not seeing it?
And one last question: the lack of documentation is because the fgl is not fully completed yet and it's still being finshed?
Regards, JMM.
Leledumbo:
For an undocumented unit without examples, certainly reading the source is the only way to find out how to use. I know this is difficult for most people, but the unit status itself is unclear.
--- Quote from: jmm72 on January 08, 2015, 11:03:50 am ---Is a map something like a hashed array of elements where each element has another element associated with it?
--- End quote ---
For TFPGMap, it's just a list with map-like behavior.
--- Quote from: jmm72 on January 08, 2015, 11:03:50 am ---* Add a new element with its value (well actually I think I have this one covered).
--- End quote ---
Using your TMyMap definition:
--- Code: ---ATMyMapInstance['a key'] := 127;
--- End code ---
--- Quote from: jmm72 on January 08, 2015, 11:03:50 am ---* Check whether a certain element is in the map (important), and if so, get its value.
--- End quote ---
to check:
--- Code: ---function Find(const AKey: TKey; out Index: Integer): Boolean; {$ifdef CLASSESINLINE} inline; {$endif}
function IndexOf(const AKey: TKey): Integer; {$ifdef CLASSESINLINE} inline; {$endif}
--- End code ---
to get:
--- Code: ---property Data[Index: Integer]: TData read GetData write PutData;
--- End code ---
--- Quote from: jmm72 on January 08, 2015, 11:03:50 am ---* Change the value of a certain element to another element.
--- End quote ---
No different than adding.
--- Quote from: jmm72 on January 08, 2015, 11:03:50 am ---* Delete a certain element from the map.
--- End quote ---
--- Code: ---function Remove(const AKey: TKey): Integer;
--- End code ---
--- Quote from: jmm72 on January 08, 2015, 11:03:50 am ---* Iterate through all the elements in the map.
--- End quote ---
--- Code: ---for i := 0 to ATMyMapInstance.Count - 1 do
// get key with ATMyMapInstance.Keys[i]
// get data with ATMyMapInstance.Data[i]
--- End code ---
jmm72:
I was doing my tests and got most of it, but your explanation made it all fit nicely. Specially I was not being aware that a map should have something like Find or IndexOf. Thank you very much.
I'm going to do some tests with IndexOfData to see if it fits my need for a "reverse dictionary". However I'm unsure whether the data is also searched quickly or sequentially. Would that usage make it too slow when the number of keys is too large?
Leledumbo:
--- Quote from: jmm72 on January 08, 2015, 12:06:24 pm ---Would that usage make it too slow when the number of keys is too large?
--- End quote ---
I believe so. If you don't set Sorted to true, then sequential search is performed. Otherwise, it's binary search.
marcov:
--- Quote from: Leledumbo on January 08, 2015, 12:15:55 pm ---
--- Quote from: jmm72 on January 08, 2015, 12:06:24 pm ---Would that usage make it too slow when the number of keys is too large?
--- End quote ---
I believe so. If you don't set Sorted to true, then sequential search is performed. Otherwise, it's binary search.
--- End quote ---
The ordered insertion of a large number of items will be slowing though. Just like TStringlist the fgl types are basically wrappers around an array.
The only exceptions are the classes hash list (used in various FPC parts) and the fcl-base binary tree implementation, used a lot by Lazarus.
Navigation
[0] Message Index
[#] Next page