Efficient approach to delete element from array in Solidity

Question

For each user, I want to keep an array of holded assets (each asset has an ID).

My solution up until now is :

struct User {
        uint userId;
        uint[] assets;
    }

For every asset the user holds I push to the user's array the ID of the asset.

I want to give the user an option to delete an asset.

What would be the most efficient approach to this?

Allocating all of the available assets for every user (would be very wasterful given you have a lot of assets available) VS. iterating over all of his assets everytime he'd like to delete an asset, finding it in the array, then deleting it from it and shifting all of the array accordingly - also, the code for this is kinda hideous :

function deleteAsset(uint assetId) external returns(uint) {
        bool assetFound = false;
        // Check if the asset found is the last asset (or we go out of boundaries)
        if (allUsers[msg.sender].assets[allUsers[msg.sender].assets.length - 1] == assetId){
            assetFound = true;
        }

        else{
            // Iterate over all user assets and find its index
            for (uint i = 0; i < allUsers[msg.sender].assets.length - 1; i++) {
                if (!assetFound && allUsers[msg.sender].assets[i] == assetId)
                    assetFound = true;

                if(assetFound)
                    allUsers[msg.sender].assets[i] = allUsers[msg.sender].assets[i + 1];
            }
        }

        if (assetFound){
            delete allUsers[msg.sender].assets[allUsers[msg.sender].assets.length - 1];
            allUsers[msg.sender].assets.length--;
        }
    }

Would be a lot easier if I could save a mapping for each user indicating what asset does he have, but you can't return a mapping from a function and I don't know the benchmarks of view functions and "brute-forcing" all of the assets available for each user can take a plenty of time I assume.

Heres a method to delete an array element at a given index https://ethereum.stackexchange.com/questions/1527/how-to-delete-an-element-at-a-certain-index-in-an-array — Karan Kurbur, Jan 11 '18 at 02:05
Possible duplicate of How to delete an element at a certain index in an array? — Ismael, Jan 11 '18 at 03:11
I'm aware of these threads, I also presented their method. Though my situation is a bit different and I'm asking about efficiency. — Random, Jan 11 '18 at 07:35
The title should be something like: Efficient approach to delete element in Solidity dynamically sized array — Roman Frolov, Jan 11 '18 at 17:50

William Entriken · Answer 1 · 2021-02-04T21:02:29.577

13

Source: https://github.com/su-squares/ethereum-contract/blob/master/contracts/SuNFT.sol

Here you go:

Algorithm:

uint[] assets;
mapping(uint=>uint) indexOfAsset;
function removeAssetFromArray(uint _assetToDelete) {
  uint index = indexOfAsset[_assetToDelete];
  if (!index) return;
if (assets.length > 1) {
    assets[index] = assets[assets.length-1];
  }
  assets.length--; // Implicitly recovers gas from last element storage
}

Caveat: this approach assumes an ordered set, not an array. In other words, it assumes the array has no duplicate items.

edited Feb 04 '21 at 21:02

answered Feb 27 '18 at 06:22

William Entriken

4,690
15
42

@random Does this help? – William Entriken Jun 27 '18 at 23:25
1

No it just refunds gas setting non-zero storage values to zero again. It's a little cheaper than explicity saynig delete array[index]
That being said no answers on efficiency in this thread so guess I'll have to research myself.
– Nico Vergauwen Nov 21 '18 at 13:20
This is unbelievable simple solution for my use case.. thanks.. – Yogesh - EtherAuthority.io Dec 19 '18 at 10:09
Do you also need to remove the entry from indexOfAsset? – JohnIdlewood Feb 05 '22 at 21:30
How does it work for the first element ? – JohnIdlewood Feb 05 '22 at 21:40
Removing from indexOfAsset depends on your use case. For my use case (NFTs that are never destroyed), a removeAssetFromArray is always followed by a addAssetToArray and so there is no need to remove from indexOfAsset. – William Entriken Feb 07 '22 at 14:37
Removing the first element is the same as removing any asset: the first element is overwritten by the last element and then the last element is deleted. – William Entriken Feb 07 '22 at 14:38

score 2 · Answer 2 · answered Dec 19 '18 at 23:18

Generally, by moving the last item in the list into the row to delete.

Working from the User struct in the OP's code.

pragma solidity 0.5.1;

contract DeleteUser {

    struct UserStruct {
        uint userId;
        uint[] assets;
    }

    mapping(address => UserStruct) public userStructs;

    function deleteUserAsset(address user, uint assetIndex, uint asset) public {
        UserStruct storage u = userStructs[user];
        require(u.assets.length > assetIndex);
        require(u.assets[assetIndex] == asset); // this is a sanity check in case the list was re-ordered
        u.assets[assetIndex] = u.assets[u.assets.length-1];
        u.assets.length--;
    }

}

The sanity check isn't strictly needed as the question is worded, but the function relies on the caller knowing what row to delete. This could be a real problem if the list is reorganized by the deleteUserAsset() function is called. A simple fix is to add that check, to be on the safe side.

Even better, in my opinion, is to not rely on the caller knowing this. In order to do so, we would need a one-step lookup to find the row a particular key lives on. It will take another 32-byte word to store that.

pragma solidity 0.5.1;

contract DeleteUser {

    struct UserStruct {
        bytes32[] assets;
        mapping(bytes32 => uint) assetPointers;
    }

    mapping(address => UserStruct) userStructs;

    function isUserAsset(address user, bytes32 assetId) public view returns(bool isIndeed) {
        if(userStructs[user].assets.length == 0) return false;
        return userStructs[user].assets[userStructs[user].assetPointers[assetId]] == assetId;
    }

    function deleteUserAsset(address user, bytes32 assetId) public {
        UserStruct storage u = userStructs[user];
        require(isUserAsset(user, assetId));
        uint rowToDelete = u.assetPointers[assetId];
        u.assets[rowToDelete] = u.assets[u.assets.length-1];
        u.assets.length--;
    }

}

Hope it helps.

score 0 · Answer 3 · answered Nov 21 '18 at 13:52

For starters , I couldn't create a storage array with more than 100 items in a constructor. Likewise I assume having to loop over one will fail too when it grows too large.

The results are clear, moving indices after deleting an element from a dynamic array is a horrible idea and 0 values should be filtered on the client instead.

Looping through a storage array with 10 entries and deleting the LAST item

 transaction cost   20514 gas

Looping through a storage array with 100 entries and deleting the LAST item

 transaction cost   43349 gas

Looping through a storage array with 10 entries and deleting the MIDDLE item

transaction cost    44762 gas

Looping through a storage array with 100 entries and deleting the MIDDLE item

transaction cost    340387 gas

That gas cost increase is just not justifyable.

Here is how to create a storage array with many elements: pragma solidity ^0.5.1; contract S {uint[] a;constructor() public {a.length = 2**20;}} — William Entriken, Dec 19 '18 at 21:20
Looping is almost always wrong. Based on your other note maybe you have a different use case, perhaps you can open a separate question. — William Entriken, Dec 19 '18 at 21:20

Efficient approach to delete element from array in Solidity

3 Answers3

Linked