File DictionarySet.h

↰ Parent directory (ADS/set)

The SET on any DICTIONARY with a foreach (sections 8.4 and 8.5): ChainedHashSet and OpenHashSet on the hash tables, contains(), insert() and remove() in O( 1 ) expected time and forEach() in O( m + n ) and O( m ), m the size of the table; TreeSet on a Red-Black tree, the three in O( log n ) and forEach() in O( n ), in order.

Definition (ADS/set/DictionarySet.h)

• Program Listing for File DictionarySet.h

Detailed Description

Their operations are the generic ones [see File SetOperations.h].

The contracts [see File Contract.h]: after insert() the item is there and after remove() it is not; the dictionary keeps its own invariant. The operations are defined in DictionarySet.tpp.

1. Montresor, Algoritmi e Strutture Dati, 2025, sections 8.4 and 8.5, https://algoritmicamente.it/materiali/libro/capitoli/cap08.pdf

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

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

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

• ADS/dictionary/ChainedHashTable.h (File ChainedHashTable.h)

• ADS/dictionary/OpenHashTable.h (File OpenHashTable.h)

• ADS/set/SetOperations.h (File SetOperations.h)

• ADS/set/impl/DictionarySet.tpp

• ADS/tree/SearchTree.h (File SearchTree.h)

• algorithm (File AkraBazzi.h)

• concepts

• cstddef

• functional

• optional

• ranges

• stdexcept

• utility

• vector

Namespaces

• Namespace ADS

Classes

• Template Class DictionarySet

Typedefs

• Typedef ADS::ChainedHashSet

• Typedef ADS::OpenHashSet

• Typedef ADS::TreeSet