File SortedArrayDictionary.h

↰ Parent directory (ADS/dictionary)

A DICTIONARY [see File ADT.h] realized with a vector of the pairs ( key , value ) sorted by key, beyond the book: lookup() is the binary search of section 1.2 [see File BinarySearch.h], in O( log n ) time, while insert() and remove() move the pairs after the place of the key, in O( n ).

Definition (ADS/dictionary/SortedArrayDictionary.h)

Detailed Description

It is the realization to prefer when the lookups far outnumber the changes, and it also gives the keys in order, and the range of keys between two values, at no further cost.

The contracts [see File Contract.h]: insert() ensures that k has the value v, remove() that k is not there; the invariant is that the keys are strictly increasing. The operations are defined in SortedArrayDictionary.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, sections 1.2 and 3.2.3, https://algoritmicamente.it/materiali/libro/capitoli/cap01.pdf

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

  • ADS/Contract.h (File Contract.h)

  • ADS/dictionary/impl/SortedArrayDictionary.tpp

  • concepts

  • cstddef

  • optional

  • utility

  • vector

Namespaces

Classes