Algorithms and Data Structures

ADS is a header-only C++20 library of the algorithms and the data structures of the (Italian) textbook

A. Montresor, Algoritmi e Strutture Dati, 2025, https://algoritmicamente.it (CC BY-NC 4.0)

(a revision of A. A. Bertossi and A. Montresor, Algoritmi e Strutture di Dati, 3rd edition, Città Studi, 2014), in which each exercise of the book is a test. It also has the structures and the algorithms that a course on the subject usually adds, and a few engineered ones meant for speed. An abstract data type is a C++20 concept whose realizations follow the pseudocode and the names of the book (empty(), head(), next(), read(), push(), enqueue(), and so on), and hence the code can be read side by side with the text. Where the book leaves a choice open, or its pseudocode has a defect (a few figures, too, disagree with the formulae they illustrate), the header states the choice made and the reason for it.

Performance

The table below compares the engineered structures of ADS with those of the standard library (libstdc++), of Boost 1.83, of GMP 6.3.0, of FFTW 3.3.10 and of pocketfft and ducc0, as measured by the benchmarks in bench/ (make bench). These were run twice on an otherwise idle Intel Xeon Gold 5120 at 2.2 GHz, on one core pinned by taskset, with g++ 13.3 at -O3 -march=native; GMP was configured for that processor, and FFTW was built with SSE2, AVX, AVX2 and AVX-512. Each cell of a benchmark is the median of 11 runs, and the clock does not include the building of the input nor the planning of FFTW and of ADS (measured apart in the row "fft plan"). A row gives the time of the library divided by that of ADS (above 1 when ADS is faster), as the median and the range over the cells of the benchmark, i.e., its cases (e.g., random, sorted or few distinct keys for the sorts) and its sizes ($10^5$ and $10^6$ items for the containers). When a library has more than one candidate, the time of a cell is that of the fastest of them (e.g., the faster of boost::pdqsort and boost::spreadsort). The same code measured twice differs by 1.1% in the median cell and by 4.3% at the 90th percentile, over the 1544 cells of the two runs; the largest differences, up to 50%, are in cells of a few hundred nanoseconds, where they are the resolution of the clock. Hence, a ratio between 0.95 and 1.05 is usually a tie.

benchmark	ADS	against	cells	median	range
sort double	ADS::sort	std	12	8.83	1.95 to 32
		Boost	12	2.20	0.93 to 14
	ADS::stableSort	std	12	4.35	1.67 to 25
		Boost	12	1.20	0.88 to 3.01
sort int64	ADS::sort	std	12	14	1.95 to 39
		Boost	12	3.52	0.84 to 17
	ADS::stableSort	std	12	13	2.33 to 32
		Boost	12	1.40	0.71 to 26
sort record	ADS::sort	std	12	2.33	1.10 to 6.60
		Boost	12	1.00	0.98 to 1.02
	ADS::stableSort	std	12	5.53	0.75 to 32
		Boost	12	0.98	0.57 to 1.16
sort string	ADS::sort	std	12	3.36	1.67 to 5.15
		Boost	12	1.45	0.90 to 2.20
	ADS::stableSort	std	12	2.37	1.68 to 6.10
		Boost	12	2.76	1.34 to 5.62
sort uint32	ADS::sort	std	12	15	3.90 to 36
		Boost	12	3.93	0.75 to 16
	ADS::stableSort	std	12	13	1.34 to 41
		Boost	12	1.03	0.63 to 36
dictionaries	ADS::FlatHashTable	std	8	5.47	4.32 to 16
		Boost	8	0.93	0.75 to 1.16
	ADS::RedBlackTree	std	8	1.45	1.00 to 2.38
priority	ADS::DaryHeap d=4	std	6	1.62	1.38 to 2.17
		Boost	6	1.04	0.87 to 1.68
	ADS::FibonacciHeapPriorityQueue	Boost	6	0.61	0.54 to 0.86
sequences	ADS::ArraySequence	std	6	1.05	1.00 to 1.12
	ADS::List	std	6	1.02	0.99 to 1.10
	ADS::SinglyList	std	6	0.98	0.86 to 1.03
bignum	ADS::BigInteger	Boost	12	4.04	1.00 to 91
		GMP	12	0.33	0.20 to 1.25
	ADS::Rational	Boost	3	4.74	1.93 to 6.03
		GMP	3	0.42	0.40 to 0.46
fft	ADS::fft	FFTW	44	1.11	0.84 to 2.41
		pocketfft	44	3.18	1.44 to 21
		ducc0	37	1.97	1.09 to 17
fft plan	ADS::fft	FFTW	7	0.22	0.07 to 1290

ADS::sort() and ADS::stableSort() are faster than the standard library in almost all the cells, by 2 to 15 times in the median (the radix sorts accounting for most of it), and they are often as fast as Boost or faster. However, boost::spinsort is 1.4 to 1.8 times faster on the stable sort of records, of sorted 32-bit keys and of reversed 64-bit keys at $10^5$, and boost::spreadsort is 1.3 times faster on sorted 32-bit keys. FlatHashTable is 4 to 16 times faster than std::unordered_map, and it is on a par with boost::unordered_flat_map on the lookups, but for the misses among $10^5$ keys (where Boost is 1.15 times faster). Boost is also 1.3 times faster on the insertions and the visits of $10^5$ keys, and 1.16 times slower on the insertions of $10^6$. It is fair to remark that the libraries built on hand-written kernels stay ahead. GMP is 2 to 5 times faster than BigInteger on products, quotients and decimal conversion (twice as fast already at 16 limbs, where both use the schoolbook algorithms), and mpq_class is 2.2 to 2.5 times faster than Rational; ADS::fft (complex, real and single precision data, the cosines of type 2, many transforms, 2 dimensions and convolutions, on powers of 2 and on other sizes) is faster than the faster plan of FFTW in the median cell, by 1.11, and 1.4 to 3 times faster than pocketfft and ducc0; FFTW stays ahead by 1.15 to 1.2 times on the real transform of $2^{14}$ points, by 1.1 on the transform of 32 x 32 points and by 1.06 to 1.23 on the real one of $2^{20}$, the other cells below 1 (0.94 to 0.99 in one of the two runs, at least 1 in the other) being ties. The plans of ADS, which time 4 factorizations up to $2^{17}$ points, cost up to 0.4 µs per point, against up to 900 µs of FFTW_MEASURE and 3 µs of FFTW_ESTIMATE. Also, the Fibonacci heap of Boost is 1.2 to 1.9 times faster than that of ADS, which follows the pseudocode of the book. The tables of all the structures, those of the book included, are in results/ together with the raw files of the two runs.

Layout

Headers are grouped by abstract data type, one header per realization, and include/ADS/ADT.h has the concepts of the book. The folders of the types (sequence/, stack/, queue/, tree/, dictionary/, set/, priority/, mfset/ and graph/) also hold the algorithms on them, e.g., the operations on sets or the visits of a graph. The other folders group the algorithms by technique or by problem:

• search/ and sort/, the searches and the sorts;
• numeric/, the products of integers, polynomials and matrices;
• string/, the algorithms on strings;
• optimization/, the problems of optimization (knapsack, intervals);
• geometry/, the convex hull;
• backtrack/, the enumerations by backtrack;
• complexity/, the problems of NP and their reductions;
• intractable/, the techniques for the intractable problems;
• memory/ and concurrent/, the allocators, the arena, the queues between threads and the concurrent hash table;
• external/, the two-level memory and the algorithms on it;
• compression/ and succinct/, the codes, the compressors and the compressed data structures;
• combinatorial/, the broadword tricks and the combinatorial generation;
• algorithm/, the rest.

