File List.h

↰ Parent directory (ADS/sequence)

The LIST of the book: a SEQUENCE [see File ADT.h] realized as a bidirectional circular list of cells with a sentinel.

Definition (ADS/sequence/List.h)

Detailed Description

A list of n items has n + 1 cells, the sentinel holding no item; the position :math:` pos_i ` is the address of the cell of the item of index i, for :math:` 0 leq i < n , while :math: pos_{-1} ` and :math:` pos_n ` are both the address of the sentinel, which is therefore what finished() looks for. Every operation takes O( 1 ) time, the list :math:` Theta( n ) ` space.

The sentinel is a member of the list rather than a cell of the heap, so that moving a list relinks its first and last cells to the new sentinel in O( 1 ) time and allocates nothing: the list moved from is left empty, and still usable. Copying a list copies its cells (the rule of five, with the copy and swap idiom for the assignment). Beyond the book, the cells come from an ObjectPool [see File ObjectPool.h] of the list, which takes back the cell of remove() for the next insert(): a cell costs no call to the allocator, the cells made one after another are next to each other in memory, and a list of items with a trivial destructor dies a block at a time; the price is that the list keeps the memory of its largest size until it dies, and that a move takes the pool along with the cells. A pool is no gain for a list of a few cells, which still takes a block per cell and a header per block: a structure of many short lists (the chains of ChainedHashTable) takes List< T , false >, whose cells come one by one from new and delete.

The contracts [see File Contract.h]: a position is a cell of this list, which costs a scan of the list and is therefore an audit, checked by the operations that change the list (insert(), remove() and write()) but not by next(), prev() and read(), where it would make every scan quadratic; read(), write() and remove() need a position that holds an item, i.e., not the sentinel; insert() and write() ensure that v is read back in its position. The invariant is that each cell is the predecessor of its successor, which also makes the walk from the sentinel come back to it. The operations are defined in List.tpp.

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

  2. Stroustrup, The C++ Programming Language, 4th ed., Addison-Wesley, 2013, section 17.5 (copy and move)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes