File SortedListSet.h

↰ Parent directory (ADS/set)

The SET as a sorted LIST of section 8.3: insert() in O( n ), min() and max() in O( 1 ), the operations by merging the two lists in O( n + m ), optimal since merging needs :math:` Omega( n + m ) ` (exercises 8.3 and 8.4).

Definition (ADS/set/SortedListSet.h)

Detailed Description

The merges append to the end of the result, the place :math:` pos_n ` = next( tail() ) of a LIST: the C.insert( C.tail() , x ) of the book, with the insert() of section 4.1 that puts x before the item in the given position, would put x before the last item.

The contracts [see File Contract.h]: insertLast() needs an item larger than the others, after insert() the item is there and after remove() it is not, and each operation of two sets gives what its name says; the invariant is that the list increases strictly. The operations are defined in SortedListSet.tpp.

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

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes

Functions