File SetOperations.h

↰ Parent directory (ADS/set)

The operations of chapter 8 on any SET that can be copied and has the foreach, forEach( f ): the union copies A and inserts the items of B, the intersection copies the smaller set and removes its items not in the other one, the difference copies A and removes its items in B, the symmetric difference adds to A - B the items of B not in A.

Definition (ADS/set/SetOperations.h)

Detailed Description

On the hash tables, with n_X keys in a table of size m_X, they take :math:` O( max( m_A , n_A ) + max( m_B , n_B ) ) ` expected time (exercise 8.6), on the Red-Black trees :math:` O( n + m log( n + m ) ) ` (exercise 8.7). The realizations that do better have their own [see File BoolSet.h, File ListSet.h and File SortedListSet.h].

The contracts [see File Contract.h]: the result of each operation holds, item by item, what its name says, an audit [see detail::isSetOperation()]. The operations are defined in SetOperations.tpp.

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

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Functions