Sign in Join
Wiki copytemporary

Data Structures, Containers, Collections: what changed

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

OldNewLine
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+
112## Introduction
213
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.
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.
415
5-Free Pascal ships with numerous data structures, at different levels (RTL, FCL) but there are also third party solutions offering such feature.
16+Free Pascal ships with numerous data structures, at different levels (RTL, FCL) but there are also third party solutions offering such feature.
617
718## [[RTL|Run time library (RTL)]]
819
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]]
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\)")
3950
4051## [[FCL|Free Component Library (FCL)]]
4152
4253### FCL-Base
4354
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
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
6374
6475### FCL-STL
6576
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
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
8697
8798## Lazarus/LCL
8899
89-- AvgLvlTree: extended versions of the FPC/FCL TAVLTree and TAVLTreeNode. See [[AVL Tree]].
100+ * AvgLvlTree: extended versions of the FPC/FCL TAVLTree and TAVLTreeNode. See [[AVL Tree]].
90101
91102## 3rd party
92103
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-
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+
130139## See also
131140
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)
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>)
135144
136145---
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
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).*

Back to history