Data Structures, Containers, Collections: what changed

Revision 2 to 3. Removed lines have a minus sign; added lines have a plus sign.

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