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

From Free Pascal wiki
Jump to navigationJump to search
(See also - FreePascal hash maps comparsion)
 
(32 intermediate revisions by 8 users not shown)
Line 9: Line 9:
 
* [[Classes unit]]
 
* [[Classes unit]]
 
** [[TList]]: Manages a list of pointers, can search and sort the list, has event notification feature
 
** [[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
+
** [[TList| 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
 
** [[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
 
** [[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)
 
** [[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
 
** [[TCollection]] and TCollectionItem: Forms basic management of named items
* [[Generics|FGL (Free Generics Library)]] [[fgl unit|unit]]
+
* [[Generics|FGL (Free Generics Library)]]
 
** [[TFPGList]]
 
** [[TFPGList]]
 
** [[TFPGObjectList]]
 
** [[TFPGObjectList]]
Line 20: Line 20:
 
** [[TFPGMap]]
 
** [[TFPGMap]]
 
** [[TFPGMapInterfacedObjectData]]
 
** [[TFPGMapInterfacedObjectData]]
 +
* [[Generics|Generics Collections (fully compatible with Delphi generics library)]]
 +
** [[TArray]]: Static methods for searching and sorting
 +
** [[TDictionary]]: Key-value pairs, has event notification feature
 +
** [[TObjectDictionary]]: Key-value pairs with automatic freeing of objects if removed, has event notification feature
 +
** [[TList]]: List of items, can search, add, remove, reverse and sort the list, has event notification feature
 +
** [[TObjectList]]: List of objects with automatic freeing of objects if removed, can search, add, remove, reverse and sort the list, has event notification feature
 +
** [[TObjectQueue]]: Queue of objects with automatic freeing of objects if removed, has event notification feature
 +
** [[TObjectStack]]: LIFO (last in, first out) stack of objects with automatic freeing of objects if removed
 +
** [[TQueue]]: Queue, has event notification feature
 +
** [[TStack]]: LIFO (last in, first out) stack, has event notification feature
 +
** <del>TThreadedQueue</del> not yet implemented
 +
** [[TThreadList]]: Thread-safe list based on TList<T>
 +
** [[TPair]]: Record for key-value pair
 +
** Different comparers, enumerators and hashes available
 +
** Additional classes (unlike the Delphi Generics Collections) available
 +
*** [[TAVLTree]]
 +
*** [[TSortedSet]]
  
 
== [[FCL|Free Component Library (FCL)]] ==
 
== [[FCL|Free Component Library (FCL)]] ==
Line 46: Line 63:
 
* GVector unit
 
* GVector unit
 
** TVector: Implements dynamically self-resizing array, item order is based on insertion order
 
** TVector: Implements dynamically self-resizing array, item order is based on insertion order
* GSet unit
+
* [[GSet]] unit
** TSet: Implements red-black tree backed set, no order is guaranteed
+
** TSet: Implements red-black tree backed set, sorted in a manner of your choosing
 
* GHashSet unit
 
* GHashSet unit
 
** THashSet: Implements hashtable backed set, no order is guaranteed
 
** THashSet: Implements hashtable backed set, no order is guaranteed
Line 66: Line 83:
  
 
== Lazarus/LCL ==
 
== Lazarus/LCL ==
* AvgLvlTree: extended versions of the FPC/FCL TAVLTree and TAVLTreeNode; see [[AVL Tree]]
+
* AvgLvlTree: extended versions of the FPC/FCL TAVLTree and TAVLTreeNode. See [[AVL Tree]].
  
 
== 3rd party ==
 
== 3rd party ==
Line 73: Line 90:
 
! project !! license !! generic !! types !! notes
 
! project !! license !! generic !! types !! notes
 
|-
 
|-
| [https://github.com/CynicRus/CL4L Containers library for Lazarus] || ?? || no  
+
|[https://github.com/CynicRus/CL4L CL4L] || Public Domain || no
|| al,rb,hm,hs,ll,q,s,v || port of public domain Delphi Container Library
+
|| 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...)
 
|-
 
|-
 
| [http://code.google.com/p/fprb/wiki/heContnrs heContnrs] || BSD3 || yes
 
| [http://code.google.com/p/fprb/wiki/heContnrs heContnrs] || BSD3 || yes
|| ... || ...  
+
|| ... || Collection of generic Free Pascal containers: BTree, lists, vectors.
 
|-
 
|-
| [http://fundementals.sourceforge.net/ Fundamentals] || BSD || no  
+
| [https://github.com/fundamentalslib/ Fundamentals] || BSD || no  
|| ... || in Utils/cDataStructs.pas
+
|| ... || GitHub account contains 2 versions of library: 4 and 5.
 
|-
 
|-
 
| [http://sourceforge.net/projects/adot/ RBS AntiDOT] || GPLv2 || ??
 
| [http://sourceforge.net/projects/adot/ RBS AntiDOT] || GPLv2 || ??
|| ... || ...  
+
|| ... || Library of containers and data structures for Pascal: Vectors, Maps, Sets, Lists and others.  
 
|-
 
|-
| [http://www.stack.nl/~marcov/lightcontainers.zip LightContainers] || FPC || no+yes
+
| [http://www.stack.nl/~marcov/lightcontainers.zip LightContainers], [https://github.com/Alexey-T/FPC_light_containers GitHub mirror] || FPC || no+yes
|| ... || Generic and non-generic variants. (Delphi does not optimize generics) Quite lowlevel
+
|| aasl || Generic and non-generic variants. Quite low-level.
|-
 
| [http://svn.freepascal.org/svn/fpcprojects/contrib/decal/ DeCAL] || MPL || no
 
|| ... || [http://svn.freepascal.org/cgi-bin/viewvc.cgi/contrib/decal/?root=fpcprojects browse]  variants + interfaces, relatively slow.
 
|-
 
| [https://bitbucket.org/hovadur/decal hovadur DeCAL] || MPL || no
 
|| al, as, ll, rb, hm, hs, tm, ts, bs || [https://bitbucket.org/hovadur/decal/src/b0649ae41d228c9b8878be9aab958ce779044d48/guide.pdf?at=default guide.pdf] DeCAL works in Lazarus (windows 64 bit/32 bit, linux 64 bit/32 bit) and Delphi7, Delphi XE2.
 
 
|-  
 
|-  
 
| [[StringHashMap]] || MPL1.0 || ??
 
| [[StringHashMap]] || MPL1.0 || ??
|| ... || port of code from JCL
+
|| ... || Port of code from JCL.
 
|-
 
|-
 
|[http://yann.merignac.free.fr/unit-gcontnrs.html GContnrs] || LGPLv2 + linking exception || yes
 
|[http://yann.merignac.free.fr/unit-gcontnrs.html GContnrs] || LGPLv2 + linking exception || yes
|| v, hm, hs, ll, q, dq, s, ts, tm, bs || ...
+
|| v, hm, hs, ll, q, dq, s, ts, tm, bs || Generic containers: doubly linked lists, dequeues, hash maps, hash sets, priority queues, queues, stacks, tree maps, tree sets, vectors and bitsets.
 
|-
 
|-
 
|[https://sourceforge.net/projects/cl4fpc/ CL4fpc] || GPLv2|| yes
 
|[https://sourceforge.net/projects/cl4fpc/ CL4fpc] || GPLv2|| yes
|| ... || ...
+
|| ... || Red-black tree, AVL tree, Decart tree, weight-balanced tree, hash-maps, FIFO, ResPool and others.
 +
|-
 +
|[https://www.benibela.de/sources_en.html#hamt HAMT] || LGPLv2 + linking exception || yes
 +
|| tm, ts || Immutable hash array mapped tree.
 +
|-
 +
|[[LGenerics]] || Apache 2.0|| yes
 +
|| gr, s, q, dq, v, rb, av, hs, hm, tm, ts, ms, mm, bm, bs... || Collection of generic algorithms and data structures for FPC and Lazarus.
 +
|-
 +
|[https://github.com/terrylao/PascalContainer PascalContainer] || BSD|| yes
 +
|| rb, q, dq, hm, tm || Generic data structure with B-Tree, B+Tree, B*Tree, T-Tree, HashMap, priority queue, red-black-Tree, AVL-tree, Quad-Tree, SkipList, LockFreeQueue.
 
|}
 
|}
  
Line 113: Line 133:
 
|-
 
|-
 
|  rb    || red-black tree
 
|  rb    || red-black tree
 +
|-
 +
|  av    || AVL tree
 
|-
 
|-
 
|  hm    || hashmap
 
|  hm    || hashmap
Line 122: Line 144:
 
|  q    || queue
 
|  q    || queue
 
|-
 
|-
|  dq    || dequeue
+
|  dq    || deque
 
|-
 
|-
 
|  s    || stack
 
|  s    || stack
Line 131: Line 153:
 
|-
 
|-
 
|  ts    || treeset
 
|  ts    || treeset
 +
|-
 +
|  ms    || multiset
 +
|-
 +
|  mm    || multimap
 +
|-
 +
|  bm    || bijective map
 
|-
 
|-
 
|  bs    || bitset
 
|  bs    || bitset
 +
|-
 +
|  gr    || graph
 +
|-
 +
|  aasl    || "array of array of T" based sorted list.
 
|-
 
|-
 
|}
 
|}
Line 138: Line 170:
 
== See also ==
 
== See also ==
 
* [http://www.benibela.de/fpc-map-benchmark_en.html FreePascal hash maps comparsion]
 
* [http://www.benibela.de/fpc-map-benchmark_en.html FreePascal hash maps comparsion]
 
+
* [https://secondboyet.com/FixedArticles/DADSBook.html Tomes of Delphi: Algorithms and Data Structures]
 +
* [https://github.com/jmbucknall/EZDSL EZDSL: Easy Data Structures Library for Delphi]
  
 
[[Category:Data Structures]]
 
[[Category:Data Structures]]

Latest revision as of 14:34, 12 March 2022

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)

  • 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)
  • Generics Collections (fully compatible with Delphi generics library)
    • TArray: Static methods for searching and sorting
    • TDictionary: Key-value pairs, has event notification feature
    • TObjectDictionary: Key-value pairs with automatic freeing of objects if removed, has event notification feature
    • TList: List of items, can search, add, remove, reverse and sort the list, has event notification feature
    • TObjectList: List of objects with automatic freeing of objects if removed, can search, add, remove, reverse and sort the list, has event notification feature
    • TObjectQueue: Queue of objects with automatic freeing of objects if removed, has event notification feature
    • TObjectStack: LIFO (last in, first out) stack of objects with automatic freeing of objects if removed
    • TQueue: Queue, has event notification feature
    • TStack: LIFO (last in, first out) stack, has event notification feature
    • TThreadedQueue not yet implemented
    • TThreadList: Thread-safe list based on TList<T>
    • TPair: Record for key-value pair
    • Different comparers, enumerators and hashes available
    • Additional classes (unlike the Delphi Generics Collections) available

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, sorted in a manner of your choosing
  • 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 ... Collection of generic Free Pascal containers: BTree, lists, vectors.
Fundamentals BSD no ... GitHub account contains 2 versions of library: 4 and 5.
RBS AntiDOT GPLv2 ?? ... Library of containers and data structures for Pascal: Vectors, Maps, Sets, Lists and others.
LightContainers, GitHub mirror FPC no+yes aasl Generic and non-generic variants. Quite low-level.
StringHashMap MPL1.0 ?? ... Port of code from JCL.
GContnrs LGPLv2 + linking exception yes v, hm, hs, ll, q, dq, s, ts, tm, bs Generic containers: doubly linked lists, dequeues, hash maps, hash sets, priority queues, queues, stacks, tree maps, tree sets, vectors and bitsets.
CL4fpc GPLv2 yes ... Red-black tree, AVL tree, Decart tree, weight-balanced tree, hash-maps, FIFO, ResPool and others.
HAMT LGPLv2 + linking exception yes tm, ts Immutable hash array mapped tree.
LGenerics Apache 2.0 yes gr, s, q, dq, v, rb, av, hs, hm, tm, ts, ms, mm, bm, bs... Collection of generic algorithms and data structures for FPC and Lazarus.
PascalContainer BSD yes rb, q, dq, hm, tm Generic data structure with B-Tree, B+Tree, B*Tree, T-Tree, HashMap, priority queue, red-black-Tree, AVL-tree, Quad-Tree, SkipList, LockFreeQueue.
code data type
al array list
as array set
rb red-black tree
av AVL tree
hm hashmap
hs hashset
ll linked list
q queue
dq deque
s stack
v vector
tm treemap
ts treeset
ms multiset
mm multimap
bm bijective map
bs bitset
gr graph
aasl "array of array of T" based sorted list.

See also