4

I have array of structures on-chain and need to sort it. I used one of that quicksort algorithms that easily can be found and adopted it to use structures instead of plain uints. But I dislike it because it requires "swap" operation - change places of 2 items is the array. With structures it is possible only by creating memory instance like MyStruct memory temp and copy one of swappables there, then replace it and put memory-stored one into copied place. It is expensive.

I though that I could use mapping like mapping (uint16 => MyStruct) list and then just "swap keys". But it seems that with mapping I have to to the same - copy values because I cannot change key values.

Am I missed something or mapping cannot helps me here?

5

You cannot swap keys in your example, that would result in creating new mapping entries, with high cost as you already said. But you could use the mapping mapping (uint16 => MyStuct) list to store the data, while you put your keys (the uint16 values) in an array. You can sort the keys in the array then, the swap operation there will be cheaper. The data itself will be read from the mapping.

| improve this answer | |
  • Yes, it was my "plan B" - store indices in additional array and store structs in array too (I don't need mapping here either) and sort only array with indices. Thanks. – Alex G.P. May 2 '18 at 7:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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