Sign in Join
Wiki copytemporary

Data Structures, Containers, Collections: what changed

Revision 0 to 1. Removed lines have a minus sign; added lines have a plus sign.

Title: Data Structures, Containers, Collections

OldNewLine
1+## Introduction
2+
3+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.
4+
5+Free Pascal ships with numerous data structures, at different levels (RTL, FCL) but there are also third party solutions offering such feature.
6+
7+## [[RTL|Run time library (RTL)]]
8+
9+- [[Classes unit]]
10+ - [[TList]]: Manages a list of pointers, can search and sort the list, has event notification feature
11+ - [[TList|TFPList]]: Manages a list of pointers, can search and sort the list, without event notification feature, faster than TList
12+ - [[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
13+ - [[TStringList]]: TStrings descendant, implements abstract methods of TStrings, can sort, handle duplicates, has event notification feature, a concrete class
14+ - [[TBits]]: Manages a list of bits (0 or 1), useful for bit-map (not bitmap image format)
15+ - [[TCollection]] and TCollectionItem: Forms basic management of named items
16+- [[Generics|FGL (Free Generics Library)]]
17+ - [[TFPGList]]
18+ - [[TFPGObjectList]]
19+ - [[TFPGInterfacedObjectList]]
20+ - [[TFPGMap]]
21+ - [[TFPGMapInterfacedObjectData]]
22+- [[Generics|Generics Collections (fully compatible with Delphi generics library)]]
23+ - [[TArray]]: Static methods for searching and sorting
24+ - [[TDictionary]]: Key-value pairs, has event notification feature
25+ - [[TObjectDictionary]]: Key-value pairs with automatic freeing of objects if removed, has event notification feature
26+ - [[TList]]: List of items, can search, add, remove, reverse and sort the list, has event notification feature
27+ - [[TObjectList]]: List of objects with automatic freeing of objects if removed, can search, add, remove, reverse and sort the list, has event notification feature
28+ - [[TObjectQueue]]: Queue of objects with automatic freeing of objects if removed, has event notification feature
29+ - [[TObjectStack]]: LIFO (last in, first out) stack of objects with automatic freeing of objects if removed
30+ - [[TQueue]]: Queue, has event notification feature
31+ - [[TStack]]: LIFO (last in, first out) stack, has event notification feature
32+ - ~~TThreadedQueue~~ not yet implemented
33+ - [[TThreadList]]: Thread-safe list based on TList\<T\>
34+ - [[TPair]]: Record for key-value pair
35+ - Different comparers, enumerators and hashes available
36+ - Additional classes (unlike the Delphi Generics Collections) available
37+ - [[TAVLTree]]
38+ - [[TSortedSet]]
39+
40+## [[FCL|Free Component Library (FCL)]]
41+
42+### FCL-Base
43+
44+- AVL_Tree unit
45+ - TAVLTree and TAVLTreeNode; see [[AVL Tree]]
46+- Contnrs unit
47+ - TFPObjectList
48+ - TObjectList
49+ - TComponentList
50+ - TClassList
51+ - TOrderedList
52+ - TStack
53+ - TObjectStack
54+ - TQueue
55+ - TObjectQueue
56+ - TFPHashList
57+ - TFPHashObjectList
58+ - TFPDataHashTable
59+ - TFPStringHashTable
60+ - TFPObjectHashTable
61+ - TBucketList
62+ - TObjectBucketList
63+
64+### FCL-STL
65+
66+- GVector unit
67+ - TVector: Implements dynamically self-resizing array, item order is based on insertion order
68+- [[GSet]] unit
69+ - TSet: Implements red-black tree backed set, sorted in a manner of your choosing
70+- GHashSet unit
71+ - THashSet: Implements hashtable backed set, no order is guaranteed
72+- GStack unit
73+ - TStack: Implements stack, LIFO (last in first out) order
74+- GQueue unit
75+ - TQueue: Implements stack, items are pushed from front, FIFO (first in first out) order
76+- GPriorityQueue unit
77+ - TPriorityQueue: Implements heap backed priority queue, order is based on given compare function
78+- GDeQue unit
79+ - TDeque: Implements double ended queue, items can be pushed and popped from either front or back
80+- GMap unit
81+ - TMap: Implements TSet (and therefore, red-black tree) backed map
82+- GHashMap unit
83+ - THashMap: Implements hashtable backed map
84+- GTree unit
85+ - TTree: Implements k-ary tree, supports depth first and breadth first traversal
86+
87+## Lazarus/LCL
88+
89+- AvgLvlTree: extended versions of the FPC/FCL TAVLTree and TAVLTreeNode. See [[AVL Tree]].
90+
91+## 3rd party
92+
93+| project | license | generic | types | notes |
94+|----|----|----|----|----|
95+| [CL4L](https://github.com/CynicRus/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...) |
96+| [heContnrs](http://code.google.com/p/fprb/wiki/heContnrs) | BSD3 | yes | \| ... | Collection of generic Free Pascal containers: BTree, lists, vectors. |
97+| [Fundamentals](https://github.com/fundamentalslib/) | BSD | no | \| ... | GitHub account contains 2 versions of library: 4 and 5. |
98+| [RBS AntiDOT](http://sourceforge.net/projects/adot/) | GPLv2 | ?? | \| ... | Library of containers and data structures for Pascal: Vectors, Maps, Sets, Lists and others. |
99+| [LightContainers](http://www.stack.nl/~marcov/lightcontainers.zip), [GitHub mirror](https://github.com/Alexey-T/FPC_light_containers) | FPC | no+yes | \| aasl | Generic and non-generic variants. Quite low-level. |
100+| [[StringHashMap]] | MPL1.0 | ?? | \| ... | Port of code from JCL. |
101+| [GContnrs](http://yann.merignac.free.fr/unit-gcontnrs.html) | 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. |
102+| [CL4fpc](https://sourceforge.net/projects/cl4fpc/) | GPLv2 | yes | \| ... | Red-black tree, AVL tree, Decart tree, weight-balanced tree, hash-maps, FIFO, ResPool and others. |
103+| [HAMT](https://www.benibela.de/sources_en.html#hamt) | LGPLv2 + linking exception | yes | \| tm, ts | Immutable hash array mapped tree. |
104+| [[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. |
105+| [PascalContainer](https://github.com/terrylao/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. |
106+
107+| code | data type |
108+|------|------------------------------------------|
109+| al | array list |
110+| as | array set |
111+| rb | red-black tree |
112+| av | AVL tree |
113+| hm | hashmap |
114+| hs | hashset |
115+| ll | linked list |
116+| q | queue |
117+| dq | deque |
118+| s | stack |
119+| v | vector |
120+| tm | treemap |
121+| ts | treeset |
122+| ms | multiset |
123+| mm | multimap |
124+| bm | bijective map |
125+| bs | bitset |
126+| gr | graph |
127+| aasl | "array of array of T" based sorted list. |
128+| | |
129+
130+## See also
131+
132+- [FreePascal hash maps comparsion](http://www.benibela.de/fpc-map-benchmark_en.html)
133+- [Tomes of Delphi: Algorithms and Data Structures](https://secondboyet.com/FixedArticles/DADSBook.html)
134+- [EZDSL: Easy Data Structures Library for Delphi](https://github.com/jmbucknall/EZDSL)
135+
136+---
137+*From the Free Pascal wiki, page "Data Structures, Containers, Collections", as it stood on 2022-03-12 after a change by Alextp, out of the wiki's dump of 2024-05-26. Copyright stays with the author who wrote it, according to the old wiki's [[Licensing]] page. If you have concerns about this material, [message the admin](/wiki-contact).*
138+Category: Collections
139+Category: Containers
140+Category: Data Structures
141+Category: FCL
142+Category: LCL
143+Category: RTL

Back to history