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;
}
Best Answer
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 ofdeleted = false
. This may save gas depending on the expected use.EDIT 2
A hastily-thrown-together doubly linked list implementation. Please test before using. :-)