Data Structures, Containers, Collections

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)
  • TFPGList
  • TFPGObjectList
  • TFPGInterfacedObjectList
  • TFPGMap
  • TFPGMapInterfacedObjectData
• 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
    • TAVLTree
    • TSortedSet

Free Component Library (FCL)

FCL-Base

• AVL_Tree unit
  • TAVLTree and TAVLTreeNode; see AVL Tree
• 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

• FreePascal hash maps comparsion
• Tomes of Delphi: Algorithms and Data Structures
• EZDSL: Easy Data Structures Library for Delphi

---

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.