Is it possible to delete the first element of an array without shifting all elements later?

My guess is that I can remember the index of the 'current first element', like so:

uint[] public myArray;
uint firstElement;
myArray.push(3);
myArray.push(6);
myArray.push(10);
delete myArray[firstElement];
firstElement++;

but, is there a convention or something built in for this?

There is nothing built in for doing this, what you have is probably the most efficient way currently.

From what you're describing though, it sounds like you want a queue. If you're okay with not using an array and using a mapping instead, this will be more efficient after the Constantinople fork due to EIP-1283 net gas metering if you ever have to enqueue and dequeue in the same call frame.

struct Queue {
    uint128 start;
    uint128 end;
    mapping(uint128 => uint256) items;
}

Queue private myQueue;


function enqueue(Queue storage queue, uint256 item) internal {
    queue.items[queue.end++] = item;
}

function dequeue(Queue storage queue) internal returns (uint256) {
    uint256 item = queue.items[queue.start];
    queue.items[queue.start++] = 0;
    return item;
}

Question from @smarx in comment: Could you explain why a mapping would save on gas versus an array after EIP-1283 when doing an enqueue and dequeue in the same transaction? It seems to me that, if anything, an array would be better because after an enqueue and dequeue, the length would remain the same. With the above implementation using a mapping, both start and end would be incremented. (This could be changed by using a length instead of an end, but that makes solo dequeue operations more expensive instead.)

If you implement a queue with an array, you either have to move all elements down 1 when you dequeue, or you have to have an ever increasing length (you can't decrease the length when you remove the 0 index since then you don't know where to insert new elements) with an increasing start point. The former is obviously out of the question due to that requiring a ton of storage updates. The latter requires the following on different interactions (this is after EIP-1283 is active)

Enqueue: 1 new storage slot, 1 update to length = ~25000 gas

Dequeue: 1 removed storage slot, 1 update to length, 1 update to start = ~0 gas

Both in one call frame: 1 new storage slot, 1 removed storage slot, 1 update to length, 1 update to start = ~20000 gas

My approach of using a mapping (the savings is really from having the start/end as two uint128s instead of how an array would have length+start) requires the following (again, after EIP-1283 is active)

Enqueue: 1 new storage slot, 1 update to end = ~25000 gas

Dequeue: 1 removed storage slot, 1 update to start/end (these are now the same slot) = ~-5000 gas

Both in one call frame: 1 new storage slot, 1 removed storage slot, 1 update to start/end = ~15000 gas

  • 1
    Could you explain why a mapping would save on gas versus an array after EIP-1283 when doing an enqueue and dequeue in the same transaction? It seems to me that, if anything, an array would be better because after an enqueue and dequeue, the length would remain the same. With the above implementation using a mapping, both start and end would be incremented. (This could be changed by using a length instead of an end, but that makes solo dequeue operations more expensive instead.) – smarx Dec 6 at 16:11
  • @smarx see my edit. I didn't mean mapping approach was better after 1283 than array approach before 1283, I meant mapping approach is always better than array. Both are of course better after 1283. – flygoing Dec 6 at 16:43
  • 1
    Oh, I think I understand. The gas savings is from using 128-bit numbers and combining them into one slot. – smarx Dec 6 at 17:45
  • 1
    I had missed that in your code originally. – smarx Dec 6 at 17:46
  • Of course if you're really confident you can just use an array and use solidity assembly to sidestep the length altogether, even cheaper, but it'd be pretty unreadable to the average dev – flygoing Dec 6 at 17:55

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.