Should I be shifting array elements as I remove them?

Question

I'm storing pending operations in a data structure similar to the multisig. wallet contract, i.e.

struct PendingState {
        uint yetNeeded;
        uint ownersDone;
        uint index;
    }

and my contract pseudo-ish code:

contract c {
    mapping(bytes32 => PendingState) m_pending;
    bytes32[] m_pendingIndex;

    // initialize operation:
    var pending = m_pending[_h];
    pending.yetNeeded = bla;
    pending.ownersDone = bla;
    pending.index = m_pendingIndex.length++;
    m_pendingIndex[pending.index] = _h;

    // remove the current operation when finished
    delete m_pendingIndex[m_pending[_h].index];
    delete m_pending[_h];
}

However, if there were three (index = 0, 1, 2) pending operations when we completed -and removed- the second one, then we end up m_pendingIndex[0] and m_pendingIndex[2] populated and m_pendingIndex[1] empty. Will this increase the required gas for later operations? Should I shift the objects back until there is no empty spot? I imagine this process will have a cost itself, but it might be preferable in order to prevent DOS attacks.

Thanks for any help,

Answer 1

These lines

delete m_pendingIndex[m_pending[_h].index];
delete m_pending[_h];

don't do what you probably think they do. Suffice it to say that you can't remove information from an immutable blockchain.

As Edmund said, linked lists. There is a way to efficiently remove an item from an unordered array (so it doesn't grow without limit) and to do so with a bounded gas cost; so the delete op is the same cost at any scale. In summary:

I've been using combination of mappings with pointers to array rows to enable a logical delete from arrays and a number of other benefits. Works in a lot of situations:

More complete description: https://medium.com/@robhitchens/solidity-crud-part-1-824ffa69509a#.c3e5nom01

Possible the pattern can help in this situation.

Answer 2

If you have to shift everything up then you'll have a potentially unbounded gas cost, which is generally something you want to avoid, unless you know that there's a practical limit. But if you don't remove the items then you'll instead have a potentially endlessly growing cost if you need to loop through the data instead, as you'll need to read all the missing entries and discover that they're not there.

The solution is often to use a linked list (or sometimes a double linked list) instead of an array, along with a variable telling you which item is the first in the list. That way you can remove items from the list with a predictable, bounded gas cost regardless of the number of items in the list.

Answer 3

I’d recommend first to swap the index you want to delete and the last index, and then just use ‘pop()’.