  The choice dictionary is introduced as a data structure that can be
initialized with a parameter $n\in\mathbb{N}=\{1,2,\ldots\}$ and subsequently
maintains an initially empty subset $S$ of $\{1,\ldots,n\}$ under insertion,
deletion, membership queries and an operation choice that returns an arbitrary
element of $S$. The choice dictionary appears to be fundamental in
space-efficient computing. We show that there is a choice dictionary that can
be initialized with $n$ and an additional parameter $t\in\mathbb{N}$ and
subsequently occupies $n+O(n(t/w)^t+\log n)$ bits of memory and executes each
of the four operations insert, delete, contains (i.e., a membership query) and
choice in $O(t)$ time on a word RAM with a word length of $w=\Omega(\log n)$
bits. In particular, with $w=\Theta(\log n)$, we can support insert, delete,
contains and choice in constant time using $n+O(n/(\log n)^t)$ bits for
arbitrary fixed $t$. We extend our results to maintaining several pairwise
disjoint subsets of $\{1,\ldots,n\}$.
  We study additional space-efficient data structures for subsets $S$ of
$\{1,\ldots,n\}$, including one that supports only insertion and an operation
extract-choice that returns and deletes an arbitrary element of $S$. All our
main data structures can be initialized in constant time and support efficient
iteration over the set $S$, and we can allow changes to $S$ while an iteration
over $S$ is in progress. We use these abilities crucially in designing the most
space-efficient algorithms known for solving a number of graph and other
combinatorial problems in linear time. In particular, given an undirected graph
$G$ with $n$ vertices and $m$ edges, we can output a spanning forest of $G$ in
$O(n+m)$ time with at most $(1+\epsilon)n$ bits of working memory for arbitrary
fixed $\epsilon>0$.
