Ever wondered how to reset an entire array of N elements in a constant slice of time? This post will introduce the algorithm along with an implementation.

Let me lay out the problem. There’s an array of N integers. We would like to be able to reset that array (set all elements to zero), in a set amount of time – regardless of the value of N. The reset operation should take the same amount of time whether it operates on 100 elements or 10,000 of them.

Like many other algorithms and data structures in computer science, we will require a little more allocated memory (3 times more, to be exact. Still O(N) space) to make such unreasonable request actually feasible. The first piece of memory is going to be our data section and hold all N elements. The other two arrays will be called “forward” and “backward” and will be used to check if a certain index is in use or not. Here’s a sketch of the setup, along with a detailed algorithm:

Needed data structures to allow O(1) reset of an array.

For every added element in index id, we are going to do the following (“used” is the number of elements in use since last reset):

• forward[id] = used
• backward[used] = id
• used++

Analyzing this algorithm we can verify that: index id is in use IFF (if and only if) 0 <= forward[id] && forward[id] < used && backward[forward[id]] == id. This is because we know that all the elements in “backward” with indices 0 to used-1 have been set by us since the last reset.

Consequently, all we need to do in a reset operation is set the “used” variable to zero.

Here’s a proper implementation of an integer array, just as an example:

// --- array.hpp ---

#include <stdexcept>
#include <boost/shared_array.hpp>

class Array {
    public:
        explicit Array (unsigned size);

        // All operations are done in constant O(1) time.
        void reset ();
        int  get   (unsigned id) const;
        void set   (unsigned id, int i);

    protected:
        bool used  (unsigned id) const;
        bool check (unsigned id) const throw(std::out_of_range);

        unsigned size_, used_;
        boost::shared_array<int> arr_;
        boost::shared_array<unsigned> forward_, backward_;

    private:
        // no implementation for these:
        Array (const Array &arr);
        Array &operator= (const Array &arr);
};

// --- array.cc ---

template <typename T>
boost::shared_array<T> make_shared_arr (size_t size) {
    // this is crucial for exception safety.
    // see: http://www.gotw.ca/gotw/056.htm
    return boost::shared_array<T>(new T[size]);
}

Array::Array (unsigned size)
 : size_(size), used_(0), arr_(make_shared_arr<int>(size)),
   forward_(make_shared_arr<unsigned>(size)),
   backward_(make_shared_arr<unsigned>(size)) { }

void Array::reset () {
    used_ = 0;
}

int Array::get (unsigned id) const {
    if (check(id) && used(id))
        return arr_[id];
    return 0;
}

void Array::set (unsigned id, int i) {
    if (check(id) && !used(id) && ++used_)
        forward_[backward_[used_-1] = id] = used_-1;
    arr_[id] = i;
}

bool Array::used (unsigned id) const {
    if (forward_[id] >= used_)
        return false;
    return backward_[forward_[id]] == id;
}

bool Array::check (unsigned id) const throw(std::out_of_range) {
    if (id >= size_)
        throw std::out_of_range("Index too big!");
    return true;
}

// --- main.cc ---

#include <iostream>

int main () {
    Array a(3);
    a.set(2,1);
    std::cout << a.get(2) << std::endl;
    a.reset();
    std::cout << a.get(2) << std::endl;
    return a.get(1);
}

You will have to forgive me for the somewhat obscure implementation of the set() method. I was going for a minimal number of implementation lines – all in the spirit of Spartan Programming.