A header is included by its path (e.g., #include "ADS/graph/ListGraph.h") and includes what it needs. It declares its classes and functions, with their contracts, and the definitions of its templates are in the folder impl/ next to it (e.g., ADS/graph/impl/ListGraph.tpp), included at the end of the header, as in Boost; hence, include/ is the whole library.

Where each thing comes from

Each header and each test cites the section, the example or the exercise of the book that it implements, and the tests are listed with their source in test/tests.txt; the solutions of the exercises are in the tests, one function per exercise. Each one is checked on the example of the book, on its edge cases and (where an enumeration is possible) on random instances against the enumeration. Since the license of the book does not allow its text in a repository under the LGPL, the code cites it instead of reproducing it.

Chapter	Section	What	Header	Tests
1	1.2	minimum, binary search	search/Minimum.h, search/BinarySearch.h	ch01.sec1.2.*
	1.4	multiplication of Ahmes	numeric/BinaryInteger.h	ch01.sec1.4.ahmes
2	2.6	sum and products of binary integers, Karatsuba	numeric/BinaryInteger.h	ch02.sec2.6.*
	2.7	Selection, Insertion, Merge, Counting Sort, lower bound	sort/	ch02.sec2.7.*
	2.9	solutions of the recurrences (Teoremi 2.2–2.5)	algorithm/MasterTheorem.h	ch02.sec2.9.recurrences
3	3.2	SEQUENCE, SET, DICTIONARY	ADT.h	ch03.*
4	4.1	LIST, bidirectional circular with sentinel	sequence/List.h	ch04.spec.List
	4.2	sequence on a vector that doubles	sequence/ArraySequence.h	ch04.spec.ArraySequence, ch04.sec4.2.doubling
	4.2.1	binary counter, amortized analysis	algorithm/BinaryCounter.h	ch04.sec4.2.1.counter
	4.3	STACK, QUEUE	ADT.h
	4.3.1	stack simulated with a sequence	stack/SequenceStack.h	ch04.sec4.3.1.stack-on-list
	4.3.2	stack on a vector	stack/ArrayStack.h	ch04.spec.ArrayStack
	4.3.3	queue on a circular vector	queue/ArrayQueue.h	ch04.spec.ArrayQueue
	4.4	towers of Hanoi, recursive and iterative	algorithm/Hanoi.h	ch04.sec4.4.hanoi
	4.6	exercises 4.1–4.11; the singly linked list of 4.6 and the linked queue of 4.10	test/ch04.cpp, sequence/SinglyList.h, queue/LinkedQueue.h	ch04.ex4.*
5	5.1, 5.3	ordered TREE, parent/first child/sibling	tree/Tree.h	ch05.spec.Tree
	5.2	previsit, postvisit, invisit, by levels	tree/Tree.h	ch05.sec5.2.visits
	5.4	vector of parents	tree/ParentTree.h	ch05.sec5.4.parents
	5.5	binary TREE and its visits, ordered tree as binary	tree/BinaryTree.h	ch05.spec.BinaryTree, ch05.sec5.5.*
	5.6	complete d-ary tree in a vector	tree/BinaryTree.h	ch05.sec5.6.dary
	5.8	exercises 5.1–5.13	test/ch05.cpp	ch05.ex5.*
6	6.1	binary search tree (ABR), DICTIONARY	tree/SearchTree.h	ch06.sec6.1.*
	6.2	Red-Black tree, Teoremi 6.1–6.3	tree/SearchTree.h	ch06.spec.RedBlackTree, ch06.sec6.2.*
	6.3	B+-tree, insertion, search, interval	tree/BPlusTree.h	ch06.sec6.3.*
	6.4	exercises 6.1–6.10	test/ch06.cpp	ch06.ex6.*
7	7	table with direct access	dictionary/DirectTable.h	ch07.sec7.direct-access
	7.1	extraction, XOR, division, multiplication, middle square	dictionary/HashFunctions.h	ch07.sec7.1.*
	7.2	lists of overflow, open addressing, deleted places	dictionary/ChainedHashTable.h, dictionary/OpenHashTable.h	ch07.sec7.2.*
	7.3	I(α) and S(α) measured against the formulas	dictionary/OpenHashTable.h	ch07.sec7.3.complexity
	7.4	restructuring, amortized cost	dictionary/TableSize.h	ch07.sec7.4.restructure
	–	exercises 7.1–7.10	test/ch07.cpp	ch07.ex7.*
8	8.1	SET on a boolean vector	set/BoolSet.h	ch08.sec8.1.boolean
	8.2	SET on an unsorted list	set/ListSet.h	ch08.sec8.2.unsorted-list
	8.3	SET on a sorted list, operations by merging	set/SortedListSet.h	ch08.sec8.3.sorted-list
	8.4	SET on hash tables	set/DictionarySet.h, set/SetOperations.h	ch08.sec8.4.hash
	8.5	SET on Red-Black trees	set/DictionarySet.h	ch08.sec8.5.tree
	8.7	exercises 8.1–8.10, LinkedHashSet, multiset	set/LinkedHashSet.h, set/HashMultiset.h, test/ch08.cpp	ch08.ex8.*
9	9.1	definitions, the case of the duke McPollock	test/ch09.cpp	ch09.sec9.1.*
	9.2, 9.4	GRAPH, lists and vectors of adjacency	graph/Graph.h, graph/ListGraph.h, graph/ArrayGraph.h	ch09.spec.ListGraph, ch09.sec9.3.matrices
	9.3	adjacency matrix, incidence matrix	graph/MatrixGraph.h	ch09.spec.MatrixGraph, ch09.sec9.3.matrices
	9.5	bfs, distances, dfs, components, dfs schema, cycles, topological order, strong components	graph/Visit.h	ch09.sec9.5.*
	9.7	exercises 9.1–9.11	test/ch09.cpp	ch09.ex9.*
10	10.1	PRIORITYQUEUE on a d-ary heap, on lists, on a Red-Black tree	priority/	ch10.spec.*PriorityQueue, ch10.sec10.1.3.heap
	10.1.4	heapBuild(), heapsort()	sort/Heapsort.h	ch10.sec10.1.4.heapsort
	10.2	MFSET on a forest (rank, compression of the paths) and on lists, incremental components	mfset/	ch10.sec10.2.*
	10.4	exercises 10.1–10.9	test/ch10.cpp	ch10.ex10.*
11	11.1–11.2	shortest paths, theorem of Bellman, the prototype	graph/ShortestPaths.h	ch11.sec11.1.bellman, ch11.sec11.2.prototype
	11.3–11.5	Dijkstra, Johnson, Fredman-Tarjan on a Fibonacci heap	graph/ShortestPaths.h, priority/FibonacciHeapPriorityQueue.h	ch11.sec11.3.dijkstra, ch11.sec11.5.fibonacci
	11.6–11.8	Bellman-Ford-Moore, the stack, Pape-D'Esopo on a dequeue	graph/ShortestPaths.h, queue/Dequeue.h	ch11.sec11.6.*, ch11.sec11.7.stack, ch11.sec11.8.pape
	11.10	exercises 11.1–11.10	test/ch11.cpp	ch11.ex11.*
12	12.1	search by interpolation	search/InterpolationSearch.h	ch12.sec12.1.interpolation
	12.2	Quicksort, its improvements, on lists	sort/QuickSort.h	ch12.sec12.2.*
	12.3	products of polynomials, Karatsuba	numeric/Polynomial.h	ch12.sec12.3.polynomials
	12.4	Strassen	numeric/Matrix.h	ch12.sec12.4.strassen
	12.6	exercises 12.1–12.13	test/ch12.cpp	ch12.ex12.*
13	13	binomial coefficients, Fibonacci	numeric/Combinatorics.h	ch13.sec13.binomial, ch13.sec13.4.fibonacci
	13.1	approximate string matching, edit distance	string/ApproximateMatching.h	ch13.sec13.1.matching
	13.2	weighted independent intervals	optimization/WeightedIntervals.h	ch13.sec13.2.intervals
	13.3	chain of matrices	numeric/MatrixChain.h	ch13.sec13.3.matrix-chain
	13.5	Floyd-Warshall, insertion of an edge	graph/AllPairsShortestPaths.h	ch13.sec13.5.floyd-warshall
	13.6	knapsack, by a table and by memoization	optimization/Knapsack.h	ch13.sec13.6.knapsack
	13.7	LCS, diff, longest common substring, alignments	string/	ch13.sec13.7.lcs
	13.8	exercises 13.1–13.13	test/ch13.cpp, algorithm/Subsequences.h	ch13.ex13.*
14	14	change with coins	optimization/CoinChange.h	ch14.sec14.change
	14.1	real knapsack	optimization/FractionalKnapsack.h	ch14.sec14.1.real-knapsack
	14.2	independent set of intervals, coloring, towers	optimization/Intervals.h	ch14.sec14.2.intervals
	14.3	Kruskal and Prim, Teorema 14.1	graph/MinimumSpanningTree.h	ch14.sec14.3.*
	14.4	code of Huffman	string/Huffman.h	ch14.sec14.4.huffman
	14.5	exercises 14.1–14.10, Shortest Job First	test/ch14.cpp, optimization/ShortestJobFirst.h	ch14.ex14.*
15	15	local search of the minimum spanning tree	test/ch15.cpp	ch15.sec15.local-search
	15.1	Shell Sort, four sequences of gaps	sort/ShellSort.h	ch15.sec15.1.*
	15.2	maximum flow (Ford-Fulkerson, Edmonds-Karp, Dinic), minimum cut, circulations	graph/MaxFlow.h	ch15.sec15.2.max-flow
	15.4	exercises 15.1–15.10, Eulerian cycle	test/ch15.cpp, graph/EulerianCycle.h	ch15.ex15.*
16	16.1	convex hull, O(n³) and Graham	geometry/ConvexHull.h	ch16.sec16.1.*
	16.2	enumeration: subsets, permutations, derangements, subset sum	backtrack/Enumeration.h	ch16.sec16.2.subsets
	16.3	Sudoku	backtrack/Sudoku.h	ch16.sec16.3.sudoku
	16.4	exercises 16.1–16.8, n queens, tour of the knight, anagrams	backtrack/, test/ch16.cpp	ch16.ex16.*
17	17	Monte Carlo: null polynomial, Freivalds, half-satisfiability	algorithm/MonteCarlo.h	ch17.sec17.monte-carlo, ch17.ex17.4, ch17.ex17.5
	17.1	selection of Hoare, median of medians	search/Selection.h	ch17.sec17.1.selection
	17.2	Euclid, powers, Miller-Rabin, primality on 64 bits	numeric/NumberTheory.h	ch17.sec17.2.primality, ch17.ex17.1–ex17.3
	17.3	RSA	numeric/RSA.h	ch17.sec17.3.rsa
18	18	the problems in NP, certificates and enumerations	complexity/Problems.h, complexity/Domino.h	ch18.sec18.examples
	18.2–18.3	nondeterminism simulated by enumeration	complexity/Nondeterminism.h	ch18.sec18.2.nondeterminism
	18.5–18.7	reductions, linear tiling in P, Teoremi 18.2–18.9	complexity/Reductions.h	ch18.sec18.5.*, ch18.sec18.7.*
	18.9	exercises 18.1–18.16	test/ch18.cpp	ch18.ex18.*
19	19.1	pseudopolynomial algorithms, scheduling	intractable/Pseudopolynomial.h	ch19.sec19.1.subset-sum
	19.2	approximation: ff, ffd, triangular salesman, apSubsetSum	intractable/Approximation.h	ch19.sec19.2.*
	19.3	branch-&-bound: bbTsp, 1-tree, Little, clique, knapsack	intractable/BranchAndBound.h	ch19.sec19.3.bb-tsp
	19.4	heuristics: greedyTsp, min-max-greedy, local search	intractable/Heuristics.h	ch19.sec19.4.*
	19.5	the fifteen puzzle	intractable/FifteenPuzzle.h	ch19.sec19.5.fifteen
	19.6	exercises 19.1–19.19	test/ch19.cpp	ch19.ex19.*
Conclusione	Tab. 19.1	easy twins of NP-hard problems, interval graphs	complexity/EasyCases.h	conclusion.*

Beyond the book

Several structures and algorithms that the book does not describe, but that a course on the subject usually covers (e.g., the realizations with cursors, the parenthesized lists of trees, the general schemes of the techniques), are written on the same classes and tested in test/beyond.cpp.

What	Header	Test
binary tree in a positional vector	tree/ArrayBinaryTree.h	beyond.array-binary-tree
binary and ordered trees with cursors	tree/CursorBinaryTree.h, tree/CursorTree.h	beyond.cursor-*
ordered tree in a vector in preorder	tree/PreorderArrayTree.h	beyond.preorder-array-tree
heap on a binary tree with pointers	priority/LinkedHeapPriorityQueue.h	beyond.linked-heap
graph of node objects with pointers	graph/PointerGraph.h	beyond.pointer-graph
k stacks in one vector	stack/MultiStack.h	beyond.multistack
search, order, bubble and natural merge sort on sequences	sequence/SequenceAlgorithms.h	beyond.sequence-*
palindromes and sorting with a stack	stack/StackAlgorithms.h	beyond.stack-algorithms
naive and Knuth-Morris-Pratt string matching	string/StringMatching.h	beyond.string-matching
exercises on lists, strings, trees and arrays	test/beyond.cpp	beyond.*-exercises, beyond.even-odd-strings
list with cursors in a shared space with a free list	sequence/CursorList.h	beyond.cursor-list, ch04.spec.CursorList
range of C++ over any sequence	sequence/SequenceRange.h	beyond.sequence-range
search with the place of insertion and sublists of a sorted sequence	sequence/SequenceAlgorithms.h	beyond.sorted-list
postfix expressions, infix to postfix (shunting-yard)	stack/Expressions.h	beyond.postfix
queue with no duplicates, positive items of a queue	queue/UniqueQueue.h, queue/QueueAlgorithms.h	beyond.queue-algorithms
dictionary on a sorted vector, pseudo-random inspection	dictionary/SortedArrayDictionary.h, dictionary/OpenHashTable.h	beyond.sorted-array-dictionary, beyond.hashing
decision tree of the binary search	search/BinarySearch.h	beyond.decision-tree
trees as parenthesized lists, tree of an expression, tree with lists of children	tree/BinaryTree.h, tree/ExpressionTree.h, tree/ChildListTree.h	beyond.list-forms, beyond.expression-tree, beyond.child-list-tree
union by size in the MFSET	mfset/MFSet.h	contract_mfset.mfset
general visit of a graph, unilateral connection	graph/Visit.h	beyond.generic-visit, beyond.unilateral-incidence
general schemes of the techniques (enumeration, backtracking, greedy, divide et impera)	algorithm/Paradigms.h	beyond.paradigms
Knuth's strong failure function, Hibbard's gaps, sentinels, minimum and maximum together	string/StringMatching.h, sort/, search/Minimum.h	beyond.kmp-strong, beyond.slide-sorts
greedy and backtracking knapsack, eight puzzle by breadth and depth	intractable/BranchAndBound.h, intractable/FifteenPuzzle.h	beyond.knapsack-heuristics, beyond.eight-puzzle

From The Art of Computer Programming

The structures and the algorithms of Knuth's The Art of Computer Programming that the book leaves out are in ADS too, from volumes 1, 2, 3, 4A and 4B, with a few relatives from the later literature; they are tested in test/taocp.cpp against the standard library, against a slower method that is obviously correct (the definition of the transform, the enumeration of the subsets, the backtrack of chapter 16) and against the counts and the bounds of their analysis.

What	Header	Test
Fibonacci search and uniform binary search (6.2.1)	search/KnuthSearches.h	taocp.knuth-searches
AVL tree (6.2.3) and B-tree with removal (6.2.4)	tree/AVLTree.h, tree/BTree.h	taocp.balanced-trees
skip list, treap, splay tree	dictionary/SkipList.h, tree/Treap.h, tree/SplayTree.h	taocp.balanced-trees
trie and compact trie (Patricia) (6.3)	dictionary/Trie.h	taocp.tries
coalesced hashing with a cellar and Brent's double hashing (6.4)	dictionary/KnuthHashing.h	taocp.knuth-hashing
Bloom filter	set/BloomFilter.h	taocp.bloom-filter
binary and list insertion, address calculation, radix exchange, tournament sort, Ford-Johnson merge insertion (5.2, 5.3.1)	sort/KnuthSorts.h	taocp.knuth-sorts
replacement selection and polyphase merge (5.4)	sort/ExternalSort.h	taocp.external-sort
threaded binary tree (2.3.1)	tree/ThreadedTree.h	taocp.threaded-tree
boundary-tag allocator with first, best and next fit, buddy system (2.5)	memory/Allocators.h	taocp.allocators
heap of cells with the marking of Deutsch, Schorr and Waite (2.3.5)	memory/CellHeap.h	taocp.cell-heap
sparse matrix on orthogonal lists, pivot step (2.2.6)	numeric/SparseMatrix.h	taocp.sparse-matrix
broadword tricks: sideways sum, ruler, Gray code, Gosper, Morton code (7.1.3)	combinatorial/Bitwise.h	taocp.bitwise
tuples, permutations, combinations, partitions, nested parentheses, with the Gray orders (7.2.1)	combinatorial/Generation.h	taocp.generation
linear congruential generators, chi-square, Kolmogorov-Smirnov, serial and spectral tests, shuffling and sampling (3.2-3.4)	numeric/RandomNumbers.h	taocp.random-numbers
fast Fourier transform (4.3.3, 4.6.4)	numeric/FFT.h	taocp.fft
integers of any length: Karatsuba, Toom-3, Toom-4, Toom-3/2 and 4/2 and the NTT, Algorithm D and the recursive division, the conversions by halves, the square root of Zimmermann, the gcd of Lehmer on two digits and the half gcd (4.3, 4.4, 4.5.2)	numeric/BigInteger.h	taocp.big-integer*
exact rationals (4.5.1)	numeric/Rational.h	taocp.rational
exact cover by dancing links, Algorithm X (7.2.2.1)	backtrack/DancingLinks.h	taocp.dancing-links
SAT by DPLL and by conflict-driven clause learning (7.2.2.2)	backtrack/SatSolvers.h	taocp.sat-solvers

From Ferragina's algorithm engineering

The algorithms of P. Ferragina's Pearls of Algorithm Engineering, from the maximum sub-array sum to the compressed data structures, are in ADS as well. Each header compares the algorithms of its chapter with the variants of the later literature (e.g., SA-IS beside the skew algorithm, or the sampled select of the practical libraries beside Clark's scheme). The tests in test/pearls_*.cpp check them against brute force, against the standard library and against the examples of the notes, with their numbers. A class simulates the two-level memory of chapters 3 to 6 and counts the reads and the writes of blocks; hence, the tests can also check the bounds on the I/Os that those chapters prove.

