Skip to content

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 monospace too, e.g., ADS/stack/ArrayStack.h, relative to include/.
  • 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 main and in tagged releases. Implicit unless stated.
    • Status — beta. The feature is in main but 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.

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)

Glossary and bibliography follow.