File SmallVector.h

↰ Parent directory (ADS/sequence)

A vector with room for N items inside itself, beyond the book: the vector that doubles of section 4.2 [see File ArraySequence.h] whose first N items need no memory of the allocator, so that the many short vectors of a structure (the children of a node, the arcs of a vertex, the items of a bucket) cost no allocation each and lie next to the object that holds them, at the price of N items of room in every vector.

Definition (ADS/sequence/SmallVector.h)

Detailed Description

Past N items the vector moves to the allocator and doubles there, as std::vector does: n pushes cost fewer than 2 n moves of items, and the space is at most 2 n + N items.

A move takes the memory of the other vector in O( 1 ) time when its items are on the allocator, and moves the items one by one, at most N, when they are inside it; the vector moved from is left empty.

The contracts [see File Contract.h]: an index is below size(), and front(), back() and pop_back() need a vector that is not empty; the invariant is :math:` size leq capacity ` and :math:` capacity geq N `. The operations are defined in SmallVector.tpp.

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

    1. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009, section 17.4 (dynamic tables)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes