Hi Nico, and thanks for reading!
addRole and addBearer are O(1), while hasRole and removeBearer are O(n) where n is the bearers for that particular role.
You are right in using a mapping for the bearers inside the Role struct, the complexity of hasRole and removeBearer would be reduced to O(1), as well as making the code cleaner. However, storing the bearers in a mapping doesn’t allow me to know whether there are any bearers for a particular role, or who they are. In an access control contract that would be problematic.
I could store the bearers in the Role struct using a mapping, especially to reduce hasRole to O(1), and also store them a second time in an array inside the struct. That would allow hasRole to be O(1) while also allowing to find who are the bearers for a role, in exchange for an extra 20000 gas to add bearers and some additional cost complexity. If you want to give it a go I suggest implementing that option and comparing the results.
With regard to using an array to store the Role structs, which is what that line actually refers to, my assumption was that retrieving data from an array was easier than retrieving data from a mapping, and you don’t need to loop through the array to find a Role because the Role id is its position in the Roles array.
However, my assumption on mappings being more expensive to use than arrays was wrong. Arrays are internally stored as mappings and are only cheaper to use if the array items can be packed, which is not the case here. This means that using an array or a mapping to store the Role structs is basically the same thing. The link below is quite a good one to understand this.
Thanks again for your feedback!