What	Headers	Tests
maximum sub-array sum, with lengths in a range and maximum density (2)	algorithm/MaximumSegments.h	pearls_io.ch2.*
random sampling, on disk and on streams, Vitter's skips (3)	numeric/RandomSampling.h	pearls_io.ch3.*
list ranking by pointer jumping and independent sets, in memory and on disk (4)	external/ListRanking.h	pearls_io.ch4.*
two-level memory, binary and multiway mergesort, distribution sort, loser tree, I/O lower bounds (5)	external/, priority/LoserTree.h	pearls_io.ch5.*
sorted set intersection: merge, binary search, mutual partition, doubling, two-level (6)	set/SortedIntersection.h	pearls_io.ch6.*
universal hashing, d-left, FKS, minimal ordered perfect hashing, cuckoo hashing, Bloom variants (8)	dictionary/, set/BloomVariants.h	pearls_hashing.*
prefix search, front coding, Patricia trie, two-level dictionary (9)	string/PrefixSearch.h, string/FrontCoding.h, dictionary/PatriciaTrie.h	pearls_hashing.*
suffix arrays (six constructions), LCP, range minimum queries, suffix trees and their applications (10)	string/SuffixArray.h, string/SuffixTree.h, search/RangeMinimum.h	pearls_suffix.*
integer codes: gamma, delta, Rice, Golomb, PForDelta, variable-byte, (s,c)-dense, interpolative, Elias-Fano (11)	compression/IntegerCodes.h, succinct/EliasFano.h	pearls_succinct.*
canonical Huffman, arithmetic coding, PPM (12), LZ77, LZSS, LZ78, LZW (13), Burrows-Wheeler, bzip, FM-index (14)	compression/	pearls_compression.*
bit vectors with rank and select, succinct trees (Jacobson, LOUDS, balanced parentheses) and graphs (k2-tree, Boldi-Vigna) (15)	succinct/	pearls_succinct.*

