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.

Answer 1

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.

Answer 2

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.

Answer 3

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.