0

im new to solidity and im trying to figure out the best way to splice an array.

in javascript you have: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/splice

is there a similar way to achieve this in solidity?

the only way i think it would be possible is if you overwrite the value at the array index and replace that value with the value of the item at the next index... then do this for every following index value until the end of the array.

that method sounds like it could be expensive. does anyone have an suggestions of how to better achieve this?

the main thing i am trying to achieve is a way to keep the order of the array even though you can remove items from the middle.

suggestion 1

so thinking about it, how about using a list of structs. for example given a list of strings we want in an array, how about the data be stored into a struct with an additional bool field deleted.

struct Queue {
    string value;
    bool deleted;
}

Queue[] public listOfItems;

function deleteItem(uint index) public {
    Queue[index].deleted = true;
}

given that read operations are free on ethereum, i can get the client to request data from some index, if the data at that index has been marked as deleted, automatically request the subsequent index until a record is found that isn't deleted.

solution 2

i could use linked lists to achieve a similar functionality. this way if an item is to be marked as deleted, i could update the key of the next item in the array.

uint counter;

mapping (uint => string) public comments;

function addComment(string newComment) public {
    comments[counter + 1](newComment);
    comments[counter].nextItem = counter + 1;
}

function removeCommentWithId(uint commentId) public {
    comments[commentId - 1].nextItem = commentId + 1;
}

2 Answers 2

2

You may want a linked list.

Removing an element and then shifting all the others over is the best way to deal with this using an array. (BTW, I'm pretty sure that's how JavaScript's splice works, too.) Using a linked list would allow you to efficiently remove an element.

That said, do you also need to insert elements and preserve sorted order? If so, how are you doing the insert? (That also sounds like an O(n) operation.) You could consider other data structures, like a heap or a balanced tree, or you could sort on-demand on the client. It all depends on what your scenario is.

EDIT

In response to the question edit, this is fine, but think about the expected ratio of deleted items to existing items. If, after much use, you have 10 items with 10,000 deleted items in between them, you'll find this is extremely inefficient. A linked list doesn't have this problem.

Also consider using exists = true instead of deleted = false. This may save gas depending on the expected use.

EDIT 2

A hastily-thrown-together doubly linked list implementation. Please test before using. :-)

pragma solidity ^0.4.21;

contract DoublyLinkedList {
    struct Node {
        bytes payload;
        uint256 next;
        uint256 prev;
    }

    uint256 nextNodeID = 1;  // 0 is a sentinel value.
    mapping(uint256 => Node) nodes;
    uint256 head;
    uint256 tail;
    uint256 count = 0;

    function append(bytes payload) public {
        if (tail == 0) {
            // 0 is a sentinel. tail == 0 means head == 0 and the list is empty.
            head = nextNodeID;
            tail = nextNodeID;
            nodes[nextNodeID].payload = payload;
        } else {
            nodes[tail].next = nextNodeID;
            nodes[nextNodeID].payload = payload;
            nodes[nextNodeID].prev = tail;
            tail = nextNodeID;
        }
        nextNodeID += 1;
        count += 1;
    }

    function validNode(uint256 nodeID) internal view returns (bool) {
        return nodeID == head || nodes[nodeID].prev != 0;
    }

    function remove(uint256 nodeID) public {
        require(validNode(nodeID));

        Node storage node = nodes[nodeID];

        // Update head and tail.
        if (tail == nodeID) {
            tail = nodes[nodeID].prev;
        }
        if (head == nodeID) {
            head = nodes[nodeID].next;
        }

        // Update previous node's next pointer.
        if (node.prev != 0) {
            nodes[node.prev].next = node.next;
        }

        // Update next node's previous pointer.
        if (node.next != 0) {
            nodes[node.next].prev = node.prev;
        }

        // Reclaim storage for the removed node.
        delete nodes[nodeID];

        count -= 1;
    }

    function getNodeIDs() public view returns (uint256[] ids) {
        ids = new uint256[](count);

        uint256 current = head;
        for (uint256 i = 0; i < count; i++) {
            ids[i] = current;
            current = nodes[current].next;
        }
    }

    function getPayload(uint256 nodeID) public view returns (bytes) {
        require(validNode(nodeID));

        return nodes[nodeID].payload;
    }
}
16
  • please see suggestion 1 i have added in question body.
    – X0r0N
    Mar 18, 2018 at 19:53
  • you are right. it would be very inefficient. especially for the client-side which could be very heavy on bandwidth use where each request would require a new http handshake. but it seems solidity is pretty limiting in how to handle such a use-case.
    – X0r0N
    Mar 18, 2018 at 21:01
  • Do you have an objection to using a linked list?
    – user19510
    Mar 18, 2018 at 21:01
  • no objection at all. do you have a link to where i can find out more about linked-lists in solidity? i will append it with an example to the suggestions above.
    – X0r0N
    Mar 18, 2018 at 21:05
  • I'd need to know more about your use case and the operations you're going to support. E.g., you mentioned removing from the middle, but do you do so by directly jumping to that node (e.g. there's a mapping somewhere that tells you where a node is) or by enumerating starting at the beginning? A linked list is trivial to build, but I wonder if you need a doubly-linked list with a mapping.
    – user19510
    Mar 18, 2018 at 21:08
1

Don't do it.

Above all, avoid O(n) operations. Reconsider the need for a splice-like operation. If you think you need it, it's probably a sub-optimal application of blockchain.

Hope it helps.

2
  • please see suggestion 1 i have added in question body.
    – X0r0N
    Mar 18, 2018 at 19:52
  • Yes. That's a common approach. It will keep the elements in the order they were appended and mark some of deleted. Some more ideas over here: ethereum.stackexchange.com/questions/13167/… Mar 18, 2018 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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