Welcome to the Farray Website!
Farray stands for Fillable Array - an array with the
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:
- Short Despription of the paper and implementation
- Advanced Features
- Project Structure
- Time and Space Analysis
The project is massively random-tested, by the .cpp test files in the tests folder.