[Ethereum] Efficient approach to delete element from array in Solidity

arraysgasmappingsoliditystruct

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.

Best Answer

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.

Related Solutions

Solidity Memory Management – Does ‘Delete’ Free Mapping Space

Based on my Debug observation:

I have tested that:

Firstly I insert data into my map data-structure as I explained in my question.
Secondly, I have returned the address of first mapped index, which is 0, this could be done for other indexes as well (0:10).
Without a delete operation I can retrieve the data perfectly fine from the address of mapped Foo[]. But if I did the delete operation, Solidity gives an error.

This debug result: leads me to conclude that memory is freed or address does not contain any valid information.

Test code:

set_txn_hash     = my_contract.transact().map_insert();
contract_address = unmigrated_chain.wait.for_receipt(set_txn_hash)

for x in range(0, 9):
   for y in range(0, 9):
         output           = my_contract.call().get_(x, y);
         print(output);  //returns correct value.

set_txn_hash     = my_contract.transact().map_remove_map();                                             
contract_address = unmigrated_chain.wait.for_receipt(set_txn_hash)                                      

set_txn_hash     = my_contract.transact().get_map_address(0);
contract_address = unmigrated_chain.wait.for_receipt(set_txn_hash)

output           = my_contract.call().get_map();
print(output);

output           = my_contract.call().try_();
print(output);  //Solidity gives error if delete map_remove_map() is called

Additional functions inside my Contract:

  function map_insert(){
    for(uint i = 0; i < 10; i++)
      for(uint j = 0; j < 10; j++)
        add(i, i*10 + j);
  }

  function map_remove_map(){
    for(uint i = 0; i < 10; i++)
      delete_(i);
  }

  function map_remove_map_item(){
    for(uint i = 0; i < 10; i++)
      for(uint j = 0; j < 10; j++)
        delete_items(i, j);
  }

  function get_map_address(uint id) {
    uint addr;
    Foo[] a = foo[id];

    assembly{
    addr := a
        }
    map_address = addr;
  }

  function get_map() constant returns (uint){
    return map_address;
  }

  function try_() constant returns (uint ){
    uint addr = map_address;
    Foo[] a;
    assembly{
    a := addr
        }
    return a[1].x;  
  }

Solidity – How to Increase Mapping or Array Values Without Loop

As Rob suggests, what you could do -since iterating a mapping is not possible, and if it was an array, it would be expensive- is to compute the values on the fly.

Say you have several scores mapped to addresses.

Address - Score

0x1 - 3

0x2 - 4

0x3 - 2

Your original intention was to iterate over every element of the mapping to increase the scores, which is not doable.

What you could do is to add a state variable uint scoreIncrement which keeps track of how many times the score has been increased for all scores.

function increase_scores() public {
    scoreIncrement++;
}

Then, you have a function which returns the score of an element, plus the scoreIncrement.

function getScore(address _a) public returns (uint){
  return scores[_a] + scoreIncrement;
}

So, instead of directly accessing an element of scores mapping, you would call this function.

You could add even more logic to this. You might not want to increase every single score that gets added in the future as well. So you might want to play with timestamps too or group addresses, so a given scoreIncrement only affects certain addresses and not all of them.

Best Answer

Related Solutions

Solidity Memory Management – Does ‘Delete’ Free Mapping Space

Solidity – How to Increase Mapping or Array Values Without Loop

Related Topic