File ListMFSet.h

↰ Parent directory (ADS/mfset)

The MFSET on lists of section 10.2.1 [see File MFSet.h], each element knowing the head of its list: find() in O( 1 ), merge() relabels the shorter list, so that an element is relabeled at most :math:` log_2 n ` times.

Definition (ADS/mfset/ListMFSet.h)

Detailed Description

The contracts [see File Contract.h]: the elements are in [ 0 , n ), and after merge() x and y have the same head; the invariant is that each element is once in the list of its head. The operations are defined in ListMFSet.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 10.2.1, https://algoritmicamente.it/materiali/libro/capitoli/cap10.pdf

    1. Hopcroft, J. D. Ullman, Set merging algorithms, SIAM Journal on Computing 2(4), 294-303, 1973, doi:10.1137/0202024

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

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

  • ADS/mfset/impl/ListMFSet.tpp

  • stdexcept

  • utility

  • vector

Namespaces

Classes