Costs

Leaving out a tag you need makes the program slower by a complexity class: what these guarantee is how much work or memory an operation takes.

They are guarantees like any other, kept by the container and checked by measurement (Benchmarks). What every operation of every representation costs is in the complexity tables of each kind.

Question

Tags

Kinds

How is it cleared?

proportional_clear, constant_clear

set, map, multiset, sequence, queue, pool, slots, partition

What happens to freed memory?

retains, reclaims

set, map, multiset, sequence, queue, pool, slots, partition

Rows share structure?

structural_sharing

set, map, multiset, sequence, queue, pool, slots, partition

Complexity requirements as part of an interface, as the C++ standard library states them (Stepanov and Lee, 1995).

How is it cleared?

Category any_clear, which promises nothing: a request that leaves the question open gets it. Asked of: set, map, multiset, sequence, queue, pool, slots, partition.

digraph any_clear { rankdir=LR; node [fontname=sans, fontsize=10]; edge [fontname=sans, fontsize=9]; any_clear [shape=plaintext, fontcolor=gray40, label="any_clear\n(promises nothing)"]; any_clear -> proportional_clear; proportional_clear -> constant_clear; }

clear costs O(elements present), or O(1).

proportional_clear

Clear takes time in proportion to the elements present.

  • Role: a guarantee: the container keeps it.

  • In plain words: cheap clear, cleared often.

  • Instead of: constant_clear (one answer per question).

  • Shortest served request: Store<set<Id>, dense, proportional_clear>.

constant_clear

Clear takes constant time, as with a generation counter.

  • Role: a guarantee: the container keeps it.

  • In plain words: reset every round, cleared per search, O(1) clear.

  • Promises at least: proportional_clear.

  • Shortest served request: Store<set<Id>, dense, constant_clear>.

What happens to freed memory?

Category any_memory, which promises nothing: a request that leaves the question open gets it. Asked of: set, map, multiset, sequence, queue, pool, slots, partition.

digraph any_memory { rankdir=LR; node [fontname=sans, fontsize=10]; edge [fontname=sans, fontsize=9]; any_memory [shape=plaintext, fontcolor=gray40, label="any_memory\n(promises nothing)"]; any_memory -> retains; any_memory -> reclaims; }

Storage freed by erase and clear is kept for reuse, or returned.

retains

Storage freed by erase and clear is kept for reuse.

  • Role: a guarantee: the container keeps it.

  • In plain words: no reallocation when refilled, reuse memory, keeps capacity.

  • Instead of: reclaims (one answer per question).

  • Shortest served request: Store<set<Id>, retains>.

reclaims

Erase and clear return the storage of what they remove.

  • Role: a guarantee: the container keeps it.

  • In plain words: frees memory, shrinks, gives memory back.

  • Instead of: retains (one answer per question).

  • Shortest served request: Store<set<Id>, reclaims>.

Rows share structure?

Category any_sharing, which promises nothing: a request that leaves the question open gets it. Asked of: set, map, multiset, sequence, queue, pool, slots, partition.

digraph any_sharing { rankdir=LR; node [fontname=sans, fontsize=10]; edge [fontname=sans, fontsize=9]; any_sharing [shape=plaintext, fontcolor=gray40, label="any_sharing\n(promises nothing)"]; any_sharing -> structural_sharing; }

Equal parts of different rows are stored once (tree pools).

structural_sharing

Parts that are equal across rows are stored once.

  • Role: a guarantee: the container keeps it.

  • In plain words: rows differing in a few places, persistent, shared structure.

  • Shortest served request: Store<pool<Store<set<int>, unique, dense, stable_refs, frozen>>, structural_sharing>.