View on GitHub


Initialize and fill an array in O(1) time and space.

Welcome to the Farray Website!

Farray stands for Fillable Array - an array with the fill(v) method,
which sets all the values in the array to v, in O(1) worst-time.
Our implementation uses only 1 extra bit of memory, which is a state-of-the-art result.

This project is an implementation of the In-Place Initializable Arrays paper, written by Takashi Katoh & Keisuke Goto.
The paper is based on the simpler Initializing an array in constant time - which uses 2n extra memory words.

Both are explained in the Medium article I published about the subject and of course, in this website.

We chose C++ for its templates and easy manipulation of memory,
and header-only to make it simple for existing projects to include it.

The Website features:

The project is massively random-tested, by the .cpp test files in the tests folder.