The exercises and the exams of the course

Beyond the exercises of the book, the tests cover the material of the course on which the book is based: the chapter collections, the thematic collections, more than 80 exams from 2011 to 2026 with their official solutions, the exercise sessions and the laboratory projects. Each problem is implemented after its official solution and checked on the examples of its statement. It is also checked against an independent oracle (brute force, a simpler algorithm, the standard library) on random instances, which usually exposes the slips of the official solutions; there, the test implements the correct version and shows the counterexample. The tests are in test/exam_*.cpp, one program per theme (e.g., backtracking, dynamic programming, flows) or per source, and the name of a test gives the problem and the date of its exam.

Engineered structures

Beside the classes of the book, which follow its pseudocode, a few structures are written for speed, for the programs that need it, and tested in test/engineered.cpp, the heaps in test/heaps.cpp, the vectors in test/sequences.cpp and, the hashing, in test/hashing.cpp, the concurrent ones also on real threads under ThreadSanitizer. FlatHashTable is the hash tested in test/engineered.cpp and, the hashing, in test/hashing.cpp and, those of the notes of Ferragina, in test/engineered_pearls.cpp, the concurrent ones also on real threads under ThreadSanitizer. FlatHashTable is the hash table that bench/dictionaries.cpp compares with boost::unordered_flat_map, while OpenHashTable stays the table of section 7.2 of the book; bench/hashing.cpp compares the hashing with Abseil, unordered_dense, robin-map, libcuckoo, XXH3, wyhash, rapidhash, fastfilter_cpp, xor_singleheader, PTHash, BBHash and RecSplit; bench/priority.cpp compares the heaps with Boost.Heap, tlx and radix-heap, also in Dijkstra's algorithm, and bench/memory.cpp the arena and the pool with std::pmr, Boost.Pool, mimalloc and jemalloc; bench/graphs.cpp runs the algorithms of the book on graphs, templates on their structures, on those of the standard library, of Boost and of ADS, with the same counts of work on the three. RecSplit, and the concurrent cuckoo table with libcuckoo, boost::concurrent_flat_map and a std::unordered_map under a std::shared_mutex. RecSplit. The combinatorial ones are tested in test/engineered_combinatorial.cpp and compared by bench/combinatorial.cpp and bench/backtrack.cpp with libpopcnt, libmorton, Hinnant's combinations and the programs DLX1, DLX2 and SSXCC of Knuth. std::pmr, Boost.Pool, mimalloc and jemalloc, and bench/allocators.cpp the standard allocators in the node containers, in std::allocate_shared and across two threads; bench/positions.cpp, bench/assembly.cpp and bench/fingerprints.cpp measure the structures of the rows of a model (the index of their positions, their assembly for the solvers of linear programs and their fingerprints) against the standard library, Boost and Eigen; their tests are in test/engineered_memory.cpp and test/engineered_sparse.cpp.

