[fpc-pascal] IntList

[Vlado Boza]

On 10/19/2010 08:28 PM, Michael Van Canneyt wrote:
>
>
> On Tue, 19 Oct 2010, Sven Barth wrote:
>
>> Am 19.10.2010 19:54, schrieb Juha Manninen (gmail):
>>> On Tuesday 19 October 2010 19:10:39 Luiz Americo Pereira Camara wrote:
>>>> Yes it's ready in fpc 240:
>>>>
>>>> uses
>>>>    Fgl;
>>>>
>>>> type
>>>>    TIntegerList = specialize TFPGList<Integer>;
>>>
>>> Well, yes. It is almost as good as a dedicated class. It has a Sort 
>>> method but
>>> you must feed the compare function for it.
>>> It does not have a Find method for a binary search in a sorted list.
>>> Indexof does a linear search.
>>>
>>> Anyway, it could be used as a base class in Lazarus. I don't know 
>>> what is the
>>> Lazarus team's policy for using generics in Lazarus code-base.
>>>
>>> In FPC 2.4.0 I had problems with memory consumption of generics 
>>> containers.
>>> A<Integer, Integer>  map hogged gigabytes of memory while my data 
>>> took only
>>> kilobytes (less than 1 MB for sure), on a 64 bit Linux.
>>> Now I have the latest FPC trunk 2.5.1 and the problems are gone. I 
>>> added
>>> 100000 integers to both a List and to a Map and didn't even notice 
>>> the memory
>>> increase in resource monitor.
>>>
>>>    TIntegerList = specialize TFPGList<Integer>;
>>>    TIntegerMap = specialize TFPGMap<Integer, Integer>;
>>>
>>> TFPGMap's problem still is that it is not a hash map and is 
>>> butt-slow with
>>> lots of data. A hash map is a superior container type, it really 
>>> should be
>>> changed.
>>> Besides, people expect to get a hash map when they see "map" in the 
>>> class
>>> name. Now they get a list which is deceivingly named as "map".
>>
>> As you seem to have experience with efficient data structures, what 
>> about creating such a generic hash map? :)
>>
>> (but don't use 2.4.2rc1 and current/unpatched 2.4.3 as a test base as 
>> those don't have the fixes from trunk to make "specialize" working 
>> again)
>
> Currently, the FPC team is looking at an implementation of Vlado Boza 
> <usama at ksp.sk> for a standard template library for inclusion in FPC.
>
> The code is on
>
> http://code.google.com/p/stlpascal
>
> Please have a look and comment on it.
>
> I'm not a generics expert and am not in the position to judge whether 
> this library is good or not.
>
> Michael.
>

Hash_map implementation shouldn't be a big problem. But I also think, 
that other structures can be usefull as well (for example in map done by 
red-black tree you can find greatest key which less than X in a good 
time, ...).

A is there any decision if it is worth to put it in FPC and where to put it?

Vlad.