File DirectTable.h

↰ Parent directory (ADS/dictionary)

The table with direct access of chapter 7: when the keys are the integers in an interval [ a , b ] of size m, the function H( k ) = k - a is injective, a perfect hash, and the DICTIONARY [see File ADT.h] is a vector of size m, every operation in O( 1 ) time.

Definition (ADS/dictionary/DirectTable.h)

Detailed Description

The contracts [see File Contract.h]: a <= b with b - a + 1 places that fit in a std::size_t, and every key in [ a , b ], checked without overflow for any long; the invariant is that size() counts the places that are not empty. The operations are defined in DirectTable.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, chapter 7, https://algoritmicamente.it/materiali/libro/capitoli/cap07.pdf

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes