I used the following library code to delete an element in array according to its index. The only way in my mind is using loop, but it costs a lot of gas. Is there any other optimized code to solve this problem?

library ArrayLibrary {
    function remove(uint[] storage _arr, uint _removedIndex) public returns(uint[] memory){
        require(_arr.length > 0, "No element in Array.");
        for(uint i; i < _arr.length - 1; i  ){
            if (i >= _removedIndex) {
                _arr[i] = _arr[i   1];               
            } 
        }
        _arr.pop();
        return _arr;
    }
}


contract TestLibrary {
    uint[] arr;
    using ArrayLibrary for uint[];

    function deleteArrEle(uint[] calldata _arr, uint deletedIndex) public returns (uint[] memory deletedArr) {
        arr = _arr;
        deletedArr = arr.remove(deletedIndex);
    }
}

CodePudding user response：

If you don't mind switching order of the items, you can copy the last item to the position of the unwanted item and then remove the last.

function remove(uint[] storage _arr, uint _removedIndex) public returns(uint[] memory){
    require(_arr.length > 0, "No element in Array.");
    _arr[_removedIndex] = _arr[_arr.length-1];
    _arr.pop();
    return _arr;
}

Input array [1,2,3,4], removing at index 1 (value 2). Output [1,4,3].

There is also a bit more complex workaround with linked sorted list. Example code in Liquity protocol's SortedTroves for example.

The sorted data is not stored in an array but in a mapping of structs that point to previous and next items.

• key A:
  • value 1
  • link to previous key: empty (meaning there's no previous value)
  • link to next key: D
• key C:
  • value 7
  • link to previous key: D
  • link to next key: empty (meaning there's no next key)
• key D:
  • value 5
  • link to previous key: A
  • link to next key: C

The contract also holds info about keys of lowest and highest value.

When you're removing an item, you only remove this specific item, and change the 2 links (next and previous) that originally pointed to this item.