What	Header	Test
two-level bucket queue for integer keys (Dial; Burns et al.)	priority/BucketQueue.h	engineered.bucket-queue
d-ary heap of plain items, no handles	priority/DaryHeap.h	engineered.dary-heap
d-ary heap of the ids with decrease-key, the places in a vector, a PRIORITYQUEUE whose handles are the ids	priority/IndexedDaryHeap.h	engineered_graph.indexed-dary-heap
graph in compressed rows, each arc next to its weight, the rows sorted by head; transpose and relabelling	graph/StaticGraph.h	engineered_graph.static-graph
union-find in one vector, by size or rank, the paths halved or compressed (Tarjan and van Leeuwen)	mfset/UnionFind.h	engineered_graph.union-find
radix heap, monotone integer keys in buckets by digits of B bits (Ahuja et al.)	priority/RadixHeap.h	heaps.radix-heap
double-ended queues: min-max heap (Atkinson et al.) and interval heap (van Leeuwen and Wood)	priority/MinMaxHeap.h	heaps.double-ended-heaps
monotone bucket queue on a circular window, overflow to a radix heap (Dial)	priority/DialQueue.h	heaps.dial-queue
sequence heap, sorted sequences merged in batches by trees of losers (Sanders)	priority/SequenceHeap.h	heaps.sequence-heap
pairing heap with decrease-key, two-pass or auxiliary two-pass (Fredman et al.; Stasko and Vitter)	priority/PairingHeap.h	heaps.pairing-heap
sort of a List by relinking its cells: radix sort of ( key , cell ) or merge of the natural runs	sequence/ListSort.h	sequences.list-sort
tiered vector: access in O( 1 ), insertion and removal anywhere in O( sqrt n ) (Goodrich and Kloss)	sequence/TieredVector.h	sequences.tiered-vector
vector with room for N items inside itself	sequence/SmallVector.h	sequences.small-vector
hash table with control bytes in groups of 15 matched by SSE2, NEON or SWAR, the hash mixed on 128 bits, at most 7/8 full (Swiss tables; Boost's unordered_flat_map)	dictionary/FlatHashTable.h	engineered.flat-hash-table
hash table of pointers, linear probing, Fibonacci hashing	dictionary/PointerTable.h	engineered.pointer-table
arena of objects in blocks, stable addresses	memory/Arena.h	engineered.arena
pool of objects in doubling blocks, the slot freed last made first	memory/ObjectPool.h	engineered.pool
allocator of small blocks by size classes, a free list and a page of 64 KB per class (mimalloc, TLSF)	memory/SizeClassAllocator.h	memory.size-class-allocator
allocator of the large blocks on transparent huge pages	memory/HugePageAllocator.h	engineered.huge-page-allocator
standard allocator of size classes of 8 bytes, free lists by page, for the node containers and std::allocate_shared (mimalloc)	memory/PoolAllocator.h	engineered_memory.pool-allocator-containers
pool of size classes shared by threads, a heap per thread, the frees of the others sent back in batches (mimalloc; snmalloc)	memory/ConcurrentPool.h	engineered_memory.concurrent-pool-threads
index of the positions of objects in a vector, renumbered in one pass after an erasure by rank (Jacobson)	dictionary/PositionIndex.h	engineered_sparse.position-index-renumber
fingerprints of rows of doubles, dense and sparse, +0 equal to -0 and every NaN to every NaN	dictionary/RowFingerprint.h	engineered_sparse.row-fingerprint
compressed sparse columns or rows from triplets, repetitions summed, into the arrays of the caller (Gustavson; Davis)	numeric/SparseAssembly.h	engineered_sparse.sparse-assembly
compressed sparse rows that grow by rows and shrink by sets of rows in one pass	numeric/DynamicCsr.h	engineered_sparse.dynamic-csr
SplitMix64, Zobrist and simple tabulation hashing	dictionary/RandomHashing.h	engineered.random-hashing
hashes of words and strings by folded products of 128 bits, stripes in AVX2 or AVX-512 past 256 bytes (wyhash, XXH3)	dictionary/FastHash.h	hashing.fast-hash
filter of Bloom in blocks of 256 bits, one bit in each of 8 words (Putze et al.; Parquet)	set/BlockedBloomFilter.h	hashing.blocked-bloom
binary fuse filter, fingerprints of 8 or 16 bits (Graf and Lemire)	set/BinaryFuseFilter.h	hashing.binary-fuse
cuckoo filter with removals, fingerprints of 8 or 16 bits, buckets of 4 places in one word (Fan et al.)	set/CuckooFilter.h	hashing.cuckoo-filter
prefix filter, bins of 25 fingerprints as pocket dictionaries of 32 bytes, the overflow in a blocked filter of Bloom (Even, Even and Morrison)	set/PrefixFilter.h	hashing.prefix-filter
standard Ribbon filter, Gauss elimination on the fly, solution by columns (Dillinger and Walzer)	set/RibbonFilter.h	hashing.ribbon-filter
minimal perfect hash function by pilots, about 3 bits per key (PTHash)	dictionary/MinimalPerfectHash.h	hashing.minimal-perfect-hash
minimal perfect hash function by recursive splitting, about 1.8 bits per key, leaves by rotation fitting (RecSplit; Bez et al.)	dictionary/RecSplit.h	hashing.recsplit
minimal perfect hash function by levels of fingerprints, ranks by blocks of 512 bits (Müller, Sanders, Schulze, Zhou; BBHash; FMPH)	dictionary/FingerprintPerfectHash.h	hashing.fingerprint-perfect-hash
cuckoo table with buckets of 4 places, tags of 8 bits, search in breadth (Li et al.; libcuckoo)	dictionary/BucketCuckooTable.h	hashing.bucket-cuckoo
hash map with its pairs in a dense vector and an index of positions in groups of 12 control bytes, a removal by moving the last pair (the dictionaries of CPython 3.6; ankerl::unordered_dense)	dictionary/DenseHashMap.h	hashing.dense-hash-map
population count of arrays by the carry-save adders of Harley and Seal (AVX-512, AVX2), pdep, pext, select in a word (Mula, Kurz and Lemire)	combinatorial/FastBitwise.h	engineered_combinatorial.fast-bitwise
permutations by Heap's method and in lexicographic order, combinations, with the innermost places in straight-line code	combinatorial/FastGeneration.h	engineered_combinatorial.fast-generation
exact cover with colors on sparse sets, the dancing cells of Knuth's SSXCC	backtrack/FastExactCover.h	engineered_combinatorial.fast-exact-cover
lock-free queue from one producer to one consumer	concurrent/SPSCQueue.h	engineered.spsc-queue
lock-free inbox of many producers	concurrent/MPSCInbox.h	engineered.mpsc-inbox
wavelet matrix: access, rank, select, range quantiles (Claude, Navarro and Ordonez)	succinct/WaveletMatrix.h	engineered_succinct.wavelet-matrix
code of Huffman of bytes, lengths of at most 11 bits by package-merge, four streams, up to three symbols a lookup	compression/HuffmanCoder.h	engineered_succinct.huffman-coder
rANS of order 0 with four interleaved states (Duda; Giesen)	compression/Rans.h	engineered_succinct.rans-coder
Stream VByte, the lengths apart, one shuffle per 4 integers (Lemire, Kurz and Rupp)	compression/StreamVByte.h	engineered_succinct.stream-vbyte
rank and select in about 3.9% of the bits, one 128-bit entry per 4096 bits (Kurpicz; Zhou, Andersen and Kaminsky)	succinct/CompactRankSelect.h	engineered_succinct.compact-rank-select
rank and select with the counts inside the lines of the bits, rank in one access (SPIDER, Laws et al.)	succinct/InterleavedRankSelect.h	engineered_succinct.interleaved-rank-select
compressed vector of bits in m H0 + 0.175 m bits with rank and select (Raman, Raman and Rao; Claude and Navarro)	succinct/RRRBitVector.h	engineered_succinct.rrr-bit-vector
tANS of order 0 with 2^11 states, two halves of four states each (Duda)	compression/Tans.h	engineered_succinct.tans-coder
directly addressable codes with the optimal widths (Brisaboa, Ladra and Navarro)	compression/DirectAccessCodes.h	engineered_succinct.direct-access-codes
parse of LZ77 with no window in O(n) time (Karkkainen, Kempa and Puglisi)	compression/LZ77Linear.h	engineered_succinct.lz77-linear
tree of losers with the keys in its nodes, matches with no jump on the integers (Knuth; MCSTL, tlx)	priority/MultiwayMerge.h	engineered_pearls.flat-loser-tree
merge of k sorted ranges by a lazy funnel of binary mergers (Frigo et al.; Brodal et al.)	priority/MultiwayMerge.h	engineered_pearls.multiway-merge
cuckoo table shared by threads, buckets of 4 places, locks on 2048 stripes, paths searched in breadth without locks (Li et al.; libcuckoo)	concurrent/ConcurrentCuckooTable.h	engineered.concurrent-cuckoo, engineered.concurrent-cuckoo-threads
cuckoo table shared by threads, buckets of 4 places, one lock per region of buckets, lookups without locks under versions (seqlock), huge pages (Li et al.; libcuckoo)	concurrent/ConcurrentCuckooTable.h	engineered.concurrent-cuckoo, engineered.concurrent-cuckoo-threads
lock-free queue of many producers, a lane of recycled blocks each	concurrent/MPSCQueue.h	engineered_queues.mpsc-queue
bounded queue of many producers and many consumers, a sequence in each place (Vyukov)	concurrent/MPMCQueue.h	engineered_queues.mpmc-queue
event count, the sleep of a thread until a condition holds, with asymmetric fences	concurrent/EventCount.h	engineered_queues.event-count
sparse matrices in compressed rows and in SELL-C-sigma (Kreutzer et al.)	numeric/CsrMatrix.h, numeric/SellMatrix.h	engineered_numeric.csr-matrix, .sell-matrix
generators xoshiro256++, xoshiro256**, wyrand and the counter-based Philox4x32 and Philox4x64 (Salmon et al.), the alias method, normal and exponential deviates by ziggurats (Marsaglia and Tsang)	numeric/RandomGenerators.h	engineered_numeric.generators, .philox, .ziggurat
work-stealing deque (Chase and Lev; Lê et al.)	concurrent/WorkStealingDeque.h	engineered_queues.work-stealing-deque
wavelet tree shaped by the code of Huffman, n(H0+1) bits (Makinen and Navarro)	succinct/HuffmanWaveletTree.h	engineered_succinct.huffman-wavelet-tree
FM-index on the wavelet tree of Huffman, the succinct suffix array (Makinen and Navarro)	compression/HuffmanFMIndex.h	engineered_succinct.huffman-fm-index
partitioned Elias-Fano, blocks full, as vectors or by Elias-Fano (Ottaviano and Venturini)	succinct/PartitionedEliasFano.h	engineered_succinct.partitioned-elias-fano
binary packing SIMD-BP128 and its patched form PFor (Lemire and Boytsov; Zukowski et al.)	compression/BinaryPacking.h	engineered_succinct.binary-packing
r-index: count and locate in space proportional to the runs of the transform (Gagie, Navarro and Prezza)	compression/RIndex.h	engineered_succinct.r-index
move structure, a permutation of shifted intervals in O(1) a step (Nishimoto and Tabei)	succinct/MoveStructure.h	engineered_succinct.move-structure
r-index on move structures (Bertram, Fischer and Nalbach)	compression/MoveRIndex.h	engineered_succinct.move-r-index

Sorting

Beside the sorts of the book, ADS has the classical ones that the book leaves out and the engineered ones of the current libraries. They are tested in test/sorting.cpp on all the permutations of up to 7 items and on the patterns that usually defeat a sort (sorted, reversed, sawtooth, organ pipe, few distinct keys), and measured by bench/sort.cpp against std::sort, std::stable_sort and Boost.Sort (make bench, or CMake with -DADS_BENCHMARKS=ON). ADS::sort() and ADS::stableSort() (sort/Sort.h) choose among them by the type of the items and by the order, i.e., the radix sort for numbers, the MSD radix sort for strings, and pdqsort and Powersort for the rest, with thresholds chosen on the measures of results/.

What	Header
bubble, cocktail shaker, odd-even transposition, comb and gnome sort	sort/ExchangeSorts.h
cycle sort (fewest writes) and pancake sort (prefix reversals)	sort/CycleSort.h
tree sort, patience sort, smoothsort, strand sort	sort/TreeSort.h, sort/PatienceSort.h, sort/Smoothsort.h, sort/StrandSort.h
sorting networks of Batcher (merge exchange, bitonic)	sort/SortingNetworks.h
stooge sort, slow sort, bogo sort	sort/DidacticSorts.h
introsort, pdqsort, dual-pivot and three-way quicksort	sort/EngineeredQuickSorts.h
Timsort and Powersort	sort/RunSorts.h
LSD radix sort of numbers and by a key, American flag sort, MSD radix sort of strings, bucket sort	sort/RadixSort.h
multikey quicksort of strings	sort/MultikeyQuickSort.h
sort of strings by integer keys of 8 characters, sorted in the vector registers	sort/StringSort.h

Parallelism

The parallel algorithms of ADS take an executor as their first argument, i.e., any object that runs the calls f( 0 ), ..., f( n - 1 ) of a function on its threads and returns when they have returned (bulk()), and that tells how many threads it has (concurrency()); the sequential algorithms, which take none, are unchanged, and an algorithm called with one thread, or on a small input, is the sequential one. The executors are Sequential, ThreadPool, the pool of ADS on std::thread (a deque of work stealing of Chase and Lev per thread, the idle threads asleep on an event count after 2 ms), and, as options, OpenMPExecutor, TBBExecutor and FastFlowExecutor, which run the same calls on the threads of OpenMP, oneTBB and FastFlow, so that a program that already has one of these runtimes (e.g., SMS++, which depends on FastFlow) does not start a second one. On them parallel/Executor.h builds the loops, the reductions (whose blocks do not depend on the threads, so that a sum of doubles is the same on every executor) and the prefix sums in one pass over the memory (the decoupled look-back of Merrill and Garland), and the other headers of parallel/ the algorithms below, each with the results of its sequential version (bit for bit for the products of matrices, up to the rounding for the transform).

What	Header
executors: the pool of ADS, OpenMP, oneTBB, FastFlow	parallel/ThreadPool.h, parallel/OpenMPExecutor.h, parallel/TBBExecutor.h, parallel/FastFlowExecutor.h
parallel loops, reductions and prefix sums, fork and join	parallel/Executor.h
sort() and stableSort() by distribution (radix classifier for the numbers, tree of splitters with buckets of equality for the rest)	parallel/ParallelSort.h
multiwayMerge() by exact multisequence selection	parallel/ParallelMerge.h
products of CsrMatrix, SellMatrix and gemm()	parallel/ParallelNumeric.h
fft() by the four steps of Bailey	parallel/ParallelFFT.h
visit in breadth that optimizes its direction, connected components by Afforest	parallel/ParallelGraph.h
LCP array by the permuted LCP	parallel/ParallelText.h
union-find with no lock, for many threads	concurrent/ConcurrentUnionFind.h
sort over the processes of MPI by regular sampling	distributed/DistributedSort.h

#include "ADS/parallel/ParallelSort.h"
#include "ADS/parallel/ThreadPool.h"

ADS::ThreadPool pool( 8 );               // 8 threads, the caller included
ADS::sort( pool , A );                   // the result of ADS::sort( A )

The pool needs nothing but the threads of the standard library (with CMake, ADS::ADS links them). The other executors are compiled only when asked for: with CMake, -DADS_WITH_OPENMP=ON, -DADS_WITH_TBB=ON and -DADS_WITH_FASTFLOW=ON (all off by default) link OpenMP and oneTBB and take the headers of FastFlow from FASTFLOW_DIR or, if it is not given, from its repository, as SMS++ does; without CMake, -fopenmp, -DADS_WITH_TBB -ltbb and -DADS_WITH_FASTFLOW -I<fastflow>. The header of FastFlow defines NO_DEFAULT_MAPPING (unless ADS_FASTFLOW_MAPPING is defined), since FastFlow otherwise pins its threads to the first cores of the machine whatever the affinity of the process. The sort over the processes of MPI, ADS::distributed::sort(), is a layer of its own, on -DADS_WITH_MPI=ON (Open MPI or MPICH found by CMake), tested on 1 to 4 processes by ctest or by make test-mpi.

The benchmark of the parallel algorithms, bench/parallel.cpp, runs each of them on 1, 2, 4 and 8 threads. The competitors are the parallel versions of oneTBB, of std::execution (libstdc++ on oneTBB), of the parallel mode of libstdc++, of OpenMP, of ParlayLib, of IPS4o and IPS2Ra, of FastFlow (its ParallelFor, ParallelForReduce and ff_DC), of tlx, of Eigen and OpenBLAS, of FFTW and of the GAP benchmark suite; for the hash tables, the concurrent tables of oneTBB, libcuckoo and ParlayLib. Each structure runs in a process of its own, since the threads that a runtime keeps spinning between its calls would slow down the next structure. The benchmark was run twice on 8 cores of the Xeon Gold 5120 of the table above, with 5 runs per cell, while other programs ran on the remaining cores. Their use of the memory and of the third level of the cache was not under control, and the same code measured twice differs by 1.7% in the median cell and by 8.3% at the 90th percentile. The ratios below are those of 8 threads, the time of the library divided by that of the pool of ADS (the median, and the range over the cells in parentheses). The sorts of ADS are faster than IPS4o and IPS2Ra by 1.5 to 1.8 times in the median (0.8 to 15). They are faster than ParlayLib by 2.3 to 2.8 times, and than tbb::parallel_sort and std::sort on std::execution::par by 6 to 7 times. They lose on few cells: 16 sorted runs of $10^6$ integers, which the integer sort of ParlayLib sorts 1.3 times faster, few distinct strings and vectors already sorted, on which IPS4o is up to 1.3 times faster. On 2 threads the distribution costs more than the second thread saves (0.8 times the speed of the sequential sort in the median), and the sorts run the sequential one there. The parallel multiwayMerge() is 1.7 times faster than those of libstdc++ and tlx, and 7.4 times faster than its sequential version; gemm() is 1.2 times faster than Eigen on OpenMP and 7.3 times faster than on one thread. The connected components are 2.3 times faster than Afforest of the GAP benchmark suite, and the prefix sums 1.3 to 1.6 times faster than those of OpenMP, ParlayLib and oneTBB, since they read the input once. It is fair to remark, however, that FFTW with its threads is faster than the parallel fft() (by 8% on 8 threads, and by 1.4 to 1.6 times on 2 and 4, where the three transpositions of the four steps cost more than they save). Also, the visit in breadth of the GAP benchmark suite, which follows the same algorithm, is 4% faster than bfsDistances(), and the product of sparse matrices by rows of oneTBB is 7% faster than that of CsrMatrix. The tables of libcuckoo and ParlayLib (the latter open addressing on keys alone) find keys 2 and 5 times faster than ConcurrentCuckooTable on 8 threads, since its lookups do not scale as well; it inserts them 1.4 times faster than libcuckoo, in a single run of $10^6$ and $4 \cdot 10^6$ keys. The same algorithms on the executors of OpenMP and oneTBB run within a few percent of the pool. On the executor of FastFlow they are 4% to 70% slower on 8 threads, and up to twice as slow on 2, since its caller waits without working while its idle workers spin.

Design by contract

ADS follows the design by contract of B. Meyer: each operation checks its specification as a contract (Contract.h) of one of four kinds, i.e., ADS_PRE for the preconditions of the book, ADS_POST for the postconditions, ADS_INVARIANT for the invariant of a structure, and ADS_AUDIT for a condition that costs more than the operation (e.g., that a vector is sorted before a binary search, or that a write left the other items as they were). The macro ADS_CONTRACTS chooses which of them are evaluated (0 none, 1 the preconditions, which is the default, 2 also the postconditions, 3 also the invariants and the audits); with NDEBUG defined, as in a release build, the default is 0, as for assert. A violated contract throws ADS::contract_violation, a std::logic_error naming the condition, the function and the place. Tests are built at the level 3; furthermore, the axioms of each abstract data type are checked on all its realizations (contract_*.*-axioms), e.g., top( push( S , v ) ) = v and pop( push( S , v ) ) = S for a stack.

The standard interface

Beside the operations of the book, the containers have the interface of the standard library: begin() and end(), the usual member types, and iterators of the strongest category that the structure allows. Both ends have the same type, as the algorithms of C++17 and of Boost require. Hence, a range-for, the algorithms of <algorithm> and of std::ranges, and those of Boost.Range and Boost.Sort run on the containers of ADS as on those of the standard library. Where the items can change in place (the sequences, the deque, the arena) the iterators are mutable. A heap, an ordered set or a dictionary keeps an invariant on its items, and its iterators are constant, since the operations of the book are then the only safe way to change it. Several containers share the iterators of Iterators.h, and the tests in test/interop.cpp check the category of each iterator at compile time and run the algorithms of std (and of Boost, when it is installed) on each container against its operations.

Category	Containers
contiguous	ArraySequence (mutable), ArrayStack, DaryHeap, SortedArrayDictionary, the adjacent nodes of ArrayGraph
random access	ArrayQueue (on the circular vector), HeapPriorityQueue, Arena (mutable), the values of PreorderArrayTree, the nodes of ArrayGraph
bidirectional	List and Dequeue (mutable), UniqueQueue, ListPriorityQueue, TreePriorityQueue, the sets on a list, LinkedHashSet, BoolSet, the open-addressing tables, DirectTable, PointerTable, the search trees, AVLTree, Treap, SplayTree, ThreadedTree, BPlusTree, LinkedHeapPriorityQueue, the nodes and the adjacent nodes of ListGraph and MatrixGraph, the nodes of the cursor trees
forward	SinglyList and CursorList (mutable), LinkedQueue, SequenceStack, the stacks of MultiStack, BucketQueue, ChainedHashTable and the sets on it, HashMultiset, SkipList, Trie, RadixTree, BTree, FibonacciHeapPriorityQueue, the children and the preorder of Tree, the preorder and the symmetric order of BinaryTree, the children of CursorTree, the rows and the columns of SparseMatrix

A dictionary gives the pairs ( key , value ) and a priority queue the pairs ( priority , item ), in the order of the structure (i.e., the order of the keys in a search tree or a trie, of the places in a hash table, of the heap in a heap). In some containers the item is built on the fly (a pair of references, a key rebuilt along a trie, the number of a node). The iterator then models the concept of C++20, but it declares the category of an input iterator to the older algorithms, as the views of the standard library do; with these iterators one should use std::ranges::prev and the algorithms of std::ranges, not std::prev and those of <algorithm>.

Further reading

Besides the book, the headers cite the textbooks and the papers from which the structures and the algorithms beyond the book come; textbooks that cover much of the same ground are

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009;
• C. Demetrescu, I. Finocchi, G. F. Italiano, Algoritmi e strutture dati, 2nd ed., McGraw-Hill, 2008;
• R. Sedgewick, Algorithms in C++, Parts 1-4, 3rd ed., Addison-Wesley, 1998;
• A. V. Aho, J. E. Hopcroft, J. D. Ullman, Data Structures and Algorithms, Addison-Wesley, 1983;
• D. E. Knuth, The Art of Computer Programming, vol. 1 (3rd ed., 1997), vol. 2 (3rd ed., 1998), vol. 3 (2nd ed., 1998), vol. 4A (2011) and vol. 4B (2022), Addison-Wesley;
• P. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023;
• B. Meyer, Object-Oriented Software Construction, 2nd ed., Prentice Hall, 1997, for the design by contract;
• M. Cadoli, M. Lenzerini, P. Naggar, A. Schaerf, Fondamenti della progettazione dei programmi: principi, tecniche e loro applicazioni in C++, CittàStudi, 1997, for the specification of the abstract data types and their realization in C++.

Build and test

With CMake,

cmake -S . -B build
cmake --build build
ctest --test-dir build

or with the makefile, which builds and runs the same tests,

make test

A single exercise runs with ctest -R ch04.ex4.4, and a test program also runs one test by name (build/test/ch04 ex4.4) and lists its tests (-l).

The documentation is at dmeoli.github.io/ADS: a site of Sphinx with the theme of Read the Docs, whose pages come from this README and whose API reference Exhale and Breathe build from the comments of the headers, extracted by Doxygen. Locally, after pip install -r docs/requirements.txt, python3 docs/pages.py && sphinx-build -b html docs build-docs/html writes it to build-docs/html.

Use

cmake --install build --prefix <dir>     # or: make install PREFIX=<dir>

then, in another CMake project,

find_package(ADS REQUIRED)
target_link_libraries(<target> PRIVATE ADS::ADS)

or, with pkg-config, pkg-config --cflags ads. The packages of vcpkg (ads), conda-forge (cpp-ads), Homebrew, Debian and Ubuntu (libads-dev), Conan, Spack, Nix, the AUR, MSYS2 and xmake install the same files, from the recipes of packaging. Without installing anything, a CMake project can also take ADS at configure time, with FetchContent (CMake 3.24 or later),

include(FetchContent)
FetchContent_Declare(ADS
    URL https://github.com/dmeoli/ADS/releases/download/v0.1.0/ADS-0.1.0.tar.gz
    FIND_PACKAGE_ARGS 0.1)               # an installed ADS, if there is one
FetchContent_MakeAvailable(ADS)
target_link_libraries(<target> PRIVATE ADS::ADS)

or with CPM.cmake,

CPMAddPackage("gh:dmeoli/ADS@0.1.0")
target_link_libraries(<target> PRIVATE ADS::ADS)

and as a subproject ADS builds neither its tests nor its benchmarks. With Bazel, bazel_dep(name = "ads", version = "0.1.0") in MODULE.bazel and deps = ["@ads"], from the Bazel Central Registry; with Meson, meson wrap install ads and dependency('ads'), from WrapDB; in both, the targets compile in C++20.

BigInteger (and through it Rational) can run on the backend of GMP, which takes the products, the quotients, the conversions and the greatest common divisor in the ranges of lengths where GMP is the faster, and leaves the others to the code of ADS: with CMake, -DADS_WITH_GMP=ON (off by default, and an error at configure time if GMP is not found) defines ADS_WITH_GMP on ADS::ADS and links GMP, also for the projects that find the installed ADS; without CMake, -DADS_WITH_GMP and -lgmp, as make test ADS_WITH_GMP=1 [GMP=<prefix>] does. GMP is under the LGPL v3 (or the GPL v2), compatible with the LGPL v3 of ADS; without the macro nothing of GMP is included.

#include "ADS/sequence/List.h"

ADS::List< int > L{ 3 , 1 , 2 };
for( auto p = L.head() ; ! L.finished( p ) ; p = L.next( p ) )
 std::cout << L.read( p );               // the positions of the book
std::ranges::reverse( L );               // the algorithms of std
for( int x : L ) std::cout << x;

License

This software is released under the GNU Lesser General Public License version 3.0 (see the file LICENSE). The book is by Alberto Montresor, under CC BY-NC 4.0.