Difference between revisions of "Data Structures, Containers, Collections"

From Lazarus wiki
Jump to navigationJump to search
(added license info to the 3rd-party implementations area.)
(→‎3rd party: began listing the provided types)
Line 69: Line 69:
 
{| class="wikitable"
 
{| class="wikitable"
 
|-
 
|-
! project !! license !! notes
+
! project !! license !! generic| !! types !! notes
 
|-
 
|-
| [https://github.com/CynicRus/CL4L Containers library for Lazarus] || public domain || port of Delphi Container Library
+
| [https://github.com/CynicRus/CL4L Containers library for Lazarus] || ?? || no
 +
|| al,rb,hm,hs,ll,q,s,v || port of public domain Delphi Container Library
 
|-
 
|-
| [http://code.google.com/p/fprb/wiki/heContnrs heContnrs] || BSD3 ||  
+
| [http://code.google.com/p/fprb/wiki/heContnrs heContnrs] || BSD3 || yes
 +
|| ... || ...
 
|-
 
|-
| [http://fundementals.sourceforge.net/ Fundamentals] || various || non-generic, but many per-type implementations. mostly under BSD-style license
+
| [http://fundementals.sourceforge.net/ Fundamentals] || BSD || no
 +
|| ... || in Utils/cDataStructs.pas
 
|-
 
|-
| [http://sourceforge.net/projects/adot/ RBS AntiDOT] || GPLv2 ||  
+
| [http://sourceforge.net/projects/adot/ RBS AntiDOT] || GPLv2 || ??
 +
|| ... || ...
 
|-
 
|-
| [http://www.stack.nl/~marcov/lightcontainers.zip LightContainers] || FPC?? ||  
+
| [http://www.stack.nl/~marcov/lightcontainers.zip LightContainers] || FPC?? || ??
 +
|| ... || ...
 
|-
 
|-
| [http://svn.freepascal.org/svn/fpcprojects/contrib/decal/ DeCAL] || FPC?? ||  
+
| [http://svn.freepascal.org/svn/fpcprojects/contrib/decal/ DeCAL] || FPC?? || ??
 +
|| ... || ...
 
|-
 
|-
| [[StringHashMap]] || MPL1.0 || port of code from JCL  
+
| [[StringHashMap]] || MPL1.0 || ??
 +
|| xx || port of code from JCL
 +
|}
  
 +
{| class="wikitable"
 +
|-
 +
! code !! data type
 +
|-
 +
|  al    || array list
 +
|-
 +
|  as  || array set
 +
|-
 +
|  rb    || red-black tree
 +
|-
 +
|  hm    || hashmap
 +
|-
 +
|  hs    || hashset
 +
|-
 +
|  q    || queue
 +
|-
 +
|  dq    || dequeue
 +
|-
 +
|  s    || stack
 +
|-
 +
|  v    || vector
 +
|-
 
|}
 
|}

Revision as of 04:27, 17 May 2013

Introduction

Most programs operate on data, either searching, sorting, iterating or simply insert and retrieve. Therefore, a means of data structure, containers and collections is required.

Free Pascal ships with numerous data structures, at different levels (RTL, FCL) but there are also third party solutions offering such feature.

RTL

  • Classes unit
    • TList: Manages a list of pointers, can search and sort the list, has event notification feature
    • TFPList: Manages a list of pointers, can search and sort the list, without event notification feature, faster than TList
    • TStrings: Manages a list of strings, can search, split, save to / load from file, store objects, act like associative array, etc., is an abstract class
    • TStringList: TStrings descendant, implements abstract methods of TStrings, can sort, handle duplicates, has event notification feature, a concrete class
    • TBits: Manages a list of bits (0 or 1), useful for bit-map (not bitmap image format)
    • TCollection and TCollectionItem: Forms basic management of named items
  • FGL (Free Generics Library) unit
    • TFPGList
    • TFPGObjectList
    • TFPGInterfacedObjectList
    • TFPGMap
    • TFPGMapInterfacedObjectData

FCL

FCL-Base

  • AVL_Tree unit
  • Contnrs unit
    • TFPObjectList
    • TObjectList
    • TComponentList
    • TClassList
    • TOrderedList
    • TStack
    • TObjectStack
    • TQueue
    • TObjectQueue
    • TFPHashList
    • TFPHashObjectList
    • TFPDataHashTable
    • TFPStringHashTable
    • TFPObjectHashTable
    • TBucketList
    • TObjectBucketList

FCL-STL

  • GVector unit
    • TVector: Implements dynamically self-resizing array, item order is based on insertion order
  • GSet unit
    • TSet: Implements red-black tree backed set, no order is guaranteed
  • GHashSet unit
    • THashSet: Implements hashtable backed set, no order is guaranteed
  • GStack unit
    • TStack: Implements stack, LIFO (last in first out) order
  • GQueue unit
    • TQueue: Implements stack, items are pushed from front, FIFO (first in first out) order
  • GPriorityQueue unit
    • TPriorityQueue: Implements heap backed priority queue, order is based on given compare function
  • GDeQue unit
    • TDeque: Implements double ended queue, items can be pushed and popped from either front or back
  • GMap unit
    • TMap: Implements TSet (and therefore, red-black tree) backed map
  • GHashMap unit
    • THashMap: Implements hashtable backed map
  • GTree unit
    • TTree: Implements k-ary tree, supports depth first and breadth first traversal

Lazarus/LCL

  • AvgLvlTree: extended versions of the FPC/FCL TAVLTree and TAVLTreeNode; see AVL Tree

3rd party

project license types notes
Containers library for Lazarus ?? no al,rb,hm,hs,ll,q,s,v port of public domain Delphi Container Library
heContnrs BSD3 yes ... ...
Fundamentals BSD no ... in Utils/cDataStructs.pas
RBS AntiDOT GPLv2 ?? ... ...
LightContainers FPC?? ?? ... ...
DeCAL FPC?? ?? ... ...
StringHashMap MPL1.0 ?? xx port of code from JCL
code data type
al array list
as array set
rb red-black tree
hm hashmap
hs hashset
q queue
dq dequeue
s stack
v vector