ADS — A User Manual¶
Donato Meoli Dipartimento di Informatica, Università di Pisa
Version 0.1 — for ADS 0.1.0 (November 2026)
Abstract¶
ADS is a header-only C++20 library of algorithms and data structures. It contains the structures of the textbooks (sequences, stacks, queues, dictionaries, search trees, priority queues, sets, graphs), each one in the form in which the textbook presents it, and beside them the engineered variants of the literature on algorithm engineering (cache-conscious, succinct, compressed, external-memory, concurrent and parallel), written to be compared with the best implementations available. Each structure is specified by the abstract data type it realizes, as a C++20 concept, and checks its preconditions, postconditions and invariants through contracts whose cost is chosen at compile time.
This manual describes the library area by area. For each structure it gives the definitions and the invariants, figures of its state in memory before and after the operations, the pseudocode of the operations (the same that the comments of the headers carry), the analysis of their costs with its proofs, the declarations of the members that a user calls with short examples of their use, and exercises, each one solved by a test of the library. It is a companion to the API reference generated from the headers, not a replacement for it.
License¶
ADS is distributed under the Boost Software License, version 1.0 (BSL-1.0); this manual is distributed under the same terms.
Conventions¶
- Class and function names are typeset in
monospace, e.g.,ArrayStack,push( v ); the names of the operations of an abstract data type are written as in the pseudocode, e.g., \(\mathrm{push}( v )\). - File-path and source-tree references are typeset in
monospacetoo, e.g.,ADS/stack/ArrayStack.h, relative toinclude/. - Abstract data types are written in capitals, e.g., STACK,
DICTIONARY, as in the textbooks; the C++20 concept that formalizes each
of them is in
ADS/ADT.h. - Pseudocode uses the conventions of the comments of the headers, from which it is extracted: numbered lines, \(\gets\) for the assignment, bold keywords, \(\triangleright\) for a comment.
- Costs are in the worst case unless they are said to be amortized or expected; \(n\) is the number of items of the structure at hand.
- Exercises end each chapter; each one names the test of the library
that solves it, which can be run with
ctest -R <name>. - Status admonitions flag the maturity of a feature explicitly.
Four forms appear in the text:
- Status — mature. The feature is stable, tested, in
mainand in tagged releases. Implicit unless stated. - Status — beta. The feature is in
mainbut its interface or semantics may change in incompatible ways. - Status — under development. The feature is partly present but is actively being reworked; the manual describes both what exists today and the direction of the intended revision.
- Status — planned. The feature is documented as intended but is not yet released. The manual indicates explicitly that it cannot be used today.
- Status — mature. The feature is stable, tested, in
When in doubt about a claim made in this manual, the authoritative sources are, in order of decreasing specificity: the headers of the library; the API reference generated from them; this manual.
Table of contents (high-level)¶
- Part I — Foundations.
- Part II — Searching and ordering.
- Chapter 6. Searching.
- Chapter 7. Hashing and dictionaries.
- Chapter 8. Trees.
- Chapter 9. Priority queues.
- Chapter 10. Sets and filters.
- Chapter 11. Disjoint sets.
- Chapter 12. Sorting.
- Part III — Algorithms.
- Chapter 13. Algorithm design.
- Chapter 14. Graphs.
- Chapter 15. Strings.
- Chapter 16. Geometry.
- Chapter 17. Numerical algorithms.
- Chapter 18. Combinatorial generation.
- Chapter 19. Backtracking.
- Chapter 20. Complexity and intractable problems.
- Part IV — Engineering.
- Chapter 21. Compression.
- Chapter 22. Succinct structures.
- Chapter 23. External memory.
- Chapter 24. Concurrency.
- Chapter 25. Parallelism.
- Chapter 26. Distributed computing.
- Appendices.
- Appendix A. Writing a new structure.
- Appendix B. The benchmarks.
- Appendix C. Working with other libraries.
Glossary and bibliography follow.