How to zero out array in O(1)?

Question

Is there an way to zero out an array in with time complexsity O(1)? It's obvious that this can be done by for-loop, memset. But their time complexity are not O(1).

Answer 1

It is impossible at runtime to zero out an array in O(1). This is intuitive given that there is no language mechanism which allows the value setting of arbitrary size blocks of memory in fixed time. The closest you can do is:

int blah[100] = {0};

That will allow the initialisation to happen at compiletime. At runtime, memset is generally the fastest but would be O(N). However, there are problems associated with using memset on particular array types.

Answer 2

It's clearly not possible to initialize an arbitrarily sized array in a fixed length of time. However, it is entirely possible to create an array-like ADT which amortizes the cost of initializing the array across its use. The usual construction for this takes upwards of 3x the storage, however. To whit:

template <typename T, size_t arr_size>
class NoInitArray
{
    std::vector<T> storage;

    // Note that 'lookup' and 'check' are not initialized, and may contain
    // arbitrary garbage.
    size_t lookup[arr_size];
    size_t check[arr_size];
public:
    T& operator[](size_t pos)
    {
        // find out where we actually stored the entry for (*this)[pos].
        // This could be garbage.
        size_t storage_loc=lookup[pos];

        // Check to see that the storage_loc we found is valid
        if (storage_loc < storage.size() && check[storage_loc] == pos)
        {
            // everything checks, return the reference.
            return storage[storage_loc];
        }
        else
        {
            // storage hasn't yet been allocated/initialized for (*this)[pos].
            // allocate storage:
            storage_loc=storage.size();
            storage.push_back(T());

            // put entries in lookup and check so we can find 
            // the proper spot later:
            lookup[pos]=storage_loc;
            check[storage_loc]=pos;

            // everything's set up, return appropriate reference:
            return storage.back();
        }
    }
};

One could add a clear() member to empty the contents of such an array fairly easily if T is some type that doesn't require destruction, at least in concept.