  A choice dictionary is a data structure that can be initialized with a
parameter $n\in\{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 is fundamental in space-efficient computing and has numerous
applications. The best previous choice dictionary can be initialized with $n$
and a second parameter $t\in\{1,2,\ldots\}$ in constant time and subsequently
executes all operations in $O(t)$ time and occupies $n+O(n({t/w})^t+\log n)$
bits on a word RAM with a word length of $w=\Omega(\log n)$ bits. We describe a
new choice dictionary that, following a constant-time initialization, executes
all operations in constant time and, in addition to the space needed to store
$n$, occupies only $n+1$ bits, which is shown to be optimal if $w=o(n)$.
Allowed $\lceil\log_2(n+1)\rceil$ bits of additional space, the new data
structure also supports iteration over the set $S$ in constant time per
element.
