File ADT.h

↰ Parent directory (ADS)

The abstract data types of the book, as C++20 concepts: SEQUENCE, SET and DICTIONARY (chapter 3), STACK and QUEUE (chapter 4).

Definition (ADS/ADT.h)

Detailed Description

A specification of an abstract data type is a triple ( D , F , A ): D is a set of domains, one of which is the designated domain (the type being defined, e.g., the stacks) and the others are the auxiliary ones (e.g., the items and the booleans); F is a set of operations on D; A is a set of axioms, i.e., the semantics of F. The pair ( D , F ) is the syntactic specification, which a concept states as the names of the operations and their domains. The semantic one may be given in two ways: (i) algebraic, i.e., by equations among the operations, those that observe or remove defined on those that construct (e.g., top( push( S , v ) ) = v below); (ii) constructive, i.e., by the preconditions and the postconditions of each operation, expressed in terms of a type already known (e.g., the sequences of items). The library follows (ii) in the code, through the ADS_PRE and ADS_POST of File Contract.h, and states (i) here; the tests check both on every realization. The operations are of four kinds: constructors, which make a value of the type (create(), insert(), push()); modifiers, which change it; observers, which return a property of it (empty(), top(), read()); iterators, which visit its items (the positions of a SEQUENCE, the forEach() of the sets).

A realization meets the requirement of abstraction, i.e., a program that uses the type does not depend on how it is realized, and the one of protection, i.e., only the operations of the type act on it: hence each realization is a class whose data are private, and a realization can replace another one under the same concept.

The names are those of the book, so that the pseudocode reads the same in the code: a SEQUENCE has empty(), finished(), head(), tail(), next(), prev(), insert(), remove(), read() and write(), a position of the type Pos. As in the book,

  • the positions :math:` pos_{-1} ` and :math:` pos_n ` come before the first and after the last element of a sequence :math:` s_0 , ldots , s_{n-1} `, and finished( p ) is true exactly on them;

  • insert( p , v ) with :math:` p = pos_i ` puts v at index i, the old elements from index i moving one place on, and returns the position of the new element; remove( p ) with :math:` p = pos_i ` removes the element at index i and returns the position of the new element at index i;

  • a precondition that costs a scan of the sequence (e.g., that p is a position of a list, which the book does not check in the realizations with pointers) is an audit of File Contract.h, checked only at its level 3.

  1. Montresor, Algoritmi e Strutture Dati, 2025, sections 3.2 and 4.3.1, https://algoritmicamente.it/materiali/libro/capitoli/cap03.pdf and https://algoritmicamente.it/materiali/libro/capitoli/cap04.pdf

  2. Liskov, S. Zilles, Programming with abstract data types, ACM SIGPLAN Notices 9(4), 50-59, 1974

    1. Parnas, On the criteria to be used in decomposing systems into modules, Communications of the ACM 15(12), 1053-1058, 1972

    1. Guttag, J. J. Horning, The algebraic specification of abstract data types, Acta Informatica 10(1), 27-52, 1978

  1. Cadoli, M. Lenzerini, P. Naggar, A. Schaerf, Fondamenti della progettazione dei programmi: principi, tecniche e loro applicazioni in C++, CittaStudi, 1997

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

  • concepts

  • cstddef

  • optional

Included By

Namespaces