4

I'm having trouble finding the most cost efficient way to keep trace of what is stored into a mapping. I'm working on a web service that requires, to display, to get the data stored in a mapping

This is close to :

mapping(address => bool) values;
address[] valuesTrue;

function getValue(address a) public view returns (bool) {
    return values[a];
} //This is pretty self-explanatory

function getAllValues() public view returns(address[]) { //This one is not
    return valuesTrue;
}

function addValue(address a, bool b) public {
    values[a] = b;
    if (b)
        valuesTrue.push(a);
    else {
        for (uint i = 0; i < valuesTrue.length; i++) {
            if (valuesTrue[i] == a) {
                valuesTrue[i] = valuesTrue[valuesTrue.length - 1];
                delete valuesTrue[valuesTrue.length - 1];
                valuesTrue.length--;
                break;
            }
        }
    }
}

This is the most efficient way I found to store all the address which lead to 'true' in the mapping. Is there a more efficient way I'm not getting ?

1

This is not an efficient way to keep a trace of mapping values. Refer this article to understand how to maintain referential integrity in solidity.

For the above code, the time complexity of function addValue is O(N) as if an argument b is false you end up iterating an array of addresses valuesTrue to search if there is an address already inserted whose flag is true.

You can reduce the time complexity of function to O(1) by maintaining a data structure with the help of which you can access address directly instead of iterating it in an array.

Let me know if any further clarification is required. Hope this will help you.

Refer following code for more details

pragma solidity ^0.4.6;
contract Mapping {
struct Entity{
    bool isActive;
    uint index;
}
mapping(address => Entity) values;
address[] valuesTrue;
function getValue(address a) public view returns (bool) {
    return values[a].isActive;
} //This is pretty self-explanatory

function getAllValues() public view returns(address[]) { //This one is not
    return valuesTrue;
}

function addValue(address a, bool b) public {
    values[a].isActive = b;
    if (b)
        values[a].index     = valuesTrue.push(a)-1;


    else {

        if (values[a].isActive) {
            uint rowToDelete = values[a].index;
            address keyToMove = valuesTrue[valuesTrue.length-1];
            valuesTrue[rowToDelete] = keyToMove;
            values[keyToMove].index = rowToDelete; 
            valuesTrue.length--;
        }

    }
}
}
  • The article mentionned is approximatively what I did above. The thing is I don't get exactly what you mean in the method used to reduce to O(1) I'll appreciate a lot further explanation on this – Yooooomi Aug 17 '18 at 10:46
  • Aah I think I found, I could do another mapping of address to uint which indicates the index of the value in the array no ? – Yooooomi Aug 17 '18 at 10:48
  • Yes, you are correct. I have added a code for more clarity. – Soham Lawar Aug 17 '18 at 10:56
  • Yes I got it now. Thank you, I'll leave this question open for a bit to welcome new answers. I'll try this one. This is the most cost efficient we can do for this type of issue ? – Yooooomi Aug 17 '18 at 10:57
  • Yes, I think this is the most efficient way to handle this issue. As there is always a tradeoff between storage and time complexity sometimes we need to compromise storage to improve time complexity. – Soham Lawar Aug 17 '18 at 11:00
0

If you need to track your addresses that are entered with either value false or true, then you can do it with

mapping(address => uint) values;

where you can set 1 for true and 2 for false, just to say.

if you just need to know the addresses that have true values

Why do you need to keep valuesTrue array at all?

by doing this: values[a] = b; you are already keeping a track of address that have been assigned with value true. By default all other address will have false if they have not been added to map. Example: if you do something like this:

if(values[c]) 

will always return false where c is some address which has not been assigned to mapping yet.

  • I need to be able to retrieve all addresses which have true in the mapping, so I need an array aside to keep track of them – Yooooomi Aug 17 '18 at 11:12
  • yeah in that manner, you'll need an array for sure because you can't iterate mapping but if that array only holds addresses with true value, then you can make it a public array and simply return that array. No need to iterate it. By default all public variables get their getter function automatically. – Shaheryar.Akram Aug 17 '18 at 11:20
  • Didn't know that :), but actually I have requirements to access this variable so I need a function – Yooooomi Aug 17 '18 at 11:28
  • that's why we are here! If it helps you in any way, then I am glad to be of some help :) – Shaheryar.Akram Aug 17 '18 at 11:30

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.