Data Structures, Containers, Collections

From Free Pascal wiki

English (en) français (fr)

Introduction

Most programs operate on data, either searching, sorting, iterating or simply insert and retrieve. Therefore, a means of data structures, 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.

Run time library (RTL)

Free Component Library (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 generic types notes
CL4L Public Domain no al, as, ll, v, hm, hs, q, s Conversion of The Delphi Container Library. Provides algorithms like in STL (Apply, Found, CountObject, Copy, Generate, Fill, Reverse, Sort...)
heContnrs BSD3 yes ... ...
Fundamentals BSD no ... in Utils/cDataStructs.pas
RBS AntiDOT GPLv2 ?? ... ...
LightContainers FPC no+yes aasl Generic and non-generic variants. (Delphi does not optimize generics) Quite lowlevel
DeCAL MPL no ... browse variants + interfaces, relatively slow.
hovadur DeCAL MPL no al, as, ll, rb, hm, hs, tm, ts, bs guide.pdf DeCAL works in Lazarus (windows 64 bit/32 bit, linux 64 bit/32 bit) and Delphi7, Delphi XE2.
StringHashMap MPL1.0 ?? ... port of code from JCL
GContnrs LGPLv2 + linking exception yes v, hm, hs, ll, q, dq, s, ts, tm, bs ...
CL4fpc GPLv2 yes ... ...
HAMT LGPLv2 + linking exception yes tm, ts immutable hash array mapped trie
LGenerics Apache 2.0 yes gr, s, q, dq, v, hs, hm, tm, ts, bs... Collection of generic algorithms and data structures for FPC and Lazarus
code data type
al array list
as array set
rb red-black tree
hm hashmap
hs hashset
ll linked list
q queue
dq dequeue
s stack
v vector
tm treemap
ts treeset
bs bitset
gr graph
aasl "array of array of T" based sorted list.

See also